群智能优化算法及其在生物信息学问题中的应用

宁静，钟一文，林娟，宁正元

（福建农林大学计算机与信息学院，福建福州350002）

群智能优化算法及其在生物信息学问题中的应用

宁静，钟一文，林娟，宁正元

（福建农林大学计算机与信息学院，福建福州350002）

生物信息学研究需要使用先进的计算工具处理大量生物的模糊的和不确定的数据。群智能优化算法以低成本、快速和准确合理地解决复杂的搜索问题的优点，使其成为一族能用以较好地解决生物信息学中的问题的启发式算法。综述群智能优化算法及其在生物信息学问题中的应用。

群智能；优化算法；生物信息学

过去几十年来，科学界所收集的有关的生物数据大规模增长，这种庞大的资源广泛存在于基因组的形式、蛋白质序列、基因表达数据等，导致我们需要有效的和高效的计算工具去存储、分析和解释这些大量的数据。

生物信息学作为应用于生物发现的计算方法的科学包括以下几个领域：生物科学、计算机科学、数学和统计学。各个领域最终目的是对生命科学有更深入的了解并且建立一个全球性视角，从此可以得出统一的生物学原理[1]。生物信息学研究的主要目标是：

（1）为探索大量生物数据集之间的关系开发算法和建立数学模型；

（2）分析和解释核苷酸和氨基酸序列、蛋白质结构域和蛋白质结构等多元的数据。

1 群智能优化算法

为能够提供一种有效存储、检索和管理大容量的生物数据库开发工具。

智能优化算法在这一领域的工作是由一组群居的昆虫（如蜜蜂、白蚁和黄蜂）的共同行为启发所产生的。这些昆虫个体的行为常常太简单，但是通过共同合作凝聚起来，却可以完成许多复杂的、生存所必需的任务，因此他们是可以呈现高度的社会组织性智能行为。一些高等哺乳类动物（如狮子）也同样具有这种群居性的社会生活。这种生物群居在一起所表现出来的集体智慧和社会行为被称为群智能（swarm intelligence，SI）。

1.1 群智能与群智能优化算法

受昆虫的社会性行为启发，研究人员通过对昆虫的社会性进行模拟，产生了一系列新的方法来解决许多传统问题，这些新的解决问题的方法就是群智能所研究得。群智能系统通常由一组可以通过改变局部环境进行彼此间的相互作用的能够执行某些操作的实体组成，这组主体能够合作进行分布问题求解。1999年，Bonabeau、Dorigo和Theraulaz给出了群智能的一种不严格定义[2]：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。

群智能优化算法中的每一个个体都需遵循以下规则：

（1）同质性：群中的每个个体具有相同的行为模式。群在没有领导者的情况下运动，即使出现了临时的领导者，群也按照其个体的行为模式运动；

（2）位置：每个个体的运动只被最接近它的群个体所影响；

（3）避免碰撞：避免与邻近的个体相碰撞；

（4）速度一致：和邻近的个体的平均速度保持一致；

（5）向中心聚集：向邻近个体的平均位置移动。

群智能优化算法的优点[3]有以下几点：

（1）分布性：群体中相互合作的个体是分布式的，不存在中心控制。这样的分布式更适合于网络环境下的工作状态；

（2）鲁棒性：系统没有集中的控制指令和数据存储，这样的系统更具有鲁棒性，不会由于某一个或者几个个体的故障而影响整个问题的求解进程；

（3）可扩充性：系统不通过个体之间的直接通信，而通过非直接通信方式进行信息的传输与合作，这样的系统具有更好的可扩充性，由于系统中个体的增加而增加的信息开销也较小；

（4）简单性：系统中每个个体的能力十分简单，每个个体的执行时间也比较短，且实现较为方便；

（5）自组织性：群体表现出来的复杂行为，是通过简单个体的交互过程突显出来的性能。

群智能为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了思路。群智能方法在大多数的优化问题的应用领域都表现出较好的性能。如多目标优化、数据分类和聚类、模式识别、电信管理、生物系统建模、信号处理、机器人控制、决策支持等领域。蚁群优化算法和粒子群优化算法是在计算智能领域已经取得成功的两种优化算法。

1.2 蚁群优化算法（ACO）

受到蚂蚁觅食时的通信机制的启发，1991年意大利学者Dorigo等人提出了蚁群优化算法(ant colony optimization，ACO)，通过候选解组成的群体进化过程来寻求最优解，解决计算机算法学中经典的NP困难问题“旅行商问题(traveling salesman problem,TSP)”[4]。

