基于布谷鳥搜索算法的蛋白質(zhì)能量優(yōu)化

王慶喜，朱麗華

(安陽工學(xué)院 計算機科學(xué)與信息工程學(xué)院，河南 安陽 455000)

基于布谷鳥搜索算法的蛋白質(zhì)能量優(yōu)化

王慶喜，朱麗華

(安陽工學(xué)院 計算機科學(xué)與信息工程學(xué)院，河南 安陽 455000)

針對蛋白質(zhì)折疊預(yù)測問題，提出了一種基于布谷鳥搜索算法的蛋白質(zhì)能量優(yōu)化方法。該方法首先對原始布谷鳥搜索算法從多種群、進(jìn)化策略和禁忌搜索等多個角度進(jìn)行改進(jìn)，提升了布谷鳥搜索算法的全局搜索能力；改進(jìn)了布谷鳥搜索算法求解蛋白質(zhì)能量問題；取得了蛋白質(zhì)能量的最小值或是可行值。對算法的仿真測試以及與其他算法的數(shù)據(jù)進(jìn)行對比，證明本文蛋白質(zhì)能量優(yōu)化方法的可行性和優(yōu)越性。

蛋白質(zhì)；能量優(yōu)化；蛋白質(zhì)折疊預(yù)測；布谷鳥搜索算法；多種群；禁忌搜索

蛋白質(zhì)的一級結(jié)構(gòu)決定了蛋白質(zhì)的空間結(jié)構(gòu)，而空間折疊結(jié)構(gòu)決定了蛋白質(zhì)的生物功能，因此蛋白質(zhì)折疊預(yù)測在生物學(xué)領(lǐng)域具有重要意義[1]。但是蛋白質(zhì)折疊預(yù)測是一個典型的非確定性多項式問題，隨著氨基酸序列的增多，其計算量呈指數(shù)級增加，成為生物信息學(xué)中的一個具有挑戰(zhàn)的研究課題。蛋白質(zhì)折疊預(yù)測問題[2]是在已知氨基酸殘基序列的情況下，求解蛋白質(zhì)的最小能量以及最小能量對應(yīng)的構(gòu)象。蛋白質(zhì)最小能量求解也稱為蛋白質(zhì)能量優(yōu)化，其在蛋白質(zhì)折疊預(yù)測中起到了基礎(chǔ)和決定作用，因此蛋白質(zhì)折疊預(yù)測問題的核心是使用全局優(yōu)化算法進(jìn)行蛋白質(zhì)能量優(yōu)化。到目前為止，已經(jīng)有很多學(xué)者嘗試使用不同的算法優(yōu)化蛋白質(zhì)能量，比如文獻(xiàn)[3-6]分別采用遺傳算法、禁忌搜索算法、微粒群優(yōu)化算法、模擬退火算法等算法對蛋白質(zhì)能量優(yōu)化，取得了較好效果，但是上述算法受限于原始算法的搜索能力，蛋白質(zhì)能量優(yōu)化效果仍有可以提升的空間。

布谷鳥搜索算法是新型啟發(fā)式群體智能算法，于2009年被提出后，已經(jīng)被證明具有強大的全局搜索能力和收斂性能[7]，并且被廣泛應(yīng)用于各個領(lǐng)域。文獻(xiàn)[8-11]采用布谷鳥搜索算法分別求解優(yōu)化游客數(shù)量預(yù)測、系統(tǒng)參數(shù)、系統(tǒng)穩(wěn)定性設(shè)計和圖像分割等問題，取得了良好效果。本文使用布谷鳥搜索算法優(yōu)化蛋白質(zhì)能量，為了提升優(yōu)化效果，還對原始布谷鳥搜索算法進(jìn)行了較大改進(jìn)。

1 蛋白質(zhì)Toy模型

1.1 蛋白質(zhì)能量

蛋白質(zhì)能量由主鏈的彎曲勢能和不相鄰殘基之間的引力勢能組成，其數(shù)學(xué)模型[2]可以表示如下。

(1)

(2)

(3)

(4)

