基于混合化學反應優(yōu)化算法的序列比對研究.pdf

1、序列比對是生物信息學研究中一種基本的信息處理方法，對序列分析、序列結構功能的預測以及進化樹的構建具有極為重要的意義。無論是雙序列比對還是多序列比對，都可以看成是數(shù)學上的優(yōu)化問題。隨著生物分子序列數(shù)據(jù)的急速增長，找到整體上最優(yōu)比對的難度也隨之增加，對于這類優(yōu)化問題研究者們致力于用啟發(fā)式算法來找到問題的近似最好解，如遺傳算法，蟻群算法等。而化學反應優(yōu)化(Chemical Reaction Optimization)是一種新的啟發(fā)式算法，通過

2、模擬化學反應中分子運動過程來搜索最優(yōu)解，并且CRO已經(jīng)成功解決一些經(jīng)典的優(yōu)化問題，因此本文首次運用CRO來完成序列比對。本文的研究是運用化學反應優(yōu)化方法來解決雙序列比對問題的一次有益嘗試，以期為序列分析領域提供全新的序列比對工具，為以后解決多序列比對問題提供平臺，也可加以并行處理技術對其進行加速，以加強其處理大規(guī)模序列比對問題的能力。
　　首先對序列比對的概念及相關知識點進行了介紹，并對現(xiàn)有經(jīng)典的雙序列比對算法進行詳細地闡述與比較

3、。針對雙序列比對問題的數(shù)學模型，在CRO的算法框架上，提出了一種新的雙序列比對算法HCRO-PSA(Hybrid Chemical Reaction Optimization for Pairwise Sequence Alignment)。CRO模擬化學反應中分子運動中能量的變化而得到的一種元啟發(fā)式方法，通過四個基本操作:撞墻、分解、分子間無損碰撞以及合成來完成對解空間的搜索，其中撞墻和分子間無損碰撞可以進行局部最優(yōu)值搜索，而分解和合

4、成是用來拓展搜索領域，從而盡可能獲得全局最優(yōu)值，最后找到系統(tǒng)中勢能值最低的分子結構。由于CRO在迭代過程中只記錄下當前質量好的分子，這樣使得搜索會陷于局部最優(yōu)解，為了更好的獲得全局最優(yōu)解本文在CRO框架上引入退火操作將Metropolis接受準則，提出解決雙序列比對的混合式CRO算法。HCRO-PSA算法針對雙序列比對的實際問題結合啟發(fā)思想完整地設計了CRO的具體操作，為加快算法處理序列比對的速度，設計了一種并行CRO模型。