王慶喜，朱麗華

(安陽(yáng)工學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河南 安陽(yáng) 455000)

基于布谷鳥(niǎo)搜索算法的蛋白質(zhì)能量?jī)?yōu)化

王慶喜，朱麗華

(安陽(yáng)工學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河南 安陽(yáng) 455000)

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

蛋白質(zhì)；能量?jī)?yōu)化；蛋白質(zhì)折疊預(yù)測(cè)；布谷鳥(niǎo)搜索算法；多種群；禁忌搜索

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

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

1 蛋白質(zhì)Toy模型

1.1 蛋白質(zhì)能量

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

(1)

(2)

(3)

(4)

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

1.2 蛋白質(zhì)能量?jī)?yōu)化

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

minf(x)

s.t.

(5)

x∈D。

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

1.3Toy模型

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

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

2 布谷鳥(niǎo)搜索算法

2.1 布谷鳥(niǎo)搜索算法

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

i=1，2，…，n。

(6)

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

(7)

2.2 算法改進(jìn)

2.2.1 多種群

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

2.2.2 進(jìn)化策略

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

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

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

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

2.3 禁忌規(guī)則

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

(1)禁忌表初始為空；

(2)當(dāng)最優(yōu)個(gè)體長(zhǎng)期無(wú)法更優(yōu)時(shí)，進(jìn)入禁忌表；

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

(8)

(9)

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

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

3 蛋白質(zhì)能量?jī)?yōu)化

3.1 適應(yīng)度值

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

Fit(xi)=E(xi)。

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

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

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

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

x2+y2+z2=1

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

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

3.3 優(yōu)化過(guò)程

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 實(shí)驗(yàn)環(huán)境

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

表1 測(cè)試序列

Table1Testsequence

長(zhǎng)度Length序列Sequence最小能量Minimumenergy13ABBABBABABBAB-3294121BABABBABABBABBABABBAB-6198034ABBABBABABBABBABABBABABBABBABABBAB-10806055BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB-1809301

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

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

4.3 實(shí)驗(yàn)結(jié)果與分析

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

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

表2 測(cè)試結(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)布谷鳥(niǎo)搜索算法的蛋白質(zhì)能量?jī)?yōu)化方法。該方法采用改進(jìn)布谷鳥(niǎo)搜索算法優(yōu)化蛋白質(zhì)能量，是人工智能算法在蛋白質(zhì)結(jié)構(gòu)研究上的應(yīng)用。改進(jìn)布谷鳥(niǎo)搜索算法在原始布谷鳥(niǎo)搜索算法的基礎(chǔ)上把單種群?jiǎn)芜M(jìn)化策略的原始布谷鳥(niǎo)搜索算法改進(jìn)為4個(gè)子群的4種進(jìn)化策略的智能算法，并且引入了遺傳和禁忌思想，增加了種群多樣性，提升了改進(jìn)后算法的全局搜索能力。改進(jìn)后的算法應(yīng)用在蛋白質(zhì)能量預(yù)測(cè)，其優(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ù)測(cè)的禁忌搜索粒子群算法[J]. 計(jì)算機(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ù)測(cè)的多種群微粒群優(yōu)化算法研究[J]. 計(jì)算機(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ù)測(cè)中的應(yīng)用[J]. 寧夏大學(xué)學(xué)報(bào)(自然科學(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)項(xiàng)目(162102210130)；安陽(yáng)工學(xué)院科研基金項(xiàng)目(YJJ2016004)

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

S13；TP18

A

1004-1524(2017)07-1216-05

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

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