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

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

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

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