面向新一代測序技術的基因拼接算法.pdf

1、基因拼接是生物信息學領域研究的基礎課題之一，也是一個難度較大但十分有意義的研究課題?；蚱唇邮侵笍慕o定的基因序列集合出發(fā)，利用計算機技術，再重新構造出該生物DNA序列的過程。新一代測序技術的出現(xiàn)和發(fā)展大大改變了基因研究領域并加快了生物學和醫(yī)學研究的進程。新一代測序技術一次可以獲得幾百萬條序列信息，能在短時間內(nèi)完成整個基因組數(shù)據(jù)的測定，但相比于傳統(tǒng)測序技術，成本卻下將了數(shù)十倍。目前，基因研究工作面臨最大的挑戰(zhàn)是新測序的基因序列數(shù)據(jù)無法得到

2、及時的計算和分析，后續(xù)的研究工作也無法開展。高效的基因拼接算法的研究，將對當前生物信息學的發(fā)展起到關鍵性的推動作用。
　　目前基于新一代測序技術產(chǎn)出的短基因序列進行基因拼接的，主要有Greedy-extension，Overlap圖和De Bruijn圖三種方法。De Bruijn圖方法需要尋找的是一條Euler路徑，而Euler路徑問題的時間復雜度在理想情況下是線性的。DeBruijn圖方法另外一個吸引人的特性是其可以將基因中的

3、重復區(qū)域進行收縮，并且不會產(chǎn)生錯誤的重疊。
　　在本文中，我們使用了動態(tài)哈希技術來構建De Bruijn圖。由于設計了性能良好的哈希函數(shù)及有效的解決沖突的方法，并選擇了合適的裝填因子，算法中哈希表的插入和查找操作的時間復雜度較低。由于在拼接過程中查找是一個頻繁的操作，查找操作時間復雜度的下降，對整體性能的提高起到了很重要的作用。同時哈希表的動態(tài)擴展使得算法可以適用于不同大小的生物數(shù)據(jù)的拼接。由于生物的基因數(shù)據(jù)很大，作為拼接算法的輸

4、入，基因文件往往可以達到數(shù)百GB甚至TB級別，這樣文件I/O時間在算法總時間中所占的比例會很大。為了有效的減少文件I/O的時間，本文提出了并行I/O思路。在算法的開始，基因文件會被平均的分割成更小的子文件，這些子文件又會被平均的分配給每一個進程。然后每個進程并行的讀取各自的子文件，并通過進程間通信來交換彼此需要的連接信息。本文在對debruijn圖進行充分分析的基礎上，在生成contig和scaffold的步驟中，同時使用了基于共享內(nèi)存