基于MapReduce的DNA序列拼接算法研究.pdf

1、生物信息學是集生物、數(shù)學和計算機等領(lǐng)域的綜合學科，主要研究內(nèi)容是生物信息的處理。生物信息學通過研究生物數(shù)據(jù)中蘊藏的生物學意義來揭示其對生物體活動的影響。生物體基因組控制著生物體遺傳、成長、衰老等生命過程，因此基因組測序是生物信息學中的重要課題之一。但是限于現(xiàn)有測序設(shè)備，大部分生物體的基因組無法直接測出，普遍使用的是鳥槍法測序。
　　鳥槍法測序中最重要的過程是序列拼接。目前，序列拼接算法主要分為基于Hamilton路徑和基于歐拉(E

2、uler)超路兩種。基于Hamilton路徑的算法利用的是“overlap-layout-consensus”方法，這種方法時間復雜度較高，且并沒有很好克服重復序列的影響?；跉W拉超路的DNA序列拼接算法的提出，給出了DNA序列拼接的一種全新方法，克服了傳統(tǒng)“overlap-layout-consensus”方法在拼接工作中的不足。但歐拉超路算法在拼接過程中需要生成de Bruijin圖，對于序列較大的拼接工作，該圖所維護的數(shù)據(jù)量十分龐

3、大，這使存儲和效率成為瓶頸問題。
　　目前已經(jīng)有基于MapReduce的拼接算法提出，但是基于seed-and-extend技術(shù)，需要參照序列。2011年，也有了一些利用MapReduce解決de Bruijin圖的探討，但大都要進行圖的劃分，且這一思路也僅限探討，沒有任何軟件的發(fā)布。
　　本文在研究歐拉超路算法的基礎(chǔ)上，尋求一種基于MapReduce且避免圖劃分的并行策略，并在集群上進行實現(xiàn)。實驗結(jié)果表明，使用并行策略，很