其中：E為蛋白質(zhì)能量；E1為蛋白質(zhì)彎曲勢能；E2為不相鄰殘基之間的引力；rij為殘基之間的空間距離。

1.2 蛋白質(zhì)能量優(yōu)化

蛋白質(zhì)能量優(yōu)化是在蛋白質(zhì)氨基酸殘基的構(gòu)象空間內(nèi)求解蛋白質(zhì)的最小能量值，問題數(shù)學(xué)定義[3]為：

minf(x)

s.t.

(5)

x∈D。

其中：f(x)為蛋白質(zhì)能量；D為構(gòu)象空間；minf(x)為蛋白質(zhì)能量的最小值，或稱為最小能量值。

1.3Toy模型

Toy模型是一種簡化的蛋白質(zhì)模型[5]，由A和B兩種氨基酸組成，其中A表示疏水性氨基酸(hydrophobic)，B表示親水性氨基酸(hydrophilic)。其中，三個氨基酸的連線角度可以自己變換。n個氨基酸形成n-2個鍵角，分別用θ2，θ3，…，θn-1表示。把前三個氨基酸形成的平面記為XOY，則兩個氨基酸的連線與XOY形成的n-3個夾角，分別表示為β3，β4，…βn-1。結(jié)合蛋白質(zhì)能量公式，可以推導(dǎo)出在Toy模型中的蛋白質(zhì)能量優(yōu)化為：

minθi，βi∈[-π，π]E(θ2，…，θi，…，θn-1，β3，…，βi，…，βn-1)。

2 布谷鳥搜索算法

2.1 布谷鳥搜索算法

布谷鳥搜索算法[7]是仿生布谷鳥寄生繁殖的自然現(xiàn)象而開發(fā)的群體性智能進(jìn)化算法。算法進(jìn)化模型為[10]：

i=1，2，…，n。

(6)

L(λ)=t-λ，1<λ≤3。

(7)

2.2 算法改進(jìn)

2.2.1 多種群

原始布谷鳥搜索算法采用單一種群，而改進(jìn)算法采用4個種群，具體為在鳥窩位置初始化以及每次進(jìn)化后，都會根據(jù)鳥窩位置的適應(yīng)度值將鳥窩分為4類(4個子群)，分別為優(yōu)群、良群、中群、差群，4個子種群采用不同的策略進(jìn)化。其優(yōu)點是可以兼顧算法的局部搜索和全局搜索能力，在兩者之間取得平衡。經(jīng)過多次實驗發(fā)現(xiàn)，4個子群的比例分別為10%、30%、40%、20%時，可以取得較好效果。

2.2.2 進(jìn)化策略

優(yōu)群中的個體是群體中的精英，是適應(yīng)度值最好的一個子群體，他們是整個群體的目標(biāo)，但是因為復(fù)雜問題中有很多局部最優(yōu)點，群體中的精英也有可能是局部最優(yōu)位置或其附近位置，若是如此，則算法就是陷入局部最優(yōu)，這是智能優(yōu)化算法常見的現(xiàn)象，也是算法改進(jìn)需要解決的核心問題。為了能夠跳出局部最優(yōu)，本文借鑒遺傳算法[12]和禁忌搜索算法[13]，采用變異和禁忌兩種方式對優(yōu)群中的個體進(jìn)行優(yōu)化。對于多次迭代無法進(jìn)化到更優(yōu)位置的鳥窩采用變異處理，防止陷入局部最優(yōu)，并且為了提升跳出局部最優(yōu)的概率，設(shè)立禁忌表。

良好中的個體適應(yīng)度值雖然不是最優(yōu)，但是在大多數(shù)情況下仍是可以接受的解，為了增加收斂能力，改進(jìn)算法采用原始布谷鳥的進(jìn)化方式。

中群中的個體值在很大意義上，無法滿足求解需要，為了增加種群中的個體多樣性，提升尋得全局最優(yōu)的概率，改進(jìn)算法采用適應(yīng)度值差的個體進(jìn)化獲得，即采用種群中最差的部分按照原始布谷鳥搜索算法的進(jìn)化方式進(jìn)化后的位置賦值給中群中的個體。

