朱均燕，溫永仙

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

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

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

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

1 改進的模擬退火算法

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

1.1 新解邊界值處理

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

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

1.2 初始溫度的選擇

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

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

1.3 算法的具體步驟

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

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

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

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

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

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

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

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

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

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

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

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

(6)最大、最小值與角度的取值坐標有關(guān)，選逆時針方向為正方向，最大值取π，最小值?。?

2 結(jié)果與分析

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

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

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

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

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

3 小結(jié)與討論

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

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

［2］馬棟蘋，阮曉鋼.基于改進BP神經(jīng)網(wǎng)絡(luò)預(yù)測蛋白質(zhì)二級結(jié)構(gòu)［J］.北京聯(lián)合大學(xué)學(xué)報:自然科學(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］張曉龍，李婷婷，蘆進.基于Toy模型蛋白質(zhì)折疊預(yù)測的多種群微粒群優(yōu)化算法研究［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］張紅娟.基于非格點模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測研究［C］.大連:大連理工大學(xué)，2005:30－31.

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

［12］李麗，朱國同，陳秀娟，等.模擬退火算法的改進及在靜校正中的應(yīng)用［J］.大慶石油地質(zhì)與開發(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.