基于BWT的DNA從頭測序重疊群生成算法.pdf

1、隨著遺傳學研究的深入,特別是人類基因組計劃完成之后,人們認識到取得各個物種的完整基因組序列對于生命本質(zhì)的探索有著非常重要的作用。如今新一代DNA測序技術已經(jīng)發(fā)展成熟并被廣泛的使用,其前所未有的測序速度逐漸的促進了基于序列研究的基因組學的研究,同時也增加了對生物信息學算法的需求。
　　新一代測序技術與傳統(tǒng)測序技術相比有速度快、成本低和準確度高的優(yōu)點,但是其產(chǎn)生的序列片段相對較短。由于傳統(tǒng)測序技術開發(fā)的序列拼接算法已不適用于新一代測序

2、技術,開發(fā)針對新一代測序技術的拼接軟件已成為生物信息學領域里一個熱門的課題。為此提出一種基于BWT的從頭測序的重疊群生成算法,該算法利用BWT的搜索功能找到read之間的最優(yōu)重疊從而實現(xiàn)序列拼接的目的。
　　首先通過分析實驗數(shù)據(jù),總結(jié)出read數(shù)據(jù)的特點。然后對序列拼接問題進行分析和建模并給出解決方案。接著詳細介紹了整個BWT索引的建立過程,講述了BWT的原理和作用,以及BTW索引的數(shù)據(jù)結(jié)構(gòu)和使用方法。對DNA序列拼接過程中需要用

3、到的BWT的向前匹配算法進行了描述,設計了向后匹配算法,并分析了這些算法的時間和空間性能。
　　然后就整個contig的生成過程進行了介紹。首先給出contig生成算法的整體流程,接下來就基于BWT的contig的最佳重疊查找算法進行了具體敘述。然后講述了contig的延伸算法,主要分正向延伸和反向延伸。并針對之前生成的contig集合里的重復問題提出了contig的修剪算法。
　　最后,評價了算法輸出的效果,并與EULER