多序列比对

生物学术语

把两个以上字符序列对齐，逐列比较其字符的异同，使得每一列的字符尽可能一致，以发现其共同的结构特征的方法称为多序列比对。多序列比对问题是双序列比对问题的推广。

背景及意义

双序列比对是序列分析的基础·然而，对于构成基因家族的成组的序列来说，我们要建立多个序列之间的关系，这样才能揭示整个基因家族的特征·多序列比对在阐明一组相关序列的重要生物学模式方面起着相当重要的作用。

定义

为了便于描述，我们对多序列比对过程给出下面的定义。把多序列比对看作一张二维表，表中每一行代表一个序列，每一列代表一个残基的位置。将序列依照下列规则填入表中：（a）一个序列所有残基的相对位置保持不变；（b）将不同序列间相同或相似的残基放入同一列，即尽可能将序列间相同或相似残基上下对齐。我们称比对前序列中残基的位置为绝对位置。相应地，我们称比对后序列中残基的位置为相对位置。显然，同一列中所有残基的相对位置相同，而每个残基的绝对位置不同，因为它们来自不同的序列。需要说明的是，绝对位置是序列本身固有的属性，或者说是比对前的位置，而相对位置则是经过比对后的位置，也就比对过程赋予它的属性。

分类

目前,构建多序列比对模型的方法大体可以分为以下三类：

手工比对方法

手工比对方法在文献中经常看到。因为难免加入一些主观因素，手工比对通常被认为有很大的随意性。其实，即使用计算机程序进行自动比对，所得结果中的片面性也不能予以忽视。在运行经过测试并具有比较高的可信度的计算机程序基础上，结合实验结果或文献资料，对多序列比对结果进行手工修饰，应该说是非常必要的。

渐进法

渐进比对思想对于多个序列两两比对并且根据不同策略构建距离矩阵，反映序列之间的远近关系，然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权，然后从最紧密的两条序列开始，逐步引入临近的序列，并不断重新构建比对，直到所有序列都被加入为止。根据不同距离策略，主要算法有：Feng-Doolittle算法及以其为基础的改进程序包CLUSTER W,Multal，Pileup。

同步法

同步法即同时比对所有序列。首先，确定某个目标函数，使得目标函数反映出每个多序列比对的质量。目标函数值越高，比对性能越好。对于序列数目多的情况下，在所有可能的多序列比对中，找出使得目标函数值最佳的比对，是一个NP-Complete问题。目前，由同时比对10条序列的MSA程序包，还有应用于多序列比对问题的随机启发式算法，模拟退火算法，图像取样，遗传算法等。

算法复杂性

多序列比对的计算量相当可观，因此有必要分析一下算法复杂性。双序列比对所需要的计算时间和内存空间与这两个序列的长度有关，或者说正比于这两个序列长度的乘积。三序列比对则可以理解为将双序列比对的两维空间扩展到三维，即在原有二维平面上增加一条坐标轴，这样，算法复杂性就变成了三个长度的乘积。

随着序列数量的增加，算法复杂性也不断增加，对n个序列进行比对时，算法复杂性相应等于n个长度的乘积。显然，随着序列数量的增加，序列比对的算法复杂性按指数规律增长。

步骤

多序列比对一般通过3个步骤完成：

（1）两两进行双重比对。

（2）生成一系统树图（dendrogram），将序列按相似性大致地分组。

（3）使用系统树图作为引导，产生出最终的多序列比对结果。

全国各地天气预报查询

上海市

市辖区

云南省