时间序列数据挖掘研究论文提纲
论文摘要: 随着计算机与信息技术的普及和大容量存储技术的发展,人们在日常事务处理和科学研究中逐渐积累了大量宝贵数据,这些数据背后蕴藏着对决策有重要参（略）.如何从这些历史数据中提取需要的信息正成为数据挖掘领域（略）在现实生活中,时间是数据本身固有的因素,在数据中常常会发现时序语义问题.时序数据的出现使得有必要在数据挖掘中考虑时间因素.时序数据在现实生活中广泛存在,如金融市场、工业过程、科学试验、医疗、气象、水文、生物信（略）储规模呈现爆炸式增长.因此对时间序列数据挖掘问题进行深入研究是非常必要和富有挑战性的. 从20世纪末开始,复杂网络的研究已经渗透到生命科学、数理学科和工程学科、社会科学等众多不同的领域.对复杂网络的研究,已成为科（略）个极其重要的富有挑战性的课题.其研究热点之一是寻找复杂网络中的社团结构,事实上这个过程就是一个聚类的过程,所以研究复杂网络社团划分新算法,对于时间（略）重要意义. 本文结合时间序列数据挖掘和复杂网络理论,开展了如下的研究工作: 综述了时间序列数据挖掘和时间序列模式挖掘的研究现状,指出了研究的现实意义.介绍并分析了最具代表性的...
With the popularity of computer and information technology,and the great（omitted）nt of storage technique of high capacity,,a great amount of data is accumulated in daily work and in s（omitted）research.Much potentially useful knowledge is hided behind data.Today how to manage and use（omitted）e series data efficiently and extract useful information is an important problem in dat（omitted）ime is the inherent attribute of data,so we should take time into account when mining association rules.Time serie...
目录:摘要 第4-5页
Abstract 第5页
1 绪论 第8-16页
·选题背景 第8-9页
·国内外研究现状 第9-14页
·数据挖掘研究现状 第9-11页
·时间序列数据挖掘的研究现状 第11-12页
·序列模式挖掘研究现状 第12页
·频繁趋势挖掘的研究与发展 第12-13页
·聚类问题的研究现状 第13-14页
·本文主要研究内容 第14-16页
2 研究背景 第16-24页
·数据挖掘与知识发现 第16页
·数据挖掘的起源 第16-17页
·引发数据挖掘的挑战 第16-17页
·相关领域对数据挖掘的`推动 第17页
·数据挖掘的过程 第17-18页
·数据挖掘的分类 第18-20页
·数据挖掘的方法 第20-22页
·数据挖掘系统 第22页
·数据挖掘软件的评价 第22-24页
3 时间序列数据挖掘 第24-36页
·时间序列 第24-25页
·时间序列概念 第24页
·时间序列分类 第24-25页
·时间序列数据挖掘研究 第25-28页
·序列模式挖掘 第28-34页
·问题描述 第28页
·序列模式挖掘 第28-29页
·序列模式挖掘算法分析与比较 第29-34页
·时间序列聚类分析 第34-36页
·复杂网络社团划分方法 第34页
·时间序列聚类与复杂网络社团结构划分 第34-36页
4 模糊频繁模式挖掘研究 第36-44页
·趋势分析 第36页
传统时间序列聚类的缺点：
1）时间序列聚类的研究一般采用等长划分，会丢失重要特征点，对聚类结果有负面影响。
2）采用时间序列测量值不能准确度量相似度。
如下埃博拉出血热、卫生部在数值上很相似，但教育部和卫生部在形状更相似。若是以形状作为度量传统的欧氏距离可能就不太合适了。
不等长时间序列滑窗STS聚类算法：
1）通过标准分数z_score预处理，消除时间序列观测值数量级差异的影响。
2）更改了相似度计算的方式，采用基于滑窗的方法计算不等长序列的距离。
3）采用类k-means的聚类算法的中心曲线计算方法。
时间序列数据因其趋势信息的直观展现形式，广泛应用于社交网络、互联网搜索和新闻媒体数据分析中。例如：Google应用搜索流感的相关信息的时间序列预测流感爆发趋势。根据某话题热度时间序列数据趋势的规律性，通过聚类区分不同类型的时间序列数据。同一类簇的Twitter话题具有相同或相似的发展趋势，进而应用于话题的发展趋势的预测。
时间序列聚类算法可以分为两类。
1）基于原始数据的时间序列聚类算法。
2）基于特征的时间序列聚类算法。
基于特征的时间序列聚类算法指根据原始数据从时间序列中提取形态特征（极值点位置、分段斜率）、结构特征（平均值、方差等统计值特征）、模型特征（模型的预测值），从而根据这些特征值进行聚类。这类方法的优点解决了不等长时间序列聚类问题，缺点是减弱了原始数据值得影响，聚类的形状趋势信息往往比较粗糙。
3. HOW
一、距离度量公式
STS距离计算的是累加时间序列间每个时间间隔斜率差的平方，公式
如上图所示，g1、g2和g2、g3的欧式距离的数值更相近。g1、g2的STS距离大于g2、g3的数值。在形状距离上，STS距离计算方式表现更好，一定程度上可以解决欧式距离度量时间序列局部特征信息确实和受观测数值数量级差异影响大的问题，但是依旧无法度量不等长时间序列的距离。
基于滑窗的STS距离公式。
如上图所示，当计算不同长度的时间序列的s和r的距离时，先不断平移时间序列s，然后找到s和r距离最近的字段，就如同上图虚线之间的位置，此时s和r距离最近，这个最近距离作为s和r之间的距离。
二、预处理过程
z-score标准分数用数据观测值和观测值平均值的距离代替原观测值。z-score处理后的数据平均值为0，标准差为1。标准差的作用是统一量纲，去除数值的数量级差异影响。
总结
本论文提出了形状距离的不等长时间序列的聚类方法。我们可以学到的有
1）z-score统一量纲，消除数值数量级差异，聚类效果更好。
2）计算x和y时间序列的STS距离，可以平移其中一个时间序列，求最小值作为STS距离值，这就消除了同一时间序列不同起始点的影响。
浅析现阶段高通量测序中的拼接问题论文
摘要：近年来，随着第二代测序技术的普及和第三代测序技术的逐步发展，高通量测序技术在实际研究中的应用越来越广泛。高速率、高性价比是其主要优点。相对于传统的桑格（Sanger）法测序来言，高通量测序得到的片段长度较为短小，故如何拼接得到完整的序列一直是炙手可热的研究方向。本文总结了现阶段高通量测序中拼接问题的研究结果，针对现在流行的各种算法进行了简单介绍。
关键词：高通量测序；reads 拼接；contigs 组装；OLC、De brujin 图
一、测序技术的发展过程和现状[1]
（一）桑格法
桑格法又叫做双脱氧链终止法，由Sanger在1977年提出。通过加入带有放射标记的dd NTP（双脱氧核苷酸）使DNA合成终止。再通过电泳，并使用放射自显影技术读出碱基。此方法得到的片段较长，能达到1000bp左右。
（二）第二代测序技术
随着科学技术的发展，传统的桑格法已经不能满足研究的需要。科学家们需要更快的速度、更高的通量以及更低廉的价格，于是第二代测序技术应运而生。其核心思想是边合成边测序。现在主要有454 GS FLX、SOLi D和Illumina/Solexa GenomeAnalyzer三个平台。第二代测序是现阶段测序技术的主流，也是高通量测序的开始。
（三）第三代测序技术
第三代测序技术是指单分子测序技术。不需要经过PCR的过程即可测序，速度可以达到每秒十个碱基。通量更大，读长更短，是现阶段测序技术的发展方向。
二、高通量测序中的拼接工作
（一）高通量测序所得片段的特点
高通量测序之后所得到的序列片段称为reads（读取），其主要特点两点。一是长度短，一般在200bp以 下，最长的454平台能达到的长度也不过1000bp,因此需要进行 大量的拼接才能得到整条DNA序列。二是有部分重叠，由于测序位置具有随机性，故各reads总会有一定的重叠，这些重叠是拼接工作的关键。
（二）拼接过程
整个拼接过程分为两步。第一步，考察reads的重复序列，并拼接成更长的片段，称为contigs（重叠群），这一步称为reads的拼接；第二步，确定contigs之间的顺序关系，并按此排列，形成称为scaffolds的序列，这一步叫做contigs的组装。
三、Reads的`拼接
（一）拼接过程的难点
reads拼接过程中要克服的难点主 要有两点，一是高通量测序得到的reads长度较短，故内含信息较少，不易确认相对顺序。二是远程连接信息（Long-range linking information）的不可靠性。 2这两点制约着reads拼接过程的准确率。
（二）方法[3]
reads拼接过程中算法的基本要求是de novo（从头测序），即不需要任何序列信息即可对原料进行测序。由此衍生出两种主流的算法：
1.OLC
OLC,即交叠-排列-共有序列算法（Overlap-layout-consensus），是一个比较传统的算法，其基本思想为根据reads间的重复部分，确定可能性的reads连接顺序。
其步骤为：构建交叠图：对每两个reads进行比对，计算它们的重叠度---排列reads:将reads进行排列，确定它们之间的相对位置，建立overlap图---生成共有序列：通过多序列比对等方法，确立最后的contig.
OLC算法的计算量主要体现在交叠图的构建，而高通量测序得到的海量短序列有大量的交叠，往往需要大量的运算时间。故OLC算法并不适合现在高通量测序的发展趋势。现在某些拼接软件，如Shorty、CABOG等仍在使用基于此的算法。虽然这些软件针对OLC算法有一定的改进和优化，但其拼接速度和准确性仍受到限制。
2.De brujin图
基于De brujin图（DBG）的算法是现在最流行的算法，许多常用的拼接软件如Velvet、ABy SS等都在使用这种算法。其特点为把基因序列的拼接问题转化为了数学上的图论问题，大大提高了拼接效率。
（1）基本思想
reads中 连 续 的k个 碱 基 称 为k -mer,作 为DBG的节点，两个k-mer如 果在同一read中 相邻，则形成一条边。故每个read都会对一些边加权，最后形成一个含有节点、有权值的边的DBG,由此生成最佳的contig.
（2）步骤
筛选reads:对reads进行检测，去除掉可能错误的reads---确定k值：k的值直接影响速度和精度。 K值较大时，精度有所提高，但更容易受覆盖率的影响。故应该根据覆盖率、reads长度等确定合适的k值---处 理DBG:根 据 确 定 的k值，做 出DBG,同时完成化简和修正---根据DBG,拼接成contig.
（3）优缺点
DBG算法在处理海量短reads的时候效果优秀，与现在测序技术的发展趋势相匹配。然而，由于k-mer的长度较短，此方法受重复序列、测序错误的影响较大。
（三）不同拼接软件的效果差异
不同的拼接软件在reads拼接过程中表现为三点：一是比起软件来说，reads质量对拼接结果影响更大；二是与标准序列的接近度随reads和拼接软件的不同有很大改变；三是各软件拼接的正确率差别很大，但与接近度的结果不一致。
四、Contigs的组装
与reads的拼接相比，contigs的组装的难度相对较小。这是因为contigs的长度较reads长很多，所含信息较多。故可以较为准确的组装成scaffold
（一）组装过程的难点[4]
Contigs组 装 过 程 中 的 难 点 主 要 有 二。一 是contigs中 含有大量的重复序列，不易确定contigs之间的相对顺序；二是由于contigs由reads拼接而成，其中不 免 会 有 一 些 错 误，这 些 错 误 也 会 对contigs的组装产生干扰。
（二）方法
Contigs组 装的方法较reads拼 接而言较多，一般常用的有图论法和光学图谱法（Optical mapping）两种。
1.图论法[5]
图论法是比较传统的方法，与reads拼接有相似的地方。它以contigs作为节点，由相连的读取对（Linking reads pair）作为边，由此形成算图。
其一般步骤为：库的构建：构建出含有所有reads的 库---计算相连读取对之 间的距离，并由此计算gap的长度---把长度放在边上，作为算图的数据。
其理想的输出结果是一条scaffold序列，对应一条染色体，包含以正确顺序排 列 的contigs和contigs之间gap的长度。
2.光学图谱法[6]
光学图谱法是一种较为新颖的方法。通过内切酶将DNA切断，此时DNA的片段的谱表现出一种特殊的指纹或是识别码的性质。利用光学方法追踪此信息得到相对位置，由此组装成正确的scaffold.
主要步骤为：将contigs放 置 在 光 学 图 谱上---修正光学图谱---做出contigs的连接图，由此决定最佳的contigs连接顺序。
光学图谱法的组装结果有着很高的覆盖率，巧妙运用光学图谱法可以获得很高的成本效益。
有研究表明，当与454平台获得的实验结果相结合的时候，光学图谱法可以迅速、价廉的得到排列好的定向的contigs组，由此可以产生一个将近完整的基因组。
（三）发展方向
Contigs组装过程的关键点 在于如何得到正确的连接顺序。现阶段此方面研究多集中在这一方向。
五、前景与展望
随着生物学研究向微观、向基因领域逐步延伸，高通量测序作为获得基因序列的主要方法，越来越受到重视，拼接技术也在不断发展。高通量测序的基因片段会变得海量且短小，应对此变化，拼接技术也会由确定“唯一的基因序列”向确定“最可能的基因序列”完成转变。因此，新一代的拼接技术会在准确率、覆盖率和速度上，作出超于现在拼接技术的改进。
参考文献：
[1]Anderson MW, Schrijver I. Next Generation DNASequencing and the Future of Genomic Medicine.?Genes.2010;1（1）：38-69. doi:10.3390/genes1010038.
[2]Salzberg SL, Phillippy AM, Zimin A, et al. GAGE: Acritical evaluation of genome assemblies and assemblyalgorithms.Genome Research. 2012;22 （3）：557 -567. doi:10.1101/gr.131383.111.
[3]Deng X, Naccache SN, Ng T, et al. An ensemble strategythat significantly improves de novo assembly of microbialgenomes from metagenomic next -generation sequencingdata.Nucleic Acids Research. 2015;43 （7）：e46. doi:10.1093/nar/gkv002.
[4]Latreille P, Norton S, Goldman BS, et al. Opticalmapping as a routine tool for bacterial genome sequencefinishing.BMC Genomics. 2007;8:321. doi:10.1186/1471 -2164-8-321.
[5]Hunt M, Newbold C, Berriman M, Otto TD. Acomprehensive evaluation of assembly scaffolding tools.Genome Biology. 2014;15 （3）：R42. doi:10.1186/gb -2014 -15-3-r42.
[6]Nagarajan N, Read TD, Pop M. Scaffolding andvalidation of bacterial genome assemblies using opticalrestriction maps.Bioinformatics. 2008;24 （10）：1229 -1235.doi:10.1093/bioinformatics/btn102.
这一次的研究是从头到尾完整的揭秘了人类基因组的序列，与20年之前基因研究的成果相比，这次的破译相当于增加了很多的零部件，增强了人们对于遗传基因各个方面的了解。
首先这次的基因破译向所有人揭示了我们人类身体里的完整的基因组序列，它破解了这么长时间以来世界最复杂的一个谜题，那就是人类的基因。让人们看见了身体里完整的 DNA基因序列。这次的基因破译对于一些遗传性的疾病和出生就有缺陷的疾病，以及人们的衰老和死亡都具有非常重要的意义。从这项破译中我们也可以更好的了解基因序列对于基因变异的研究意义和基因对遗传疾病的贡献。
同时这次的破译也是美国科学家第1次在同一本杂志上连续发表了6份论文，来揭秘人类的基因序列研究。论文的发表者表示这次的基因组研究对于我们现在生物方面的研究具有划时代的意义。
除此之外，这次的基因序列研究还纠正了之前科学家们在遗传基因方面的几千个错误。并且发现了大约200万个的变异基因，里边还有622个与现在的医学研究有关的基因。从中我们就可以看到这次的机组成果，对于人类如何进化到现在这样的程度，以及人类的遗传和，衰老有多么重要的意义。
科学家们还把人们体内的每一个染色体重新进行了排序和测序，把这些染色体的RNA基因进行了无数次的拷贝。这次参与基因组研究的科学家们表示他们还会进一步致力于人类基因序列的研究，为了更全面的掌握人类身体里基因的多样性，还有就是近期结合以及与人类基因相关的动物的关系。
论文要自己写 知道不
