基因組組裝算法

目前，構(gòu)建Graph的主流方法有3種,，Overlap-Layout-Consensus（Celera Assembler,、PBcR），de Bruijn Graph（SOAPdenovo ）和 String Graph（Falcon）,。

相關(guān)文獻(xiàn)

·                 基于De Bruijn圖的宏基因組序列組裝算法研究（CNKI）

·                 對(duì)基因組組裝算法的分析和研究（CNKI）

·                 基于De Bruijn圖的De Novo序列組裝軟件性能分析（CNKI）

·                 DNA序列拼接中de Bruijn圖結(jié)構(gòu)的研究（CNKI）

·                 基因組學(xué)策略（二）揭開(kāi)組裝的神秘面紗上篇（諾禾致源）

·                 String graph – Wikipedia

·                 De Bruijn graph – Wikipedia

·                  

前言

基因組組裝的基本思路：無(wú)論是一代sanger,、二代短reads、三代長(zhǎng)Pacbio,，我們得到的測(cè)序數(shù)據(jù)相較于整個(gè)基因組而言仍然是極小的,；我們的任務(wù)就是將這些小片段連接起來(lái)；序列之間的聯(lián)系因?yàn)?/span>重復(fù)序列的存在變得非常復(fù)雜,，通過(guò)overlap我們最終都會(huì)構(gòu)建Graph,，所有的算法都會(huì)從Graph中得到最優(yōu)路徑，從而得到最初的contig,。

1 OLC算法

適用于reads讀長(zhǎng)較大的測(cè)序數(shù)據(jù),，如一代和三代的reads。

主要分為三步：（1）Overlap：,，對(duì)所有reads進(jìn)行兩兩比對(duì),，找到片段間的重疊信息,；（2）Layout：根據(jù)得到的重疊信息將存在的重疊片段建立一種組合關(guān)系，形成重疊群,，即Contig；（3）根據(jù)構(gòu)成Contig的片段的原始質(zhì)量數(shù)據(jù),，在重疊群中尋找一條質(zhì)量最重的序列路徑,，并獲得與路徑對(duì)應(yīng)的序列，即Consensus,。

OLC算法最初成功的用于Sange測(cè)序數(shù)據(jù)的組裝,，比如Celera Assembler，Phrap,，Newbler等均采用該算法進(jìn)行拼接組裝,。

2 DBG算法

適用于reads比較短的測(cè)序數(shù)據(jù)，二代數(shù)據(jù),。缺點(diǎn)：難以對(duì)重復(fù)序列區(qū)域進(jìn)行分析,，更依賴(lài)于建庫(kù)。

首先將reads打斷成長(zhǎng)度為K的核酸片段,，即Kmer,，在利用Kmer間的overlap關(guān)系構(gòu)建DBG，再通過(guò)DBG得到基因組序列,。

DBG算法最早應(yīng)用于如細(xì)菌類(lèi)小的基因組的組裝上,，直到李瑞強(qiáng)等(2010)開(kāi)發(fā)SOAPdenovo 算法，成功的組裝了采用二代測(cè)序的黃瓜及熊貓的基因組,，DBG算法開(kāi)始普遍運(yùn)用,。

  
 
假設(shè)我們獲得的reads是20bp，圖1a中,，生成6個(gè)片段,，每個(gè)片段長(zhǎng)度（L）是10bp，至少重疊長(zhǎng)度（O）為5bp,，然后各個(gè)片段建立OLC圖,。圖1b的Kmer為5，建立DBG圖,。

DBG算法相比于OLC的優(yōu)勢(shì)是什么,？

由于二代測(cè)序得到的reads長(zhǎng)度較短，包含的信息量較少,，因此完成基因組拼接需要較高的覆蓋度,。OLC算法適用于讀長(zhǎng)較長(zhǎng)的序列組裝，通過(guò)構(gòu)成的OLC圖尋找Consensus sequence的過(guò)程,，實(shí)際上是哈密頓通路尋找的問(wèn)題,，算法非常復(fù)雜,。

若采用OLC算法，會(huì)大大增加拼接的復(fù)雜性以及運(yùn)算量,。而采用DBG算法,，通過(guò)K-1的overlap關(guān)系，構(gòu)建DBG圖,，通過(guò)尋找歐拉路徑得到Contig序列,，從算法的角度極大的簡(jiǎn)化了組裝的難度。

講完算法,，我們以目前應(yīng)用廣泛的 SOAPdenovo 軟件為例來(lái)介紹組裝過(guò)程,。

SOAPdenovo軟件的組裝過(guò)程

（1）通過(guò)Kmer之間K-1的overlap關(guān)系構(gòu)建contig（重疊群），如圖2：