蚂蚁在觅食过程中会留下一种随时间逐渐消失的分泌物，即信息素。如果蚂蚁从巢穴到食物源所走的路径较短，则蚂蚁在走这条路径时，从巢穴到食物源再返回到巢穴所经历的时间就短，从而在相同时间内，在较短路径上蚂蚁所留下的信息素就比较多。而后面的蚂蚁要根据前面走过的蚂蚁所留下的信息素的多少选择其要走的路径。一条路径上的信息素越多，蚂蚁选择这条路径的概率就越大。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。因此，蚂蚁群体的集体觅食行为实际上构成了一种学习信息的正反馈机制，蚂蚁之间通过这种信息交流寻求从巢穴到食物源之间的最短路径,使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。蚁群优化算法正是模拟了这样的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解。

由于蚁群优化算法特有的解决方法，它已经被成功用于传统方法难以解决的非凸、非线性、非连续的优化问题，例如图的着色(graph coloring)以及最短超串(shortest common super-sequence)等问题[5]。

1.3 粒子群优化算法（PSO）

PSO算法是一种基于随机种群的优化算法[6-7]。该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于群智能（swarm intelligence,SI）的优化方法。

PSO算法有两个变型，一种是具有全局邻域，另外一种是具有局部邻域。在全局模式中，每个粒子向它最好的先前位置和向整个种群中最好的粒子所在位置移动。而在局部模式中，每个粒子向它最好的先前位置并且向在指定邻域（拓扑相邻或者空间相邻）中最好的粒子所在位置移动。

假设在N维的搜索空间中，群中的第i个粒子可以用一个N维向量Xi=（xi1，xi2，…，xiN）表示。体现粒子位置变化的粒子速度，可以由另一个N维向量Vi=（vi1，vi2，…，viN）表示。第i个粒子的最好的先前访问位置表示为Pi=（pi1，pi2，…，piN）。对于全局变量种群的最好的先前访问位置可表示为Gi=（gi1，gi2，…，giN），并用上标表示迭代的次数，依照下列的两个公式操作每一个粒子[8]：

这里j=1,2,…,N；i=1,2,…,M，M是种群的大小；ω称为惯性权重，用来控制历史上先前的速度对现在速度的影响，从而影响粒子在平衡全局和局部探测的能力；c1，c2是两个正常量，分别称为认知参数和社会参数；r1，r2是均匀分布在[0,1]上的随机数；t=1,2,…,用来决定迭代次数。公式(1)用来通过粒子的先前速度和它现在的位置与它历史最佳访问位置以及全局历史最佳访问位置的距离来计算粒子的新速度。然后依据公式(2)粒子飞向一个新的位置。

1.4 两种群智能优化算法比较

ACO与PSO的共同点：

（1）都是不确定的概率型全局优化算法；

（2）都不依赖于优化问题本身的严格数学性质（如连续性、可导性等），稳健性强；

（3）都具有本质并行性，容易并行实现，并且都容易与多种启发式算法进行结合，适当改善算法的性能；

（4）都具有自组织性和进化性；

（5）都对初始值不作要求，可以从各个点开始朝最佳值的方向搜索。

ACO与PSO的区别点：

（1）优化方式不同：PSO是每个个体通过关注自身迭代过程中的最佳值，整个种群的最优值，再结合自身状态来控制其收敛方向；ACO是通过判断信息素的大小以及同伴间的信息交流、传递来达到最优;

（2）算法机理不同：PSO是启发式算法，由迭代进行；ACO则是采用正反馈机制;

（3）主要应用范畴不同。

两种算法都有很大的改进空间。粒子群优化算法的权值和学习因子可以进行适应性改进，可以再考虑一个个体周围粒子的最佳值；蚁群优化算法的参数也可以进行适应性改进，对收敛性进行改进以及在离散域和连续域应用的改进。这些改进的主要目的是避免算法陷入局部最优，加快算法的全局收敛[9]。

2 群智能优化算法在生物信息学问题中的应用

2.1 应用群智能优化算法的若干研究问题描述

群智能优化算法的一些最新研究表明，群智能优化算法已应用到不同的生物信息学问题领域。我们相信在不久的将来群智能优化算法将超越传统的进化算法，成为在生物信息学领域不可缺少的计算方法。

