基于MapReduce的基因組組裝算法改進

何　遠，張麗娜，朱興文

（大理大學數學與計算機學院，云南大理　671003）

基于MapReduce的基因組組裝算法改進

何遠，張麗娜，朱興文

（大理大學數學與計算機學院，云南大理671003）

生物信息數據的飛速增長需要新的技術引入到該學科，目前的基因組組裝算法還存在著精度不高、并行化不足等缺點。對目前組裝算法的分析后，提出了基于MapReduce的組裝算法，通過統計去除組裝過程中的錯誤數據，通過增加k-mer的長度消除組裝過程中的重復數據，最后在MapReduce平臺實現了并行組裝算法，實驗結果表明算法提高了組裝的準確度和計算速度。

基因組組裝；高通量測序；de Bruijn；MapReduce

［DOI］10. 3969 / j. issn. 2096-2266. 2016. 06. 002

生物信息學是多理論交叉的學科，它綜合了計算機科學、信息技術、數學理論、統計方法等。近些年來生物數據呈指數增長，傳統的分析方法已無法滿足海量數據分析的要求，因此迫切需要把云計算、數據挖掘等新的計算技術應用到生物信息學領域中來〔1-2〕。基因組組裝（Genome Assembly）是基因組學研究的重要內容之一，其目的是通過測序獲取所研究有機體的全序列，從而實現在分子層面對有機體進行分析研究。

測序技術一般分為三代，第一代DNA測序技術〔3〕主要是指以化學降解法和雙脫氧鏈終止法為基礎的測序技術。第二代測序技術〔4〕實現高通量，大規模測序，被廣泛使用。第三代測序技術〔5〕正在研究和發展的過程中，主要特點是單分子測序，最具代表性的就是Helicos公司研發的單分子測序儀和Oxford Nanopore Technologies公司正在研發的納米單分子技術。

第三代測序技術正在研究和發展，第二代測序技術廣泛應用的情況下，將云計算等新興技術應用于生物信息學領域具有很重要的現實意義。

1　序列拼接問題研究現狀

DNA測序過程大致如下〔6〕：給定一個DNA分子，將其復制n份，然后將n份DNA分子打碎，得到若干小的DNA片段。接著進行過濾，受到測序儀讀取片段長度的限制，較短的片段和較長的片段被丟棄掉，這可能導致原DNA分子中有一部分區域不能被讀取到，也就是說測序儀讀出的序列不能完全覆蓋原有的DNA分子，但只要n足夠大，就可以保證原DNA分子完全被那些小片段覆蓋。最后，那些留下的片段被測序儀讀出，讀出的DNA片段稱為read。由所有read拼接成原DNA分子的過程稱為基因組組裝。

打碎DNA分子的過程是隨機的，使得DNA片段在分子中的位置不可知，組裝的過程就是重現DNA分子原有順序的過程。組裝過程中主要有序列錯誤、缺少足夠的覆蓋、重復片段等問題，重復片段是拼接過程中最棘手的問題。原因是在測序時（為保證覆蓋）進行過DNA序列復制，因此無法判斷它們是來自DNA序列的同一位置，還是來自不同位置的重復內容。

目前的研究主要以denove拼接為主〔7-8〕，這類算法主要包括貪心算法、Hamilton路徑算法和歐拉超路算法。Hamilton路徑算法沒有克服重復序列的問題。歐拉超路算法由于對read進行了進一步的拆分，一定程度上克服了重復序列問題。

歐拉超路算法主要基于de Bruijn圖進行拼接。但目前該算法主要是單機運算，運算速度受到限制，同時單機模式不利于完成后續的一系列信息處理。近年來云計算有了較大的發展，MapReduce技術具有計算速度更快、運算數據量更大、運算可靠性更高的特點。

通過MapReduce技術對現有組裝方法改進，不僅在一定程度上克服了基因組中的重復片段造成的問題，而且利用MapReduce技術使得組裝速度得到提高。

2　基因組裝算法缺陷分析

序列拼接過程中的基本問題主要有：序列誤差、缺少足夠的覆蓋、重復片段等，由測序過程可知，缺少足夠的覆蓋可以通過多次復制解決，序列錯誤往往由于實驗數據錯誤造成，重復片段問題主要是無法區分重復片段是由于復制過程造成的，還是由于基因組自身的序列重復而造成。

考慮如下兩個read〔9〕：

ATCTTATTCG

ATCTAATTCG

這兩個read除了第5個位置的堿基不同外，其他部分堿基完全相同，取k-mer長度為4，其de Bruijn圖如圖1所示。

圖1　Bubble分支結構

圖1中的Bubble分支結構，主要由1位堿基錯誤造成，本來屬于重復片段（為保證覆蓋多次復制而造成），由于復制過程中有1組分子的1位堿基發生錯誤，使得算法誤認為是新數據，從而干擾了拼接算法。

