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

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

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

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

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

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

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