（1）基因表达数据的聚类[10]。基因表达就是指细胞在生命过程中将存储在DNA序列中的遗传信息转录成mRNA再由mRNA翻译成具有生命活性的蛋白质分子的过程。随着基因芯片技术和先进生物技术的快速发展,基因芯片可以同时对大量的基因表达谱进行快速的测量分析,这就更加速了基因表达数据的产生。以SOM-PSO为例，此算法源于大脑皮层中的信息有序映射。通过此算法，高位数据投影到一维或者二维空间。通常，建立一个关于神经元的二维网格，每一个神经元代表一类。学习过程是无监督的。所有的神经元对输入模式竞争，当输入模式赢了的时候选择此神经元。PSO用来改进SOM的权重，使其避免产生不均衡的分类。（SOM-PSO，QPSO）

（2）分子对接问题（molecular docking）[11-12]。分子对接是依据“锁-钥原理”(lock and key principle)，模拟受体生物大分子与配体小分子相互作用。受体与配体相互作用是两个或多个分子之间的识别过程，这个过程涉及分子之间的空间匹配及能量匹配（静电作用力、氢键作用力、疏水作用力、范德华作用力等）。通过计算，可以预测受体与配体之间的结合模式和亲和力，是药物发现和设计中一种非常重要的方法，也是国内外前沿研究课题。使用PSO对接技术，可以获得更好的鲁棒性、准确性和收敛速度。主要优化的是分子间的能量（范德华力、氢键作用力和电势能）和分子的内部能量。有四个阶段：速度更新，粒子移动，本地搜索，更新本地和全局的最优位置。本地搜索可能通过一个预先定义的概率P1s应用于粒子。最后，如果粒子能量增加则本地和全局的最优位置更新。这些粒子有着符合灵活的对接问题的解的最小的能量。（PSO）

（3）多序列比对问题（MSA）[13]。多序列比对是指按一定的规律排列基本的DNA、RNA或蛋白质序列，找出它们之间结构、功能、进化的相似性以至于同源性。最常见的算法有FASTA和BLAST，它们都是基于序列两两比对的。解决多序列比对问题的方法有：Pileup算法、Clustalw算法、Carrillo-Lipman算法以及DCA算法。这些算法是通过渐进的比对思想，或者是采用迭代比对算法。两两比对的局部结果在多序列比对中往往并不最优，这样会给多序列比对带来错误信息，并且这些错误信息不能在后期阶段被纠正。而蚁群优化算法的信息素的正反馈作用可以有效解决多序列比对问题，并且提高多序列比对的正确性。（ACO）

（4）系统发育树的构造[14]。系统发育树构建问题近似于标准的TSP问题。可以将每个分支群和一个虚拟城市简单的联系起来，并定义两个城市之间的距离为生物数据矩阵中一对相应的分类群的数据。这方面已经有很成熟的软件，如MEGA、PAUP、PHYLIP、MOLPHY、PAML等，MATLAB中的Bioinformatics Toolbox也有建立系统发育树的功能。（ACO）

（5）RNA二级结构的预测[15]。RNA二级结构是指由小内环中断的长茎环结构（发夹结构、凸起和内环）。RNA分子的二级机构可以通过计算所有不同氢键和域的组合的最小自由能（MFE）结构来计算的预测。可以用改进的粒子群优化算法来优化RNA分子结构（SetPSO，由Neethling和Engelbrecht提出）。一个有效的RNA二级结构（重叠或茎）需要满足一些约束，比如每个残基只能与一个标准基配对、不允许有假结等。收集所有满足条件的茎组成集合U。SetPSO中的每一个粒子初始化为从U中随机选择的子集。这些粒子的位置和速度，根据改进的加减算子以RNA结构定义下的热力学自由能函数极小化的原理进行更新。此算法可以得到一个在多重基准下的RNA分子近似最优的结构。（PSO）

（6）蛋白质二级结构的预测[16-17]。蛋白质二级结构指蛋白质多肽链本身通过氢键沿一定方向进行折叠和盘绕的方式。二级结构主要有α-螺旋、β-折叠、β-转角。由于所涉及的蛋白质折叠过程非常复杂，并且只有部分理解的简化模型（如亲-疏水格点模型（HP））成为研究蛋白质的主要手段之一。但是其优化问题是一个非确定型的多项式问题，难以计算。蚂蚁在给定蛋白质序列随机选择一个起点，从这个起点出发，蛋白质序列每一次像两个方向折叠并增加一个氨基酸记号，这样就构成一个给定蛋白质序列的候选构型，可以用于本地搜索以实现进一步的改进，并且最终在更新信息素的基础上找到优质的解。蚁群系统集成为一个意味着由传递局部最小和防止过早收敛组成的本地搜索元素。还可以采用多蚁群优化（MACOS）算法，多个人工蚂蚁群落并行解决HP蛋白质折叠问题。（ACO）

