基于布谷鸟搜索算法的蛋白质能量优化

王庆喜，朱丽华

(安阳工学院 计算机科学与信息工程学院，河南 安阳 455000)

基于布谷鸟搜索算法的蛋白质能量优化

王庆喜，朱丽华

(安阳工学院 计算机科学与信息工程学院，河南 安阳 455000)

针对蛋白质折叠预测问题，提出了一种基于布谷鸟搜索算法的蛋白质能量优化方法。该方法首先对原始布谷鸟搜索算法从多种群、进化策略和禁忌搜索等多个角度进行改进，提升了布谷鸟搜索算法的全局搜索能力；改进了布谷鸟搜索算法求解蛋白质能量问题；取得了蛋白质能量的最小值或是可行值。对算法的仿真测试以及与其他算法的数据进行对比，证明本文蛋白质能量优化方法的可行性和优越性。

蛋白质；能量优化；蛋白质折叠预测；布谷鸟搜索算法；多种群；禁忌搜索

蛋白质的一级结构决定了蛋白质的空间结构，而空间折叠结构决定了蛋白质的生物功能，因此蛋白质折叠预测在生物学领域具有重要意义[1]。但是蛋白质折叠预测是一个典型的非确定性多项式问题，随着氨基酸序列的增多，其计算量呈指数级增加，成为生物信息学中的一个具有挑战的研究课题。蛋白质折叠预测问题[2]是在已知氨基酸残基序列的情况下，求解蛋白质的最小能量以及最小能量对应的构象。蛋白质最小能量求解也称为蛋白质能量优化，其在蛋白质折叠预测中起到了基础和决定作用，因此蛋白质折叠预测问题的核心是使用全局优化算法进行蛋白质能量优化。到目前为止，已经有很多学者尝试使用不同的算法优化蛋白质能量，比如文献[3-6]分别采用遗传算法、禁忌搜索算法、微粒群优化算法、模拟退火算法等算法对蛋白质能量优化，取得了较好效果，但是上述算法受限于原始算法的搜索能力，蛋白质能量优化效果仍有可以提升的空间。

布谷鸟搜索算法是新型启发式群体智能算法，于2009年被提出后，已经被证明具有强大的全局搜索能力和收敛性能[7]，并且被广泛应用于各个领域。文献[8-11]采用布谷鸟搜索算法分别求解优化游客数量预测、系统参数、系统稳定性设计和图像分割等问题，取得了良好效果。本文使用布谷鸟搜索算法优化蛋白质能量，为了提升优化效果，还对原始布谷鸟搜索算法进行了较大改进。

1 蛋白质Toy模型

1.1 蛋白质能量

蛋白质能量由主链的弯曲势能和不相邻残基之间的引力势能组成，其数学模型[2]可以表示如下。

(1)

(2)

(3)

(4)

其中：E为蛋白质能量；E1为蛋白质弯曲势能；E2为不相邻残基之间的引力；rij为残基之间的空间距离。

1.2 蛋白质能量优化

蛋白质能量优化是在蛋白质氨基酸残基的构象空间内求解蛋白质的最小能量值，问题数学定义[3]为：

minf(x)

s.t.

(5)

x∈D。

其中：f(x)为蛋白质能量；D为构象空间；minf(x)为蛋白质能量的最小值，或称为最小能量值。

1.3Toy模型

Toy模型是一种简化的蛋白质模型[5]，由A和B两种氨基酸组成，其中A表示疏水性氨基酸(hydrophobic)，B表示亲水性氨基酸(hydrophilic)。其中，三个氨基酸的连线角度可以自己变换。n个氨基酸形成n-2个键角，分别用θ2，θ3，…，θn-1表示。把前三个氨基酸形成的平面记为XOY，则两个氨基酸的连线与XOY形成的n-3个夹角，分别表示为β3，β4，…βn-1。结合蛋白质能量公式，可以推导出在Toy模型中的蛋白质能量优化为：

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

2 布谷鸟搜索算法

2.1 布谷鸟搜索算法

布谷鸟搜索算法[7]是仿生布谷鸟寄生繁殖的自然现象而开发的群体性智能进化算法。算法进化模型为[10]：

i=1，2，…，n。

(6)

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

(7)

2.2 算法改进

2.2.1 多种群

原始布谷鸟搜索算法采用单一种群，而改进算法采用4个种群，具体为在鸟窝位置初始化以及每次进化后，都会根据鸟窝位置的适应度值将鸟窝分为4类(4个子群)，分别为优群、良群、中群、差群，4个子种群采用不同的策略进化。其优点是可以兼顾算法的局部搜索和全局搜索能力，在两者之间取得平衡。经过多次实验发现，4个子群的比例分别为10%、30%、40%、20%时，可以取得较好效果。

2.2.2 进化策略

优群中的个体是群体中的精英，是适应度值最好的一个子群体，他们是整个群体的目标，但是因为复杂问题中有很多局部最优点，群体中的精英也有可能是局部最优位置或其附近位置，若是如此，则算法就是陷入局部最优，这是智能优化算法常见的现象，也是算法改进需要解决的核心问题。为了能够跳出局部最优，本文借鉴遗传算法[12]和禁忌搜索算法[13]，采用变异和禁忌两种方式对优群中的个体进行优化。对于多次迭代无法进化到更优位置的鸟窝采用变异处理，防止陷入局部最优，并且为了提升跳出局部最优的概率，设立禁忌表。

良好中的个体适应度值虽然不是最优，但是在大多数情况下仍是可以接受的解，为了增加收敛能力，改进算法采用原始布谷鸟的进化方式。

中群中的个体值在很大意义上，无法满足求解需要，为了增加种群中的个体多样性，提升寻得全局最优的概率，改进算法采用适应度值差的个体进化获得，即采用种群中最差的部分按照原始布谷鸟搜索算法的进化方式进化后的位置赋值给中群中的个体。

