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

基因组组装算法研究摘要基因组测序是生物信息学的核心，有着极其重要的应用价值。近些年来，新的测序技术大量涌现，与传统的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测序仪进行测序，结合附录中的测序策略、数据格式以及读长数据，在测序长度约为70X的情况下，对上述所建立的模型与算法程序进行组装验算。二、问题分析本题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。2.1read长度较短，数量较多debruijn图新一代测序技术所得的read长度较短，数量较多，不易发现read之间的重叠关系。可以将read转化成定长的k-mer,然后寻找k-mer之间的重叠关系。然后建立debruijn图，把短序列拼接问题转化为debruijn图中的欧拉路径问题。2.2个别碱基对识别错误——多重对比纠错通过将多个read放在一起比对来发现错误，如图1所示。图中通过途中4条read比对，可发现read3中的一个碱基错误（read3的第五个碱基）readlAACATGCATGCTTGAC......reda2TGCATGCTTGACACAG....read3TGCTCGACACAGCGTTread4TGACACAG■CGTT……图14条read对比图基因组中存在大量重复片段重复片段可能导致拼接错误，或者导致不连续的较短contig出现。重叠片段类型主要有以下几种，如图2所示重复片段问题可以用如下问题解决：通过对比，可先将重复片段隔离开来，较高的覆盖度有利于重复片段的隔离，但是，较多的测序错误将不利于该过程的进行。如果重复片段比read长，可利用paredendread来解决；如果重复片段比read短，那么该read又被称为spanner，—个spanner就是一个重复片段两端再加几个碱基组成。利用spanner解决重复片段问题需要如下两个信息：一是重复片段两端配对的read，这两个read必须不相同；二是重复片段中的一个配对read，只要知道一个即可，另一个配对read可以不在重复片段中。通过分析已知的基因组，可获得有关重复片段的更多信息，如，重复片段的长度，重复片段的模式等。原基因组：屮A+J拼接之后;原基因组捋接之后:原基因组:拼接之后图原基因组：屮A+J拼接之后;原基因组捋接之后:原基因组:拼接之后图2重叠片段类型三、模型假设1.假设测序过程中没有其他因素的干扰；2.假设题目所给定的序列相对位置的碱基全部遵循GU-AC法则；假设题目中所有的序列都是正常可判别的序列，没有出现序列的基因突变等情况;假设一个完整基因组，打断成500bp的片段是随机的；假设基因组每个位置被测到的几率是等可能的；所有片段上的碱基都已经被识别出来，不存在未知碱基。四、符号说明Gji原基因进行第j-1次复制并对其进行任意切割后的第i个基因Lji基因Gj的长度，即Gj有Lj个碱基对iiiK碱基对数量，即有K个碱基对read1ijGj第一个碱基对到第K个碱基对组成的基因iread3ijGj第Lj-K+1个碱基对到第Lj个碱基对组成的基因iii

