基于BWT的DNA重疊群序列合并算法研究.pdf

1、自1977年基因測序技術(shù)的產(chǎn)生發(fā)展之后,人們對(duì)基因分子生物學(xué)的研究和探索的熱情日益高漲,分子生物學(xué)迅猛發(fā)展,第二代測序技術(shù)的產(chǎn)生使基因分子生物學(xué)的發(fā)展產(chǎn)生巨大變革。隨之第三代測序技術(shù)不斷發(fā)展,人們能夠更容易的獲得大量的基因測序數(shù)據(jù)。不同于第一代測序技術(shù)產(chǎn)生的較長序列片段,新一代測序的數(shù)據(jù)片段相對(duì)較短,錯(cuò)誤率也較高,同時(shí),新一代測序技術(shù)的擁有的顯著優(yōu)點(diǎn)就是高通量,成本低,其顯著優(yōu)點(diǎn)促使研究人員對(duì)基因組拼接組裝算法的研究產(chǎn)生更大的熱情。生物

2、測序技術(shù)革命性的飛躍,使基因的拼接合并技術(shù)面臨新的挑戰(zhàn)。
　　本文將要探討的DNA重疊群序列的合并算法,是全基因組拼接組裝算法的一個(gè)重要過程,即為全基因組組裝過程,但是在很多研究中,基因的組裝過程都只是在基因拼接之后的一個(gè)拼接優(yōu)化過程。研究獨(dú)立于全基因組拼接組裝并高效率的處理海量測序數(shù)據(jù)的重疊群序列合并算法是非常值得深入探討的。
　　本文提出了一種新的DNA重疊群序列的合并算法。該算法是基于BWT方法,建立關(guān)于DNA重疊群參

3、考序列的索引結(jié)構(gòu)。利用現(xiàn)有的配對(duì)信息數(shù)據(jù)庫,將配對(duì)信息與DNA重疊群之間的位置關(guān)系搜索過程轉(zhuǎn)化為BWT索引的序列匹配過程,這種方法能提高處理海量測序數(shù)據(jù)的時(shí)間效率。同時(shí)采用抽樣保存 BWT的索引信息方法,降低算法實(shí)現(xiàn)的內(nèi)存占有率。實(shí)驗(yàn)中,將參考序列的BWT索引得到的與配對(duì)信息的位置關(guān)系信息保存在數(shù)據(jù)結(jié)構(gòu)中,同時(shí)對(duì)重疊群序列之間的匹配關(guān)系進(jìn)行比較刪除,得到關(guān)聯(lián)性最高的重疊群序列,將其進(jìn)行合并,最后得到具有較高質(zhì)量的重疊群序列合并成更長的堿

4、基序列。同時(shí)考慮相鄰重疊群序列之間的兩種位置關(guān)系,對(duì)重疊群序列合并結(jié)果進(jìn)行優(yōu)化更新,修正重復(fù)的序列片段并填充空隙,最終輸出重疊群序列合并結(jié)果序列。
　　本文提出的重疊群序列合并算法,是獨(dú)立于基因拼接組裝技術(shù)的針對(duì)重疊群序列處理的算法,利用BWT結(jié)構(gòu)的快速序列匹配功能,降低內(nèi)存空間的占用,提高算法運(yùn)行的速度,實(shí)現(xiàn)重疊群序列的合并。最后通過對(duì)重疊群序列合并結(jié)果序列的完善,充分考慮重疊群序列之間存在的重復(fù)序列片段和空隙情況,將84％的重