差群中的個體對于求解最沒有參考價值，為了提升收斂速度，提升局部搜索能力，改進(jìn)算法借鑒遺傳算法，采用差群個體與優(yōu)群個體交叉的方式進(jìn)化。與精英個體交叉可以快速提升鳥窩位置的適應(yīng)度值，加速改進(jìn)算法的進(jìn)化，提升算法性能。

2.3 禁忌規(guī)則

為了避免進(jìn)入局部最優(yōu)，提升算法的全局搜索能力，引入禁忌算法中的禁忌規(guī)則。禁忌表中存放的被禁忌的解，禁忌規(guī)則為：

(1)禁忌表初始為空；

(2)當(dāng)最優(yōu)個體長期無法更優(yōu)時，進(jìn)入禁忌表；

(3)被禁忌規(guī)則：

(8)

(9)

其中：t為禁忌表中解；c為進(jìn)化的解。

(4)禁忌表有長度限制，當(dāng)更多的解進(jìn)入禁忌表時，從最先進(jìn)入的解刪除。

3 蛋白質(zhì)能量優(yōu)化

3.1 適應(yīng)度值

蛋白質(zhì)能量為一個實數(shù)值，其可以作為優(yōu)化算法的適應(yīng)度值，即：

Fit(xi)=E(xi)。

其中，xi表示第i個蛋白質(zhì)構(gòu)象位置，即氨基酸殘基位置矩陣。比如蛋白質(zhì)由n個氨基酸殘基組成，則xi可以標(biāo)為

其中(aj1， aj2， aj3)表示第j個殘基的空間位置。

3.2 氨基酸構(gòu)象位置

蛋白質(zhì)的氨基酸殘基必須在構(gòu)象空間位置，設(shè)定蛋白質(zhì)的第一個氨基酸殘基的位置為(0， 0， 0)，則第二個氨基酸殘基的位置(x， y， z)必須滿足：

x2+y2+z2=1

第三個氨基酸殘基必須滿足距離第二個氨基酸殘基位置的距離為1，以此類推。

在布谷鳥搜索算法中，鳥窩位置代表氨基酸殘基位置，但是鳥窩位置是隨機生產(chǎn)或在原有鳥窩的基礎(chǔ)上按照移動后生產(chǎn)沒有條件限制的，因此必須在初始化或進(jìn)化后的鳥窩限制在構(gòu)象空間。本文采用鳥窩與上一個氨基酸殘基的連線或連線的延長線與距離上一個氨基酸為1的球面的交點，作為初始化或進(jìn)化后的鳥窩位置。

3.3 優(yōu)化過程

步驟一，種群初始化，隨機生成n個蛋白質(zhì)；步驟二，計算蛋白質(zhì)對應(yīng)的能量值；步驟三，把蛋白質(zhì)種群根據(jù)其能量值分為優(yōu)良中差4個子群；步驟四，根據(jù)本文2.2節(jié)的進(jìn)化策略進(jìn)化蛋白質(zhì)的殘基位置；步驟五，判斷是否違反禁忌規(guī)則，若是則重新進(jìn)化；步驟六，計算進(jìn)化后的蛋白質(zhì)能量值；步驟七，進(jìn)化代數(shù)是否等于最大迭代次數(shù)，若是則進(jìn)入步驟八，若否則進(jìn)入步驟三；步驟八，輸出n個蛋白質(zhì)中的最小能量和最小能量對應(yīng)的蛋白質(zhì)殘基空間位置。

4 實驗

4.1 實驗數(shù)據(jù)

為了測試蛋白質(zhì)能量優(yōu)化方法的有效性，本文選用被大量使用的4條序列進(jìn)行測試[3-6]，測試序列如表1所示。

4.2 實驗環(huán)境

硬件：Intel(R)Pentium(R)CPUG630，6G內(nèi)存。

表1 測試序列

Table1Testsequence

長度Length序列Sequence最小能量Minimumenergy13ABBABBABABBAB-3294121BABABBABABBABBABABBAB-6198034ABBABBABABBABBABABBABABBABBABABBAB-10806055BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB-1809301

