廣州市天河區(qū)黃埔大道中124號(hào)2705室
電話(huà)：020-29031124
手機(jī)：18102256923
Email：servers@gzscbio.com
Fax：020-85625352
QQ：2913120624
全基因組序列拼接是生物信息學(xué)研究領(lǐng)域的核心問(wèn)題。新一代測(cè)序技術(shù)正在引領(lǐng)生命科學(xué)研究進(jìn)入一個(gè)嶄新階段。人類(lèi)基因組計(jì)劃完成之后，獲得個(gè)體基因組的全部序列對(duì)于生物學(xué)研究、探索與認(rèn)識(shí)生命的本質(zhì)具有十分重要的科學(xué)意義。
新一代測(cè)序技術(shù)作為目前生命科學(xué)研究的基礎(chǔ)手段，隨著應(yīng)用領(lǐng)域的迅速擴(kuò)增與不斷深入，對(duì)生物信息學(xué)提出了必須正視的基礎(chǔ)研究課題。而全基因組序列拼接作為生物信息學(xué)的核心問(wèn)題，面臨的主要挑戰(zhàn)有：（1）海量的數(shù)據(jù)（覆蓋深度一般為40-200倍，數(shù)據(jù)量達(dá)20-200GB），迫切需要海量數(shù)據(jù)的拼接組裝算法；（2）測(cè)序數(shù)據(jù)中的錯(cuò)誤，容易導(dǎo)致錯(cuò)拼；（3）基因組中重復(fù)片段大量存在，由于讀取片段reads長(zhǎng)度過(guò)短，一般只有幾十個(gè)堿基，這使得重復(fù)序列的處理變得困難。
針對(duì)新一代測(cè)序數(shù)據(jù)reads長(zhǎng)度較短、數(shù)據(jù)海量的特點(diǎn)，全基因組測(cè)序方面的數(shù)據(jù)分析軟件的研發(fā)，已成為生物信息學(xué)領(lǐng)域最迫切、最重要的研究課題。雖然目前已開(kāi)發(fā)有一些全基因組拼接軟件，但是基本都局限在大型計(jì)算平臺(tái)上完成數(shù)據(jù)分析過(guò)程，難以滿(mǎn)足一般的研究需求，而且數(shù)據(jù)處理速度仍然遠(yuǎn)遠(yuǎn)落后于數(shù)據(jù)產(chǎn)生速度，已經(jīng)成為整個(gè)基因組圖譜繪制工作的瓶頸，并且其拼接結(jié)果在準(zhǔn)確性方面還有待提高。
基因組序列拼接的核心思想是利用序列之間的交疊關(guān)系，通過(guò)類(lèi)似于“搭積木”的方式重建目標(biāo)基因組序列。其基本方法是將序列之間的交疊關(guān)系轉(zhuǎn)換成計(jì)算機(jī)可以識(shí)別的結(jié)構(gòu)，通過(guò)不斷迭代擴(kuò)展的方式延長(zhǎng)目標(biāo)序列，然后利用配對(duì)數(shù)據(jù)，確定各個(gè)目標(biāo)序列的相對(duì)方向和位置關(guān)系，最終還原目標(biāo)基因組序列。 基于新一代測(cè)序數(shù)據(jù)的基因組序列拼接，通常分為如下三個(gè)階段：（1）數(shù)據(jù)的預(yù)處理階段。該階段通過(guò)特定的方法，移除測(cè)序數(shù)據(jù)中的錯(cuò)誤堿基；（2）基因組連續(xù)片段（contigs）生成階段。該階段將reads拼接成contigs；（3）超長(zhǎng)序列片段（scaffoldings）組裝階段。該階段使用配對(duì)數(shù)據(jù)，確定contigs之間的方向和位置關(guān)系，生成scaffoldings。
全基因組從頭測(cè)序拼接（denovoassembly）是生物信息學(xué)研究領(lǐng)域的核心問(wèn)題。測(cè)序產(chǎn)生的讀取片段（reads）數(shù)據(jù)通過(guò)序列拼接、組裝，獲得基因組的堿基排列。目前，基于新一代測(cè)序數(shù)據(jù)的從頭測(cè)序拼接組裝算法，主要基于3種策略：貪心（greedy）、交疊-排列-生成共有序列（Overlap-Layout-Consensus,OLC）與DeBruijn圖。
1 貪心策略
貪心策略類(lèi)型的序列拼接算法主要采用種子迭代擴(kuò)展的方法，按一定條件選擇初始reads作為待生成contigs的種子，通過(guò)啟發(fā)式搜索方式使得每一步都合并與其具有最多交疊的reads,直至reads或contigs兩端都不能再做進(jìn)一步的擴(kuò)展。一般而言，reads的選擇是按照拼接質(zhì)量遞減的順序考慮的，拼接質(zhì)量通常用堿基質(zhì)量和覆蓋度來(lái)衡量。為避免錯(cuò)拼，有些擴(kuò)展操作在發(fā)現(xiàn)沖突的信息時(shí)就立即停止。SSAKE、SHARCGS、VCAKE即采用了該類(lèi)拼接策略。SSAKE和VCAKE能夠處理非完全匹配的reads，SHARCGS適用于均勻分布、非配對(duì)的reads.貪心策略適用于小型基因組，而對(duì)于有大量重復(fù)序列存在的大型基因組的測(cè)序數(shù)據(jù)進(jìn)行拼接時(shí)，拼接效果往往很差。
2 交疊-排列-生成共有序列（OLC）策略
OLC策略在第一代測(cè)序中被廣泛采用，并取得了很好的結(jié)果。該種策略主要包含3個(gè)主要的步驟：（1）構(gòu)建交疊圖，計(jì)算任意兩條reads之間的交疊。為了減少計(jì)算復(fù)雜度，可以先對(duì)reads建立類(lèi)似后綴數(shù)據(jù)、后綴樹(shù)的索引，而后在所建索引的基礎(chǔ)上進(jìn)行計(jì)算；（2）排列reads，確定reads之間的相對(duì)位置，建立ove-rlap圖，分析overlap圖，獲得遍歷整個(gè)圖的最佳近似路徑；（3）生成共有序列，通過(guò)多序列比對(duì)等方法，獲得最終的基因組序列。
由于新一代測(cè)序數(shù)據(jù)的reads海量，計(jì)算reads交疊的平方復(fù)雜度以及reads長(zhǎng)度較短等限制， 基于OLC策略的拼接方法并不適于處理新一代的海量短序列數(shù)據(jù)，為此，在該種策略的基礎(chǔ)上又相繼提出了多個(gè)更加實(shí)用的拼接算法，主要有：CABOG、Edena、Shorty。Shorty用于處理SOLiD數(shù)據(jù)，利用300-500bp長(zhǎng)度的種子上的配對(duì)數(shù)據(jù)，估算兩個(gè)相鄰contigs之間的gap的大小。CABOG采用一種被稱(chēng)為“rocksandstones”的技術(shù)，先通過(guò)reads之間的交疊關(guān)系，建立reads之間的多序列比對(duì)，然后使用配對(duì)數(shù)據(jù)分割不滿(mǎn)足約束條件的多序列比對(duì)，再由多序列比對(duì)上的配對(duì)數(shù)據(jù)確定其相對(duì)位置，最終生成共有序列。
隨著測(cè)序技術(shù)的不斷發(fā)展，基因組測(cè)序產(chǎn)生的數(shù)據(jù)質(zhì)量會(huì)越來(lái)越高，生成的reads片段也會(huì)越來(lái)越長(zhǎng)，以reads為計(jì)算中心的拼接策略或許會(huì)再次進(jìn)入人們的視野，成為研究主題。
3 De Bruijn圖策略
基于De Bruijn圖（DBG）策略的拼接算法被最廣泛地應(yīng)用到新一代測(cè)序數(shù)據(jù)的處理中。典型算法有：ABySS、ALLPATHS、Euler-SR、SOAPdenovo和Velvet。基于De Bruijn圖的拼接算法，非常巧妙地將具有交疊關(guān)系的reads映射到一起，降低了計(jì)算交疊時(shí)的復(fù)雜度，減少了內(nèi)存消耗。
基于DeBruijn圖策略的拼接算法的大致步驟是：（1）構(gòu)建De Bruijn圖。將reads分割成一系列連續(xù)的子串k-mers （一般用K值表征kmer堿基數(shù)目的大小），作為圖中的邊，相鄰的兩個(gè)k-mers交疊（K-1）個(gè)堿基；（2）化簡(jiǎn)De Bruijn圖。方法是合并路徑出度入度唯一的節(jié)點(diǎn)，按照一定的規(guī)則去除圖中的尖端（tips）和泡狀結(jié)構(gòu)（bubbles）；（3）構(gòu)建contigs.在DeBruijn圖或其子圖中尋找一條最優(yōu)的歐拉路徑（一次且僅有一次地經(jīng)過(guò)每條邊的路徑），該路徑對(duì)應(yīng)的堿基序列即為contigs； （4）生成scaffolding。利用配對(duì)數(shù)據(jù)，確定contigs之間的相對(duì)方向與位置關(guān)系，對(duì)contigs進(jìn)行組裝，并填充contigs之間的gaps，最終得到scaffolds序列。
圖1 De Bruijn圖示例
基于De Bruijn圖的拼接算法中，一個(gè)關(guān)鍵操作是K值的選擇。選擇大的K值能夠解決更多的短小重復(fù)片段（tinyrepeats），降低圖的復(fù)雜性，但同時(shí)也降低了圖的連通性，后續(xù)的拼接過(guò)程會(huì)產(chǎn)生更多的間隙（gaps）；選擇小的K值，對(duì)應(yīng)的De Bruijn圖具有相對(duì)好的連通性，但圖變得更加復(fù)雜，重復(fù)片段的處理也變得更加困難，增加了錯(cuò)拼的可能性。目前， 還沒(méi)有通用的K值選擇方法，需要根據(jù)特定的應(yīng)用，選擇合適的K值。一般認(rèn)為對(duì)于原核生物的基因組拼接，K值選取在21-35之間是合適的；而對(duì)于真核生物基因組的K值的選擇要相對(duì)復(fù)雜得多，目前還沒(méi)有明確的結(jié)論或者一致的建議。
4序列拼接算法的比較
自從基因組測(cè)序產(chǎn)生以來(lái)，序列拼接算法就不斷地處于研發(fā)和改進(jìn)之中。通常，基于圖的拼接算法與采用貪心策略的拼接算法相比，在序列長(zhǎng)度和準(zhǔn)確率，運(yùn)行時(shí)間以及內(nèi)存消耗等方面，往往具有相對(duì)更好的拼接表現(xiàn)。基于OLC策略的拼接算法多用于傳統(tǒng)測(cè)序數(shù)據(jù)的拼接，而基于De Bruijn圖的拼接算法則更多地用于新一代測(cè)序數(shù)據(jù)。不同的拼接算法在處理不同的測(cè)序數(shù)據(jù)時(shí)，通常具有各異的表現(xiàn)，目前還沒(méi)有一種拼接程序能在所有方面都表現(xiàn)得出色。由于基因組和測(cè)序數(shù)據(jù)的復(fù)雜性，拼接長(zhǎng)度與準(zhǔn)確率往往是一個(gè)平衡的關(guān)系，高精度往往是以犧牲長(zhǎng)度為代價(jià)的，反之亦然。而這種平衡如何選擇，則取決于具體的應(yīng)用。同樣，拼接結(jié)果的準(zhǔn)確率與算法的內(nèi)存消耗也存在類(lèi)似的平衡關(guān)系。就適用的基因組規(guī)模而言，除了SOAPdenovo、AByss等少數(shù)軟件外，大多數(shù)拼接軟件只適用于簡(jiǎn)單的小型基因組。目前，幾乎所有軟件都需要較大內(nèi)存的計(jì)算平臺(tái)。如何優(yōu)化數(shù)據(jù)處理方法、高效地存儲(chǔ)海量reads數(shù)據(jù)，是序列拼接算法軟件研發(fā)過(guò)程中必須面對(duì)的一個(gè)重要課題。