基于模擬退火算法的兩物種小系統(tǒng)發(fā)育問題算法研究.pdf

1、隨著分子生物學(xué)和高通量基因測序技術(shù)的飛速發(fā)展，大量的DNA序列數(shù)據(jù)已被測定，這為研究基因家族分子進化提供了必要的前提條件。根據(jù)現(xiàn)有生物基因重建基因家族進化史可以推斷出一個可靠的系統(tǒng)發(fā)生，這對揭示有關(guān)基因家族進化過程具有重要意義。重建基因家族進化史不僅有助于我們更好的研究生物進化的進化機制和歷史，而且還可以幫助我們揭示顯性的基因組學(xué)基礎(chǔ)、研究基因的功能。近年來，重建基因家族進化史受到國內(nèi)外眾多學(xué)者的關(guān)注和研究，已經(jīng)成為了比較基因組學(xué)中一個

2、重要的研究方向。
　　本文主要針對兩物種小系統(tǒng)發(fā)育問題進行研究，并基于模擬退火算法提出求解該問題的SA2SP算法和multiSA2SP算法。具體工作如下:針對復(fù)制-丟失比對問題模型，對兩物種小系統(tǒng)發(fā)育問題的算法進行研究，并提出解決該問題的模擬退火算法SA2SP。首先，算法SA2SP包含比對算法ALING，該算法通過對給定的兩條基因序列有針對性的插入一定數(shù)量的字符‘-’，以獲得使兩條基因序列上基因最大匹配的一個序列比對。其次，對于給

3、定的一個序列比對，算法SA2SP包括一種標記算法LABLE，該算法利用復(fù)制-丟失操作序列標記給定的序列比對，其最終問題解為對應(yīng)標記代價最小的比對基因組。算法SA2SP利用ALIGN算法產(chǎn)生問題初始解，利用LABLE算法來衡量解的優(yōu)劣，并在保持鄰域解多樣性的前提下，引入基因塊智能移動、相鄰基因塊位置互換和重新匹配基因塊3種智能鄰域算子，以產(chǎn)生當前解較好的鄰域解，提高算法尋找問題最優(yōu)解的能力。通過對算法SA2SP與算法PBLP用4種菌屬的真

4、實RNA基因數(shù)據(jù)對進化代價與時間性能測試，實驗結(jié)果表明，算法SA2SP能夠獲得較PBLP算法更小的進化代價，且其運行時間在實際應(yīng)用中是可行的，是求解兩物種小系統(tǒng)發(fā)育問題的一種有效方法。
　　進一步，對僅考慮復(fù)制、丟失操作的復(fù)制-丟失比對問題模型進行研究，新添加倒位(Inversion)操作，提出復(fù)制-丟失-倒位比對問題模型，并提出求解該模型下兩物種小系統(tǒng)發(fā)育問題的求解算法multiSA2SP。首先，提出基于動態(tài)規(guī)劃求解最長公共子串

5、問題的比對算法multiALING，通過在兩條基因序列中不匹配位置插入字符‘-’，以得到兩條基因序列的一個序列比對。其次，對于給定的一個序列比對，本文提出一種標記算法multiLABLE，該算法利用復(fù)制-丟失-倒位操作序列標記給定的序列比對，并獲得對應(yīng)標記進化代價較小的操作序列。論文基于提出的multiALING算法和multiLABLE算法，設(shè)計了一種求解復(fù)制-丟失-倒位演化模型下兩物種小系統(tǒng)發(fā)育問題的模擬退火算法multiSA2SP

6、。算法multiSA2SP通過multiALIGN產(chǎn)生初始解，利用multiLABLE來衡量產(chǎn)生鄰域解的優(yōu)劣，根據(jù)鄰域解進化代價作為是否替換當前解為新解的重要依據(jù)。同時還引入基因塊智能移動、相鄰基因塊位置互換、重新匹配基因塊和倒位基因塊智能組合4種智能鄰域算子，以產(chǎn)生當前解較好的鄰域解，提高算法尋找問題最優(yōu)解的能力。算法multiSA2SP在僅考慮復(fù)制、丟失操作的前提下，利用4種真實菌屬的RNA基因數(shù)據(jù)對算法進化代價和運行時間性能進行測

7、試，實驗結(jié)果表明，算法multiSA2SP在僅考慮考慮復(fù)制、丟失操作的情況下，能夠獲得較PBLP算法更小的進化代價，是求解復(fù)制-丟失-倒位模型下兩物種小系統(tǒng)發(fā)育問題的一種有效方法。
　　綜上所述，針對兩物種小系統(tǒng)發(fā)育問題，本文提出了求解復(fù)制-丟失比對問題模型下該問題的模擬退火算法SA2SP，并獲得了較好的優(yōu)化效果。此外，本文對復(fù)制-丟失比對問題模型進行擴展，不僅提出了復(fù)制-丟失-倒位比對問題模型，而且還提出了求解該問題的模擬退火算