基因全序列拼接分析
全基因组序列拼接是生物信息学研究领域的核心问题。新一代测序技术正在引领生命科学研究进入一个崭新阶段。人类基因组计划完成之后，获得个体基因组的全部序列对于生物学研究、探索与认识生命的本质具有十分重要的科学意义。
新一代测序技术作为目前生命科学研究的基础手段，随着应用领域的迅速扩增与不断深入，对生物信息学提出了必须正视的基础研究课题。而全基因组序列拼接作为生物信息学的核心问题，面临的主要挑战有：（1）海量的数据（覆盖深度一般为40-200倍，数据量达20-200GB），迫切需要海量数据的拼接组装算法；（2）测序数据中的错误，容易导致错拼；（3）基因组中重复片段大量存在，由于读取片段reads长度过短，一般只有几十个碱基，这使得重复序列的处理变得困难。
针对新一代测序数据reads长度较短、数据海量的特点，全基因组测序方面的数据分析软件的研发，已成为生物信息学领域最迫切、最重要的研究课题。虽然目前已开发有一些全基因组拼接软件，但是基本都局限在大型计算平台上完成数据分析过程，难以满足一般的研究需求，而且数据处理速度仍然远远落后于数据产生速度，已经成为整个基因组图谱绘制工作的瓶颈，并且其拼接结果在准确性方面还有待提高。
基因组序列拼接的核心思想是利用序列之间的交叠关系，通过类似于“搭积木”的方式重建目标基因组序列。其基本方法是将序列之间的交叠关系转换成计算机可以识别的结构，通过不断迭代扩展的方式延长目标序列，然后利用配对数据，确定各个目标序列的相对方向和位置关系，最终还原目标基因组序列。 基于新一代测序数据的基因组序列拼接，通常分为如下三个阶段：（1）数据的预处理阶段。该阶段通过特定的方法，移除测序数据中的错误碱基；（2）基因组连续片段（contigs）生成阶段。该阶段将reads拼接成contigs；（3）超长序列片段（scaffoldings）组装阶段。该阶段使用配对数据，确定contigs之间的方向和位置关系，生成scaffoldings。
全基因组从头测序拼接（denovoassembly）是生物信息学研究领域的核心问题。测序产生的读取片段（reads）数据通过序列拼接、组装，获得基因组的碱基排列。目前，基于新一代测序数据的从头测序拼接组装算法，主要基于3种策略：贪心（greedy）、交叠-排列-生成共有序列（Overlap-Layout-Consensus,OLC）与DeBruijn图。
1 贪心策略
贪心策略类型的序列拼接算法主要采用种子迭代扩展的方法，按一定条件选择初始reads作为待生成contigs的种子，通过启发式搜索方式使得每一步都合并与其具有最多交叠的reads,直至reads或contigs两端都不能再做进一步的扩展。一般而言，reads的选择是按照拼接质量递减的顺序考虑的，拼接质量通常用碱基质量和覆盖度来衡量。为避免错拼，有些扩展操作在发现冲突的信息时就立即停止。SSAKE、SHARCGS、VCAKE即采用了该类拼接策略。SSAKE和VCAKE能够处理非完全匹配的reads，SHARCGS适用于均匀分布、非配对的reads.贪心策略适用于小型基因组，而对于有大量重复序列存在的大型基因组的测序数据进行拼接时，拼接效果往往很差。
2 交叠-排列-生成共有序列（OLC）策略
OLC策略在第一代测序中被广泛采用，并取得了很好的结果。该种策略主要包含3个主要的步骤：（1）构建交叠图，计算任意两条reads之间的交叠。为了减少计算复杂度，可以先对reads建立类似后缀数据、后缀树的索引，而后在所建索引的基础上进行计算；（2）排列reads，确定reads之间的相对位置，建立ove-rlap图，分析overlap图，获得遍历整个图的最佳近似路径；（3）生成共有序列，通过多序列比对等方法，获得最终的基因组序列。
由于新一代测序数据的reads海量，计算reads交叠的平方复杂度以及reads长度较短等限制， 基于OLC策略的拼接方法并不适于处理新一代的海量短序列数据，为此，在该种策略的基础上又相继提出了多个更加实用的拼接算法，主要有：CABOG、Edena、Shorty。Shorty用于处理SOLiD数据，利用300-500bp长度的种子上的配对数据，估算两个相邻contigs之间的gap的大小。CABOG采用一种被称为“rocksandstones”的技术，先通过reads之间的交叠关系，建立reads之间的多序列比对，然后使用配对数据分割不满足约束条件的多序列比对，再由多序列比对上的配对数据确定其相对位置，最终生成共有序列。
随着测序技术的不断发展，基因组测序产生的数据质量会越来越高，生成的reads片段也会越来越长，以reads为计算中心的拼接策略或许会再次进入人们的视野，成为研究主题。
3 De Bruijn图策略
基于De Bruijn图（DBG）策略的拼接算法被最广泛地应用到新一代测序数据的处理中。典型算法有：ABySS、ALLPATHS、Euler-SR、SOAPdenovo和Velvet。基于De Bruijn图的拼接算法，非常巧妙地将具有交叠关系的reads映射到一起，降低了计算交叠时的复杂度，减少了内存消耗。
基于DeBruijn图策略的拼接算法的大致步骤是：（1）构建De Bruijn图。将reads分割成一系列连续的子串k-mers （一般用K值表征kmer碱基数目的大小），作为图中的边，相邻的两个k-mers交叠（K-1）个碱基；（2）化简De Bruijn图。方法是合并路径出度入度唯一的节点，按照一定的规则去除图中的尖端（tips）和泡状结构（bubbles）；（3）构建contigs.在DeBruijn图或其子图中寻找一条最优的欧拉路径（一次且仅有一次地经过每条边的路径），该路径对应的碱基序列即为contigs； （4）生成scaffolding。利用配对数据，确定contigs之间的相对方向与位置关系，对contigs进行组装，并填充contigs之间的gaps，最终得到scaffolds序列。
图1 De Bruijn图示例
基于De Bruijn图的拼接算法中，一个关键操作是K值的选择。选择大的K值能够解决更多的短小重复片段（tinyrepeats），降低图的复杂性，但同时也降低了图的连通性，后续的拼接过程会产生更多的间隙（gaps）；选择小的K值，对应的De Bruijn图具有相对好的连通性，但图变得更加复杂，重复片段的处理也变得更加困难，增加了错拼的可能性。目前， 还没有通用的K值选择方法，需要根据特定的应用，选择合适的K值。一般认为对于原核生物的基因组拼接，K值选取在21-35之间是合适的；而对于真核生物基因组的K值的选择要相对复杂得多，目前还没有明确的结论或者一致的建议。
4序列拼接算法的比较
自从基因组测序产生以来，序列拼接算法就不断地处于研发和改进之中。通常，基于图的拼接算法与采用贪心策略的拼接算法相比，在序列长度和准确率，运行时间以及内存消耗等方面，往往具有相对更好的拼接表现。基于OLC策略的拼接算法多用于传统测序数据的拼接，而基于De Bruijn图的拼接算法则更多地用于新一代测序数据。不同的拼接算法在处理不同的测序数据时，通常具有各异的表现，目前还没有一种拼接程序能在所有方面都表现得出色。由于基因组和测序数据的复杂性，拼接长度与准确率往往是一个平衡的关系，高精度往往是以牺牲长度为代价的，反之亦然。而这种平衡如何选择，则取决于具体的应用。同样，拼接结果的准确率与算法的内存消耗也存在类似的平衡关系。就适用的基因组规模而言，除了SOAPdenovo、AByss等少数软件外，大多数拼接软件只适用于简单的小型基因组。目前，几乎所有软件都需要较大内存的计算平台。如何优化数据处理方法、高效地存储海量reads数据，是序列拼接算法软件研发过程中必须面对的一个重要课题。