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

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

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

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