经典:基因组测序数据从头拼接或组装算法的原理

时间:2024-01-25 13:08:35

 


基因组测序数据的拼接/组装 (图片来源:google)  
 

每一个物种的参考基因组序列(reference genome)的产生都要先通过测序的方法,获得基因组的测序读段(reads),然后再进行从头拼接或组装(英文名称为do novo genome assembly),最后还原测序物种的各条染色体的序列,即ATGC四种碱基的排列顺序。

 

之所以要进行基因组拼接,是因为现在的测序技术还只能测较短的序列,无法直接获取一整条染色体的序列。如一代测序(Sanger测序)一般可测1kb左右的序列;二代测序(next-generation sequencing),一般可测50~500bp;三代测序虽然可测100kb甚至更长的序列,但现在三代测序技术还不是很成熟,还有较高的测序错误率。(欢迎关注微信公众号:AIPuFuBio,和使用生物信息学平台AIPuFu:www.aipufu.com)

 

基因组测序数据的从头组装过程,可简单描述为:reads---->contig---->scaffold---->chromosome,具体如下所示:


基因组序列从头组装示意图(图片来源:Guo et al. Genomics, 2017)。
 
首先基因组测序产生reads,然后对reads进行组装产生长片段Contigs,再确定Contig的方向和顺序,组装产生更长的片段Scaffolds,最后再组装连接Scaffold得到完整的染色体序列。

 

接下来,给大家依次介绍一下上图从头拼接中涉及到的两个概念:contig和scaffold

Contig是由多个reads通过组装而形成的长片段。由于测序读段较短、基因组序列通常含有较多重复序列、而且还有测序错误等原因,除了简单的基因组序列外,大部分物种的基因组序列组装都会先产生很多contig,无法一次获得完整的染色体序列。

Scaffold为多条contig序列连接形成更长片段,这些contig方向和顺序已经确定,且contig间未知序列(一般用NNNN表示)的长度也获知。

 

Scaffold的获得一般主要通过双端测序(如paired-end sequecing或mate-pair sequencing)来确定contig的顺序和方向,以及contig之间的间隔距离,具体如下示意图所示。


由reads组装产生contig,再由contig连接形成scaffold的示意图 (图片来源:google)  

 

基因组测序数据的从头组装的核心算法主要可以分为以下几大类:

1、基于贪心算法(greedy-extention);

2、基于Overlap-Layout-Consensus(OLC);

3、基于de Bruijn Graph;

4、以上两种或多种算法的组合;

5、其他类型。

 

具体如下图所示:


基因组从头组装算法分类及代表性软件发表的时间(图片来源:Zhanget al. PlosOne, 2011)

其中最经典的两类为:

1)Overlap-Layout-Consensus(OLC)算法,基于OLC算法的组装软件主要是针对长测序读段(如Sanger测序、454测序等)设计的;

2)de Bruijn Graph算法,基于de Bruijn Graph的组装软件则主要是针对二代测序产生的短读段数据设计。

 

具体如下所示:

1)Overlap-Layout-Consensus(OLC)算法


Overlap-Layout-Consensus(OLC)算法的示意图(图片来源:Ayling et al. Briefings in Bioinformatics, 2019)

 

2)de Bruijn Graph算法


de Bruijn Graph算法的示意图(图片来源:Ayling et al. Briefings in Bioinformatics, 2019)

 

现在主流的是二代测序技术,因此再给大家详细介绍一下专门针对二代测序数据开发的基于de Bruijn Graph的从头拼接方法。

 

其中一个非常著名的软件就是Velvet,是基于de Bruijn Graph设计的经典代表,其算法示意图如下:


Velvet从头组装软件的算法设计示意图( 图片来源:Zerbinoet al. 2008, Genome Research)。其中红色碱基为测序错误或SNP位点。

 

Velvet的组装原理,主要可分为这几个步骤:

1)首先把所有测序读段(reads)都分割为更小的片段k-mer;


Reads产生k-mer的过程示意图。这里k为7,假如read的长度为n,则总共可产生n-1个k-mer。

2)把每个k-mer作为一个节点,然后判断k-mer之间是否有k-1碱基的重叠,如果有则作为两个不同的节点连接起来。依次这样连接所有可连接的k-mer就形成了Velvet从头组装软件算法设计示意图中第2步的de Bruijn Graph;

3)依次合并相邻的k-mer,因为相邻的k-mer有k-1个碱基的重叠,就可进一步简化de Bruijn Graph形成Velvet从头组装软件算法设计示意图中第3步的简化后的图;

4)使用一系列算法消除由测序错误而形成的tips(具体如Velvet从头组装软件的算法设计示意图中所示),并合并bubbles(两条或多条路径序列,一般由SNP造成,如Velvet从头组装软件的算法设计示意图);

5)最后拼接得到Contig序列。

 

值得注意的是,Velvet从头组装软件算法设计示意图中最后一步拼接产生了回文序列,主要是由于原始序列中含有回文,如果k取为偶数(图中k=4)就容易在组装中形成这种现象。

为了有效的避免拼接中产生回文序列,一般k取为奇数。

 

那么基于基因组测序数据的从头拼接软件,那些具有较好的性能呢?


不同从头组装软件在拼接C.elegans、Yeast、E.coli、Swinepox基因组时的准确性和覆盖度比较( 图片来源:Zhanget al. PlosOne, 2011)

 

从上图中可以看出,Velvet和SOAPdenovo在拼接C.elegans、Yeast、E.coli、Swinepox的基因组序列时,相对于其他软件,组装结果更准确(A:Percentage of correctly mapped contigs)且拼接出来的序列能更完整的覆盖原基因组序列(B:Genome Coverage)。

 

大部分处理测序数据的软件都是由国外开发的,其中这里提到的SOAPdenovo为华大基因开发的从头拼接软件。

 

​今天就给大家介绍到这里。更多精彩,可见大型免费综合生物信息学资源和工具平台AIPuFu:www.aipufu.com,关注微信公众号:AIPuFuBio。

 

希望今天的内容对大家有用,会持续更新经典内容,欢迎留言~~!