并行遺傳算法在DNA雜交測序中的應(yīng)用研究.pdf

1、由基因序列解開一切生命的奧秘是生物信息學(xué)的研究目標，而DNA測序是了解基因結(jié)構(gòu)與功能的基礎(chǔ)，是生物信息學(xué)研究的起點。人類基因組計劃的啟動推進了生物信息學(xué)的飛速發(fā)展。2008年7月2日，美國能源部聯(lián)合基因組研究所宣稱其群體測序項目將在2009年支持DNA測序計劃。上述表明，生物基因組序列的快速測序一直是一種迫切的需求。
　　 雜交測序是目前使用最廣的一種測序方法，它分為雜交實驗和序列重構(gòu)兩個步驟。雜交實驗由于技術(shù)和條件的限制往往出

2、現(xiàn)兩類錯誤，由此得到的非理想譜集就給序列重構(gòu)帶來了極大的困難。已經(jīng)證明含有錯誤的序列重構(gòu)問題是NP-hard問題。
　　 國內(nèi)外已有許多關(guān)于雜交問題的研究文獻。求解雜交測序問題主要有精確算法(分支定界算法，動態(tài)規(guī)劃方法等)和啟發(fā)式搜索方法(禁忌搜索算法，遺傳算法，蟻群算法，模擬退火算法等)兩類。比較之下，精確算法只在序列長度較小時適用，而啟發(fā)式搜索方法因不依賴于問題空間得到了更多的應(yīng)用。
　　 遺傳算法是基于達爾文生物進

3、化論的自然選擇學(xué)說和群體遺傳學(xué)原理而開發(fā)出的一種隨機全局搜索與優(yōu)化的自適應(yīng)智能算法。遺傳算法不受搜索空間的限制性假設(shè)的約束。已驗證在求解含有錯誤的DNA測序問題上優(yōu)于其他算法。由于遺傳算法固有的并行性非常適用于大規(guī)模并行計算，所以并行遺傳算法往往能提高運算速度，改善求解性能。
　　 基于以上所述，本文的意圖在于改進現(xiàn)有的并行遺傳算法，將其應(yīng)用到DNA雜交測序問題中，使得重構(gòu)的DNA序列更加精確，花費的時間更少。本文首先對問題建模

4、，利用現(xiàn)有的求解該問題的遺傳算法模型，確定進化策略；然后改進并行遺傳算法，對模型進行優(yōu)化求解；最后搭建機群環(huán)境，并對計算結(jié)果進行分析討論。本文的核心在于并行遺傳算法框架的選擇和遷移操作的改進兩方面。本文分析了四種并行模型的通信方式，結(jié)合DNA雜交測序問題，選擇使用粗粒度-主從式雙層并行框架；分析了遷移操作對并行框架的影響，提出一種新的遷移策略。通過實驗驗證，新的遷移策略有效地減少了通信開銷。
　　 本文的分析研究為使用并行遺傳算