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

1、生物信息學(xué)是在生命科學(xué)的研究中，以計(jì)算機(jī)為工具對(duì)生物信息進(jìn)行儲(chǔ)存、檢索和分析的科學(xué)。序列比對(duì)是生物信息學(xué)中一種基本的信息處理方法，對(duì)于發(fā)現(xiàn)核酸和蛋白質(zhì)序列功能、結(jié)構(gòu)和進(jìn)化的信息具有非常重要的意義。隨著生物序列數(shù)據(jù)庫(kù)中序列數(shù)據(jù)的激增，開(kāi)發(fā)兼有高度生物敏感性和高效率的算法就顯得非常迫切。本文研究了生物信息學(xué)中的雙序列比對(duì)算法。 論文敘述了序列比對(duì)算法領(lǐng)域從70年代到現(xiàn)在的發(fā)展過(guò)程，討論了Needleman和Wunsch最早提出的生物

2、序列比對(duì)算法——全局比對(duì)動(dòng)態(tài)規(guī)劃算法，同時(shí)分析了目前雙序列比對(duì)動(dòng)態(tài)規(guī)劃算法及啟發(fā)式算法存在的問(wèn)題。 遺傳算法是模擬自然界生物進(jìn)化過(guò)程來(lái)求解最優(yōu)極值問(wèn)題的一類(lèi)自組織、自適應(yīng)人工智能技術(shù)，它通過(guò)對(duì)當(dāng)前群體施加選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生新一代的群體，并逐漸使群體進(jìn)化到包含或接近最優(yōu)解的狀態(tài)。由于其具有易于實(shí)現(xiàn)、應(yīng)用效果明顯等優(yōu)點(diǎn)而被眾多應(yīng)用領(lǐng)域所接受，在自適應(yīng)控制、組合優(yōu)化、模式識(shí)別、機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域得到了廣泛

3、的應(yīng)用。但許多仿真和應(yīng)用結(jié)果都表明遺傳算法還存在群體易陷入“早熟”現(xiàn)象，局部搜索能力弱等問(wèn)題。模擬退火算法剛好可以補(bǔ)充遺傳算法這一不足，模擬退火算法是模擬物理退火過(guò)程的一種隨機(jī)優(yōu)化搜索算法。算法以?xún)?yōu)化過(guò)程的求解與物理退火過(guò)程的相似性為基礎(chǔ)，通過(guò)接受準(zhǔn)則和對(duì)下降溫度的控制，能夠有效的克服優(yōu)化過(guò)程陷入局部極小從而獲得全局最優(yōu)解。 論文將遺傳算法結(jié)合模擬退火思想用于雙序列比對(duì)問(wèn)題，建立了相應(yīng)的數(shù)學(xué)模型。實(shí)驗(yàn)結(jié)果表明，對(duì)于雙序列比對(duì)問(wèn)題