蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)的現(xiàn)實(shí)求解方法——高效啟發(fā)式優(yōu)化算法.pdf

1、蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問題是計(jì)算生物學(xué)領(lǐng)域的核心問題之一，對(duì)其求解是后基因時(shí)代蛋白質(zhì)工程的一項(xiàng)重要任務(wù)。已經(jīng)證明，即使按最簡(jiǎn)化的數(shù)學(xué)模型，所導(dǎo)出的問題仍然是NP難度的。因此，蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問題的研究在當(dāng)今國(guó)際學(xué)術(shù)界是一項(xiàng)具有挑戰(zhàn)性的重大課題。求解NP難度問題的方法主要有三種完整算法、近似算法和啟發(fā)式算法。完整算法雖然能保證給出最優(yōu)解，但由于人們普遍相信P6=NP，指數(shù)級(jí)的計(jì)算復(fù)雜度導(dǎo)致其在實(shí)際應(yīng)用中很難求解較大規(guī)模的問題實(shí)例。近似算法能保證在最

2、壞情況下所得解的精度與最優(yōu)解之間的誤差在一定的范圍內(nèi)，但其實(shí)際計(jì)算效率往往不能令人滿意。另一種方法是啟發(fā)式優(yōu)化算法。啟發(fā)式算法的主要思想來源于生物世界和社會(huì)現(xiàn)象，它往往可以在算法速度和精度之間達(dá)到一種很好的平衡，有可能在較短時(shí)間內(nèi)求解大規(guī)模的問題實(shí)例，并達(dá)到令人滿意的精度。擬物擬人算法是一種借助物理知識(shí)和人類社會(huì)經(jīng)驗(yàn)來求解NP難度問題的啟發(fā)式方法。對(duì)于蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問題，當(dāng)前的研究重點(diǎn)是設(shè)計(jì)求解該問題的高效啟發(fā)式優(yōu)化算法。研究了蛋白質(zhì)結(jié)

3、構(gòu)預(yù)測(cè)問題的兩個(gè)簡(jiǎn)化模型—-HP格點(diǎn)模型和AB非格點(diǎn)模型。HP格點(diǎn)模型中，PERM算法不夠簡(jiǎn)潔，不便于理解。AB非格點(diǎn)模型中，沒有非常貼近問題本質(zhì)的高效求解算法。對(duì)于這兩個(gè)模型，文獻(xiàn)中算法的計(jì)算效率不夠高。對(duì)于HP格點(diǎn)模型，PERM(Pruned-Enrichment Rosenbluth Method)算法是當(dāng)今國(guó)際文獻(xiàn)中最先進(jìn)的求解算法。
　　 本研究在介紹PERM算法的基礎(chǔ)上，對(duì)其給出了一種擬人解釋—-人口控制策略，使該算

4、法變得好想，易于理解，對(duì)算法中的權(quán)重及預(yù)測(cè)值進(jìn)行了改進(jìn)，并對(duì)選擇動(dòng)作時(shí)不同情況下的權(quán)重計(jì)算公式進(jìn)行了統(tǒng)一。綜合這些策略得到了改進(jìn)的PERM算法。在此基礎(chǔ)上提出了進(jìn)一步的擬人改進(jìn)策略。根據(jù)擬人思想對(duì)權(quán)重預(yù)測(cè)公式進(jìn)行了重新定義，擬人改進(jìn)后的PERM算法在鏈生長(zhǎng)過程中不僅考慮氨基酸的類型(H或P)，同時(shí)考慮氨基酸在整個(gè)鏈中的位置。擬人改進(jìn)的PERM算法的計(jì)算結(jié)果可概括為以下三點(diǎn)：第一，算法的計(jì)算速度要優(yōu)于目前國(guó)際文獻(xiàn)中最先進(jìn)的求解算法—-nP

5、ERMis(new PERM importancesampling)，計(jì)算速度是nPERMis的幾倍到幾十倍。第二，對(duì)一個(gè)鏈長(zhǎng)為103的標(biāo)準(zhǔn)問題實(shí)例，擬人改進(jìn)的PERM算法得到的最低能量為-55，該最低能量要優(yōu)于nPERMis算法所得的最低能量-54。第三，對(duì)一個(gè)鏈長(zhǎng)為46的標(biāo)準(zhǔn)問題實(shí)例，擬人改進(jìn)的PERM算法首次得到了最低能量-35，該最低能量要優(yōu)于文獻(xiàn)中所報(bào)道的最低能量-34。對(duì)于AB非格點(diǎn)模型，找到了貼近問題本質(zhì)的物理模型—-彈簧

6、模型。在此基礎(chǔ)上通過將原始約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，提出了求解基于AB非格點(diǎn)模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問題的擬物算法。擬物算法的思想基于所提出的物理模型。擬物算法及其計(jì)算結(jié)果可概括為以下三點(diǎn)：第一，算法提出的擬物思想很好地貼近了問題的本質(zhì)。第二，以HP格點(diǎn)模型為基礎(chǔ)生成初始解，算法所得解的精度要優(yōu)于一種以PERM算法生成初始解的共軛梯度法所得解的精度。第三，以ELP(EnergyLandscape Paving)算法為基礎(chǔ)生成初始解，