摘要：多重序列比对是生物信息学特别是生物序列分析中一个重要的基本操作。提出求解多重序列比对问题的蚁群算法，利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中，蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中字符的概率，通过信息素的更新与调节相结合的策略较为有效地解决了局部收敛的问题，加强了算法寻求全局最优解的能力。另外在该算法的基础上，提出了基于分治策略的多序列比对蚁群求解算法，不但减少了原算法的计算时间，而且显著改善了算法所求得的解的质量。
关键词：生物信息学； 多重序列比对；蚁群算法； 分治策略
1引言
多序列比对是生物信息学及计算分子生物学中的一个重要问题，是基因识别、蛋白质结构预测、生物进化树的构建、基因组信息分析等问题中用到的一个基本操作。通过序列比对可以探索生物序列中所包含的功能、结构和进化信息。在生物信息学中，最常见的比对是蛋白质序列之间或核酸序列之间的比对。
假设我们已经发现一个基因并且知道它的功能，我们可以将它与基因组数据库中所有的序列片段进行比对，如果某个序列与该基因很相似，则可能它们的功能也相似，并且它们可能是同源序列。通过同源序列的多重比对能够发现与功能相关的保守序列片段，对于一系列同源蛋白质，人们希望研究隐含在蛋白质序列中的系统发育关系，以便更好地理解这些蛋白质的进化。在实际研究中，生物学家着重于研究相关蛋白质序列中的保守区域，进而分析蛋白质的结构和功能。所以要发现多个序列的共性，必须同时比对多条同源序列。
序列比对也可以用来发现遗传疾病的病因。我们可以将一些健康者的基因序列与一些疾病患者的基因序列进行比对，如果疾病患者的基因都有共同的某种变异，而没有一个健康者的基因含有这种变异，则很明显，这种变异是该疾病的病因。
通过多序列比对可以得到一个序列家族的序列特征。当给定一个新序列时，根据序列特征可以判断序列是否属于该家族。进行多序列比对后，可以对比对结果进行进一步处理，如构建序列的特征模式，将序列聚类构建分子进化树等。总之，序列比对是生物信息学中一个非常重要的基本操作。
多序列比对的目标是发现多个序列的共性。简单来说，就是对于输入的多条序列插入空位并排列比对，使其达到相同的长度，并使得序列之间匹配字符的个数尽可能地多，而不匹配字符和空位（Gap）的个数尽可能地少。为了反映序列比对的质量，要有一个定量的标准来度量它们之间的相似程度，我们可以通过计分函数来评估多重序列比对的质量。在实际计算中，SumofPairs（SP）模型是应用最为广泛的计分方法，该函数将所有两两序列比对得分的和作为多序列比对的得分。对于两个序列比对的分值，传统的基于编辑距离的计算方法是将比对中所有列（即字符对）的得分求和作为两个序列比对的得分。其中对于非空位字符对的打分，通常我们可以根据打分矩阵（Scoring Matrix）得出，最常用到的打分矩阵有PAM系列矩阵以及BLOSUM系列矩阵。
2多序列比对
序列比对的目标是分析序列的相似性，推测其结构功能及进化上的联系，序列比对问题是基因识别、结构预测、分子进化、生命起源研究的基础。最常见的比对是多个蛋白质序列或多个DNA序列同时进行比较，因而形成了多重序列比对问题。
在解决多重序列比对问题时，要解决两个问题：①如何根据包括结构信息在内的生物学意义对给定比对打分;②在打分机制确定的情况下，如何求得分值最高的最优比对。问题①要依据生物学的知识和实际问题的需要来决定。本文提出的基于蚁群的多重序列比对算法主要是用来求解问题②，即在计分机制确定的前提下，对于给定的多条序列寻找使得分值最高的最优比对。
