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

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

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

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

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