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

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

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

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

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