朱榜

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

蛋白質(zhì)是由20種不同氨基酸組成的生物大分子，其在生物細(xì)胞中扮演著許多重要角色，例如酶的活性、物質(zhì)的儲存和運(yùn)輸、信號轉(zhuǎn)導(dǎo)、抗體等[1]。而蛋白質(zhì)的功能與其三維結(jié)構(gòu)是直接相關(guān)的，因此預(yù)測蛋白質(zhì)的三維結(jié)構(gòu)對于研究蛋白質(zhì)的功能和作用有非常重要的意義。理論計算方法（也稱熱力學(xué)方法）是一種常用的蛋白質(zhì)結(jié)構(gòu)預(yù)測方法，由于它僅利用一級序列信息進(jìn)行預(yù)測，而不需要任何其他已知蛋白質(zhì)結(jié)構(gòu)信息，所以，該方法也是一種較理想的預(yù)測方法[2]。理論計算方法的有效性取決于兩方面：①勢能函數(shù)（評估函數(shù)），該函數(shù)模擬參與蛋白質(zhì)折疊過程的相互作用力，理想地將蛋白質(zhì)結(jié)構(gòu)排列為全局最小值；②有效的搜索算法，能夠處理具有大量不可行構(gòu)象的多維構(gòu)象搜索空間。因此，理論蛋白質(zhì)結(jié)構(gòu)預(yù)測具有較高的計算成本，無法通過詳盡的搜索來獲得結(jié)果，一般采用元啟發(fā)式算法。

當(dāng)一個優(yōu)化問題涉及多個目標(biāo)函數(shù)，找到這些目標(biāo)函數(shù)的最優(yōu)解，稱為多目標(biāo)優(yōu)化[3]。在多目標(biāo)優(yōu)化中，一個目標(biāo)的最優(yōu)解對于另一個目標(biāo)可能不是最優(yōu)的，因此，人們不能選擇只有一個目標(biāo)達(dá)到最優(yōu)的解。一般來說，在一個以上相互沖突的問題中，沒有一個最優(yōu)解，相反，存在一組最優(yōu)解，稱為最優(yōu)帕累托前沿。這個組合包括在不減少另一子目標(biāo)的情況下不可能改進(jìn)一個目標(biāo)的解集。理論蛋白質(zhì)結(jié)構(gòu)預(yù)測問題也可以被適當(dāng)?shù)乇硎緸槎嗄繕?biāo)優(yōu)化問題（MO），因為其勢能函數(shù)一般有幾個能量項組合而成，這些能量項在優(yōu)化過程中可能存在沖突。跟以往單目標(biāo)方法中直接使用加權(quán)系數(shù)對這些能量項進(jìn)行耦合不同，MO方法通過將這些能量項以不同的方式組合成多個目標(biāo)同時進(jìn)行優(yōu)化，避免了優(yōu)化過程中能量項沖突導(dǎo)致的誤差，從而能夠更好地探索蛋白質(zhì)構(gòu)象空間。在過去幾年中，已經(jīng)有不少M(fèi)O方法被應(yīng)用到理論蛋白質(zhì)結(jié)構(gòu)預(yù)測中[4-7]。

粒子群算法（PSO）是基于群體協(xié)作的隨機(jī)搜索算法[8]，是一種廣泛應(yīng)用的優(yōu)化和搜索問題的元啟發(fā)式算法。PSO能夠同時探索搜索空間的多個區(qū)域，且能夠有效地處理多模態(tài)問題。這些特征使得PSO算法在解決多目標(biāo)優(yōu)化問題上具有很大的優(yōu)勢：第一，它的高效搜索能力有利于得到多目標(biāo)意義下的最優(yōu)解；第二，它通過代表整個解集種群，按并行方式同時搜索多個非劣解，也即搜索到多個Pareto最優(yōu)解；第三，PSO算法的通用性比較好，適合處理多種類型的目標(biāo)函數(shù)和約束，并且容易與傳統(tǒng)的優(yōu)化方法結(jié)合，從而改進(jìn)自身的局限性，達(dá)到更高效率的解決問題[9]。本文針對蛋白質(zhì)結(jié)構(gòu)預(yù)測問題，將蛋白質(zhì)構(gòu)象相似度引入到多目標(biāo)粒子群算法中，增加帕累托前沿的多樣性，從而得到最優(yōu)蛋白質(zhì)構(gòu)象。

1 算法實現(xiàn)蛋白質(zhì)表示及勢能函數(shù)

本文采用粗粒度蛋白質(zhì)模型用于降低評估特定構(gòu)象能量所需的計算成本。該模型中蛋白質(zhì)側(cè)鏈被鏈接主鏈的第一個碳原子Cb取代，主鏈僅用N、C、Ca三個原子表示。每個蛋白質(zhì)構(gòu)象由其氨基酸序列中每個殘基的主鏈二面角{φ，ψ，ω}集合表示。新的蛋白質(zhì)構(gòu)象由改變二面角φ和ψ實現(xiàn)，肽鍵角度ω在算法搜索期間不變，保持在180°。

