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

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

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

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

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

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

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

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