（2）利用pair-end信息,，將無(wú)overlap關(guān)系的contigs搭建成scaffold(腳手架）,，如圖3：

1數(shù)據(jù)糾錯(cuò)

要得到一個(gè)有較高準(zhǔn)確性的基因組圖譜，首先對(duì)測(cè)序得到的數(shù)據(jù)進(jìn)行處理：

 
將reads逐bp打斷成長(zhǎng)度為K的連續(xù)核酸序列,，如上圖a所示,，若這條reads中間由于測(cè)序錯(cuò)誤有一個(gè)錯(cuò)誤的堿基，那么在得到的Kmer中,，也會(huì)有一些錯(cuò)誤Kmer或者低頻Kmer,。

繪制Kmer頻數(shù)分布圖時(shí)，如上圖b所示,，Error free代表沒(méi)有測(cè)序錯(cuò)誤的Kmer頻數(shù)分布,，Error rate1%代表有1%錯(cuò)誤率的Kmer頻數(shù)分布。

錯(cuò)誤Kmer對(duì)后續(xù)組裝會(huì)產(chǎn)生很大的困擾,，因此,，在構(gòu)建DBG圖之前，需要先對(duì)數(shù)據(jù)進(jìn)行糾錯(cuò),。糾錯(cuò)的兩種方法：

（1）基于Read間的比對(duì),，通過(guò)多序列比對(duì)，通過(guò)概率模型區(qū)分測(cè)序錯(cuò)誤引起的錯(cuò)誤Kmer,。這種方法糾錯(cuò)準(zhǔn)確,，但需要消耗較大的計(jì)算資源。如ALLPATH-LG,，ECHO等糾錯(cuò)軟件都基于這種方法,。

（2）通過(guò)Kmer頻數(shù)圖譜進(jìn)行區(qū)分，這類(lèi)軟件如SOAPdenovo,，Euler等,。

2構(gòu)建Contig

根據(jù)Kmer之間的overlap關(guān)系進(jìn)行連接，如下圖所示：

 
reads（read1：AGATCTTGTTATT,；read2：GTTATTGATCTCC）逐bp的打斷成長(zhǎng)度為5bp的Kmer,，根據(jù)Kmer間的overlap關(guān)系進(jìn)行連接,。可以看到兩條reads中 GATCT 和 GTTATT 是兩個(gè)重復(fù)的片段,，在構(gòu)建De Bruijn圖中,，會(huì)形成如上圖的泡狀結(jié)構(gòu)以及多個(gè)分支的情況，面對(duì)這種很復(fù)雜的圖,，如何才能找到那一條正確的路徑呢,？

（1）對(duì)De Bruijn圖進(jìn)行化簡(jiǎn)

簡(jiǎn)化DeBruijn圖需要去掉無(wú)法繼續(xù)連接的分支、低覆蓋度的分支,，并且利用序列信息化簡(jiǎn)重復(fù)序列在De Bruijn圖的分叉通路，對(duì)于少量的雜合位點(diǎn),，采用隨機(jī)選擇策略,，合并雜合位點(diǎn)。通常需要考慮如下幾種情況：

  
（2）得到一個(gè)簡(jiǎn)化的De Bruijn圖后,，仍然會(huì)因有很多分叉位點(diǎn)無(wú)法確定真正的連接關(guān)系,，因此接下來(lái)在每個(gè)分叉位點(diǎn)將序列截?cái)啵玫搅俗畛?/span>contigs,。

  
 
留給大家一個(gè)思考題：根據(jù)上述步驟,，我們看下圖4中復(fù)雜的De Bruijn示意圖，可以得到什么樣的contigs呢,？（答案見(jiàn)文末）

3構(gòu)建scaffold

將測(cè)序得到的reads比對(duì)回得到的contigs,，利用reads之間的連接關(guān)系和插入片段大小信息，將contigs組裝成scaffolds,。

4補(bǔ)洞

得到的scaffold中間會(huì)有較多的gap,，為了使組裝的序列更完整，需再次利用測(cè)序的雙末端數(shù)據(jù)之間的配對(duì)關(guān)系連接contigs,，并利用測(cè)序數(shù)據(jù)與已經(jīng)組裝的contig之間的覆蓋關(guān)系對(duì)contig之間空隙進(jìn)行補(bǔ)洞,，延長(zhǎng)contigs，補(bǔ)洞后的contigs長(zhǎng)度相比補(bǔ)洞之前一般增加2-7倍,。

  
 
以上就是SOAPdenovo組裝的基本過(guò)程,，看明白了嗎？

“揭開(kāi)組裝的神秘面紗下篇”敬請(qǐng)期待～

參考文獻(xiàn)

1.                Li RQ, Zhu HM, Ruan J, et al. Denovo assembly ofhuman genomes with massively parallel short readsequencing. Genome Res. 2010,20(2), 265-72.

2.                Li ZY, Chen YX, Mu DS, et al. Comparison of the two majorclasses ofassembly algorithms: overlap-layout-consensus andde-bruijn-graph. Brief Funct Genomics. 2012, 11(1), 25-37

3 string graph算法

有利于組裝散列重復(fù)序列,。

string graph中的節(jié)點(diǎn)是長(zhǎng)度不一的序列,，這些序列是由overlappingreads生成，需要設(shè)置一個(gè)最小overlap大小,。

 本文轉(zhuǎn)自http://www.cnblogs.com/leezx/p/5590159.html