第2卷第4期2012年8月
智能计算机与应用
INTELLIGENT COMPUTER AND APPLICATIONS
Vol．2No．4Aug．2012
全基因组序列拼接研究进展
曾培龙，王亚东
（哈尔滨工业大学计算机科学与技术学院，哈尔滨150001）
摘数据海量、精确度要：全基因组序列拼接是生物信息学研究领域的核心问题。针对新一代测序数据读取片段reads 长度短、
低等特点带来的严峻挑战，能够满足实际应用的序列拼接软件的研发，已成为生物信息学领域最为迫切的研究课题。深入探讨全基因组序列拼接的发展动态、所采用的主要策略等方面，总结序列拼接相关理论，并为未来新算法的研发提出具体的改进建议。
关键词：全基因组序列拼接；生物信息学；新一代测序
中图分类号：TP391
文献标识码：A
文章编号：2095－2163（2012）04－0004－05
Research Progress of Whole Genome Assembly
ZENG Peilong, WANG Yadong
（School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China )
Abstract :Whole genome assembly is the core issue of bioinformatics. On conditions that next generation sequencing brings bioinfor-
matics an unprecedented challenge due to its data of mass, short length and relatively low precision, development of sequence assembly soft-ware that could meet practical application has become the most important research topic. This paper analyses the development progress and main strategies of whole genome assembly deeply, sums up the relevant theory and provide specific suggestions for future algorithms.
Key words:Whole Genome Assembly ；Bioinformatics ；Next-Generation Sequencing
0引言
基本方法是将序列之间的交叠关系转换成计算机可以识别的结构，通过不断迭代扩展的方式延长目标序列，然后利用配对数据，确定各个目标序列的相对方向和位置关系，最终还原目标基因组序列。
基于新一代测序数据的基因组序列拼接，通常分为如下三个阶段：
（1）数据的预处理阶段。该阶段通过特定的方法，移除测序数据中的错误碱基；
（2）基因组连续片段（contigs ）生成阶段。该阶段将reads 拼接成contigs ；
该阶段使（3）超长序列片段（scaffoldings ）组装阶段。用配对数据，确定contigs 之间的方向和位置关系，生成scaffoldings 。
新一代测序技术正在引领生命科学研究进入一个崭新阶段。人类基因组计划完成之后，获得个体基因组的全部序列对于生物学研究、探索与认识生命的本质具有十分重要的科学意义[1,2]。
新一代测序技术作为目前生命科学研究的基础手段，随着应用领域的迅速扩增与不断深入，对生物信息学提出了必须正视的基础研究课题。而全基因组序列拼接作为生物信息学的核心问题，面临的主要挑战有：
（1）海量的数据（覆盖深度一般为40－200倍，数据量迫切需要海量数据的拼接组装算法；达20－200GB ），
（2）测序数据中的错误，容易导致错拼；
由于读取片段reads （3）基因组中重复片段大量存在，
长度过短，一般只有几十个碱基，这使得重复序列的处理变得困难。
针对新一代测序数据reads 长度较短、数据海量的特点，全基因组测序方面的数据分析软件的研发，已成为生物信息学领域最迫切、最重要的研究课题。虽然目前已开发有一些全基因组拼接软件，但是基本都局限在大型计算平台上完成数据分析过程，难以满足一般的研究需求，而且数据处理速度仍然远远落后于数据产生速度，已经成为整个基因组图谱绘制工作的瓶颈，并且其拼接结果在准确性方面还有待提高。
2全基因组序列拼接的发展动态
新一代测序技术的出现为生命科学重大问题研究提供
新的手段的同时，其海量数据及其长度短、精度相对较低等特点，为生物信息学设置了前所未有的时代挑战。海量reads 数据的处理能力远远落后于测序数据的爆炸性增长速度，测试数据的快速、准确分析已经成为生命科学研究的短板[3]。如图1所示，从2006～2010年积累的新一代短片段数据量远远超过了过去10年所获得的基因组测序数据的总和。
符合SRA 标准的新一代测序数据从2005～2010年的增长情况如图2所示。与图1相比可以看出，数据分析速度远远落后于数据产生速度，尤其是2010年数据的增长更是“爆炸式的”，而这些还只占目前产生的新一代测序数属于
1全基因组序列拼接的含义
基因组序列拼接的核心思想是利用序列之间的交叠关
系，通过类似于“搭积木”的方式重建目标基因组序列。其
收稿日期:2012－06－11
作者简介:曾培龙（1987－），男，河南商丘人，硕士研究生，主要研究方向：生物信息学；
王亚东（1964－），男，辽宁锦州人，硕士，教授，博士生导师，主要研究方向：人工智能、机器学习、知识工程等。
第4
期
曾培龙，等：全基因组序列拼接研究进展·5·
据的很小部分，目前一台SOLiD 测序仪一次运行即可获得0．2T 的数据量。由此可知，当前的数据分析和处理能力与数据产生的速度是难以匹配的，海量reads 数据的分析和处理技术的研究已经居于当务之急的首要位置[1－4]。
物种基因组规模可分为小型基因组从头测序和大型基因组从头测序。小型基因组从头测序（基因组规模10Mb 以内）一般通过某种拼接算法直接完成全基因组序列组装；而大型基因组（例如，1Gb 以上大型基因组）由于很难直接拼接形成完整的全基因组序列，因此通常采用迭代的方式，首先利用拼接算法产生3kb～10Mb以内的一群基因组片段con－tigs ，然后以这些contigs 作为参考序列进行延伸，并通过合上述过程反复迭代，最终得到大型基并得到更长的contigs ，
20]
因组完整的全基因组序列[19，。
目前，从头测序的短序列拼接算法普遍采用De Bruijn 图[21]。在De Bruijn 图中，每个k－mer都构成图的节点，如果两个k－mers在某read 中相邻，那么这两个节点之间就有一reads 集合中的每条read 都对其所含的节点和边进行条边。
了加权，这样，就构造了节点和边都具有权值的De Bruijn 图。
传统Sanger 测序的reads 较长，数据量较少，精度较高，所有的拼接算法都利用reads 之间的交叠，通过寻找公共路而新一代测序产生的数据更短、覆径的方法解决拼接问题。
盖深度更高、序列精度较低，为此这种“reads 为中心”的方法面临海量计算的困境，无法找到恰当的启发式方法来处短序理大量的交叠。De Bruijn 图框架却能为处理高覆盖、列数据提供了很好思路。该框架借鉴了Pevzner 和Water－man 等人针对传统reads 提出的欧拉路径方法[22]，并在此基础上针对新一代测序数据的特点进行了改进。第一个利用此技术的拼接算法是Newbler
[19]
，之后2007年末到2010
年，陆续出现了很多直接或间接使用De Bruijn 图的拼接算
23－27]法[21，，这些方法在处理测序错误的方式和使用reads 信
息的程度上（例如是否使用mate－pair信息）有所不同。EULER－SR[28]在拼接前进行碱基错误的处理，Velvet [29]将错误的处理放到拼接的过程中，而SOAPdenovo [25]在拼接前处理碱基错误，在拼接的过程中又处理由于碱基错误导致的
传统的序列拼接方法是针对Sanger 测序数据而设计的。Sanger 测序的拼接组装问题具有如下特点：读取片段reads 比较长（750～1000bp ）、测序精度高（每个碱基的准确率高达99．999％）、采用配偶成对（mate－pairs）文库技术等，每次拼接范围较小（～10Mbp大小的DNA 片段）、以及测序速度较慢（900000bp ／天）。为此，传统的拼接算法是以巨大的测序费用和时间开销为代价使计算复杂性得以降低。新一代测序技术的出现，对传统的拼接组装方法提出了挑战。新一代测序的reads 长度普遍较短，测序的错误率较高，产生的数据量大（一次测序产生的数据能够覆盖1Gbp 范围内DNA 序列），因而要求算法具有海量数据拼接的能力，对此传统的基于Sanger 测序数据的拼接方法遇到了性能极限，很难直接用于新一代测序数据。由于新一代DNA 测序技术的高通量、低成本的优点，尤其在全基因组测序中取得的成功引发了人们对新一代测序技术的研究热潮[5－8]，相继组建了不同研究团队，针对各自研究课题，研发全基因组拼接软件工具，以求解决具体生物学问题[9－18]。
短序列从头拼接是新物种从头测序的关键。根据测序
尖端和“泡沫”结构。最新提出的拼接算法还考虑了覆盖深
30，31]度信息[1，，但是却没有采用GC 含量校正拼接结果中重
复段的拷贝数。
3全基因组序列拼接的主要策略
全基因组从头测序拼接（de novo assembly ）是生物信
息学研究领域的核心问题。测序产生的读取片段（reads ）数据通过序列拼接、组装，获得基因组的碱基排列。目前，基于新一代测序数据的从头测序拼接组装算法，主要基于3种策略：贪心（greedy ）、交叠－排列－生成共有序列（Overlap－Layout－Consensus,OLC ）与De Bruijn 图[21]。3．1贪心策略
贪心策略类型的序列拼接算法主要采用种子迭代扩展的方法，按一定条件选择初始reads 作为待生成contigs 的种子，通过启发式搜索方式使得每一步都合并与其具有最多交叠的reads ，直至reads 或contigs 两端都不能再做进一步的扩展。一般而言，reads 的选择是按照拼接质量递减的顺序考虑的，拼接质量通常用碱基质量和覆盖度来衡量。为避免错拼，有些扩展操作在发现冲突的信息时就立即停止。
·6
·
智能计算机与应用
最终得到scaffolds 序列。tigs 之间的gaps ，
第2卷
SSAKE [16]、SHARCGS [11]、VCAKE [9]即采用了该类拼接策略。SSAKE 和VCAKE 能够处理非完全匹配的reads ，SHARCGS 适用于均匀分布、非配对的reads 。贪心策略适用于小型基因组，而对于有大量重复序列存在的大型基因组的测序数据进行拼接时，拼接效果往往很差。
3．2交叠－排列－生成共有序列（OLC ）策略
OLC 策略在第一代测序中被广泛采用，并取得了很好的结果。该种策略主要包含3个主要的步骤：
（1）构建交叠图，计算任意两条reads 之间的交叠。为了减少计算复杂度，可以先对reads 建立类似后缀数据、后缀树的索引，而后在所建索引的基础上进行计算；
（2）排列reads ，确定reads 之间的相对位置，建立ove－rlap 图，分析overlap 图，获得遍历整个图的最佳近似路径；
（3）生成共有序列，通过多序列比对等方法，获得最终的基因组序列。
由于新一代测序数据的reads 海量，计算reads 交叠的平基于OLC 策略的拼接方复杂度以及reads 长度较短等限制，
方法并不适于处理新一代的海量短序列数据，为此，在该种策略的基础上又相继提出了多个更加实用的拼接算法，主要有：CABOG [32]、Edena [12]、Shorty [33]。Shorty 用于处理SOLiD 数据，利用300－500bp 长度的种子上的配对数据，采用类似于Huson 等人[34]的方法，来估算两个相邻contigs 之间的gap 的大小。CABOG 基于Celera Assembler [14]，采用一种被称为“rocks and stones ”的技术，先通过reads 之间的交叠关系，建立reads 之间的多序列比对，然后使用配对数据分割不满足约束条件的多序列比对，再由多序列比对上的配对数据确定其相对位置，最终生成共有序列。
随着测序技术的不断发展，基因组测序产生的数据质量会越来越高，生成的reads 片段也会越来越长，以reads 为计算中心的拼接策略或许会再次进入人们的视野，成为研究主题。
3．3De Bruijn 图策略
基于De Bruijn 图（DBG ）策略（如图3所示）的拼接算法被最广泛地应用到新一代测序数据的处理中。典型算法有：ABySS [10]、ALLPATHS [23]、Euler－SR[28]、SOAPdenovo [25]和Velvet [29]。基于De Bruijn 图的拼接算法，非常巧妙地将具有交叠关系的reads 映射到一起，降低了计算交叠时的复杂度，减少了内存消耗。基于De Bruijn 图策略的拼接算法的大致步骤是：
（1）构建De Bruijn 图。将reads 分割成一系列连续的（一般用K 值表征kmer 碱基数目的大小），作子串k－mers
为图中的边，相邻的两个k－mers交叠（K －1）个碱基；
（2）化简De Bruijn 图。方法是合并路径出度入度唯一的节点，按照一定的规则去除图中的尖端（tips ）和泡状结构（bubbles ）；
（3）构建contigs 。在De Bruijn 图或其子图中寻找一条最优的欧拉路径（一次且仅有一次地经过每条边的路径），该路径对应的碱基序列即为contigs ；
（4）生成scaffolding 。利用配对数据，确定contigs 之间
的相对方向与位置关系，对contigs 进行组装，并填充con－
基于De Bruijn 图的拼接算法中，一个关键操作是K 值的选择。选择大的K 值能够解决更多的短小重复片段（tiny repeats ），降低图的复杂性，但同时也降低了图的连选择小通性，后续的拼接过程会产生更多的间隙（gaps ）；的K 值，对应的De Bruijn 图具有相对好的连通性，但图变得更加复杂，重复片段的处理也变得更加困难，增加了错拼还没有通用的K 值选择方法，需要根据特的可能性。目前，
定的应用，选择合适的K 值。一般认为对于原核生物的基因组拼接，K 值选取在21～35之间是合适的[25,29]；而对于真核生物基因组的K 值的选择要相对复杂得多，目前还没有明确的结论或者一致的建议。3．4序列拼接算法的比较
自从基因组测序产生以来，序列拼接算法就不断地处于研发和改进之中。Hernande 等人[12]的研究表明，通常，基于图的拼接算法与采用贪心策略的拼接算法相比，在序列长度和准确率，运行时间以及内存消耗等方面，往往具有相对更好的拼接表现。基于OLC 策略的拼接算法多用于传统测序数据的拼接，而基于De Bruijn 图的拼接算法则更多地用于新一代测序数据。不同的拼接算法在处理不同的测序数据时，通常具有各异的表现，目前还没有一种拼接程序能在所有方面都表现得出色，这个结论可在Narzisi 等人[35]的研究成果中找到论据：由于基因组和测序数据的复杂性，拼接长度与准确率往往是一个平衡的关系，高精度往往是以牺牲长度为代价的，反之亦然。而这种平衡如何选择，则取决于具体的应用。同样，拼接结果的准确率与算法的内存消耗也存在类似的平衡关系。就适用的基因组规模而言，除了SOAPdenovo [25]、AByss [10]等少数软件外，大多数拼接软件只适用于简单的小型基因组。目前，几乎所有软件都需要较大内存的计算平台。如何优化数据处理方法、高效地存储海量reads 数据，是序列拼接算法软件研发过程中必须面对的一个重要课题。
4全基因组序列拼接的发展方向
目前，绝大多数的基因组拼接软件还无法满足具体的
应用需要，无论在拼接质量、拼接效率还是内存消耗等方面都需要更进一步地改进和完善。展望未来，全基因组的序列拼接组装存在着如下几个发展方向：
（1）采用多种配对文库（mate－pair或paired－end）。基因组中存在的大量重复片段是序列拼接过程中最难解决的
第4期
曾培龙，等：全基因组序列拼接研究进展
ormatics, 2007, 23（21）:2942－2944．
·7·
问题，也是影响拼接质量的关键因素。配对数据可以为重复片段的解决提供有利助益：大片段配对文库用于解决大尺寸的重复片段，小片段配对文库用于解决小尺寸的重复片段。结合不同片段大小的配对文库，能够起到相互补充的作用；
（2）使用长序列（Sanger 数据或contigs ）与短序列的混合数据策略。长序列片段具有很好的片段交叠性，使拼接的可信度增强，并能跨越小的重复片段；而短序列具有很高的覆盖度，能够减少并填充拼接过程中出现的序列间隙（gaps ）。长短序列的结合使用，能有效避免错误拼接，提升拼接质量；
（3）并行化拼接。基因组的序列拼接并行化包括两个方面：一是reads 数据的分布式存储；二是拼接过程的并行化。reads 数据的分布式存储能有效解决基因组拼接所需大型计算平台的问题，有助于内存瓶颈的缓解。拼接过程的并因此，并行化是行化能加快序列的拼接速度，提高拼接效率。基因组序列拼接软件发展的一个主要趋势。
ing assembly of short DNA sequences to handle error[J]．Bioinf－[10]SIMPSON J T, WONG K, JACKMAN S D, et al．Abyss:a p－
arallel assembler for short read sequence data[J]．Genome Res, 2009, 19（6）:1117－1123．
[11]DOHM J C, LOTTAZ C, BORODINA T, et al．Sharcgs, a fast
and highly accurate short－readassembly algorithm for De Novo genomic sequencing[J]．Genome Research, 2007, 17（11）:16－97－1706．
[12]HERNANDEZ D, FRANCOIS P, FARINELLI L, et al．De No－
vo bacterial genome sequencing:millions of very short reads assembled on a desktop computer[J]．Genome Research, 2008, 18（5）:802－809．
[13]DIGUISTINI S, LIAO N Y, PLATT D, et al．De Novo genom－
e sequence assembly of a filamentous fungus Using Sanger,454and Illumina Sequence Data[J]．Genome Biology, 2009, 10（9）:R94．
[14]LI R Q, FAN W, TIAN G, et al．The sequence and De Novo
assembly of the Giant panda genome[J]．Nature, 2010, 463（7－279）:311－317．
[15]YE K, SCHULZ M H, LONG Q, et al．Pindel:a pattern gro－
wth approach to detect break points of large deletions and m－edium sized insertions from paired－endshort reads[J]．Bioinfor－（21）:2865－2871．matics, 2009, 25
[16]WARREN R L, SUTTON G G, JONES S J, et al．Assembling
millions of short DNA sequences using ssake[J]．Bioinformatics, （4）:500－501．2007, 23
[17]ZIMIN A V, SMITH D R, SUTTON G, et al．Assembly reco－
nciliation[J]．Bioinformatics, 2008, 24（1）:42－45．
[18]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
（Su－assemblies around seeds[J]．BMC Bioinformatics, 2009, 10ppl＋1）:S16．
[19]FLICEK P, BIRNEY E．Sense from sequence Reads:methods
（11Suppl ）:for alignment and assembly．Nat Methods, 2009, 6S6－S12．
[20]LI R Q, LI Y R, KRISTIANSEN K, et al．Soap:short oligon－
（5）:7－ucleotide alignment program[J]．Bioinformatics, 2008, 2413－714．
[21]MILLER J R, KOREN S, SUTTON G．Assembly algorithms for
next－generationsequencing data[J]．Genomics, 2010, 95（6）:315－327．
[22]PEVZNER P A, TANG H, WATERMAN M S．An Eulerian p－
ath approach to DNA fragment assembly[C]／／Proc Natl Acad Sci USA, 2001, 98（17）:9748－9753．
[23]BUTLER J, MACCALLUM I, KLEBER M, et al．Allpaths:De
Novo assembly of whole－genomeshotgun Microreads[J]．Genome （5）:810－820．Research, 2008, 18
[24]MACCALLUM I, PRZYBYLSKI D, GNERRE S, et al．All pa－
ths 2:small genomes assembled accurately and with high con－tinuity from short paired Reads[J]．Genome Biology 2009, 10（10）:R103．
（下转第13页）
5结束语
新一代测试数据在提高测序速度、降低测序成本的同
时，也给后续的生物信息学数据处理带来了严峻的挑战。尽管目前人们针对各自的研究课题开发了一些处理全基因组序列拼装软件，并且成功地进行了许多物种的全基因组拼接。然而，数据的处理和分析过程一般局限在大型集群的计算平台上完成，并且拼接质量较低、效率也不高（小型基因组也需要若干小时的拼接组装时间），迫切需要适合于新一代测序的海量reads 数据拼接算法，以便为新一代测序数据的分析与处理提供理论指导和技术支持，加快全基因组测序研究的推进。
参考文献:
[1]METZKER M L．Sequencing Technologies －the Next Generati－
on[J]．Nat Rev Genet, 2010, 11（1）:31－46．
[2]SHENDURE J, JI H．Next－generationDNA sequencing[J]．Nat－（10）:1135－1145．Biotechnol, 2008, 26
[3]POP M, SALZBERG S L．Bioinformatics challenges of new se－quencing Technology[J]．Trends Genet, 2008, 24（3）:142－149．[4]WHITEFORD N, HASLAM N, WEBER G, et al．An analysis of
the feasibility of short read sequencing[J]．Nucleic Acids Res,2－（19）:e171．005, 33
[5]WANG J, WANG W, LI R, et al．The diploid genome sequence of an Asian individual[J]．Nature, 2008, 456（7218）:60－65．[6]LI R Q,
LI Y R,
ZHENG H C, et al．Building the sequence
map of the Human pan－genome[J]．Nature Biotechnology, 2010, （1）:57－63．28
[7]TONG P, PRENDERGAST J G, LOHAN A J, et al．Sequencing and analysis of an Irish human genome[J]．Genome Biol, 2010, 11（9）:R91．
[8]HIATT J B, PATWARDHAN R P, TURNER E H, et al．Paral－lel, tag－directedassembly of locally derived short sequence rea－ds[J]．Nat Methods, 2010, 7（2）:119－122．
[9]JECK W R, REINHARDT J A, BALTRUS D A, et al．Extend－
第4期
闫昕，等：支持大规模个性化需求描述的服务过程模型
·13·
[7]王显志，王忠杰，徐晓飞．面向服务整合的顾客个性化需求
分类与描述方法[J]．黑龙江大学自然科学学报，2009，26（5）:622－626．[8]
莫同，徐晓飞，王忠杰．面向服务系统设计的服务需求模型[J]．
计算机集成制造系统，2009,15（4）：661－669．
[9]詹蓉，陈荣秋．个性化需求分类的定量分析研究[J]．软科学，
2007，21（3）:5－8．
．．
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
（上接第7页）
[25]LI R, ZHU H, RUAN J, et al．De Novo assembly of human
genomes with massively parallel short Read sequencing[J]．Ge－nome Research, 2009, 20（2）:265－272．[26]CHAISSON M J, BRINZA D, PEVZNER P A．
De Novo frag－
ment assembly with short mate－pairedReads:Does the Read length matter芽[J]．Genome Research, 2009, 19（2）:336－346．[27]SCHEIBYE－ALSINGK, HOFFMANN S, FRANKEL A, et al．
Sequence assembly[J]．Comput Biol Chem, 2009, 33（2）:121－136．
[28]CHAISSON M J, PEVZNER P A．Short Read fragment assem－
bly of Bacterial genomes[J]．Genome Research, 2008, 18（2）:324－330．
[29]ZERBINO D R, BIRNEY E．Velvet:algorithms for De Novo
short read assembly using De Bruijn graphs[J]．Genome Resea－rch, 2008, 18（5）:821－829．
[30]REINHARDT J A, BALTRUS D A, NISHIMURA M T, et al．
De Novo assembly using low－coverageshort Read sequence d－ata from the rice pathogen pseudomonas Syringae Pv．Oryzae．[J]Genome Research, 2009, 19（2）:294－305．
[31]HARISMENDY O, NG P C, STRAUSBERG R L, et al．Eval－
uation of next generation sequencing platforms for population targeted sequencing studies[J]．Genome Biology, 2009, 10（3）:R32．
[32]MILLER J R, DELCHER A L, KOREN S, et al．Aggressive
assembly of pyrosequencing reads with mates[J]．Bioinformatics, 2008, 24（24）:2818－2824．
[33]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
assemblies around seeds[J]．BMC Bioinformatics, 2009, 10（Su－（ppl＋1）:S16．
[34]HUSON D H, REINERT K, MYERS E W．The greedy path－
merging algorithm for contig scaffolding[J]．Journal of the Acm, （5）:603－615．2002, 49
[35]MILLER J R, DELCHER A L, KOREN S, et al．Aggressive
assembly of pyrosequencing Reads with mates[J]．Bioinformati－cs, 2008, 24（24）:2818－2824．
[36]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
assemblies around seeds[J]．BMC Bioinformatics, 2009, 10（Su－ppl＋1）:S16．
[37]NARZISI G, MISHRA B．Comparing De Novo genome assemb－
ly:the long and short of It[J]．PLoS ONE, 2011, 6（4）．
第2卷第4期2012年8月
智能计算机与应用
INTELLIGENT COMPUTER AND APPLICATIONS
Vol．2No．4Aug．2012
全基因组序列拼接研究进展
曾培龙，王亚东
（哈尔滨工业大学计算机科学与技术学院，哈尔滨150001）
摘数据海量、精确度要：全基因组序列拼接是生物信息学研究领域的核心问题。针对新一代测序数据读取片段reads 长度短、
低等特点带来的严峻挑战，能够满足实际应用的序列拼接软件的研发，已成为生物信息学领域最为迫切的研究课题。深入探讨全基因组序列拼接的发展动态、所采用的主要策略等方面，总结序列拼接相关理论，并为未来新算法的研发提出具体的改进建议。
关键词：全基因组序列拼接；生物信息学；新一代测序
中图分类号：TP391
文献标识码：A
文章编号：2095－2163（2012）04－0004－05
Research Progress of Whole Genome Assembly
ZENG Peilong, WANG Yadong
（School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China )
Abstract :Whole genome assembly is the core issue of bioinformatics. On conditions that next generation sequencing brings bioinfor-
matics an unprecedented challenge due to its data of mass, short length and relatively low precision, development of sequence assembly soft-ware that could meet practical application has become the most important research topic. This paper analyses the development progress and main strategies of whole genome assembly deeply, sums up the relevant theory and provide specific suggestions for future algorithms.
Key words:Whole Genome Assembly ；Bioinformatics ；Next-Generation Sequencing
0引言
基本方法是将序列之间的交叠关系转换成计算机可以识别的结构，通过不断迭代扩展的方式延长目标序列，然后利用配对数据，确定各个目标序列的相对方向和位置关系，最终还原目标基因组序列。
基于新一代测序数据的基因组序列拼接，通常分为如下三个阶段：
（1）数据的预处理阶段。该阶段通过特定的方法，移除测序数据中的错误碱基；
（2）基因组连续片段（contigs ）生成阶段。该阶段将reads 拼接成contigs ；
该阶段使（3）超长序列片段（scaffoldings ）组装阶段。用配对数据，确定contigs 之间的方向和位置关系，生成scaffoldings 。
新一代测序技术正在引领生命科学研究进入一个崭新阶段。人类基因组计划完成之后，获得个体基因组的全部序列对于生物学研究、探索与认识生命的本质具有十分重要的科学意义[1,2]。
新一代测序技术作为目前生命科学研究的基础手段，随着应用领域的迅速扩增与不断深入，对生物信息学提出了必须正视的基础研究课题。而全基因组序列拼接作为生物信息学的核心问题，面临的主要挑战有：
（1）海量的数据（覆盖深度一般为40－200倍，数据量迫切需要海量数据的拼接组装算法；达20－200GB ），
（2）测序数据中的错误，容易导致错拼；
由于读取片段reads （3）基因组中重复片段大量存在，
长度过短，一般只有几十个碱基，这使得重复序列的处理变得困难。
针对新一代测序数据reads 长度较短、数据海量的特点，全基因组测序方面的数据分析软件的研发，已成为生物信息学领域最迫切、最重要的研究课题。虽然目前已开发有一些全基因组拼接软件，但是基本都局限在大型计算平台上完成数据分析过程，难以满足一般的研究需求，而且数据处理速度仍然远远落后于数据产生速度，已经成为整个基因组图谱绘制工作的瓶颈，并且其拼接结果在准确性方面还有待提高。
2全基因组序列拼接的发展动态
新一代测序技术的出现为生命科学重大问题研究提供
新的手段的同时，其海量数据及其长度短、精度相对较低等特点，为生物信息学设置了前所未有的时代挑战。海量reads 数据的处理能力远远落后于测序数据的爆炸性增长速度，测试数据的快速、准确分析已经成为生命科学研究的短板[3]。如图1所示，从2006～2010年积累的新一代短片段数据量远远超过了过去10年所获得的基因组测序数据的总和。
符合SRA 标准的新一代测序数据从2005～2010年的增长情况如图2所示。与图1相比可以看出，数据分析速度远远落后于数据产生速度，尤其是2010年数据的增长更是“爆炸式的”，而这些还只占目前产生的新一代测序数属于
1全基因组序列拼接的含义
基因组序列拼接的核心思想是利用序列之间的交叠关
系，通过类似于“搭积木”的方式重建目标基因组序列。其
收稿日期:2012－06－11
作者简介:曾培龙（1987－），男，河南商丘人，硕士研究生，主要研究方向：生物信息学；
王亚东（1964－），男，辽宁锦州人，硕士，教授，博士生导师，主要研究方向：人工智能、机器学习、知识工程等。
第4
期
曾培龙，等：全基因组序列拼接研究进展·5·
据的很小部分，目前一台SOLiD 测序仪一次运行即可获得0．2T 的数据量。由此可知，当前的数据分析和处理能力与数据产生的速度是难以匹配的，海量reads 数据的分析和处理技术的研究已经居于当务之急的首要位置[1－4]。
物种基因组规模可分为小型基因组从头测序和大型基因组从头测序。小型基因组从头测序（基因组规模10Mb 以内）一般通过某种拼接算法直接完成全基因组序列组装；而大型基因组（例如，1Gb 以上大型基因组）由于很难直接拼接形成完整的全基因组序列，因此通常采用迭代的方式，首先利用拼接算法产生3kb～10Mb以内的一群基因组片段con－tigs ，然后以这些contigs 作为参考序列进行延伸，并通过合上述过程反复迭代，最终得到大型基并得到更长的contigs ，
20]
因组完整的全基因组序列[19，。
目前，从头测序的短序列拼接算法普遍采用De Bruijn 图[21]。在De Bruijn 图中，每个k－mer都构成图的节点，如果两个k－mers在某read 中相邻，那么这两个节点之间就有一reads 集合中的每条read 都对其所含的节点和边进行条边。
了加权，这样，就构造了节点和边都具有权值的De Bruijn 图。
传统Sanger 测序的reads 较长，数据量较少，精度较高，所有的拼接算法都利用reads 之间的交叠，通过寻找公共路而新一代测序产生的数据更短、覆径的方法解决拼接问题。
盖深度更高、序列精度较低，为此这种“reads 为中心”的方法面临海量计算的困境，无法找到恰当的启发式方法来处短序理大量的交叠。De Bruijn 图框架却能为处理高覆盖、列数据提供了很好思路。该框架借鉴了Pevzner 和Water－man 等人针对传统reads 提出的欧拉路径方法[22]，并在此基础上针对新一代测序数据的特点进行了改进。第一个利用此技术的拼接算法是Newbler
[19]
，之后2007年末到2010
年，陆续出现了很多直接或间接使用De Bruijn 图的拼接算
23－27]法[21，，这些方法在处理测序错误的方式和使用reads 信
息的程度上（例如是否使用mate－pair信息）有所不同。EULER－SR[28]在拼接前进行碱基错误的处理，Velvet [29]将错误的处理放到拼接的过程中，而SOAPdenovo [25]在拼接前处理碱基错误，在拼接的过程中又处理由于碱基错误导致的
传统的序列拼接方法是针对Sanger 测序数据而设计的。Sanger 测序的拼接组装问题具有如下特点：读取片段reads 比较长（750～1000bp ）、测序精度高（每个碱基的准确率高达99．999％）、采用配偶成对（mate－pairs）文库技术等，每次拼接范围较小（～10Mbp大小的DNA 片段）、以及测序速度较慢（900000bp ／天）。为此，传统的拼接算法是以巨大的测序费用和时间开销为代价使计算复杂性得以降低。新一代测序技术的出现，对传统的拼接组装方法提出了挑战。新一代测序的reads 长度普遍较短，测序的错误率较高，产生的数据量大（一次测序产生的数据能够覆盖1Gbp 范围内DNA 序列），因而要求算法具有海量数据拼接的能力，对此传统的基于Sanger 测序数据的拼接方法遇到了性能极限，很难直接用于新一代测序数据。由于新一代DNA 测序技术的高通量、低成本的优点，尤其在全基因组测序中取得的成功引发了人们对新一代测序技术的研究热潮[5－8]，相继组建了不同研究团队，针对各自研究课题，研发全基因组拼接软件工具，以求解决具体生物学问题[9－18]。
短序列从头拼接是新物种从头测序的关键。根据测序
尖端和“泡沫”结构。最新提出的拼接算法还考虑了覆盖深
30，31]度信息[1，，但是却没有采用GC 含量校正拼接结果中重
复段的拷贝数。
3全基因组序列拼接的主要策略
全基因组从头测序拼接（de novo assembly ）是生物信
息学研究领域的核心问题。测序产生的读取片段（reads ）数据通过序列拼接、组装，获得基因组的碱基排列。目前，基于新一代测序数据的从头测序拼接组装算法，主要基于3种策略：贪心（greedy ）、交叠－排列－生成共有序列（Overlap－Layout－Consensus,OLC ）与De Bruijn 图[21]。3．1贪心策略
贪心策略类型的序列拼接算法主要采用种子迭代扩展的方法，按一定条件选择初始reads 作为待生成contigs 的种子，通过启发式搜索方式使得每一步都合并与其具有最多交叠的reads ，直至reads 或contigs 两端都不能再做进一步的扩展。一般而言，reads 的选择是按照拼接质量递减的顺序考虑的，拼接质量通常用碱基质量和覆盖度来衡量。为避免错拼，有些扩展操作在发现冲突的信息时就立即停止。
·6
·
智能计算机与应用
最终得到scaffolds 序列。tigs 之间的gaps ，
第2卷
SSAKE [16]、SHARCGS [11]、VCAKE [9]即采用了该类拼接策略。SSAKE 和VCAKE 能够处理非完全匹配的reads ，SHARCGS 适用于均匀分布、非配对的reads 。贪心策略适用于小型基因组，而对于有大量重复序列存在的大型基因组的测序数据进行拼接时，拼接效果往往很差。
3．2交叠－排列－生成共有序列（OLC ）策略
OLC 策略在第一代测序中被广泛采用，并取得了很好的结果。该种策略主要包含3个主要的步骤：
（1）构建交叠图，计算任意两条reads 之间的交叠。为了减少计算复杂度，可以先对reads 建立类似后缀数据、后缀树的索引，而后在所建索引的基础上进行计算；
（2）排列reads ，确定reads 之间的相对位置，建立ove－rlap 图，分析overlap 图，获得遍历整个图的最佳近似路径；
（3）生成共有序列，通过多序列比对等方法，获得最终的基因组序列。
由于新一代测序数据的reads 海量，计算reads 交叠的平基于OLC 策略的拼接方复杂度以及reads 长度较短等限制，
方法并不适于处理新一代的海量短序列数据，为此，在该种策略的基础上又相继提出了多个更加实用的拼接算法，主要有：CABOG [32]、Edena [12]、Shorty [33]。Shorty 用于处理SOLiD 数据，利用300－500bp 长度的种子上的配对数据，采用类似于Huson 等人[34]的方法，来估算两个相邻contigs 之间的gap 的大小。CABOG 基于Celera Assembler [14]，采用一种被称为“rocks and stones ”的技术，先通过reads 之间的交叠关系，建立reads 之间的多序列比对，然后使用配对数据分割不满足约束条件的多序列比对，再由多序列比对上的配对数据确定其相对位置，最终生成共有序列。
随着测序技术的不断发展，基因组测序产生的数据质量会越来越高，生成的reads 片段也会越来越长，以reads 为计算中心的拼接策略或许会再次进入人们的视野，成为研究主题。
3．3De Bruijn 图策略
基于De Bruijn 图（DBG ）策略（如图3所示）的拼接算法被最广泛地应用到新一代测序数据的处理中。典型算法有：ABySS [10]、ALLPATHS [23]、Euler－SR[28]、SOAPdenovo [25]和Velvet [29]。基于De Bruijn 图的拼接算法，非常巧妙地将具有交叠关系的reads 映射到一起，降低了计算交叠时的复杂度，减少了内存消耗。基于De Bruijn 图策略的拼接算法的大致步骤是：
（1）构建De Bruijn 图。将reads 分割成一系列连续的（一般用K 值表征kmer 碱基数目的大小），作子串k－mers
为图中的边，相邻的两个k－mers交叠（K －1）个碱基；
（2）化简De Bruijn 图。方法是合并路径出度入度唯一的节点，按照一定的规则去除图中的尖端（tips ）和泡状结构（bubbles ）；
（3）构建contigs 。在De Bruijn 图或其子图中寻找一条最优的欧拉路径（一次且仅有一次地经过每条边的路径），该路径对应的碱基序列即为contigs ；
（4）生成scaffolding 。利用配对数据，确定contigs 之间
的相对方向与位置关系，对contigs 进行组装，并填充con－
基于De Bruijn 图的拼接算法中，一个关键操作是K 值的选择。选择大的K 值能够解决更多的短小重复片段（tiny repeats ），降低图的复杂性，但同时也降低了图的连选择小通性，后续的拼接过程会产生更多的间隙（gaps ）；的K 值，对应的De Bruijn 图具有相对好的连通性，但图变得更加复杂，重复片段的处理也变得更加困难，增加了错拼还没有通用的K 值选择方法，需要根据特的可能性。目前，
定的应用，选择合适的K 值。一般认为对于原核生物的基因组拼接，K 值选取在21～35之间是合适的[25,29]；而对于真核生物基因组的K 值的选择要相对复杂得多，目前还没有明确的结论或者一致的建议。3．4序列拼接算法的比较
自从基因组测序产生以来，序列拼接算法就不断地处于研发和改进之中。Hernande 等人[12]的研究表明，通常，基于图的拼接算法与采用贪心策略的拼接算法相比，在序列长度和准确率，运行时间以及内存消耗等方面，往往具有相对更好的拼接表现。基于OLC 策略的拼接算法多用于传统测序数据的拼接，而基于De Bruijn 图的拼接算法则更多地用于新一代测序数据。不同的拼接算法在处理不同的测序数据时，通常具有各异的表现，目前还没有一种拼接程序能在所有方面都表现得出色，这个结论可在Narzisi 等人[35]的研究成果中找到论据：由于基因组和测序数据的复杂性，拼接长度与准确率往往是一个平衡的关系，高精度往往是以牺牲长度为代价的，反之亦然。而这种平衡如何选择，则取决于具体的应用。同样，拼接结果的准确率与算法的内存消耗也存在类似的平衡关系。就适用的基因组规模而言，除了SOAPdenovo [25]、AByss [10]等少数软件外，大多数拼接软件只适用于简单的小型基因组。目前，几乎所有软件都需要较大内存的计算平台。如何优化数据处理方法、高效地存储海量reads 数据，是序列拼接算法软件研发过程中必须面对的一个重要课题。
4全基因组序列拼接的发展方向
目前，绝大多数的基因组拼接软件还无法满足具体的
应用需要，无论在拼接质量、拼接效率还是内存消耗等方面都需要更进一步地改进和完善。展望未来，全基因组的序列拼接组装存在着如下几个发展方向：
（1）采用多种配对文库（mate－pair或paired－end）。基因组中存在的大量重复片段是序列拼接过程中最难解决的
第4期
曾培龙，等：全基因组序列拼接研究进展
ormatics, 2007, 23（21）:2942－2944．
·7·
问题，也是影响拼接质量的关键因素。配对数据可以为重复片段的解决提供有利助益：大片段配对文库用于解决大尺寸的重复片段，小片段配对文库用于解决小尺寸的重复片段。结合不同片段大小的配对文库，能够起到相互补充的作用；
（2）使用长序列（Sanger 数据或contigs ）与短序列的混合数据策略。长序列片段具有很好的片段交叠性，使拼接的可信度增强，并能跨越小的重复片段；而短序列具有很高的覆盖度，能够减少并填充拼接过程中出现的序列间隙（gaps ）。长短序列的结合使用，能有效避免错误拼接，提升拼接质量；
（3）并行化拼接。基因组的序列拼接并行化包括两个方面：一是reads 数据的分布式存储；二是拼接过程的并行化。reads 数据的分布式存储能有效解决基因组拼接所需大型计算平台的问题，有助于内存瓶颈的缓解。拼接过程的并因此，并行化是行化能加快序列的拼接速度，提高拼接效率。基因组序列拼接软件发展的一个主要趋势。
ing assembly of short DNA sequences to handle error[J]．Bioinf－[10]SIMPSON J T, WONG K, JACKMAN S D, et al．Abyss:a p－
arallel assembler for short read sequence data[J]．Genome Res, 2009, 19（6）:1117－1123．
[11]DOHM J C, LOTTAZ C, BORODINA T, et al．Sharcgs, a fast
and highly accurate short－readassembly algorithm for De Novo genomic sequencing[J]．Genome Research, 2007, 17（11）:16－97－1706．
[12]HERNANDEZ D, FRANCOIS P, FARINELLI L, et al．De No－
vo bacterial genome sequencing:millions of very short reads assembled on a desktop computer[J]．Genome Research, 2008, 18（5）:802－809．
[13]DIGUISTINI S, LIAO N Y, PLATT D, et al．De Novo genom－
e sequence assembly of a filamentous fungus Using Sanger,454and Illumina Sequence Data[J]．Genome Biology, 2009, 10（9）:R94．
[14]LI R Q, FAN W, TIAN G, et al．The sequence and De Novo
assembly of the Giant panda genome[J]．Nature, 2010, 463（7－279）:311－317．
[15]YE K, SCHULZ M H, LONG Q, et al．Pindel:a pattern gro－
wth approach to detect break points of large deletions and m－edium sized insertions from paired－endshort reads[J]．Bioinfor－（21）:2865－2871．matics, 2009, 25
[16]WARREN R L, SUTTON G G, JONES S J, et al．Assembling
millions of short DNA sequences using ssake[J]．Bioinformatics, （4）:500－501．2007, 23
[17]ZIMIN A V, SMITH D R, SUTTON G, et al．Assembly reco－
nciliation[J]．Bioinformatics, 2008, 24（1）:42－45．
[18]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
（Su－assemblies around seeds[J]．BMC Bioinformatics, 2009, 10ppl＋1）:S16．
[19]FLICEK P, BIRNEY E．Sense from sequence Reads:methods
（11Suppl ）:for alignment and assembly．Nat Methods, 2009, 6S6－S12．
[20]LI R Q, LI Y R, KRISTIANSEN K, et al．Soap:short oligon－
（5）:7－ucleotide alignment program[J]．Bioinformatics, 2008, 2413－714．
[21]MILLER J R, KOREN S, SUTTON G．Assembly algorithms for
next－generationsequencing data[J]．Genomics, 2010, 95（6）:315－327．
[22]PEVZNER P A, TANG H, WATERMAN M S．An Eulerian p－
ath approach to DNA fragment assembly[C]／／Proc Natl Acad Sci USA, 2001, 98（17）:9748－9753．
[23]BUTLER J, MACCALLUM I, KLEBER M, et al．Allpaths:De
Novo assembly of whole－genomeshotgun Microreads[J]．Genome （5）:810－820．Research, 2008, 18
[24]MACCALLUM I, PRZYBYLSKI D, GNERRE S, et al．All pa－
ths 2:small genomes assembled accurately and with high con－tinuity from short paired Reads[J]．Genome Biology 2009, 10（10）:R103．
（下转第13页）
5结束语
新一代测试数据在提高测序速度、降低测序成本的同
时，也给后续的生物信息学数据处理带来了严峻的挑战。尽管目前人们针对各自的研究课题开发了一些处理全基因组序列拼装软件，并且成功地进行了许多物种的全基因组拼接。然而，数据的处理和分析过程一般局限在大型集群的计算平台上完成，并且拼接质量较低、效率也不高（小型基因组也需要若干小时的拼接组装时间），迫切需要适合于新一代测序的海量reads 数据拼接算法，以便为新一代测序数据的分析与处理提供理论指导和技术支持，加快全基因组测序研究的推进。
参考文献:
[1]METZKER M L．Sequencing Technologies －the Next Generati－
on[J]．Nat Rev Genet, 2010, 11（1）:31－46．
[2]SHENDURE J, JI H．Next－generationDNA sequencing[J]．Nat－（10）:1135－1145．Biotechnol, 2008, 26
[3]POP M, SALZBERG S L．Bioinformatics challenges of new se－quencing Technology[J]．Trends Genet, 2008, 24（3）:142－149．[4]WHITEFORD N, HASLAM N, WEBER G, et al．An analysis of
the feasibility of short read sequencing[J]．Nucleic Acids Res,2－（19）:e171．005, 33
[5]WANG J, WANG W, LI R, et al．The diploid genome sequence of an Asian individual[J]．Nature, 2008, 456（7218）:60－65．[6]LI R Q,
LI Y R,
ZHENG H C, et al．Building the sequence
map of the Human pan－genome[J]．Nature Biotechnology, 2010, （1）:57－63．28
[7]TONG P, PRENDERGAST J G, LOHAN A J, et al．Sequencing and analysis of an Irish human genome[J]．Genome Biol, 2010, 11（9）:R91．
[8]HIATT J B, PATWARDHAN R P, TURNER E H, et al．Paral－lel, tag－directedassembly of locally derived short sequence rea－ds[J]．Nat Methods, 2010, 7（2）:119－122．
[9]JECK W R, REINHARDT J A, BALTRUS D A, et al．Extend－
第4期
闫昕，等：支持大规模个性化需求描述的服务过程模型
·13·
[7]王显志，王忠杰，徐晓飞．面向服务整合的顾客个性化需求
分类与描述方法[J]．黑龙江大学自然科学学报，2009，26（5）:622－626．[8]
莫同，徐晓飞，王忠杰．面向服务系统设计的服务需求模型[J]．
计算机集成制造系统，2009,15（4）：661－669．
[9]詹蓉，陈荣秋．个性化需求分类的定量分析研究[J]．软科学，
2007，21（3）:5－8．
．．
．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
（上接第7页）
[25]LI R, ZHU H, RUAN J, et al．De Novo assembly of human
genomes with massively parallel short Read sequencing[J]．Ge－nome Research, 2009, 20（2）:265－272．[26]CHAISSON M J, BRINZA D, PEVZNER P A．
De Novo frag－
ment assembly with short mate－pairedReads:Does the Read length matter芽[J]．Genome Research, 2009, 19（2）:336－346．[27]SCHEIBYE－ALSINGK, HOFFMANN S, FRANKEL A, et al．
Sequence assembly[J]．Comput Biol Chem, 2009, 33（2）:121－136．
[28]CHAISSON M J, PEVZNER P A．Short Read fragment assem－
bly of Bacterial genomes[J]．Genome Research, 2008, 18（2）:324－330．
[29]ZERBINO D R, BIRNEY E．Velvet:algorithms for De Novo
short read assembly using De Bruijn graphs[J]．Genome Resea－rch, 2008, 18（5）:821－829．
[30]REINHARDT J A, BALTRUS D A, NISHIMURA M T, et al．
De Novo assembly using low－coverageshort Read sequence d－ata from the rice pathogen pseudomonas Syringae Pv．Oryzae．[J]Genome Research, 2009, 19（2）:294－305．
[31]HARISMENDY O, NG P C, STRAUSBERG R L, et al．Eval－
uation of next generation sequencing platforms for population targeted sequencing studies[J]．Genome Biology, 2009, 10（3）:R32．
[32]MILLER J R, DELCHER A L, KOREN S, et al．Aggressive
assembly of pyrosequencing reads with mates[J]．Bioinformatics, 2008, 24（24）:2818－2824．
[33]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
assemblies around seeds[J]．BMC Bioinformatics, 2009, 10（Su－（ppl＋1）:S16．
[34]HUSON D H, REINERT K, MYERS E W．The greedy path－
merging algorithm for contig scaffolding[J]．Journal of the Acm, （5）:603－615．2002, 49
[35]MILLER J R, DELCHER A L, KOREN S, et al．Aggressive
assembly of pyrosequencing Reads with mates[J]．Bioinformati－cs, 2008, 24（24）:2818－2824．
[36]HOSSAIN M S, AZIMI N, SKIENA S．Crystallizing short－read
assemblies around seeds[J]．BMC Bioinformatics, 2009, 10（Su－ppl＋1）:S16．
[37]NARZISI G, MISHRA B．Comparing De Novo genome assemb－
ly:the long and short of It[J]．PLoS ONE, 2011, 6（4）．