（7）序列拼接问题（FAP）[18]。FAP基本上是一个置换问题，类似于TSP问题，不同之处在于噪音、个体之间的特殊关系等等。在本质上FAP也是一个典型的NP完全问题。在单重叠群等问题中蚁群优化算法优于考虑多重叠群问题的最近邻启发式算法。（ACO）

2.2 群智能优化算法的进一步研究方向

还有许多可以应用群智能优化算法进行研究的方向，现在几乎还没有什么研究进展。在这些方面发表的论文数量很少，但是对未来的生物信息学研究有着重大的意义。我们注意到，群智能优化算法尚未应用到计算生物学的NP困难问题中去，这些问题迄今都没有得到普遍可接受的解。这些问题有：

（1）识别基因调控网络[19]。生物信息学研究领域中最具有挑战性的问题之一就是从基于DNA微阵列技术得到的基因表达数据中推断基因调控网络。可以用PSO非常有效地解决基因调控网络的识别问题。每个粒子代表所有基因表达水平的实际价值。每个基因相对于另一个基因都有不同的特定表达水平。因此N个基因相当于有N2个表达水平。粒子的适应性可以从生成表达模式（表达模式的和）与目标表达模式的绝对误差计算出来。（PSO）

（2）蛋白质三级结构的预测和折叠[17,20]。一旦蛋白质序列已经确定，推断其独特的三维天然结构是一项艰巨的任务。它需要完整的用从头的方法接近蛋白质三维结构预测。从头折叠的过程可分为两部分：设计一个计分函数来从错误的（非天然的）结构中区分出正确的/好的（天然的或者接近天然的）结构；设计一个搜索方法探索构象空间。（PSO）

（3）不同基因之间的代谢途径的描述[21]。描述代谢途径的目标是估计一组“最佳”的参数值，最大限度地减少过程数据和代谢网络模型之间的错误。这个参数估计问题可以归为一个非凸的非线性的优化问题，因此可以使用全局优化技术解决。（PSO）

（4）计算机辅助分子设计（CAMD）[22-24]。如药物设计开发——群智能优化算法可以帮助设计一个配体分子，这个配体分子可以结合到目标蛋白的活性位点上。（ACO）

3 总结与展望

随着对基因组序列的注释形成的数据爆炸性的增长，生物信息学已成为一门具有挑战性和令人着迷的科学领域。它提出完美和谐的统计、生物学和计算智能方法来分析和处理在基因、DNA、RNA和蛋白质形式存储的生物信息。此外群智能优化算法可以为研究人员对一些NP困难的问题在现实世界中寻找近似的最佳解决方案提供有力的帮助，获得了广泛的普及。生物信息学的问题很少需要精确的最佳解决方案，只需要强大的、快速的、近似的最佳解决方案。生物信息学的文献调查显示，这个领域需要有快速而强大的搜索机制来解决大量的问题。属于这一类的问题包括多序列比对（MSA），蛋白质二级和三级结构的预测，蛋白配体对接，启动子识别和进化树重构等。古典确定性搜索算法和衍生为基础的优化技术对这些问题是没有用的，因为它们的搜索空间可能会非常巨大并且是断点不连续的。群智能优化算法提供了一批多Agent并行搜索技术来非常有效的解决这类生物信息学相关问题。

[1]孙啸，陆祖宏，谢建明.生物信息学基础[M].北京：清华大学出版社，2005.

[2]BONABEAU E,DORIGO M,THERAULAZ G.Swarm intelligence：from natural to artificial systems[M].New York：Oxford University Press,1999.

[3]张青，康立山，李大农.群智能算法及应用[J].黄冈师范学院学报,2008,28(6)：44-48.

[4]CLOLRNI A,DORIGO M,MANIEZZO V.Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life.London：MIT Press,1991：134–142.

[5]武飞周,薛源.智能算法综述[J].工程地质计算机应用,2005(2)：9-15.

[6]KENNEDY J,EBERHART R.Particle swarm optimization[C]//IEEE Intl Conf on Neural Networks.Australia：Perth, 1995：1942–1948,

