朱均燕，溫永仙

(福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院，福建福州350002)

蛋白質(zhì)是一種生物大分子，是由20種氨基酸以肽鍵連接成的肽鏈［1］.蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)對(duì)于探索蛋白質(zhì)空間結(jié)構(gòu)與功能的關(guān)系，以及進(jìn)行蛋白質(zhì)結(jié)構(gòu)設(shè)計(jì)、突變體設(shè)計(jì)等具有重要意義.蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)是指直接從氨基酸序列推斷某一蛋白質(zhì)的功能位點(diǎn)或?qū)ζ淙S結(jié)構(gòu)進(jìn)行預(yù)測(cè)(包括二級(jí)和三級(jí)結(jié)構(gòu))，是目前分子生物學(xué)研究中迫切需要解決的問(wèn)題［2］.蛋白質(zhì)二級(jí)結(jié)構(gòu)預(yù)測(cè)不僅是聯(lián)系蛋白質(zhì)一級(jí)結(jié)構(gòu)和三級(jí)結(jié)構(gòu)的紐帶，還是從一級(jí)結(jié)構(gòu)預(yù)測(cè)其三級(jí)結(jié)構(gòu)的關(guān)鍵步驟［3］.

迄今為止，對(duì)蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問(wèn)題已提出了一些簡(jiǎn)化模型.目前有2種典型的蛋白質(zhì)折疊的簡(jiǎn)化模型，一種是由Dill et al提出的HP格點(diǎn)模型(HP lattice model)［4，5］，但該模型僅考慮了蛋白質(zhì)殘基之間的疏水性，忽略了殘基之間的親水性，且相鄰殘基之間的夾角只能是直角或平角;另一種是由Stillinger et al提出的Toy模型(AB off-lattice model)［6］，該模型同時(shí)考慮了蛋白質(zhì)殘基之間的疏水性和親水性，而且相鄰殘基之間的夾角可是任意的.研究［7］表明，Toy模型比HP模型更接近真實(shí)蛋白質(zhì)，由此，本文選用Toy模型作為蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)的研究對(duì)象.

1995年Stillinger對(duì)Toy模型所體現(xiàn)出來(lái)的蛋白質(zhì)折疊的共有特點(diǎn)進(jìn)行了研究，并提出了用于Toy模型的2種氨基酸序列，即Center-doped序列和Fibonacci序列［8］.由于Center-doped序列考慮的情況比較特殊，主鏈上的氨基酸序列必須是對(duì)稱的，這與多數(shù)天然蛋白質(zhì)序列結(jié)構(gòu)不符，所以本文選用Fibonacci序列.

1 改進(jìn)的模擬退火算法

模擬退火算法最初的思想是Metropolis在1953年提出的，Kirkpatrick于1983年將其成功地應(yīng)用在組合最優(yōu)化問(wèn)題中［9］.其主要特點(diǎn)是在搜索的過(guò)程中，不僅接受優(yōu)化解，也以一定的概率接受惡化解，這樣就容易陷入局部最優(yōu)解.文獻(xiàn)［10］針對(duì)蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)模型中目標(biāo)函數(shù)的多極值多變量的特點(diǎn)，給出了一種新解的產(chǎn)生方法，本文對(duì)這一算法進(jìn)行了改進(jìn).

1.1 新解邊界值處理

在蛋白質(zhì)Toy二維模型中，通過(guò)找到最佳的折疊角度獲得最小能量值，針對(duì)這一問(wèn)題，本文在模擬退火算法中對(duì)于產(chǎn)生新解邊界值的處理給出一種新方法.對(duì)于產(chǎn)生的一個(gè)新解X中的任意一個(gè)分量xr，按如下規(guī)則進(jìn)行邊界處理:

經(jīng)式(1)處理后，新解的任意一個(gè)分量的值都在規(guī)定的范圍內(nèi)，且分量值符號(hào)保持不變.

1.2 初始溫度的選擇

