【摘要】：DNA序列拼接是生物信息學領域研究的重要課題。隨著高通量、短序列測序科技的出現(xiàn),測序覆蓋度進一步提高,這給原有的序列拼接技術帶來了嚴峻的挑戰(zhàn)。高效的適用于大規(guī)�；蚪M的拼接技術成為處理DNA測序數(shù)據(jù)的關鍵。如何結合并行計算技術從而提高序列拼接處理速度成為本文研究的重要課題。 通過對已有的基于de Bruijn圖的序列拼接技術的研究與分析,將序列拼接問題抽象為多步-雙向de Bruijn圖的結構(本文簡稱為雙向deBruijn圖),建立數(shù)學模型,并對其性質進行推導與論證。根據(jù)該圖的性質,設計基于雙向de Bruijn圖結構的并行序列拼接方法,該方法通過融合半擴展單步-雙向邊得到全擴展多步-雙向邊集合,即DNA序列拼接過程中contig結構的集合,最終完成序列拼接。 通過對基于雙向deBruijn圖結構的并行序列拼接方法的每一個執(zhí)行步驟的確切分析,將該方法劃分為四大功能模塊進行實現(xiàn),主要包括：并行I/O模塊的設計與實現(xiàn)、單步-雙向de Bruijn子圖的構建、單步-雙向de Bruijn圖的分布式存儲與構建以及單步-雙向de Bruijn圖的鄰邊融合模塊的設計與實現(xiàn)。其計算復雜度為O(n/p),通訊復雜度為O(n/p),單機節(jié)點的通訊量為O(nlog(n)/p),其中n為DNA序列read的數(shù)量,p為CPU個數(shù)。 實驗測試表明,基于雙向de Bruijn圖的并行序列拼接有效提高了序列拼接的運算速度,降低了單機運行的內存消耗。在拼接數(shù)據(jù)量20G的C.elegans基因組時,其可從10個CPU擴展到640,加速比達到20倍,具有良好的可擴展性。
【學位授予單位】：中南大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：Q523;TP338.6

【參考文獻】

相關期刊論文 前5條

1 張勇,張軼博,劉軍,雷振明;基于取模運算哈希函數(shù)映射均衡性研究[J];重慶郵電學院學報(自然科學版);2004年02期

2 遲利華,劉杰,胡慶豐;數(shù)值并行計算可擴展性評價與測試[J];計算機研究與發(fā)展;2005年06期

3 鄭緯民;林皎;羅水華;;DNA序列拼接中歐拉超路算法的新并行策略[J];計算機學報;2006年01期

4 謝桂園;魏文國;;并行文件系統(tǒng)的框架設計和性能研究[J];計算機工程;2009年11期

5 解增言;林俊華;譚軍;舒坤賢;;DNA測序技術的發(fā)展歷史與最新進展[J];生物技術通報;2010年08期

相關碩士學位論文 前2條

1 張博鋒;全基因組DNA測序中的片段拼接方法及其并行處理[D];中國人民解放軍國防科學技術大學;2002年

2 方小永;DNA序列拼接的分布式并行處理[D];國防科學技術大學;2003年

，

本文編號：2570753