基于構象相似度的多目標粒子群算法

朱榜

（上海海事大學信息工程學院，上海 201306）

0 引言

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

當一個優化問題涉及多個目標函數，找到這些目標函數的最優解，稱為多目標優化[3]。在多目標優化中，一個目標的最優解對于另一個目標可能不是最優的，因此，人們不能選擇只有一個目標達到最優的解。一般來說，在一個以上相互沖突的問題中，沒有一個最優解，相反，存在一組最優解，稱為最優帕累托前沿。這個組合包括在不減少另一子目標的情況下不可能改進一個目標的解集。理論蛋白質結構預測問題也可以被適當地表示為多目標優化問題（MO），因為其勢能函數一般有幾個能量項組合而成，這些能量項在優化過程中可能存在沖突。跟以往單目標方法中直接使用加權系數對這些能量項進行耦合不同，MO方法通過將這些能量項以不同的方式組合成多個目標同時進行優化，避免了優化過程中能量項沖突導致的誤差，從而能夠更好地探索蛋白質構象空間。在過去幾年中，已經有不少MO方法被應用到理論蛋白質結構預測中[4-7]。

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

1 算法實現蛋白質表示及勢能函數

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

蛋白質的勢能函數表達式如下：

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

本文從多目標優化角度考慮蛋白質預測問題，故將勢能函數的能量項分解成不同的目標。Edih、Evdw、Ehb分別作為一個子目標。

2 基于表型擁擠的多目標粒子群算法

2.1多目標粒子群算法

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

式中：

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

為了避免算法陷入局部最優，并增加解的精確度，本文采用動態變化的慣性權重與加速系數，其公式如下：

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

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

圖1 多目標粒子群流程圖

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

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

算法1基于擂臺塞法則的非支配集構造

2.3基于構象相似度的外部檔案裁剪技術

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

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

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

基于蛋白質構象相似度的外部檔案裁剪技術具體步驟如下：

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

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

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

2.4基于構象相似度的多目標粒子群算法流程

根據2.1到2.3小節，本文算法的具體流程如下：

算法2 PCMOPSO

3 結果與分析

本文算法的運行環境為搭載Intel Core i7處理器，8GB運行內存的64位Windows10操作系統。算法參數設置為：最大迭代次數T=1000，外部檔案大小N=100，種群大小M=100，算法獨立運行30次。

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

表1 蛋白質信息及其測試結果

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

4 結語

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