軟件：Win7 64位操作系統(tǒng)、MATLAB 2014A軟件。

各算法的參數(shù)設(shè)置：粒子群算法粒子個數(shù)設(shè)為40，學(xué)習(xí)因子設(shè)為2，慣性權(quán)重設(shè)為0.8；布谷鳥搜索算法的鳥窩個數(shù)設(shè)為40，鳥蛋被發(fā)現(xiàn)的概率設(shè)為0.2，子群的規(guī)模大小如2.2節(jié)所述。

4.3 實驗結(jié)果與分析

為了減少誤差，算法優(yōu)化獨立運行30次，然后從30次優(yōu)化結(jié)果中取最優(yōu)解、最差解、平均值和標(biāo)準(zhǔn)偏差進(jìn)行對比，其結(jié)果如表2所示。

從表2可以得知，對于維度較低的簡單問題，粒子群優(yōu)化算法和原始布谷鳥搜索算法都能夠優(yōu)化求解出蛋白質(zhì)的最小能量值，但是對于維度較高的復(fù)雜問題，粒子群和原始布谷鳥搜索算法大多只能求出較為接近最優(yōu)的值，而改進(jìn)后的布谷鳥搜索算法卻能求得最優(yōu)解，另外從平均值和標(biāo)準(zhǔn)偏差兩個指標(biāo)也可以看出改進(jìn)后的布谷鳥搜索算法更加穩(wěn)定。

表2 測試結(jié)果

Table 2 The test results

算法Methods最優(yōu)值Optimalvalue最差值Worstvalue平均值A(chǔ)verage標(biāo)準(zhǔn)偏差StandarddeviationPSO-32941-32941-329410-6198-60122-61006167E?10-10806-96931-100026425E?04-171122-15957-169978289E?01MPSO-32941-32941-329410-6198-6198-61980-10806-99865-102453294E?08-1801-1609301-1729301146E?03CS-32941-32941-329410-6198-6198-61980-10806-10806-108060-1809301-173194-179988624E?06ICS-32941-32941-329410-6198-6198-61980-10806-10806-108060-1809301-1809301-18093010

5 結(jié)論

本文提出了一種基于改進(jìn)布谷鳥搜索算法的蛋白質(zhì)能量優(yōu)化方法。該方法采用改進(jìn)布谷鳥搜索算法優(yōu)化蛋白質(zhì)能量，是人工智能算法在蛋白質(zhì)結(jié)構(gòu)研究上的應(yīng)用。改進(jìn)布谷鳥搜索算法在原始布谷鳥搜索算法的基礎(chǔ)上把單種群單進(jìn)化策略的原始布谷鳥搜索算法改進(jìn)為4個子群的4種進(jìn)化策略的智能算法，并且引入了遺傳和禁忌思想，增加了種群多樣性，提升了改進(jìn)后算法的全局搜索能力。改進(jìn)后的算法應(yīng)用在蛋白質(zhì)能量預(yù)測，其優(yōu)化效果明顯，取得了較好的優(yōu)化結(jié)果。

[1] ENGLANDER S W， MAYNE L， KAN Z Y， et al. protein folding-how and why: by hydrogen exchange, fragment separation, and mass spectrometry[J].AnnualReviewofBiophysics， 2016， 45:135-152.

[3] ZHANG X， LIN X. Protein folding prediction using an improved genetic-annealing algorithm[M]//SATTAR A， KANG B. AI 2006: Advances in artificial intelligence. AI 2006. Lecture notes in computer science， vol 4304. Berlin: Springer， 2006: 1196-1200.

[4] 郭禾， 蘭任， 陳鑫， 等. 蛋白質(zhì)折疊預(yù)測的禁忌搜索粒子群算法[J]. 計算機工程與應(yīng)用， 2011，47(24):46-50. GUO H， LAN R， CHEN X， et al. Protein folding prediction of tabu search particle swarm optimization algorithm[J].ComputerEngineeringandApplications， 2011，47(24):46-50. (in Chinese with English abstract)