在模擬退火算法中，溫度是一個(gè)比較關(guān)鍵的參數(shù).如果初始溫度不夠高或者退火時(shí)間不夠長(zhǎng)會(huì)使得搜索過(guò)快，從而導(dǎo)致算法陷入局部最優(yōu)解;但是如果初始溫度過(guò)高或者退火時(shí)間過(guò)長(zhǎng)，則會(huì)造成因算法的運(yùn)行時(shí)間過(guò)長(zhǎng).溫度參數(shù)的設(shè)定將影響到模擬退火算法是否能收斂到全局最優(yōu)解.

雖然模擬退火算法的求解不依賴于初始值，但初始溫度的選擇也不是隨機(jī)的.初始溫度的選擇與臨界溫度有關(guān)［11］.臨界溫度是指液體變成固體時(shí)的溫度，從模擬退火算法來(lái)說(shuō)是指目標(biāo)函數(shù)值開(kāi)始變化時(shí)的溫度［12］.采用文獻(xiàn)［12］中區(qū)間分半搜尋臨界溫度的方法來(lái)確定初始溫度.

1.3 算法的具體步驟

(1)用區(qū)間分半法確定初始溫度tmax，設(shè)置同一溫度下的迭代次數(shù)k、鄰域規(guī)模因子λ、溫度下降因子dt、折疊角度的最大值和最小值.

(2)利用xr=rand*(max－min)+min產(chǎn)生初始解X0(x01，x02，…，x0n)，計(jì)算目標(biāo)函數(shù)值f0=f(X0).

(3)判斷是否滿足程序終止條件，如果滿足就結(jié)束程序;否則，令t=t*dt，k=1，轉(zhuǎn)下一步.

(4)從{1，2，…，n}中隨機(jī)選一數(shù) r，xr=x0r+λ*rand*(max－min)，rand產(chǎn)生－1到1之間的隨機(jī)數(shù).如果xr超出上下邊界最大和最小值，則按式(1)進(jìn)行邊界處理后，計(jì)算產(chǎn)生的新解的目標(biāo)函數(shù)f=f(X).

(5)計(jì)算△f=f(X)－f(X0)，根據(jù)Metropolis法則來(lái)判斷是否接受新解，若接受，則用X代替X0，用f(X)代替f(X0).

(6)判斷是否達(dá)到最大迭代值k，若達(dá)到則轉(zhuǎn)步驟(3);否則迭代次數(shù)加1，轉(zhuǎn)步驟(4).

在算法中有以下幾個(gè)可調(diào)參數(shù).

(1)初始溫度Tmax:主要根據(jù)目標(biāo)函數(shù)取值范圍來(lái)確定，取值應(yīng)保證初始接受率足夠高.

(2)終止條件:在最優(yōu)值未知的情況下，終止條件比較難確定.一般采取2種準(zhǔn)則:一是給定終止溫度;二是連續(xù)多次降溫，直到能量函數(shù)的值不再下降為止.

(3)溫度下降因子 dt:一般取0.95－0.98.

(4)同一溫度迭代次數(shù)(Markov鏈長(zhǎng)度):Lmax的選取與問(wèn)題規(guī)模和解空間大小有關(guān).

(5)鄰域規(guī)模因子scale:鄰域規(guī)模因子的取值和解空間有直接關(guān)系，取0.2－0.5.

(6)最大、最小值與角度的取值坐標(biāo)有關(guān)，選逆時(shí)針?lè)较驗(yàn)檎较颍畲笾等ˇ?，最小值?。?

2 結(jié)果與分析

本文數(shù)據(jù)是選用Fibonacci序列形式.首先對(duì)于N＜8序列進(jìn)行了測(cè)試，結(jié)果表明本文的算法能迅速獲得最小能量值，并與Stillinger所獲得的最小能量值［6，7］完全一致.隨后又對(duì)N值分別為13、21、34、55的序列進(jìn)行了測(cè)試，并與利用其它算法所得的最低能量值進(jìn)行比較，結(jié)果如表1所示.

表1 序列及最小能量值1)Table 1 Sequences and the minimum values of energy

