多序列比对算法综述

王樱 李锡辉

【摘要】在生物信息学中，如何对多组基因序列进行有效且快速的比对一直都是热门课题之一，也是至今仍未解决的NP难题之一。本文详细介绍序列比对的背景与意义，并针对几种常用的多序列比对算法进行比较，并提出了多序列比对算法研究的方向。

【关键词】生物信息学序列比对动态规划算法

一、背景与意义

随着人类基因组计划的顺利实施和信息技术的迅速发展，GeneBank、EMBL和DDBJ国际三大核酸序列数据库数据量呈指数增长。生物学家、数学家和计算机科学家都面临着一个相同的并且严峻的问题，如何利用、表达这些数据进而分析与解释基因序列间的潜在关系，从中发掘出对人类有利的信息。为迎接挑战，一门涉及生物、数学、物理、化学、计算机科学等诸多科学的新型学科应运而生，并且日益成为二十一世纪自然科学的核心领域之一。

生物信息学的主要研究对象是DNA序列和蛋白质序列，主要通过分类、分析和检索核苷酸序列或氨基酸序列，获取基因编码和调控、代谢途径、DNA和蛋白质结构功能及其相互关系等各方面的知识。所以在生命起源、生物进化以及细胞、器官和个体的出现、生长、病变、消亡等生命科学问题中，生物信息学都起着非常重要的作用。生物信息学是发现生命科学问题中的基本规律和时空联系，发掘生物序列数据中蕴含的生物学意义的交叉学科[1]。

在生物信息学中，序列比对是最基本、最重要的操作。对于基因序列，通过比对可以推测出哪个基因家族可能包含该序列，并可以推测出该序列可能具有的生物学功能；对于蛋白质序列，通过比对可以推测出该序列可能的功能和结构，并可以找出与它同源的蛋白质序列。所以在生物信息学中，序列比对具有非常重要的意义和实用价值。目前，国际上提出了众多经典的比对算法，也开发了众多的序列比对软件。但对于同一组序列，不同的软件采用不同的序列比对算法，其运算速度和比对结果都有很大差异。有些软件考虑了比对结果而运行时间较长，而有些软件运算速度很快比对结果却不理想。一般情况下两者不能同时兼得。所以，对于序列比对算法的研究还有待继续深入。

二、多序列比对的研究現状及发展趋势

多序列比对是双序列比对的一般性推广。由于核酸数据库容量的增长呈指数级，序列比对的数量通常都会远远大于两个，使用动态规划算法来解决比对问题已经是不可行的了，这使得多序列比对成为一NP难题。为了解决这一难题，人们提出了许多近似算法。

2.1动态规划算法

多序列比对最早采用的是动态规划算法来解决。动态规划算法中最为经典的是Needleman-Wunsch算法，其解决思路是把整个问题分解成多个相互联系的子问题，通过依次解决每个子问题，从而解决整个问题。动态规划算法最初用于求解两个序列的比对，当把动态规划的基本思想推广到多序列比对时，3个很短序列的比对还可以顺利进行。比对序列的数量如果超过3个，由于需要很大的存储空间和很长的运行时间，比对根本无法进行下去。所以多序列比对问题不能采用动态规划算法来解决。Carrillo和Lipman等人对该算法进行了改进，提出了Carrillo-Lipman算法，通过减少存储空间将序列比对的数量提高到10。2004年，唐玉荣等人对动态规划算法进行了优化[2]，与基本动态规划法敏感性相同，但降低了算法的时间复杂度，并在减少存储空间方面也有一定的效果。

2.2启发式算法