[5] 張曉龍， 李婷婷， 盧進(jìn). 基于Toy模型蛋白質(zhì)折疊預(yù)測的多種群微粒群優(yōu)化算法研究[J]. 計算機科學(xué)， 2008， 35(10): 230-235. ZHANG X L， LI T T， LU J. Multiple species based on protein folding Toy model particle swarm optimization algorithm research[J].ComputerScience， 2008， 35(10): 230-235. (in Chinese with English abstract)

[6] 王麗美， 楊輝， 鐘一文. GPU加速的并行模擬退火算法在蛋白質(zhì)預(yù)測中的應(yīng)用[J]. 寧夏大學(xué)學(xué)報(自然科學(xué)版)， 2015， 36(2): 140-145. WANG L M， YANG H， ZHONG Y W. GPU acceleration parallel simulated annealing algorithm in the application of protein prediction[J].JournalofNingxiaUniversity(NaturalScienceEdition)， 2015， 36(2): 140-145. (in Chinese with English abstract)

[7] OUAARAB A， AHIOD B， YANG X S. Discrete cuckoo search algorithm for the travelling salesman problem[J].NeuralComputingandApplications， 2014， 24(7):1659-1669.

[8] SUN X， SUN W， WANG J， et al. Using a grey-markov model optimized by cuckoo search algorithm to forecast the annual foreign tourist arrivals to China[J].TourismManagement， 2016， 52: 369-379

[9] WANG J， ZHOU B. A hybrid adaptive cuckoo search optimization algorithm for the problem of chaotic systems parameter estimation[J].NeuralComputingandApplications， 2016， 27(6): 1511-1517.

[10] ELAZIM S M A， ALI E S. Optimal power system stabilizers design via cuckoo search algorithm[J].InternationalJournalofElectricalPower&EnergySystems， 2016， 75:99-107.

[11] ILUNGA-MBUYAMBA E， CRUZ-DUARTE J M， AVINA-CERVANTES J G， et al. Active contours driven by cuckoo search strategy for brain tumour images segmentation[J].ExpertSystemswithApplications， 2016， 56: 59-68.

[12] NAGANO M S， RUIZ R， LORENA L A N. A constructive genetic algorithm for permutation flowshop scheduling[J].Computers&IndustrialEngineering， 2014， 55(1):195-207.

[13] ESCOBAR J W， LINFATI R， TOTH P， et al. A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem[J].JournalofHeuristics， 2014， 20(5):1-27.

(責(zé)任編輯 張 韻)

Protein energy optimization based on cuckoo search algorithm

WANG Qingxi， ZHU Lihua

(SchoolofComputerScience&InformationEngineering，AnyangInstituteofTechnology，Anyang455000，China)

For the protein folding prediction problem， a protein energy optimization method based on cuckoo search algorithm was put forward. Firstly， the algorithm from the point of view of multi population evolutionary strategy， tabu search in the original cuckoo search algorithm， and the global search ability of cuckoo search algorithm were improved. Secondly， the problem of protein and energy by the improved cuckoo search algorithm was solved， and the minimum or feasible energy values were obtained. Finally， the feasibility and superiority of the method was proven from the comparative data of the simulation test algorithm and other algorithms.

protein; energy optimization; protein folding prediction; cuckoo search algorithm; multi swarm; tabu search

http://www.zjnyxb.cn

10.3969/j.issn.1004-1524.2017.07.22

2017-01-22

河南省科技攻關(guān)項目(162102210130)；安陽工學(xué)院科研基金項目(YJJ2016004)

王慶喜(1979—)，男，河南內(nèi)黃人，碩士，講師，主要從事生物信息學(xué)和智能算法研究。E-mail: qingxiwang1111@163.com

S13；TP18

A

1004-1524(2017)07-1216-05

浙江農(nóng)業(yè)學(xué)報ActaAgriculturaeZhejiangensis， 2017，29(7): 1216-1220

王慶喜，朱麗華. 基于布谷鳥搜索算法的蛋白質(zhì)能量優(yōu)化[J].浙江農(nóng)業(yè)學(xué)報，2017，29(7)： 1216-1220.