基于遺傳退火的生物信息學(xué)多序列比對算法研究.pdf

1、隨著人類基因組計劃(HGP)等項目的實施，生物學(xué)及相關(guān)數(shù)據(jù)的積累速度呈爆炸性增長，生物信息學(xué)這個融合了生命科學(xué)、信息科學(xué)等眾多相關(guān)學(xué)科的邊緣學(xué)科，為“海量”生物信息的處理提供了新的方法。序列比對是生物信息學(xué)中序列分析的基本操作，它對于發(fā)現(xiàn)生物序列中的功能、結(jié)構(gòu)和進(jìn)化信息具有非常重要的意義。目前雙序列比對算法已趨于完善，相比之下，現(xiàn)有實用的多序列比對方法還不能保證一定給出最優(yōu)的比對結(jié)果，而是只能給出一個近似值。如何開發(fā)出準(zhǔn)確和高效的多序列

2、比對程序是目前序列比對的一個難點。本文主要研究當(dāng)前多序列比對發(fā)展現(xiàn)狀，設(shè)計并實現(xiàn)了一種將組合優(yōu)化中遺傳算法和模擬退火算法運用到多序列比對中的方法。 本文首先分析了序列比對中相似性記分矩陣、空位罰分和目標(biāo)函數(shù)對比對結(jié)果的影響，并具體實現(xiàn)了兩種廣泛應(yīng)用的目標(biāo)函數(shù)：SP函數(shù)和COFFEE函數(shù)。然后深入研究了當(dāng)前流行的比對算法，并系統(tǒng)地論述了雙序列比對中經(jīng)典的全局比對Needleman—Wunsch算法和局部比對Smith—Waterm

3、an算法；討論了多序列比對的精確算法——動態(tài)規(guī)劃法，分析了該算法呈指數(shù)增長的算法復(fù)雜性，進(jìn)而引入了當(dāng)前流行的漸進(jìn)比對算法和迭代比對算法，并闡述了經(jīng)典漸進(jìn)比對軟件CLUSTAL的算法機制。 在此基礎(chǔ)上本文引入遺傳算法。遺傳算法是一種模擬自然界生物進(jìn)化過程的人工智能技術(shù)，通過選擇、交叉、變異等遺傳操作迭代更新種群，從而產(chǎn)生適應(yīng)度更高的個體。本文對多序列比對問題建立遺傳算法模型，實現(xiàn)了MSA—GA算法，設(shè)計出了適合多序列比對的二維染色

4、體編碼策略和三種遺傳算子，以SP目標(biāo)函數(shù)實現(xiàn)了MSA—GA算法，并在BAliBASE3.0比對庫中與經(jīng)典的CLUSTAL算法比較測試。從研究表明MSA—GA算法的比對結(jié)果比較滿意，但與CLUSTAL相比還存在差距。 此后研究了MSA—GA算法不足之處，深入闡述了遺傳算法中普遍存在的“早熟”現(xiàn)象。傳統(tǒng)的遺傳操作在不斷迭代中強化了某些個體的優(yōu)勢，使得搜索范圍迅速變窄，令算法最終收斂于一個局部最優(yōu)解。為了尋求更高效的多序列比對算法，本

5、文將模擬退火算法引入到傳統(tǒng)的遺傳算法中，設(shè)計并實現(xiàn)了MSA—GSA算法。模擬退火算法模擬了固體退火過程，運用接受準(zhǔn)則和對下降溫度的控制跳出局部極值的陷阱，并確保搜索的全局優(yōu)化性。主要的工作是設(shè)計并實現(xiàn)了將退火操作加入到遺傳算法的三種主要操作選擇、交叉和變異中，在種群更新階段，通過Metropolis接受準(zhǔn)則調(diào)整遺傳算法的進(jìn)化過程，保證了種群多樣性，并在迭代后期加快了收斂速度，克服“早熟”現(xiàn)象，得到全局最優(yōu)解。在適應(yīng)度函數(shù)方面，以COFF