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

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

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

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