read12ijGj第一个碱基对到第Lj-K个碱基对组成的基因iiread23ijGj第K+1个碱基对到第Lj个碱基对组成的基因iiConting(C)由Gj经过贪心算法和最短路径算法后拼接产生的基因i人)n1m1从顶点£到g的一条路的权•也就是Lm1的值00n严1竹z「g的父亲点，用以确认最短路的路线.九严1S具有永久标号的顶点集.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，分别记作r和r，其中0<i，jWn且iijHj。若这两条read可以被表示为r=xy，r=yz，则y即为这两条read之间的最ij大重叠区域，当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进行拼接。overlap-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等。debruijn图算法二十世纪八十年代末，Pevzner等人提出基于debruijn图的算法，并首次将该算法用于DNA序列拼接。基于debruijn图的算法的核心思想是将序列拼接问题转换为人们所熟悉的欧拉路径问题。Pevzner等人认为传统的overlap-layout-consensus算法导致了将DNA序列拼接问题转换为Hamilton路径问题，他们受到杂交测序方法SBH（SequencingbyHybridization）的启发，创造性地提出了在deBruijn图中寻找欧拉路径的构想，尽管杂交测序方法SBH从未在测序工程中实际应用过，但它直接引发了基因芯片工业的诞生。构造deBruijn图的方法如下所述：图2deBruijn图（1）在read集合R二｛r,r,…，r｝中，首先将每一条read分割成若干k-mer（长12n度更短的DNA片段）。假定集合R中任意一条read的长度均为l,k-mer长度值设为k,那么集合R中的任意一条read均可被分为l-k+1条k-mer，并且这些k-mer作为deBruijn图的顶点。（2）对于给定的两条k-merx和y,如果在某readri中存在一条长度为k+1的子串，且该子串的前k个碱基与k-merx（或y）精确匹配，同时该子串的后k个碱基与k-mery（或x）精确匹配，那么该算法认为两条k-merx和y之间存在一条公共边。将采用上述方法构造的deBruijn图记作G。对于read集合R=｛r,r，…，12r｝中的任意一条readr，若在deBruijn图G中存在一条路径P,且该路径P访问nir中的每一条k-mer仅一次，则欧拉路径问题便可理解为：给定某一deBruijn图G以i及G中的路径集合P,在deBruijn图G中确定某一条欧拉路径Q,使得路径集合P中的每一个元素都是欧拉路径Q的子路径。利用欧拉路径算法进行DNA序列拼接的主要步骤如下所述：首先利用纠错软件修正read中测序错误的碱基；然后按照上述方法构建deBruijn图；构建deBruijn图之后，应将read集合中的所有read排列在deBruijn图中，在deBruijn图中，每一条read均被视作一条路径；最后在deBruijn图中寻找一条欧拉路径，使得该路径包含deBruijn图中所有read所对应的路径。与overlap-layout-consensus算法相比，基于debruijn图的算法有更低的时间复杂度，这是因为欧拉路径问题实际上是一个线性时间的问题。利用欧拉路径思想的拼接算法有EULER-SR、ALLPATHSVelvet、和EULER等。令Gj=令Gj=i其中1<i<n,1<j<m.GmGmGm•••Gm123nnxm5.5debruijn图算法模型的建立G1G1G1…G1123nG2G2G2…G2123n设n，ngi。m,mgj且1<n，n<n,1<m,m<m。12121212设A为nxm阶空矩阵。若read3=read1，贝UA(nxn+m,nxn+m)=1n1m1n2m21122若read3丰read1，贝UA(nxn+m,nxn+m)=+gn1m1n2m21122则可得关于迪克斯特拉(Dijkstra)算法的邻接矩阵A。接下来利用最短路径算法和贪心算法求出基因重组的最佳方案。定义Gj为节点图，Gj中的任意一点皆为一个结点，则Gj共有nxm个点，其中第n+1iii个点表示G2，即以n个点为一周期，以此类推。并从其中随意定义一点为初始点g・100)),其中：1*)),其中：1*上S算法的过程就是在每一步改进这两个标记，使最终1ck从顶点g到g的最短00^m]对每个顶点，定义两个标记(lz,z竹眈1〃严1n1m1路的权•输入为带权邻接矩阵W.(1)赋初值：令S={g,1(g(1)赋初值：令S={g,1(g」=0}.vgGs=V\S，令1C0000n1m1n1>w(gm〔00gn严]),zQ)〃严1=g00,gn2m广g00(2)更新l(),n/m11)=l(g)+(2)更新l(),n/m11)=l(g)+w(gn1m1n2m2zQ)：vgG7=V\S，若1C)<1(gnmnmnm11/11、11,g),z'g丿二gn2m2n1m1n1m1n2m2n2)+w(gm2n2m2,gn1m1)，则令(3)设g*是使1()取得最小值的s中的顶点，则令S=SU{g*qm]*九严1n1m1}，g〜g*n2m2^m]⑷若?工0，转（2）；否则，停止.5.6模型的求解（1）将k值定为4。把上述readl文件中的序列存入库中，开始建立read条目的数据结构和k-mer条目的数据结构。预读数据，逐条读取read数据，每条readID进行升序保存；生成该read上所有k-mer（共85个k-mer），统计这些k-mer出现的次数，填写k-mer结构中的num字段。如图所示，为相关代码片段。相关数据录入程序源代码见附录。（2）遍历debruijn图，根据上一步统计的k-mer数量，申请readID_pos数组所需要的内存空间。依次读取每一个read，填写readID_pos数组中的第cur行，填好之后把cur值加1。（3）将碱基替换成2位二进制数。｛A=00，C=01，G=10,T=11｝。由于数据非常庞大，演算拼接过程不能完整的展示，接下来将列举一段算法拼接的过程：（1）初始k-mer定为AAAC即00000001，该k-mer出现在4条read上，且k-mer出现在每条read上的pos为1.这四条read开始参与拼接。如图为k-mer比对拼接相关代码（2）此时num为4，addr为1，cur为-1；read100000001011111010100001011101111000100001001110100001000read200000001000011100000101010010000011000111000110011010100read300000001110001001010101110111111110101101101000010010010read400000001111110001110101000000011010001011111111111000010初始kmer00000001后继kmercontig00000001当前候选后继k-mer情况如下:初始kmer0000000100000101000001000000011100000111候选后继kmerl候选后继kmer2候选后继00000101000001000000011100000111选定后继k-mer为AACT,即00000111；进行下一段拼接，此时num为5，前驱结点cur为1，addr为2；此时contig增加了一个碱基；read100000001011111010100001011101111read200000001000011100000101010010000read300000001110001001010101110111111read400000001111110001110101000000011read500000100111111001111110000000010初始kmer00000001后继kmer00000111contig0000000111重复(4)步骤，直到无法找到符合条件的后继k-mer则该条contig拼接结束；若该条contig的长度大于100bp则保存下来，否则删除；程序继续运行以上案列，得到一个长度为360bp的contig如下：{110111110010010100001000100011000111111000111010010110010011100011011010111011000000010000111000010111110100001011110100010000111011000011001101111000000111111111010000001010010100100010010011011001011001111011001110100010010110001001110010010110010100111110110101111101010001010001011100001110100000110111101011011011011011011011010101111000101111010111110001001000111101101001101000110010000000110010000101001010001011100010011000111011101100010000010011100110101111100110101110000010100100000101111011001100110110001010101010110010001101001111010111001011111011001101001111111111101111110100111011110111111111001100001111001110111111001101001001001101110010011100101111010011101101110011110111001111001101001101111011}到此一条contig拼接结束，开始重复(1)步骤；最终得到若干条长度大于lOObp的contig。{101100010011100100101100101001111101101011111010100010100010111000011101000001101111010110110110110110110110101011110001011110101111100010010001111011010011010001100100000001100100001010010100010111000100110001110111011000100000100111001100}5.7基于概率模型的基因组从头测序算法在算法设计之初，我们的构想是如果已知第一条碱基片段和第二条碱基片段，那么就可以通过这两条碱基片段确定基因组中的下一条碱基片段。实际上，在基因组中通过第一条碱基片段和第二条碱基片段可以确定的第三条碱基片段往往不止一个，通常情况下出现次数最多的第三条碱基片段是正确的。这是因为read数据中存在大量的碱基测序错误，因此那些出现次数较低的碱基片段往往含有测序错误的碱基。简而言之，算法的核心思想就是通过第一条碱基片段和第二条碱基片段确定第三条碱基片段，然后再通过这第二条碱基片段和第三条碱基片段确定第四条碱基片段，重复这样的操作，理想情况下，最终便可以得到满足一定长度要求的contigo实际上，这与二阶马尔可夫模型的思想不谋而合，即都是系统未来某一时刻的状态仅仅依赖于当前的两个状态。因此,本文所研究的基于概率模型的基因组从头测序算法将二阶马尔可夫模型运用到DNA拼接过程中。基于概率模型的基因组从头测序算法首先利用read中的信息构建概率模型，然后在序列末端截取两条相同长度的碱基片段，利用概率模型便可确定这两条碱基片段之后出现概率最大的某一碱基片段，并将其拼接在序列末端，这样序列便在原有长度的基础上得到了扩展。算法继续在序列末端截取两条相同长度的碱基片段，用同样的方法便可得到新的后继碱基片段，序列就在这样的操作过程中得到不断地扩展，最终获得一定长度的contig。具体的拼接过程如下所述。若以now和next作为种子，假定now二kk・・・k,next二kk…艮(实际中now和1210111220next已被转换为相应的十进制数)。首先在主表中定位索引值为now的元素，即prim-aryTable[now]。然后遍历primaryTable[now]中的指针所指向的副表，若副表中只存在唯一的项含有next，则该项中的lastMer值即为所要寻找的后缀last，假定last二kkkk，此时应将该项中的freContig值加一，避免在下次拼接中选择该组now和next21222324作为种子。这样便通过第一前缀now和第二前缀next并结合概率模型确定了概率值为1的后缀last，同时序列在原有的基础扩展了4个碱基。然后取当前序列的最后20个碱基作为新的第一前缀和第二前缀，即now=kk-k，next=kk-k，用同样的方法确5614151624定新的第一前缀now和第二前缀next的后缀last。重复执行上述操作，序列便在原有的基础上不断地扩展，最后得到一个完整的contig。然而，在实际的拼接过程中，通过第一前缀now和第二前缀next在哈希表中能够确定的后缀last往往不止一个，这是因为尽管使用HiTEC方法进行了测序数据纠错处理,但在read数据中仍然存在大量的碱基测序错误，因此对于同一个后缀last,它们在read数据中可能有多种存在形式，区别仅在于1~2个碱基不同。实际上，对于一个后缀last,尽管存在一些含有测序错误碱基的后缀的干扰，但正确的后缀last的出现概率要明显大于那些含有测序错误碱基的后缀，因此对于这种情况，应该选择出现概率明显较大的后缀作为正确的后缀last。当出现无后缀情况或出现概率较大的后缀不止一个时,算法结束本次拼接并输出一条contig,然后选取新的种子now和next进行下一条contig的拼接。综上所述，基于概率模型的基因组从头测序算法描述如下。基于概率模型的基因组从头测序算法：算法输入：经HiTEC方法纠错处理的read数据算法输出：n条conitg(0<n<3000)算法步骤：01.由read数据构建概率模型；02.确定种子now和next，若不存在种子，则转至步骤8；03.在主表中定位索引值为now的元素，遍历primaryTable[now]中的指针所指向的副表；04.若副表中存在唯一项t满足nextMer等于next，则last等于该项中的lastMer值，获取新的now和next,转至步骤3,否则继续步骤5；05.若副表中存在n(n>1)项，即tl,12,…，tn。对于其中任意一项ti的nextMer值均等于next,则继续步骤6,否则转至步骤7；06.若n项中存在唯一项ti满足freRead/n项freRead值之和>0.6，而对于其它n-1项，该值均小于0.2,则last等于该项中的lastMer值，获取新的now和next,转至步骤3,否则转至步骤7；07.结束本次拼接并输出一条contig,获取新的now和next,转至步骤3；08.输出n条contig,算法终止；7、模型的优化利用第二代测序技术可以在一次实验中获得高通量短read。然而第二代测序技术并不完美,由于在测序前要通过PCR手段对待测片段进行扩增,因此增加了测序的错误率。例如，Iliumina公司的Solexa技术在一次测序中可以获得100万条read，每一条read长度在35bp~75bp，与此同时，碱基的测序错误率在1%~2%。在DNA拼接过程中，测序错误能够造成大量问题，大大降低了拼接结果的准确率。因此，在进行DNA序列拼接之前,有必要对read数据进行预处理,修正read中测序错误的碱基,从而提高DNA序列拼接的效果。目前对read数据进行预处理的方法大体上可以分为两类：一类是修正测序错误的碱基，我们称之为“纠错”，另一类是删除含有大量测序错误的read。然而，第二类方法存在降低read数据覆盖率的风险,这在一定程序上会降低算法的精确性,因此下面给出HiTEC纠错算法,优化模型。给定某一长度为L的基因组G,G可以理解为由字符A、T、G、C组成的字符串,且每一个字符出现的概率均为0.25。假定有n条来自基因组G的read,记作r,r,…，12r,其中每一条read的长度均为l,且基因组G中的碱基测序错误率为p。注意，算法将n包含非A、T、G、C碱基的read删除。如果某一条read的某一位置上的碱基与基因组G中相应位置上的碱基不同,或与其他read中相应位置上的碱基不同,则该碱基为错误的碱基。由n条read及其反向互补串构造字符串R,即R=r$r$r$r$…匸$r$,1122nn其中$表示非A、T、G、C的字符，令SA和LCP分别表示R的后缀数组和最长公共前缀数组。假定从基因组G中位置j处抽取一条read,记作r,该read中的位置k处存在i一个测序错误的碱基，在位置k之前的w个位置上的碱基均是正确的，即r[k-w・・・k-i1]是正确的。令r=xuay,其中x,u，y均是由字符A、T、G、C组成的字符串，x的i长度记作|x|，且|x|二k-w-1，u的长度记作|u|，且|u|二w，a为字符A、T、G、C中的某一字符，且a与基因组G中位置j+k-1处的字符b不同。然而，很多其他的read也是从基因组G中这一区域抽取的，因此这些read均含有正确的子串ub。在实际的纠错过程中，若发现字符串u后边的字符是b的次数明显多于a,则该位置上的字符a很有可能是错误的，实际上应该是b，若证据充分，则应将a替换为b。实际上字符串u足以说明字符a是错误的，而正确的应该是字符b。对于字符a,supp(u,a)表示R中字符串ua出现的次数。8.模型的评价8.1模型的优点本模型的算法容易推广到实际的基因组组装中，具有一定的实际应用价值；本模型针对新一代测序技术出现的问题逐一进行了解决。新一代分割的读长较短，不易发现reads之间的重叠关系，本文放弃了传统的重叠图算法。把基因重组问题成功的转化为Dijkstra的问题，配合全基因组鸟枪法测序实现了在较短的时间内对大量reads数据进行比对处理。8.2模型的不足忽略了碱基存在的内环境因素及其生化结构的影响；在实际中，基因组组装是一个复杂的数学问题，存在着大量的不确定性；一些新的想法缺乏足够的理论根据，所以有些问题的解决带有一定的主观性；该模型处理重复片段的能力较弱。当有reads拼接失败时，意味着小于reads长度的重复片段被检验出来，但无法处理大于reads长度的重复片段。参考文献：高随祥，杨德庄.扩展deBurijn图的生成树和广播[J].系统科学与数学,2003.王东阳，任世军，王亚东DNA序列拼接中deBurijn图结构的研究[J].智能计算机与应用,2011.韩东涛.基于概率模型的基因组从头测序算法研究.邱风.基于deBurijn图的短序列拼接算法的优化及并行化.附录packagecn.data;importjava.io.*;importjava.sql.*;publicclassDataInput{/***A=00*C=01*G=10*T=11*/publicstaticvoidmain(String[]args)throwsSQLException,ClassNotFoundException{//TODOAuto-generatedmethodstubFilefile=newFile("E:\\基因数据"，”data1.txt");/*Filefile2=newFile("D:\\基因数组"，”oo.txt");*/String[]a=newString[60000];String[]b=newString[60000];String[]c=newString[60000];DataInputmyData=newDataInput();try{FileReaderinOne=newFileReader(file);BufferedReaderinTwo=newBufferedReader(inOne);/*FileWriteroutOne=newFileWriter(file2);*//*BufferedWriteroutTwo=newBufferedWriter(outOne);*/Strings=nuII;inti;intj;intk;intp；for(j=0,k=0,p=0,i=1;(s=inTwo.readLine())!=null;i++)