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

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

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

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

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