【2.0】基因组组装-拼接的两种算法OLC和DBG

从测序的代数看

  • 一代测序双脱氧终止法:成本高,读长长,但是通量低
  • 二代测序焦磷酸(illumina):成本低,读长短,通量高且拼装的原理是基于德布鲁因图来拼装的
  • 三代PacBio,Nanopore:成本高,读长超长,通量高,基于overlap拼接

通常来说拼接顺序如下:

  • reads:为我们测序的读段reads
  • contig:片段重叠群,指拼接软件基于短序列之间的重叠区(overlap),拼接获得的较长序列。
  • 片段框架,由先后顺序已知的Contigs组成的序列,中间有Gap。基因组de novo测序中,通过reads拼接获得Contigs后,往往还需要构建454 Paired end库或Illumina Matepair库,以获得一定大小片段(如3Kb、6Kb、10Kb、20Kb)两端的序列。基于这些序列,可以确定一些Contig之间的顺序关系,这些先后顺序已知的Contigs组成Scaffold。
  • N50:Reads拼接后会获得一些不同长度的Contigs。将所有的Contigs长度相加,获得Contig总长度。然后将所有的Contigs按照从长到短进行排序,如获得Contig1,Contig2,Contig3…Contig25。将Contigs按照这个顺序依次相加,当相加的长度达到Contig总长度的一半时,最后一个加上的Contig长度即为Contig N50,可以作为基因组拼接的结果好坏的一个判断标准。此概念很容易被误认为所有Contigs长度排名第50的序列长度,与之类似的有N90,N50与N90同样适用于Scaffolds。

测序拼接的主要过程就是把reads分组为重叠群(contigs),把重叠群分组为支架( scaffolds)。重叠群以reads 进行多重排列,并且形成共同序列,而支架( 即超级重叠群或巨型重叠群)规定了重叠群的顺序和方向以及重叠群之间缺口的大小。

两种算法:

  • overlap–layout–consensus (OLC)
  • de-bruijn-graph (DBG)

一、OLC

Over lap Layout Consensus

OLC generally works in three steps: first overlaps (O) among all the reads are found, then it carries out a layout (L) of all the reads and overlaps information on a graph and finally the consensus (C) sequence is inferred 它是intuitionistic assembly algorithm,由Staden (1980)发明,主要用于长的低丰度序列的拼接,特别是一代数据,常见的软件有Arachne[6], Celera Assembler [7], CAP3 [8], PCAP [9],Phrap [10], Phusion [11] and Newbler [12].

基于OLC算法的拼接,基本原理如下: 首先找到reads与reads之间的overlap区域,然后根据这些overlap区域拼接出scaffolds,最后基于这些scaffold的关系确定先后顺序,完成拼接

二、DBG

DBG是anti-intuition algorithm,它是首先将reads分割为更短的k-mers,然后来构图。1995 by Ramana M.Idury and Michael S. Waterman. 适合搞丰度的短的序列的拼接。相应的软件有Euler-USR [15],Velvet [16], ABySS [17], AllPath-LG [18] ,SOAPdenovo [19] 【22,23】对这种算法提出了质疑,而【18,19】认为这种算法还是有较高的可信度的。争议一直存在,但软件的改进也没有停止过。

图A是OLC,图B是DBG,假设我们获得的reads是20bp.图A中,我们生成6个片段,每个片段长度(L)是10bp,至少重叠长度(O)为5bp,然后各个片段建立OLC图。图B的k-mers为5,建立DBG图。 拼接软件拼接结果的好坏

重复区域拼接效果很差。。

这个方法主要基于图论里面的德布鲁因图来完成拼接的

比方说以读段AGATACT为例,那么3-mer(k=3)构成的德布鲁因图如上,每个3-mer前后错位1个碱基,依次排列开。 那么对于两条读段来说,首先找到两条序列重叠的部分,发现它们之间仅一个碱基不同,根据德布鲁因图,发现它们其中三个k-mer会有所不同,并形成一个小包

那么小包外的部分就确定为我们的基因组的一部分了 对于10个读段来说:

对于不同的k-mer,会隆起一个小包,那么小包外的部分即可以确定为基因组的一部分,对于小包来说,根据更多的读段,在进行打分,从而选择最优的那条路径

目前二代组装常用的软件有:

  1. OLC:Canu,Celera Assembler,Falcon等
  2. DBG:SOAPdenovo2,SPAdes,ALLPath-LG,Velvet等

三、三代数据组装基因组

三代数据读长较长,需要30X以上的深度 它的拼接基本想法和二代的OLC比较类似,先寻找测序reads之间的overlap关系,把它们拼接成Contig,然后根据图论的方法,解出最优路径,然后对Contig进行矫正,从而拿到一致性序列

只不过较二代数据来说,由于三代读长较长,所以基于长reads拼接较为准确直观

目前三代拼接的软件有:

  1. CANU
  2. WTDBG2

四、遗传图谱挂载染色体

一般来说,无论是二代还是三代数据,按照上面两节介绍的技术来组装,只能组装到scaffolds的水平,接下来拼接到染色体水平,需要利用HI-C来做染色体挂载

Hi-C建库

Hi-C建库原理是,在同一条染色体上的DNA片段因为空间距离更近,所以更容易被蛋白交联在一起。所以Hi-C测的是被蛋白交联的DNA片段,所以这样组装就可以将这些Contig依据染色体进行分组

像热图红色部分即为染色体分组 目前染色体挂载常用的软件有:ALLHIC,3d-DNA,LACHESIS,SALSA2

五、讨论

一般使用重叠群和支 架的尺寸大小和精确度进行评判,拼接结果尺寸通 常以最大contig长度、contig平均长度、全部contig 总全长和N50 值等统计数据表示。作为评判拼接 结果好坏的另一指标———精确度,一般情况下则很 难准确衡量。

参考资料:

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn