高效、务实、严谨、敬业
技术服务
技术专题
联系我们

联系我们

广州赛诚生物科技有限公司
广州市天河区黄埔大道中124号2705室
电话:020-29031124
手机:18102256923
Email:servers@gzscbio.com
Fax:020-85625352
QQ:2913120624
基因全序列拼接分析

      全基因组序列拼接是生物信息学研究领域的核心问题。新一代测序技术正在引领生命科学研究进入一个崭新阶段。人类基因组计划完成之后,获得个体基因组的全部序列对于生物学研究、探索与认识生命的本质具有十分重要的科学意义。

      新一代测序技术作为目前生命科学研究的基础手段,随着应用领域的迅速扩增与不断深入,对生物信息学提出了必须正视的基础研究课题。而全基因组序列拼接作为生物信息学的核心问题,面临的主要挑战有:(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序列。

 

De Bruijn图示例

图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数据,是序列拼接算法软件研发过程中必须面对的一个重要课题。

目录浏览