[7]EBERHART R,KENNEDY J.A new optimizer using particle swarm theory[C]//Proc of the Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan：1995：39–43,

[8]SHI Y,EBERHART R.Parameter selection in particle swarm optimization[C]//Proceedings of the Seventh Annual Conference on Evolutionary Programming.USA：New York,1998：591–600.

[9]尤晓清,邱矩平,林苗,等.仿生智能算法的比较分析[J].福建电脑,2009,25(1)：13-14.

[10]高倩倩.基因表达数据的聚类算法研究及其实现[D].无锡：江南大学,2009.

[11]何书萍,李凡长.一个基于量子群的分子对接药物设计算法[J].南京大学学报：自然科学版,2008,44(5)：512-519.

[12]段爱霞,陈晶,刘宏德,等.分子对接方法的应用与发展[J].分析科学学报,2009,25(4)：473-477

[13]宁正元.计算机在生物科学研究中的应用[M].厦门：厦门大学出版社,2006.

[14]宁静,钟一文,宁正元,等.基于rbcL蛋白质序列的石斛属植物系统发育研究[J].漳州师范学院学报：自然科学版, 2011(4)：34-39.

[15]宁正元,林世强.RNA二级结构预测方法[J].福建农林大学学报：自然科学版,2007,36(1)：60-63.

[16]宁正元,林世强.蛋白质结构的预测及其应用[J].福建农林大学学报：自然科学版,2006,：309-310.

[17]殷志祥.蛋白质结构预测方法的研究进展[J].计算机工程与应用,2004,40(20)：54-57.

[18]涂俐兰,王能超,陈莹,等.生物序列拼接及其算法[J].生命科学研究,2003,7(2)：79-82.

[19]蒋炜,彭新一,周育人.基于改进PSO的基因调控网络重构方法[J].计算机工程,2009,35(20)：181-183.

[20]宁静.蛋白质结构预测的多agent模拟退火算法研究[D].福州：福建农林大学,2012.

[21]吕丽丽,余永红,孙俊,等.代谢途径智能优化的研究[J].计算机仿真,2011,28(11)：205-209.

[22]徐筱杰,侯廷军,乔学斌,等.计算机辅助药物分子设计[M]．北京：化学工业出版社,2004.

[23]李洪林,沈建华,王希诚,等.虚拟筛选与新药发现[J].生命科学,2005,17(2)：125-131.

[24]冯毅.生物信息学在药物研发中的应用与展望[J].西部医学,2007,19(5)：971-973.

[25]王翼飞,史定华.生物信息学—智能化算法及其应用[M].北京：化学工业出版社,2005.

[26]宁正元,黄伟奇.生物数据标准化，从HTML到RDF[J].福建农林大学学报：自然科学版,2007,36(2)：208-214.

[27]宁正元,王爱荣,王宗华,等.拟南芥DNA-J结构域蛋白的生物信息学分析及其亚细胞定位验证[J].福建农林大学学报：自然科学版，2007,36(4)：427-434.

[28]钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践，2006，26(6)：88-94.

[29]钟一文,蔡荣英,宁正元,等.一种改进的离散粒子群优化算法[J].小型微型计算机系统，2006，7(10)：1893-1896.

[30]王秀丽,宁正元.基于动态适应度的独立任务调度算法[J].计算机应用,2006,26(12)：3001-3003

[31]宁正元,黄健,钟一文,等.异构环境独立任务分配的导引式局部搜索算法[J].集美大学学报：自然科学版,2006,11 (2)：177-181.

An Overview of Swarm Intelligence Algorithms and Their Applications in Bioinformatics

NING Jing,ZHONG Yi-wen,LIN Juan,NING Zheng-yuan
(Computer and Information College,Fujian Agriculture and Forestry University,Fuzhou 350002,China)

Bioinformatics research requires the use of advanced computational tools to deal with a large number of biological vague and uncertain data.With the advantages of low cost,solving complex search problems fast,accurately and reasonably,swarm intelligence optimization algorithms become a group of heuristic algorithms which can be used to get a better solution to the bioinformatics problems.An overview of swarm intelligence optimization algorithms and their applications in bioinformatics are provided in this paper.

swarm intelligence;optimization algorithm;bioinformatics

TP301.6

A

1673-4343（2013）04-0013-06

2013-05-09

福建省自然科学基金（2008J0316）

宁静，女，陕西咸阳人，助理实验师。研究方向：智能计算、计算生物。通讯作者:宁正元，男，陕西武功人，教授。