蛋白質(zhì)的勢能函數(shù)表達(dá)式如下：

其中，Ebond和Eangle分別是鍵伸縮勢能和鍵角彎曲能，為了減少構(gòu)象空間復(fù)雜度，本文將鍵長鍵角設(shè)置為理想值，故Ebond=Eangle=0；Edih是二面角扭轉(zhuǎn)勢能，由簡單的傅里葉級數(shù)表示；Evdw是范德華相互作用，由所有主鏈原子之間及主鏈原子與側(cè)鏈原子之間的相互作用和側(cè)鏈原子與側(cè)鏈原子的相互作用兩部分組成；Ehb是氫鍵相互作用，氫鍵由蛋白質(zhì)主鏈上的羰基和酰胺基團(tuán)形成，對于蛋白質(zhì)的結(jié)構(gòu)穩(wěn)定性至關(guān)重要，其形成方式確定了蛋白質(zhì)的二級結(jié)構(gòu)（α螺旋，β-折疊和彎曲），本文使用文獻(xiàn)[10]結(jié)合角度項的徑向12-10 Lennard-Jones勢表示。該勢能函數(shù)的詳細(xì)信息見文獻(xiàn)[11]。

本文從多目標(biāo)優(yōu)化角度考慮蛋白質(zhì)預(yù)測問題，故將勢能函數(shù)的能量項分解成不同的目標(biāo)。Edih、Evdw、Ehb分別作為一個子目標(biāo)。

2 基于表型擁擠的多目標(biāo)粒子群算法

2.1多目標(biāo)粒子群算法

粒子群算法是受鳥類覓食這種社會行為的啟發(fā)提出的，模擬鳥類覓食時個體之間自我認(rèn)知和相互協(xié)作，相互交換信息來尋找最優(yōu)解的一種隨機(jī)優(yōu)化的智能技術(shù)[12]。在PSO中，每個粒子是優(yōu)化問題的一個潛在解，它跟隨當(dāng)前的最優(yōu)粒子在解空間中飛行，從而向最優(yōu)解靠近。因此每個粒子的速度和位置公式可表示為：

式中：

vi(t)和xi(t)分別為t代粒子i的速度與位置，pBesti是粒子i的個體最優(yōu)位置，gBest(t)是t代所有粒子的全局最優(yōu)位置，r1、r2為[0 ,1]區(qū)間上獨(dú)立的隨機(jī)數(shù)，ω為慣性權(quán)重，一般在（0,1）區(qū)間，c1、c2為加速系數(shù)。

為了避免算法陷入局部最優(yōu)，并增加解的精確度，本文采用動態(tài)變化的慣性權(quán)重與加速系數(shù)，其公式如下：

式中：ωmax和ωmin分別取0.9和0.4；T為最大迭代次數(shù)；k表示當(dāng)前迭代的次數(shù)。

多目標(biāo)粒子群算法與單目標(biāo)粒子群算法的主要區(qū)別是多了存檔和限制外部檔案規(guī)模的過程，并且也不是簡單地通過適應(yīng)度函數(shù)的比較來求出解，而是用一組非劣解集去逼近真實的Pareto前沿[13]。算法的大致步驟如圖1所示。

圖1 多目標(biāo)粒子群流程圖

2.2基于擂臺賽法則的非支配集求解

在多目標(biāo)優(yōu)化中，給定x和y兩個解，如果x在所有目標(biāo)中至少等于y，且至少在一個目標(biāo)中x大于y，則稱x支配y。Pareto最優(yōu)集是由所有非支配解組成的集合。在多目標(biāo)粒子群算法中，每一代外部檔案由上一代外部檔案與當(dāng)前粒子群集合的非支配解集構(gòu)成。本文采用擂臺賽法則構(gòu)造非支配，在每一輪比較時，從構(gòu)造集中選出一個個體出任擂主（一般為當(dāng)前構(gòu)造集的第1個個體），由擂主與構(gòu)造集中其他個體進(jìn)行比較，敗者被淘汰出局,勝者成為新的擂主，并繼續(xù)該輪比較；一輪比較后，最后的擂主個體即為非支配個體；按照這種方法進(jìn)行下一輪比較，直至構(gòu)造集為空[14]。其具體算法流程如下：

算法1基于擂臺塞法則的非支配集構(gòu)造

2.3基于構(gòu)象相似度的外部檔案裁剪技術(shù)

多目標(biāo)粒子群中采用外部檔案來存儲每一代產(chǎn)生的非劣解。隨著迭代的進(jìn)行，外部檔案會逐漸膨脹，算法的計算復(fù)雜度也隨之增加，對此一般通過對外部檔案設(shè)置一個最大規(guī)模N，當(dāng)檔案中粒子數(shù)超過N時，則按照一定規(guī)則進(jìn)行裁剪。目前常見的外部檔案的維護(hù)策略有自適應(yīng)網(wǎng)格法[15]、擁擠距離法[16]、k近鄰法[17]等。其中，自適應(yīng)網(wǎng)格法的基本思路是對目標(biāo)空間進(jìn)行網(wǎng)格劃分，通過統(tǒng)計網(wǎng)格中的粒子數(shù)來估計粒子密度，粒子所在網(wǎng)格包含粒子越多則其密度越大，當(dāng)外部檔案中粒子數(shù)超過最大規(guī)模N時，則從密度最大的網(wǎng)格中隨機(jī)選擇粒子進(jìn)行刪除。

