面向新一代測(cè)序技術(shù)的基因拼接算法.pdf

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

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

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

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