考慮下面的基因片段：

AAGACTCGACTG

取k-mer長度為4，得到的deBruijn圖如圖2所示。

圖2　由repeat引起的分支結構

圖2中由repeat引起的分支結構，其重復來自于堿基序列自身的重復，導致k-mer重復，歐拉超路算法具有一定消除重復的能力，但對repeat分支結構遍歷時，將會造成拼接精度降低。圖2所示的例子中，可以得到AAGACTCGACTG，或者AAGACTG，使得正確率降低。

對圖2的分支結構分析后可知，其k-mer重復的原因是其長度太小（長度值為4），如果長度為5就不會出現k-mer重復。所以需要對算法進行改進。

3　MapReduce組裝算法

從上述分析可知，Bubble分支結構往往由于復制過程引入單個堿基錯誤造成，repeat引起的分支結構往往由堿基序列自身重復引起，而堿基序列自身重復主要由所考慮的堿基數目過小造成，所以解決上述問題從以下兩方面入手。

首先，對k-mer長度進行修改，其長度增加意味著重復的概率將減小，例如長度為4，則k-mer重復的概率為1/44，很容易出現重復，所以直接改為測序儀可讀的最小read的堿基數，例如Solexa測序儀read長度為25～35 bp〔4〕，則直接取25為k-mer長度。則k-mer重復的概率變為1/425。

其次，由測序過程可知，不考慮堿序列自身的重復，則重復主要由復制造成，為了保證覆蓋率一般復制n次，所以完成k-mer劃分后，每個k-mer的數目是1-n，由概率知識可知，復制n次后，堿基片段的數目為1的概率較低，所以當k-mer數目為1時，組裝過程不考慮該k-mer。但為了保證覆蓋率，增加組裝的準確性，如果序列出現斷裂（無法完成拼接）時，使用k-mer數目為1的序列參與拼接，使其覆蓋整個序列。

最后，通過MapReduce完成拼接過程的并行化，MapReduce是一種簡化的分布式編程模型，核心思想是將要執行的問題分解成Map（映射）和Reduce（化簡）的方式，先通過Map程序將數據切割成不相關的區塊，分配（調度）給大量計算機處理，達到分布式運算的效果，再通過Reduce程序將結果匯總整理后輸出。

整個拼接過程使用MapReduce改進后，具體流程如圖3所示。

圖3　MapReduce組裝算法流程

1）將所有read進行初始化處理，read長度的最小值作為k-mer的長度，例如取25，對大于最小值的read劃分為長度為最小值的k-mer，把所有k-mer平均分布到各個節點。

2）通過MapReduce并行計算，統計出k-mer的數目，統計結果大于1的數據作為下一步的輸入數據，結果為1的數據保存為k-mer-num，指導后續斷裂拼接。具體如圖4所示。

圖4　MapReduce統計k-mer原理圖

3）對統計大于1的數據作為原始數據輸入，對其進行編號，然后平均分派到各個節點，在Map過程中參照所有數據進行拼接，在每個節點中查找對應的后繼節點。對k-mer進行de Bruijn圖的遍歷，算法如圖5所示。頭尾節點需特殊處理，圖5中節點1為頭節點，節點6為尾節點。

圖5　MapReduce拼接流程圖

4）對遍歷過程中出現的斷裂，通過“2）”的統計結果進行指導。如無斷裂直接完成拼接。

5）最后輸出對應的完整基因組序列。

4　實驗及結果分析

實驗平臺主要由3個同配置節點利用Hadoop框架搭建的集群，每個節點擁有4 GB內存，Intel Q9400雙核CPU，裝載Ubuntu 12.04 LTS 64 bits系統，各節點間通過局域網互聯。

4.1正確率檢驗BioLign〔10〕是一個針對生物信息處理的綜合性軟件，其中一項功能就是序列拼接，該軟件的序列拼接功能采用歐拉超路算法。實驗數據來自NCBI（網址是http：//www.ncbi.nlm.nih.gov）的短根瘤菌（FJ555236.1）數據，其長度為1 987 bp。

為化簡實驗過程，使用下載的數據對測序過程進行模擬。下載數據后，復制6次數據，使用隨機函數對6組數據隨機打斷，丟棄小于25 bp和大于35 bp的數據，剩下的數據形成模擬基因組數據。得到模擬數據后分別使用BioLign組裝方法與MapReduce算法進行組裝。對組裝結果和原基因序列對比，完成正確率的比較。對測序過程發生的堿基錯誤，通過對6組數據中的1組數據進行堿基錯誤模擬，然后再次組裝，實驗結果如表1所示。

表1　BioLign與MapReduce算法準確率比較

