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

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

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

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

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

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