由表1可知:采用本文的模擬退火算法獲得的最小能量值都優(yōu)于Stillinger獲得的最小能量值，也優(yōu)于文獻(xiàn)［10］中改進(jìn)的模擬退火算法獲得的最小能量值.對(duì)于N值分別為13、21、55的序列，采用本文算法獲得的最小能量值優(yōu)于用PERM方法得到的最小能量值;對(duì)于N值為34的序列，采用本文算法獲得的最小能量值與采用PERM方法得到的最小能量值有差異，但兩者的結(jié)果還比較接近.

圖1是采用本文改進(jìn)的模擬退火算法獲得的表1中各序列的最小能量構(gòu)象.

圖1 各序列最小能量構(gòu)象Fig.1 The minimum values of energy conformation form

3 小結(jié)與討論

本文對(duì)模擬退火算法中產(chǎn)生的新解邊界值的處理給出一種新方法.在初始溫度選擇方面，采用李麗等提出的區(qū)間分半搜尋臨界溫度的方法來(lái)確定算法的初始溫度［12］.將改進(jìn)后的算法應(yīng)用到蛋白質(zhì)二維的Toy模型中，通過(guò)對(duì)序列長(zhǎng)度分別是13、21、34、55的Fibonacci序列測(cè)試結(jié)果的分析，證明該算法可行有效.但是由于天然蛋白質(zhì)結(jié)構(gòu)遠(yuǎn)比Toy模型復(fù)雜得多，所以模擬退火算法在蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)中的應(yīng)用有待更深入研究.

［1］陳清西，李松剛.KCIO3誘導(dǎo)龍眼成花及其葉片碳水化合物與蛋白質(zhì)的變化［J］.福建農(nóng)林大學(xué)學(xué)報(bào):自然科學(xué)版，2004，33(2):182－185.

［2］馬棟蘋，阮曉鋼.基于改進(jìn)BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)蛋白質(zhì)二級(jí)結(jié)構(gòu)［J］.北京聯(lián)合大學(xué)學(xué)報(bào):自然科學(xué)版，2005，19(2):70－73.

［3］WANG Z X.The current situation and prospect of protein structure prediction［J］.Chemistry of Life，1998，18(6):19－22.

［4］SHORTLE D，CHAN H S，DILL K A.Modeling the effects of mutations on the denatured states of proteins［J］.Protein Science，1992(1):201－205.

［5］DILL K A，BROMBERG S，YUE K，et al.Principles of protein folding-A perspective from simple exact models［J］.Protein Science，1995(4):561－602.

［6］FRANK H S，TERESA H G，CATHERINE L H.Toy model for protein folding［J］.Physical Review E，1993，48(2):1469－1477.

［7］張曉龍，李婷婷，蘆進(jìn).基于Toy模型蛋白質(zhì)折疊預(yù)測(cè)的多種群微粒群優(yōu)化算法研究［J］.計(jì)算機(jī)科學(xué)，2008，35(10):230－235.

［8］FRANK H S.Collective aspects of protein folding illustrated by a toy model［J］.Physical Review E，1995，52(3):2872－2877.

［9］王翼飛，史定華.生物信息學(xué)——智能化算法及其應(yīng)用［M］.北京:化學(xué)工業(yè)出版社，2006:195－197.

［10］張紅娟.基于非格點(diǎn)模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)研究［C］.大連:大連理工大學(xué)，2005:30－31.

［11］姚姚.地球物理非線性反演模擬退火算法的改進(jìn)［J］.地球物理學(xué)報(bào)，1995，38(5):643－650.

［12］李麗，朱國(guó)同，陳秀娟，等.模擬退火算法的改進(jìn)及在靜校正中的應(yīng)用［J］.大慶石油地質(zhì)與開(kāi)發(fā)，2008，10，27(5):120－123.

［13］HSU H P，MEHRA V，GRASSBERGER P.Structure optimization in off-lattice protein model［J］.Physical Review E，2003，68(3):1－4.