從結果可知，MapReduce組裝方法因為去除了重復數據的影響，準確率較高。實驗在理想條件下，準確率達到100%。增加k-mer的長度導致重復概率很低，以實驗數據為例，其重復概率為（1987-24）/425，幾乎不用考慮k-mer重復問題，當堿基數量較大時，如人類基因組達30億bp，重復概率為（3×109-24）/425，約為1/219，從理論推導可知準確率仍達到0.999以上。

6組數據只對其中1組數據進行堿基錯誤模擬后能正常拼接，但拼接速度下降。因為其他5組數據的準確性不受影響，所以除了速度降低外，準確率沒有下降。但BioLign組裝方法因為處理Bubble分支結構和repeat引起的分支結構，其準確率有所下降，準確率主要取決于所采用的策略。

4.2拼接速度檢驗對單機與MapReduce組裝方法的運行速度進行實驗，實驗對數據初始化、統計k-mer部分的操作時間等統一沒有計算。實驗仍以模擬基因組數據進行；對測序過程發生的堿基錯誤，仍通過對6組數據中的1組數據進行堿基錯誤模擬，獲得數據后分別進行組裝，實驗結果如表2所示。

表2　單機與MapReduce組裝方法速度比較結果

從結果可看出MapReduce組裝方法的速度接近單機的3倍，對錯誤數據處理，因為需要滿足覆蓋率的要求，對斷裂部分特殊處理，增加了運行時間，但速度仍接近3倍。當數據錯誤率增加時，MapReduce組裝方法的耗時會增加。同時，在拼接過程中，可能會因為節點數據的差異造成負載不均衡問題而導致拼接速度的下降。

5　結束語

MapReduce算法具有更高的準確性，更快的拼接速度。但對此方法仍有一定不足，如實驗過程使用了理想化數據。組裝過程需要對數據進行預處理，中間需要通過統計結果指導斷裂處的拼接，如果斷裂較多會造成多次拼接操作，會嚴重影響拼接速度。此外需要對頭尾節點進行特殊處理等工作消耗的時間也不少，如何更高效的提高精度和速度需要進一步研究。

〔1〕楊帥，胡宗倩，伯曉晨，等.云計算在生物醫學中的應用〔J〕.中國科學，2013，43（7）：569-578.

〔2〕SCHADT E E，LINDERMAN M D，SORENSON J，et al. Computational solutions to large-scale data management and analysis〔J〕.Nat Rev Genet，2010，11（11）：647-657.

〔3〕MAXAM A M，GILBERT W.A new method for sequencing DNA〔J〕.Proc Natl Acad Sci USA，1977，74（3）：560-564.

〔4〕MILNE I，BAYER M，CARDIE L，et al.Tablet-next generation sequence assembly visualization〔J〕.Bioinformations，2010，26（3）：401-402.

〔5〕CLARKE J，WU H C，JAYASINGHE L，et al.Continuous base identification for single-molecule nanopore DNA sequencing〔J〕.Nat Nanotechnol，2009，4（4）：265-270.

〔6〕王旭.基于de Brujin圖的DNA Contig生成算法〔D〕.哈爾濱：哈爾濱工業大學，2011：6.

〔7〕孫曉斐.基因組序列 de novo拼接系統的設計與實現〔D〕.哈爾濱：哈爾濱工業大學，2014：5.

〔8〕王小艷.基于De Bruijn圖的基因拼接算法研究〔D〕.武漢：武漢理工大學，2014：5.

〔9〕王東陽，任世軍，王亞東.DNA序列拼接中de Bruijn圖結構的研究〔J〕.智能計算機與應用，2011，8（4）：20-27.

〔10〕FERRARINI M，MORETTO M，WARD J A，et al.An evaluation of the PacBio RS platform for sequencing and de novo assembly of a chloroplast genome〔J〕.BMC Genom，2013，14（1）：670-671.

〔Abstract〕The rapid increase of biological information data requires the import of new technology.At present，the genome assembly algorithm is neither precised nor parallelize.A new algorithm based on MapReduce is proposed after analysis of the current assembly algorithm.The error data is removed through statistics way，and the duplicate data is eliminated by increasing the length of the k-mer in the process of assembly.Finally，the parallel assembly algorithm is realized in MapReduce platform.The experimental results show that the accuracy and speed of this algorithm are improved.

〔Key words〕genome assembly；high throughput sequencing；de Bruijn；MapReduce

（責任編輯袁霞）

Improvement of Genome Assembly Algorithm Based on MapReduce

He Yuan，Zhang Lina，Zhu Xingwen
（College of Mathematics and Computer，Dali University，Dali，Yunnan 671003，China）

TP309.2：TP399

A

2096-2266（2016）06-0004-04

大理大學青年教師科研基金資助項目（KYQN201218）

2016-01-25

2016-03-02

何遠，實驗師，主要從事計算機科學研究.