基因组组装算法研究(已审核)

基因组组装算法研究摘要基因组测序是生物信息学的核心，有着极其重要的应用价值。近些年来，新的测序技术大量涌现，与传统的Sanger方法相比，这些方法产生的read(由测序仪直接测得的DNA片段)长度更短，数量更多，覆盖率更大。然而，传统的拼接算法并不适用于利用短read进行拼接，新的拼接算法在拼接效果上仍有待提高。本文首先介绍了传统的基因组拼接所用的贪婪算法和overlap-layout-consensus算法，这两种算法仅适用用于第一代测序技术所得的reads,并不适用于第二代基因测序。对于第二代测序技术所得的reads,可以建立debruijn图算法的数学模型，然后编写程序，组装基因片段。利用第二代测序技术可以在一次实验中获得高通量短read，然而第二代测序技术并不完美，由于在测序前要通过PCR手段对待测片段进行扩增，因此增加了测序的错误率。因此，本文利用HiTEC纠错算法对debruijn图算法进行优化。另外，本文还利用了基于概率模型的基因组从头测序算法克服了原有拼接算法过度依赖碱基片段之间重叠信息的缺陷，创造性地将DNA拼接过程抽象为二阶离散马尔可夫过程，与此同时，每一条碱基片段被抽象为系统中的一个状态。关键词：贪婪算法，OLC算法，debruijn图算法，HiTEC纠错算法一、问题重述遗传信息是生物遗传与进化的主要研究依据。能否快速和准确地获取生物体的遗传信息对于生命科学研是否有重大发现具有重要意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。确定基因组碱基对序列的过程称为测序。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。现有的测序技术中，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、deBruijn图方法等尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。本题要求我们尝试建立模型，由程序计算得到基因组的长须组装。算法与程序要求能有效地解决在测序过程中出现的碱基对识别错误，或则基因中出现重复片段的情况。将所建立的模型检查运行后，本题要求我们进一步对其进行探究。针对一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，结合附录中的测序策略、数据格式以及读长数据，在测序长度约为70×的情况下，对上述所建立的模型与算法程序进行组装验算。二、问题分析本题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。2.1read长度较短，数量较多——debruijn图新一代测序技术所得的read长度较短，数量较多，不易发现read之间的重叠关系。可以将read转化成定长的k-mer，然后寻找k-mer之间的重叠关系。然后建立debruijn图，把短序列拼接问题转化为debruijn图中的欧拉路径问题。2.2个别碱基对识别错误——多重对比纠错通过将多个read放在一起比对来发现错误，如图1所示。图中通过途中4条read比对，可发现read3中的一个碱基错误（read3的第五个碱基）2.3基因组中存在大量重复片段重复片段可能导致拼接错误，或者导致不连续的较短contig出现。重叠片段类型主要有以下几种，如图2所示重复片段问题可以用如下问题解决：通过对比，可先将重复片段隔离开来，较高的覆盖度有利于重复片段的隔离，但是，较多的测序错误将不利于该过程的进行。如果重复片段比read长，可利用paredendread来解决；如果重复片段比read短，那么该read又被称为spanner，一个spanner就是一个重复片段两端再加几个碱基组成。利用spanner解决重复片段问题需要如下两个信息：一是重复片段两端配对的read，这两个read必须不相同；二是重复片段中的一个配对read，只要知道一个即可，另一个配对read可以不在重复片段中。通过分析已知的基因组，可获得有关重复片段的更多信息，如，重复片段的长度，重复片段的模式等。read1AACATGCATGCTTGAC……reda2TGCATGCTTGACACAG……read3TGCTCGACACAGCGTT……read4TGACACAGCGTT……图14条read对比图图2重叠片段类型三、模型假设1．假设测序过程中没有其他因素的干扰；2．假设题目所给定的序列相对位置的碱基全部遵循GU-AC法则；3．假设题目中所有的序列都是正常可判别的序列，没有出现序列的基因突变等情况；4．假设一个完整基因组，打断成500bp的片段是随机的；5．假设基因组每个位置被测到的几率是等可能的；6．所有片段上的碱基都已经被识别出来，不存在未知碱基。四、符号说明jiG原基因进行第j-1次复制并对其进行任意切割后的第i个基因jiL基因jiG的长度，即jiG有jiL个碱基对K碱基对数量，即有K个碱基对1ijreadjiG第一个碱基对到第K个碱基对组成的基因3ijreadjiG第jiL-K+1个碱基对到第jiL个碱基对组成的基因12ijreadjiG第一个碱基对到第jiL-K个碱基对组成的基因23ijreadjiG第K+1个碱基对到第jiL个碱基对组成的基因Conting（C）由jiG经过贪心算法和最短路径算法后拼接产生的基因11mngl从顶点00g到11mng的一条路的权.也就是11mnL的值11mngz11mng的父亲点，用以确认最短路的路线.S具有永久标号的顶点集.read利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长；contig（C）：由read经过一定算法拼接产生3kb～10Mb以内的一些基因组片段;supercontig（S）：使用contig作为参考序列延伸，并进行合并得到更长的contig,即supercontig;quality（Q）:根据本题数据，每一个read都含有一个质量值，该值能反映该read的正确率。质量值越高，read的正确率越高。k-mer长度为k的一段DNA片段五、模型的建立及求解5.1拼接算法简介目前，DNA拼接组装算法大体上可以分为两类：一类是有参考基因组的重测序，一类是无参考基因组的从头测序。重测序是针对有参考基因组的物种提出的。通过使用第一代测序方法，消耗大量人力物力，经过较长时间，测定了一些物种的基因组，并且已将测序完成的基因组存入基因库中，将来可以作为参考基因组使用。对于这些物种的其它个体，它们的基因组与其相应的参考基因组相差不大，故在拼接时参考基因组会起到重大作用。但对于其他新的个体，没有参考基因组可供使用，于是人们提出了从头测序，即仅仅使用测序仪读出的一条条read来拼接组装成整个基因组。目前，从头测序主要有三类DNA拼接组装算法：（1）贪婪算法；（2）基于overlap-layout-consensus（重叠-排列-生成一致序列）思想的算法；（3）基于debruijn图的算法。其中贪婪算法和基于overlap-layout-consensus思想的算法是针对第一代测序数据提出的。第一代测序所得的read较长，数量相对较少，易于发现read之间的重叠关系。基于overlap-layout-consensus思想的算法建立重叠图，将DNA拼接问题转化为图论问题。新一代测序技术所得的read长度较短，数量较多，不易发现read之间的重叠关系，因此前两种方法不再适用，于是人们提出了基于debruijn图的算法，将read转化成定长的k-mer(长度较短的碱基片段)，然后寻找k-mer之间的重叠关系，建立debruijn图，最后将DNA拼接问题转为图论问题。5.2贪婪算法假定在read集合中存在两条read，分别记作ri和rj，其中0i，j≤n且i≠j。若这两条read可以被表示为ri=xy，rj=yz，则y即为这两条read之间的最大重叠区域，当y的值等于0时，表示这两条read之间无重叠区域。若两条read之间的重叠区域y大于一定的阈值，则将这两条read合并为一条read。贪婪算法的具体步骤是：首先选择满足一定要求的read作为contig的种子，然后寻找和该read的两端含有重叠区域的read，并对选作种子的read进行扩展，直到当前拼接的序列的两端无法继续扩展。最后选择下一条满足要求的read重复执行上述操作，直到拼接结束。利用贪婪算法进行序列拼接时，若存在两个及以上的read与当前拼接的序列的某一段含有重叠区域时，算法无法确定应该选择哪一条read进行扩展，因此当遇到这种情况时，算法终止，所以利用贪婪算法所拼接的contig的长度往往较短。实际上为避免这种情况的发生，贪婪算法在选择种子的阶段，首先依据覆盖度文件和质量文件contig中的种子进行打分，并且优先选择分数较高的read作为种子。利用贪婪算法的软件主要有：SHARCGS，SSAKE和VCAKE。SHARCGS只能拼接测序错误率低于0.05%的read，因此利用SHARCGS对第二代测序技术所产生的数据进行拼接时效果并不理想。SSAKE只能对无碱基测序错误的read进行拼接，尽管该方法能够拼接的read的长度为25bp，但产生大量的拼接错误。VCAKE在SSAKE基础上进行了改进，能够对含有更多测序错误的read进行拼接。5.3overlap-layout-consensus算法利用overlap-layout-consensus算法进行DNA拼接时，第一步是利用所有待拼接的read构造一个有向图G，图G中的每一个结点均是与之对应的一条特定的read。如果图G中的某两个结点由一条公共边相连，则说明这两个结点所代表的read之间的重叠部分大于预先设定的阈值。然后确定经过每个结点唯一一次的一条路径，实际上这条路径刚好访问每个结点仅一次。通过上述操作，DNA序列拼接问题便转化为人们所熟悉的Hamilton路径问题。overlap-layout-consensus算法大体可以分为如下三步：（1）首先确定适当的阈值，当两条read间重叠区域的长度大于该阈值时，算法便认为这两个read之间存在重叠区域。（2）同贪婪算法类似，首先将某一条read看作为一条contig，然后通过寻找与该read之间存在重叠区域的read来扩展这条被视作contig的read，重复执行这样的操作，最终便得到一定长度的contig。（3）在contig图中对read进行排列，然后确定一种投票机制，即根据碱基的质量值对read进行加权计算，通过投票机制来确定最终的DNA序列。基于“overlap-layout-consensus”思想的算法有：Edena和Arachne等。5.4debruijn图算法二十世纪八十年代末，Pevzner等人提出基于debruijn图的算法，并首次将该算法用于DNA序列拼接。基于debruijn图的算法的核心思想是将序列拼接问题转换为人们所熟悉的欧拉路径问题。Pevzner等人认为传统的overlap-layout-consensus算法导致了将DNA序列拼接问题转换为Hamilton路径问题，他们受到杂交测序方法SBH(SequencingbyHybridization)的启发，创造性地提出了在deBr