并行蟻群算法求解DNA雜交測序問題的研究.pdf

1、DNA測序是分子生物學(xué)進一步研究的基礎(chǔ)，但測序是一項艱巨的工作，因為直接使用顯微鏡讀取DNA序列是不可行的，而間接的測序方法即使非常嚴(yán)密也避免不了錯誤的產(chǎn)生。DNA雜交測序(Sequencing by Hybridization，SBH)是目前使用最多的測序方法，該方法分為雜交實驗和序列重構(gòu)兩個步驟。其中雜交實驗產(chǎn)生的錯誤使得序列的重構(gòu)更加困難，已經(jīng)證明含有錯誤的序列重構(gòu)問題是NP-hard問題。在實際研究當(dāng)中，生物學(xué)工作者面對的是含有

2、數(shù)萬個堿基的DNA序列，因此，如何使得重構(gòu)的序列更加精確，耗費時間更少，是本課題的目的與意義所在。
　　 國內(nèi)外現(xiàn)有的求解DNA雜交測序問題的算法大致分為兩類：精確算法和啟發(fā)式搜索方法。精確算法有分支定界算法，動態(tài)規(guī)劃方法等；啟發(fā)式搜索方法有禁忌搜索算法，遺傳算法，蟻群算法，模擬退火算法等。比較之下，啟發(fā)式搜索方法得到的解更優(yōu)，但隨著數(shù)據(jù)規(guī)模的增大，算法的性能隨之下降。因此，進一步的研究工作是提高解的精度和收斂速度。
　　

3、 蟻群算法是在螞蟻群體覓食過程中沿最短路徑行進的生物學(xué)行為之上發(fā)展起來的一類群集智能優(yōu)化方法，吸引了眾多學(xué)者的注意。經(jīng)過近20年的研究與實踐，蟻群算法已顯示出它在求解復(fù)雜優(yōu)化問題的優(yōu)勢。它具有強大的全局尋優(yōu)能力，較強的魯棒性和適應(yīng)性，且易于與其他算法融合，除此之外，蟻群算法固有的并行性非常適用于大規(guī)模并行計算，因此它已在組合優(yōu)化和并行處理等領(lǐng)域得到了越來越廣泛的應(yīng)用。
　　 首先，本文對并行計算、蟻群算法和并行蟻群算法的發(fā)展和

4、特點進行綜述，并介紹并行處理的硬件系統(tǒng)及支撐軟件，其中主要敘述PC機群及該平臺上采用的編程環(huán)境MPI(Message Passing Interface)。其次，將DNA序列重構(gòu)問題與圖論相結(jié)合，轉(zhuǎn)化為一種特殊的哈密爾頓路徑問題，并作形式化描述。再次，對最大最小蟻群算法做兩方面改進，一是分別采用了雙向構(gòu)造解路徑，二是利用不同階段的最優(yōu)解更新信息素；同時根據(jù)主從式并行程序的設(shè)計思想提出了一種新的信息交換策略——排序交叉信息交換策略。最后，