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

朱榜

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

式中：

vi(t)和xi(t)分別為t代粒子i的速度與位置，pBesti是粒子i的個(gè)體最優(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)，并增加解的精確度，本文采用動(dòng)態(tài)變化的慣性權(quán)重與加速系數(shù)，其公式如下：

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

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

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

2.2基于擂臺(tái)賽法則的非支配集求解

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

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

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

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

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

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

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

Step 1：選擇密度最大的網(wǎng)格Gi，隨機(jī)選擇該網(wǎng)格中的一個(gè)粒子j，并根據(jù)式（6）計(jì)算該粒子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次。

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

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

為了評(píng)估預(yù)測(cè)得到蛋白質(zhì)構(gòu)象的質(zhì)量，本文采用與蛋白質(zhì)天然結(jié)構(gòu)的均方根偏差（RMSD）作為預(yù)測(cè)構(gòu)象的度量。RMSD的值越低，則預(yù)測(cè)構(gòu)象越接近天然結(jié)構(gòu)，因此在多目標(biāo)方法中，本文選取外部檔案中RMSD值最小的粒子作為該蛋白質(zhì)的預(yù)測(cè)構(gòu)象。本文所有RMSD的計(jì)算中只考慮氨基酸的骨架原子。表1給出了本文算法PCMOPSO與MOPSO算法針對(duì)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?的改善。測(cè)試結(jié)果表明采用構(gòu)象相似度策略的多目標(biāo)粒子群算法能夠更好的搜索蛋白質(zhì)構(gòu)象空間，從而找到更接近天然結(jié)構(gòu)的蛋白質(zhì)構(gòu)象。

4 結(jié)語(yǔ)

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