目前，绝大多数算法属于启发式算法，包括星比对算法，渐进式比对算法，迭代细化方法等。其中应用最早的是星比对算法，而应用最广并且效果较好的是渐进式比对算法。Hogeweg和Hesper首先提出渐进式比对算法，而后Feng和Taylor对其加以完善。与动态规划算法相比，该算法在计算速度、存储空间和序列数目等方面都更加优良。并且，渐进式比对算法能够直接用于构造进化树，反映序列间的进化关系。2005年，段敏等人提出了一种用减少序列比对过程中总评分的方法来达到局部优化目的的多序列比对算法[3]。启发式算法虽然在一定层度上减少了算法的运行时间和存储空间，但都有一些不足之处。星比对算法中，无论采用何种方法并不能保证找到的序列是最好的中心序列。渐进式比对算法中，构造的指导树有时不一定真正反映系统的进化信息，根据指导树渐进比对容易产生局部最优化问题。迭代细化算法中，无法采用何种迭代策略得到的结果最优。

2.3随机算法

多序列比对中，应用最多的随机算法有遗传算法、模拟退火算法和粒子群算法等。遗传算法是一种全局意义上的自适应随机搜索方法，它借鉴生物进化规律，模拟生物进化过程中的一系列事件，包括突变、交配和选择，最终得到一个优化解。模拟退火算法则是模拟物理中的退火过程并结合复杂系统中的组合优化之间的相似性来寻找最优解。2008年，向昌盛等人提出了将遗传算法和模拟退火算法相结合的遗传退火进化思想[4]，设计了运用该思想进行多序列比对的算法过程，实验结果表明该算法是行之有效的。2011年，徐小俊等人针对粒子群优化易陷入局部最优、收敛速度慢的现象，提出了一种分段取值惯性权重（SW）方法[5]，该方法在解决多序列比对问题时可以有效地避免算法早熟，并提高解的精度。

2.4分治算法

分治算法是把一个大问题分解成若干个小问题来解决。Stoye提出了一种新的分治算法DCA，将Carrillo-Lipman算法引入进来。在不影响特征表现的前提下，把序列分割成完全满足Carrillo-Lipman算法长度要求的子序列，使用Carrillo-Lipman算法进行序列比对。2000年Stoye又提出了一种OMA算法，以达到减少存储空间的目的。2009年，业宁等人设计了一个DCA-ClustalW算法来解决多序列比对问题[6]，从纵向和横向两个方面将复杂问题简单化，并在BaliBase基准数据集上测试了算法的可行性。

2.5其他算法

2006年，陈娟等人给出了多重序列比对的蚁群算法[7]，结果显示蚁群算法可以有效解决多重序列比对问题并具有自适应性、鲁棒性等特点。而文献[8，9]针对蚁群算法易于陷入局部最优解、收敛速度慢等问题，提出了改进的方法。

三、结论

生物信息学中最基本和最核心的问题之一就是多序列比对。由于多序列比对处理的数据越来越庞大和复杂，所以其算法对计算精度和运算速度的要求也越来越高。如何能快速有效的获得比对的结果，一直苦恼着众多的学者们。

参考文献

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

[2]唐玉荣，一种优化的生物序列比对算法.计算机工程与设计，2004，25（11）：1936-1945

[3]段敏，许龙飞.生物DNA序列比对算法研究.佳木斯大学学报，2005，23（2）：153-158

[4]向昌盛，周建军，周子英.模拟退火遗传算法在生物多序列比对中的应用.湖南农业科学，2008，（4）：29-34

[5]徐小俊，雷秀娟，郭玲.基于SWGPSO算法的多序列比对.计算机工程，2011，37（6）：184-186

[6]业宁，张倩倩，许翠云.一种多序列比对分值算法DCA-ClustalW.计算机与数学工程，2010，38（11）：30-33

[7]陈娟，陈.多重序列比对的蚁群算法.计算机应用，2006，26（6）：124-128

[8]彭东海，骆嘉伟，袁辉勇.基于改进蚁群算法的多序列比对.计算机工程与应用，2009，45（33）：114-119

[9]李方洁，刘希玉.基于渐进蚁群算法的DNA多序列比对.网络安全技术与应用，2010，（9）：78-80