基于煙花算法的分子構象搜索方法

廖靈志 楊智歡 洪玲慧 李 瑾

（西南醫科大學 醫學信息與工程學院,四川 瀘州646000）

1 概述

分子對接[1]算法中的采樣方法,即構象搜索方法對于分子對接的精度、尤其是效率有著至關重要的影響。早期構象搜索中應用的算法包括：遺傳算法[2]、模擬退火[3]、禁忌搜索[4]等各種方法。隨著群體智能算法的發展,一種新的群體智能算法——煙花算法[5,6]因其具有很強的優化問題求解能力而倍受關注。本文對分子對接中的構象搜索問題展開研究,提出一種基于煙花算法的構象搜索方法,我們的工作證明了煙花算法在解決蛋白質- 配體對接的構象搜索問題方面表現出的強大性能,具有更快的收斂速度,更加穩定的表現。

2 FWAVina 構象搜索方法構建

2.1 分子對接的模型表示

2.2 相關算子設計

2.2.1 煙花初始化

2.2.2 爆炸算子

將煙花按適應度值進行排序,通過煙花的適應度值排序進行火花數目的分配,而不再依賴適應度值數值本身。采用公式（3）的方式進行火花數目的計算,公式如下所示：

其中,M為每個煙花最多爆炸的火花數目；ri表示煙花wi的適應度值排序。

我們將該構象搜索算法的解空間搜索范圍分為三個層次。一是構象中心位置在蛋白質結合口袋中的變化；二是構象中心位置固定后,取向的變化；三是中心位置和取向固定后,可扭轉鍵的鍵角變化。因此,對應解空間的這三個層次,將煙花爆炸的范圍劃分為如下三個區域：

Ω1：變化區域為可扭轉鍵變化,范圍為[-π, π]；

Ω2：變化區域為取向變動,范圍為[-π, π]；

Ω3：變化區域為中心位置變動。

從Ω1 到Ω3 代表爆炸半徑越來越大。

若爆炸后的火花為不可行解,則在解空間里隨機生成一個火花。

2.2.3 變異算子

FWAVina 采用隨機變異的方式來產生變異煙花,以增加種群多樣性,避免陷入局部最優。從煙花種群（包含N 個初始煙花及S 個爆炸出的火花）中隨機選擇N 個煙花,每個煙花隨機選擇幾個維度,將這些維度上隨機產生變量得到變異個體。

2.2.4 煙花選擇策略

當代種群中的N 個初始煙花、S 個火花、N 個變異煙花構成了候選集合K,從候選集合K 中選擇N 個個體作為下一代初始煙花。

2.3 算法流程

FWAVina 構象搜索方法的具體步驟可以分成如下幾步。

2.3.1 煙花初始化。初始化N 個煙花（每個煙花代表一個配體的構象）,將配體構象表示為解向量,設置AutodockVina 打分函數為適應度函數。

2.3.2 煙花爆炸。根據煙花爆炸范圍的計算公式和產生火花數量的計算方法,將初始煙花進行爆炸,產生爆炸火花,其數量用S 表示。

2.3.3 煙花變異。從N 個煙花和S 個火花中隨機選擇N 個個體,每個個體按照煙花變異策略發生變異,形成變異煙花。

2.3.4 煙花選擇。將候選集合（包括當代種群中的N 個煙花、S 個爆炸火花和N 個變異火花） 中的所有煙花按適應度函數值從小到大排序,按選擇策略選擇N 個煙花組成下一代種群。

2.3.5 判斷適應度函數值是否滿足收斂準則,如果是,轉步驟2.3.7,否則,轉步驟2.3.6。

2.3.6 判斷是否達到最大迭代次數,如果是,轉步驟2.3.7,否則,轉步驟2.3.2。

2.3.7 輸出近似最優配體構象以及分值。

3 實驗設計與結果

為了測試FWAVina 在對接和虛擬篩選中的性能,我們使用了廣泛應用的標準數據PDBbind 的核心集。對核心集中的每個復合物分別進行了30 次對接,然后每個復合物的預測結合能、RMSD 值及運行時間均取其平均值。201 個復合物的平均結合能、平均RMSD 值、平均運行時間見表1。我們分別對Vina 和FWAVina 預測的201 個復合物的結合能、RMSD 值以及運行時間,進行配對樣本t 檢驗。p 值表明FWAVina 預測構象的結合能、RMSD 值以及運行時間均顯著低于Vina。另外,表1 中展示了Vina 和FWAVina 30 次對接的平均準確率,即201 個復合物對接一次后計算準確率,一共對接30 次,準確率取其平均值。

在運行效率方面,與Vina 相比,FWAVina 的執行時間減少了52.5%,見表1。顯然,FWAVina 的對接速度有了很大的提高。在基于分子對接的虛擬篩選應用方面,分子對接程序的速度對虛擬篩選的效率起決定性作用,因此一個快速的分子對接程序更適合應用于藥物的虛擬篩選。

表1 在Coreset 數據集上進行30 次對接后Vina 和FWAVina 的對接性能對比

4 結論

本文提出了一種基于煙花算法的分子構象搜索方法,并且在AutodockVina 的框架上予以實現,編寫了分子對接程序FWAVina。其次,本文在PDBbind 數據集上進行了分子對接模擬。結果表明,FWAVina 與Vina 相比,分子對接的準確性略有提升,而對接效率提升較大,并且FWAVina 對于不同柔性的配體對接來說迭代次數不會呈現大幅上升。