基于DeBruijn圖的基因拼接算法研究.pdf

1、隨著基因測(cè)序在工業(yè)中的廣泛應(yīng)用以及以高通量、短序列、覆蓋度高、測(cè)序引入錯(cuò)誤等為特點(diǎn)的第二代基因測(cè)序儀的大量使用，需要進(jìn)行處理的基因組測(cè)序數(shù)據(jù)常常長(zhǎng)達(dá)數(shù)十億堿基對(duì)，現(xiàn)有的全基因組DNA序列拼接技術(shù)通常不能勝任拼接工作。人們對(duì)序列拼接技術(shù)這一生物信息學(xué)領(lǐng)域最重要的研究課題進(jìn)行廣泛而深入地研究，以實(shí)現(xiàn)海量基因組序列拼接。當(dāng)前，基因測(cè)序技術(shù)主要是基于圖論的算法，其中最常用的是基于De Bruijn圖的拼接算法。針對(duì)海量的基因測(cè)序數(shù)據(jù)，構(gòu)建分布式

2、的De Bruijn圖，實(shí)現(xiàn)基因拼接的并行化，可以有效的解決因數(shù)據(jù)量大而造成計(jì)算過程中內(nèi)存資源不足的問題，也能合理提高拼接速度，縮短測(cè)序的時(shí)間周期，降低測(cè)序成本，優(yōu)化拼接質(zhì)量，以應(yīng)對(duì)大規(guī)模應(yīng)用的要求。因此，基于De Bruijn圖，針對(duì)大規(guī)模基因數(shù)據(jù)序列拼接的并行化研究具有重大的理論和實(shí)踐意義，同時(shí)也是研究的熱點(diǎn)。
　　本文以生物的基因序列數(shù)據(jù)為研究對(duì)象，提出了采用圖論的方法和并行計(jì)算技術(shù)，研究基于De Bruijn圖的快速、高效

3、和可擴(kuò)展的并行基因序列拼接算法。
　　作者的主要研究工作如下：
　　（1）闡述了應(yīng)用于基因測(cè)序技術(shù)中的基本計(jì)算模型（OLC圖模型和 De Bruijn圖模型）的一些基本概念與相關(guān)算法，其中重點(diǎn)研究了具有參考對(duì)比價(jià)值的YAGA算法。
　?。?）本文提出了一種加速效率顯著、擴(kuò)展性能良好的并行拼接算法實(shí)現(xiàn)De Bruijn圖拼接。在構(gòu)圖方面，改進(jìn)YAGA圖形的存儲(chǔ)模式，使用更少的存儲(chǔ)空間。在圖化簡(jiǎn)上，借鑒velvet對(duì)tip

4、結(jié)構(gòu)的處理原則，去除長(zhǎng)度小于2k的鏈。運(yùn)用深度優(yōu)先搜索算法遍歷圖形，大量減少處理器之間的通信以及計(jì)算節(jié)點(diǎn)的移動(dòng)，降低拼接過程中時(shí)間、空間消耗。在頂點(diǎn)數(shù)據(jù)處理方面，依據(jù)頻度原則，去除閾值以下的頂點(diǎn)，減少了圖中頂點(diǎn)的數(shù)量，降低了測(cè)序錯(cuò)誤帶來的錯(cuò)拼問題，優(yōu)化了拼接結(jié)果。
　?。?）在算法性能測(cè)試階段，采用四組不同規(guī)模的生物基因數(shù)據(jù)從執(zhí)行時(shí)間、加速效率和可擴(kuò)展性等方面對(duì)算法各個(gè)模塊以及整體性能進(jìn)行測(cè)試與驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，本文的拼接算法加