差群中的个体对于求解最没有参考价值，为了提升收敛速度，提升局部搜索能力，改进算法借鉴遗传算法，采用差群个体与优群个体交叉的方式进化。与精英个体交叉可以快速提升鸟窝位置的适应度值，加速改进算法的进化，提升算法性能。

2.3 禁忌规则

为了避免进入局部最优，提升算法的全局搜索能力，引入禁忌算法中的禁忌规则。禁忌表中存放的被禁忌的解，禁忌规则为：

(1)禁忌表初始为空；

(2)当最优个体长期无法更优时，进入禁忌表；

(3)被禁忌规则：

(8)

(9)

其中：t为禁忌表中解；c为进化的解。

(4)禁忌表有长度限制，当更多的解进入禁忌表时，从最先进入的解删除。

3 蛋白质能量优化

3.1 适应度值

蛋白质能量为一个实数值，其可以作为优化算法的适应度值，即：

Fit(xi)=E(xi)。

其中，xi表示第i个蛋白质构象位置，即氨基酸残基位置矩阵。比如蛋白质由n个氨基酸残基组成，则xi可以标为

其中(aj1， aj2， aj3)表示第j个残基的空间位置。

3.2 氨基酸构象位置

蛋白质的氨基酸残基必须在构象空间位置，设定蛋白质的第一个氨基酸残基的位置为(0， 0， 0)，则第二个氨基酸残基的位置(x， y， z)必须满足：

x2+y2+z2=1

第三个氨基酸残基必须满足距离第二个氨基酸残基位置的距离为1，以此类推。

在布谷鸟搜索算法中，鸟窝位置代表氨基酸残基位置，但是鸟窝位置是随机生产或在原有鸟窝的基础上按照移动后生产没有条件限制的，因此必须在初始化或进化后的鸟窝限制在构象空间。本文采用鸟窝与上一个氨基酸残基的连线或连线的延长线与距离上一个氨基酸为1的球面的交点，作为初始化或进化后的鸟窝位置。

3.3 优化过程

步骤一，种群初始化，随机生成n个蛋白质；步骤二，计算蛋白质对应的能量值；步骤三，把蛋白质种群根据其能量值分为优良中差4个子群；步骤四，根据本文2.2节的进化策略进化蛋白质的残基位置；步骤五，判断是否违反禁忌规则，若是则重新进化；步骤六，计算进化后的蛋白质能量值；步骤七，进化代数是否等于最大迭代次数，若是则进入步骤八，若否则进入步骤三；步骤八，输出n个蛋白质中的最小能量和最小能量对应的蛋白质残基空间位置。

4 实验

4.1 实验数据

为了测试蛋白质能量优化方法的有效性，本文选用被大量使用的4条序列进行测试[3-6]，测试序列如表1所示。

4.2 实验环境

硬件：Intel(R)Pentium(R)CPUG630，6G内存。

表1 测试序列

Table1Testsequence

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

软件：Win7 64位操作系统、MATLAB 2014A软件。

各算法的参数设置：粒子群算法粒子个数设为40，学习因子设为2，惯性权重设为0.8；布谷鸟搜索算法的鸟窝个数设为40，鸟蛋被发现的概率设为0.2，子群的规模大小如2.2节所述。

4.3 实验结果与分析

为了减少误差，算法优化独立运行30次，然后从30次优化结果中取最优解、最差解、平均值和标准偏差进行对比，其结果如表2所示。

从表2可以得知，对于维度较低的简单问题，粒子群优化算法和原始布谷鸟搜索算法都能够优化求解出蛋白质的最小能量值，但是对于维度较高的复杂问题，粒子群和原始布谷鸟搜索算法大多只能求出较为接近最优的值，而改进后的布谷鸟搜索算法却能求得最优解，另外从平均值和标准偏差两个指标也可以看出改进后的布谷鸟搜索算法更加稳定。

表2 测试结果

Table 2 The test results

算法Methods最优值Optimalvalue最差值Worstvalue平均值Average标准偏差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 结论

本文提出了一种基于改进布谷鸟搜索算法的蛋白质能量优化方法。该方法采用改进布谷鸟搜索算法优化蛋白质能量，是人工智能算法在蛋白质结构研究上的应用。改进布谷鸟搜索算法在原始布谷鸟搜索算法的基础上把单种群单进化策略的原始布谷鸟搜索算法改进为4个子群的4种进化策略的智能算法，并且引入了遗传和禁忌思想，增加了种群多样性，提升了改进后算法的全局搜索能力。改进后的算法应用在蛋白质能量预测，其优化效果明显，取得了较好的优化结果。

[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] 郭禾， 兰任， 陈鑫， 等. 蛋白质折叠预测的禁忌搜索粒子群算法[J]. 计算机工程与应用， 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] 张晓龙， 李婷婷， 卢进. 基于Toy模型蛋白质折叠预测的多种群微粒群优化算法研究[J]. 计算机科学， 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加速的并行模拟退火算法在蛋白质预测中的应用[J]. 宁夏大学学报(自然科学版)， 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.

(责任编辑 张 韵)

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

河南省科技攻关项目(162102210130)；安阳工学院科研基金项目(YJJ2016004)

王庆喜(1979—)，男，河南内黄人，硕士，讲师，主要从事生物信息学和智能算法研究。E-mail: qingxiwang1111@163.com

S13；TP18

A

1004-1524(2017)07-1216-05

浙江农业学报ActaAgriculturaeZhejiangensis， 2017，29(7): 1216-1220

王庆喜，朱丽华. 基于布谷鸟搜索算法的蛋白质能量优化[J].浙江农业学报，2017，29(7)： 1216-1220.