【摘要】：DNA序列拼接是生物信息學(xué)領(lǐng)域研究的重要課題。隨著高通量、短序列測(cè)序科技的出現(xiàn),測(cè)序覆蓋度進(jìn)一步提高,這給原有的序列拼接技術(shù)帶來了嚴(yán)峻的挑戰(zhàn)。高效的適用于大規(guī)�；蚪M的拼接技術(shù)成為處理DNA測(cè)序數(shù)據(jù)的關(guān)鍵。如何結(jié)合并行計(jì)算技術(shù)從而提高序列拼接處理速度成為本文研究的重要課題。 通過對(duì)已有的基于de Bruijn圖的序列拼接技術(shù)的研究與分析,將序列拼接問題抽象為多步-雙向de Bruijn圖的結(jié)構(gòu)(本文簡(jiǎn)稱為雙向deBruijn圖),建立數(shù)學(xué)模型,并對(duì)其性質(zhì)進(jìn)行推導(dǎo)與論證。根據(jù)該圖的性質(zhì),設(shè)計(jì)基于雙向de Bruijn圖結(jié)構(gòu)的并行序列拼接方法,該方法通過融合半擴(kuò)展單步-雙向邊得到全擴(kuò)展多步-雙向邊集合,即DNA序列拼接過程中contig結(jié)構(gòu)的集合,最終完成序列拼接。 通過對(duì)基于雙向deBruijn圖結(jié)構(gòu)的并行序列拼接方法的每一個(gè)執(zhí)行步驟的確切分析,將該方法劃分為四大功能模塊進(jìn)行實(shí)現(xiàn),主要包括：并行I/O模塊的設(shè)計(jì)與實(shí)現(xiàn)、單步-雙向de Bruijn子圖的構(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(nlog(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.elegans基因組時(shí),其可從10個(gè)CPU擴(kuò)展到640,加速比達(dá)到20倍,具有良好的可擴(kuò)展性。
【學(xué)位授予單位】：中南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：Q523;TP338.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

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

2 遲利華,劉杰,胡慶豐;數(shù)值并行計(jì)算可擴(kuò)展性評(píng)價(jià)與測(cè)試[J];計(jì)算機(jī)研究與發(fā)展;2005年06期

3 鄭緯民;林皎;羅水華;;DNA序列拼接中歐拉超路算法的新并行策略[J];計(jì)算機(jī)學(xué)報(bào);2006年01期

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

，

本文編號(hào)：2570753