在蛋白質(zhì)結(jié)構(gòu)預(yù)測中，為了更廣泛地搜索構(gòu)象空間，維持外部檔案中構(gòu)象的多樣性，本文引入蛋白質(zhì)構(gòu)象相似度來裁剪外部檔案。蛋白質(zhì)構(gòu)象相似度使用疏水性殘基Ca位置的距離矩陣誤差（DME）表示，其計算公式如下：

其中pij和qij分別是蛋白質(zhì)p、q疏水性殘基i、j的Ca原子距離，N是蛋白質(zhì)疏水性殘基的個數(shù)。

基于蛋白質(zhì)構(gòu)象相似度的外部檔案裁剪技術(shù)具體步驟如下：

Step 1：選擇密度最大的網(wǎng)格Gi，隨機(jī)選擇該網(wǎng)格中的一個粒子j，并根據(jù)式（6）計算該粒子j與Gi中其他粒子的DME值；

Step 2：刪除Gi中除粒子j以外，DME值最小的粒子，更新Gi的密度；

Step 3：如果外部檔案大小小于最大規(guī)模N則算法結(jié)束，否則返回Step1。

2.4基于構(gòu)象相似度的多目標(biāo)粒子群算法流程

根據(jù)2.1到2.3小節(jié)，本文算法的具體流程如下：

算法2 PCMOPSO

3 結(jié)果與分析

本文算法的運(yùn)行環(huán)境為搭載Intel Core i7處理器，8GB運(yùn)行內(nèi)存的64位Windows10操作系統(tǒng)。算法參數(shù)設(shè)置為：最大迭代次數(shù)T=1000，外部檔案大小N=100，種群大小M=100，算法獨(dú)立運(yùn)行30次。

算法測試數(shù)據(jù)為 2rlg、1vii、2p81、2jzq、1xzy、2evq、1e0l、2dmv、1k36、1fna、2kp0、1crn、1e0g、2hbb、2gb1 等15條長度不等，具有不同二級結(jié)構(gòu)的天然蛋白質(zhì)，這些蛋白質(zhì)的天然結(jié)構(gòu)已由實驗等方法測得，其相關(guān)數(shù)據(jù)從PDB數(shù)據(jù)庫下載得到。

表1 蛋白質(zhì)信息及其測試結(jié)果

為了評估預(yù)測得到蛋白質(zhì)構(gòu)象的質(zhì)量，本文采用與蛋白質(zhì)天然結(jié)構(gòu)的均方根偏差（RMSD）作為預(yù)測構(gòu)象的度量。RMSD的值越低，則預(yù)測構(gòu)象越接近天然結(jié)構(gòu)，因此在多目標(biāo)方法中，本文選取外部檔案中RMSD值最小的粒子作為該蛋白質(zhì)的預(yù)測構(gòu)象。本文所有RMSD的計算中只考慮氨基酸的骨架原子。表1給出了本文算法PCMOPSO與MOPSO算法針對15種蛋白質(zhì)的RMSD值，其中，MOPSO外部檔案維護(hù)策略為擁擠距離法，其他速度位置更新等配置與PCMOPSO相同。從表1中可看出基于表型擁擠的多目標(biāo)粒子算法所得結(jié)果明顯優(yōu)于MOPSO，80%（12條）的蛋白質(zhì)都得到了優(yōu)化。其中1vii的RMSD得到0.8?的改善，1eol得到1.05?的改善，2hbb得到0.73?的改善，2gb1更是得到了2.84?的改善。測試結(jié)果表明采用構(gòu)象相似度策略的多目標(biāo)粒子群算法能夠更好的搜索蛋白質(zhì)構(gòu)象空間，從而找到更接近天然結(jié)構(gòu)的蛋白質(zhì)構(gòu)象。

4 結(jié)語

本文提出了一種基于構(gòu)象相似度的構(gòu)象搜索算法，其采用擂臺賽法則提高獲得非劣解集的性能，并引入構(gòu)象相似度對外部檔案集進(jìn)行維護(hù)，提高Pareto前沿的多樣性與均勻性，利用搜索效率高，全局搜索能量強(qiáng)的多目標(biāo)粒子群算法對蛋白質(zhì)構(gòu)象空間進(jìn)行多目標(biāo)優(yōu)化。實驗結(jié)果表明，相比普通多目標(biāo)粒子群算法在蛋白質(zhì)結(jié)構(gòu)預(yù)測中的應(yīng)用，加入構(gòu)象相似度策略能夠更好地維持外部檔案中構(gòu)象的多樣性與均勻性，從而獲得較好的蛋白質(zhì)預(yù)測構(gòu)象。