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

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

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

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

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