基于雙向de Bruijn圖的序列拼接并行化研究與實(shí)現(xiàn).pdf

1、DNA序列拼接是生物信息學(xué)領(lǐng)域研究的重要課題。隨著高通量、短序列測(cè)序科技的出現(xiàn)，測(cè)序覆蓋度進(jìn)一步提高，這給原有的序列拼接技術(shù)帶來(lái)了嚴(yán)峻的挑戰(zhàn)。高效的適用于大規(guī)模基因組的拼接技術(shù)成為處理DNA測(cè)序數(shù)據(jù)的關(guān)鍵。如何結(jié)合并行計(jì)算技術(shù)從而提高序列拼接處理速度成為本文研究的重要課題。
　　 通過(guò)對(duì)已有的基于de Bruijn圖的序列拼接技術(shù)的研究與分析，將序列拼接問(wèn)題抽象為多步-雙向de Bruijn圖的結(jié)構(gòu)（本文簡(jiǎn)稱為雙向deBruij

2、n圖），建立數(shù)學(xué)模型，并對(duì)其性質(zhì)進(jìn)行推導(dǎo)與論證。根據(jù)該圖的性質(zhì)，設(shè)計(jì)基于雙向de Bruijn圖結(jié)構(gòu)的并行序列拼接方法，該方法通過(guò)融合半擴(kuò)展單步-雙向邊得到全擴(kuò)展多步-雙向邊集合，即DNA序列拼接過(guò)程中contig結(jié)構(gòu)的集合，最終完成序列拼接。
　　 通過(guò)對(duì)基于雙向de Bruijn圖結(jié)構(gòu)的并行序列拼接方法的每一個(gè)執(zhí)行步驟的確切分析，將該方法劃分為四大功能模塊進(jìn)行實(shí)現(xiàn)，主要包括:并行I/O模塊的設(shè)計(jì)與實(shí)現(xiàn)、單步-雙向de Bru

3、ijn子圖的構(gòu)建、單步-雙向de Bruijn圖的分布式存儲(chǔ)與構(gòu)建以及單步-雙向de Bruijn圖的鄰邊融合模塊的設(shè)計(jì)與實(shí)現(xiàn)。其計(jì)算復(fù)雜度為O(n/p)，通訊復(fù)雜度為O(n/p)，單機(jī)節(jié)點(diǎn)的通訊量為O(n log(n)/p），其中n為DNA序列read的數(shù)量，p為CPU個(gè)數(shù)。
　　 實(shí)驗(yàn)測(cè)試表明，基于雙向de Bruijn圖的并行序列拼接有效提高了序列拼接的運(yùn)算速度，降低了單機(jī)運(yùn)行的內(nèi)存消耗。在拼接數(shù)據(jù)量20G的C.elega