基于改进的蚁群算法的多序列比对

来源:用户上传      作者: 亓新建

　　摘要：该文将蚁群算法进行了改进，将其应用于多序列比对，只根据信息素的强度对序列比对进行信息素强度的局部和全局动态更新，在避免了多序列比对容易陷入局部最优解的前提下，提高了收敛速度。同时，本算法应用在多序列比对中的最大优势是减少了传统算法在多序列比对问题中的生成系统树的步骤，减少了多序列比对过程的复杂度，在没有降低比对结果精确度的同时，提高了比对效率。
　　关键词：蚁群算法；信息素；多序列比对；比对效率
　　中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)06-1374-03
　　多序列比对（Multiple sequence alignment）是把两条以上有可能有系统进化关系的序列同时进行比对，在识别具有功能、结构重要性的局部保守区中具有极其重要的意义，同时多序列比对还可以辅助检查一个序列家族中的全局相似性和进化亲缘关系。在SP比对(sum-of-all-pairs or SP alignment)模型上求解最优多序列比对已经被证明是NP-hard问题[1~5]。
　　蚁群算法(Ant Colony Optimization,简称ACO)又称蚂蚁算法，是一种模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，是20世纪90年代由意大利的学者M.Dorigo,V. Maniez-zo,A. Colorni等人首先提出来的[6~8]。十几年来的研究成果已经表明：蚁群算法采用的正反馈并行自催化机制，具有优良的分布式计算机制、较强的鲁棒性、易于与其他方法结合等优点，用于组合优化具有很强的发现较好解的能力，在解决许多复杂优化问题方面已经展现出了其优异的性能和巨大的发展潜力，在动态环境中也表现出了高度的灵活性和健壮性。目前，蚁群算法在国际智能计算领域中的应用研究备受关注，并已成为前沿性课题[9]。然而，蚁群算法也存在着易陷于局部最优解、搜索时间长等缺陷，因此，不少学者也提出了各种改进算法，目的在于弥补基本蚁群算法的不足之处，有效地提高其收敛速度。
　　本文将蚁群算法进行改进并应用到了多序列比对中，只根据信息素强度对序列比对进行信息素强度的局部和全局动态更新，在避免了多序列比对容易陷入局部最优解的前提下，提高了收敛速度。
　　 1基于蚁群算法的多序列比对
　　打分函数
　　对于一个序列S，|S|是S中的字符个数，S[i]是S的第i个字符。Ω是确定S的有限字符集（如DNA序列由4中核糖核酸A,T,C,G确定，即Ω={A,T,C,G}），基因序列在突变中的变化包括替换、插入和删除，我们用‘-’来表示插入或删除所产生的一个空位。对于x,y∈Ω?{-},定义一个简单的打分函数如下：
　　其中：公式（8）表示m只蚂蚁都完成一次循环后的全局信息素更新后的信息素强度；公式（9）表示m只蚂蚁都完成一次循环后的需要加强的信息素强度；公式（10）表示此次循环中一只蚂蚁走完路径后的需要加强的信息素强度。
　　第五步：如果算法尚未满足结束条件，即尚未达到设定的循环次数计数器，m只蚂蚁进入下一次循环，即进行下次序列比对。反之，输出最理想的序列比对结果，结束算法。
　　 3仿真实验
　　下面针对标准Bali BASE库中的数据集合进行了实验。Bali BASE库是一个多序列比对库，其中有144个测试用例(包含1000多条序列)，根据各序列的特征，将比对用例分成五个子集[10]，如表2。
　　 4结束语
　　本文对蚁群算法进行了改进，应用在多序列比对中。在算法中，信息素、位置偏差及字符匹配得分等因素决定了蚂蚁选择各序列中下一字符的概率，通过信息素强度的局部和全局更新策略，有效的解决了该算法局部收敛的问题，加强了寻求全局最优解的能力。其最大优势是减少了传统算法在多序列比对中的生成系统发育树的步骤，降低了该算法在多序列比对中的复杂度，在没有降低比对结果精确度的同时，提高了比对效率。
　　参考文献：
　　[1] JIANG T, XU Y, ZHANG M Q. Current Topics in Computational Molecular Biology[M].北京:清华大学出版社, 2002.
　　[2] Bonizzoni P, Della Vedova G. The complexity of multiple sequence alignment with SP-score that is metric[J]. Theoretical Computer Sci? ence, 2001, 259(1-2):63-79.
　　[3] WANG L, JIANG T. On the complexity of multiple sequence alignment[J]. J Comput. Biol., 1994,1:337-348.
　　[4] JIANG T, Lawler E L, WANG L. Aligning sequences via an evolutional tree:complexity and approximation[A]. Proc. 26th ACM Symp. on Theory of Computing [C]. New York:ACM Press,1994. 760-769.
　　[5] LI M, MA B, WANG L. Finding similar regions in many strings[A]. Proc 31 st ACM Symp. on Theory of Computing[C], New York:ACM Press, 1999,473-482.
　　[6] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. In: Varela F, Bourgine P, eds. Proc. of the ECAL’91 European Conf. of Artificial Life. Paris: Elsevier, 1991. 134-144.
　　[7] Dortgo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony cooperating Agents. IEEE Trans. on Systems, Man, and Cybernet? ics Part B: Cybernetics, 1996,26(1):29-41.
　　[8] Dortgo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. on Evolu? tionary Computation, 1997,1(l):53-66.
　　[9]段海滨.蚁群算法原理及其应用[M].北京:科学出版社, 2005,34-35,119,141-142.
　　[10] Julie D. Thompson, Frederic Plewniak and Olivier Poch. A comprehensive comparison of multiple sequence alignment programs. Nucle? ic Acids Research.1999,27(13):2689-2690.

转载注明来源:https://www.xzbu.com/8/view-1683767.htm