54调和序列 多序列比对的最终结果可以用一个调和序列( consensus)表示,有时也称假想序列 ( pseudo- sequence),通常加在比对后所有序列的下面。这一调和序列的残基是由对应的同 列残基归纳而得到。 调和序列只是多序列比结果的一种表示方式。还可以用权重矩阵来表示比对结果,如 下面将要介绍的序列谱方法。而 BLOCKS数据库则是找出比对结果中没有空位出现的保守 模块),并把它们转化成位置特异性分数矩阵。而 PRINTS数据库则用人工方法从比对结果 中找出所有没有空位的序列模体,其长度一般较短,并依此建立一个非加权的分数矩阵。这 些方法在第3章和第8章中分别予以详细讨论。 55算法复杂性 多序列比对的计算量相当可观,因此有必要分析以下技术的复杂性。双序列比对所需 要的计算时间和内存空间与这两个序列的长度有关,或者说正比于这两个序列长度的乘积, 用O(mm2)表示。其中m、m2是指两条序列的长度。三序列比对则可以理解为将双序列 比对的两维空间扩展到三维,即在原有二维平面上增加一条坐标轴。这样算法复杂性就变成 了O(mm2m3),其中m3表示第三条序列的长度。 随着序列数量的增加,算法复杂性也不断增加。我们用O(mm2m3.mn)表示对n个 序列进行比对时的算法复杂性,其中mn是最后一条序列的长度。若序列长度相差不大,则 可简化成O(m2),其中n表示序列的数目,m表示序列的长度。显然,随着序列数量的增 加,序列比对的算法复杂性按指数规律增长。 降低算法复杂性,是研究多序列比对的一个重要方面。为此,产生了不少很有实用意 义的多序列比对算法。这些方法的特点是利用启发式( heuristics)算法降低算法复杂性,以 获得一个较为满意但并不一定是最优的比对结果,用来找出子序列、构建进化树、查找保守 序列或序列模板,以及进行聚类( clustering)分析等。有的算法将动态规划和启发性算法结 合起来。例如,对所有的序列进行两两比对,将所有的序列与某个特定的序列进行比对,根 据某种给定的亲源树进行分组比对,等等。必须指出,上述方法求得的结果通常不是最优解, 至少需要经过n-1次双序列比对,其中n为参与比对的序列个数 56手工比对方法 工比对方法在文献中经常看到。因为难免加入一些主观因素,手工比对通常被认为 有很大的随意性。其实,即使用计算机程序进行自动比对,所得结果中的片面性也不能予以 忽视。在运行经过测试并具有比较高的可信度的计算机程序基础上,结合实验结果或文献资 料,对多序列比对结果进行手工修饰,应该说是非常必要的。 多序列比对的软件已经有许多,其中一些带有编辑程序。最好的办法是将自动比对程 序和编辑器整合在一起。为了便于进行交互式手工比对,通常使用不同颜色表示具有不同特 性的残基,以帮助判别序列之间的相似性。颜色的选择十分重要,如果使用不当,看起来不 很直观,就会使比对结果中一些有用的信息丢失。相反,如果选择得当,就能从序列比对结 果中迅速找到某些重要的结构模式和功能位点。例如,如果用某种颜色表示一组高度保守的 残基,则某个序列的某一位点发生突变时,则由于颜色不同,就可以很快找出。颜色的选择 可以根据主观愿望和喜好,但最好和常规方法一致。用来构筑三维模型的按时氨基酸残基组 件和三维分子图形软件所用的颜色分类方法,比较容易为大家接受(表73) 表53基酸分组方法和代表性颜色 残基种类 残基特性 颜色 Asp(D), Glu(e) 酸性 红色 His(h), Arg(R), Lys(k) 碱性 兰色 Ser(S), Thr(T), Asn(N), Gln(Q) 极性 绿色5.4 调和序列 多序列比对的最终结果可以用一个调和序列（consensus）表示，有时也称假想序列 （pseudo-sequence），通常加在比对后所有序列的下面。这一调和序列的残基是由对应的同 一列残基归纳而得到。 调和序列只是多序列比结果的一种表示方式。还可以用权重矩阵来表示比对结果，如 下面将要介绍的序列谱方法。而 BLOCKS 数据库则是找出比对结果中没有空位出现的保守 模块），并把它们转化成位置特异性分数矩阵。而 PRINTS 数据库则用人工方法从比对结果 中找出所有没有空位的序列模体，其长度一般较短，并依此建立一个非加权的分数矩阵。这 些方法在第 3 章和第 8 章中分别予以详细讨论。 5.5 算法复杂性 多序列比对的计算量相当可观，因此有必要分析以下技术的复杂性。双序列比对所需 要的计算时间和内存空间与这两个序列的长度有关，或者说正比于这两个序列长度的乘积， 用 O（m1m2）表示。其中 m1、m2 是指两条序列的长度。三序列比对则可以理解为将双序列 比对的两维空间扩展到三维，即在原有二维平面上增加一条坐标轴。这样算法复杂性就变成 了 O（m1m2m3），其中 m3 表示第三条序列的长度。 随着序列数量的增加，算法复杂性也不断增加。我们用 O（m1m2m3…mn）表示对 n 个 序列进行比对时的算法复杂性，其中 mn 是最后一条序列的长度。若序列长度相差不大，则 可简化成 O（mn ），其中 n 表示序列的数目，m 表示序列的长度。显然，随着序列数量的增 加，序列比对的算法复杂性按指数规律增长。 降低算法复杂性，是研究多序列比对的一个重要方面。为此，产生了不少很有实用意 义的多序列比对算法。这些方法的特点是利用启发式（heuristics）算法降低算法复杂性，以 获得一个较为满意但并不一定是最优的比对结果，用来找出子序列、构建进化树、查找保守 序列或序列模板，以及进行聚类（clustering）分析等。有的算法将动态规划和启发性算法结 合起来。例如，对所有的序列进行两两比对，将所有的序列与某个特定的序列进行比对，根 据某种给定的亲源树进行分组比对，等等。必须指出，上述方法求得的结果通常不是最优解， 至少需要经过 n-1 次双序列比对，其中 n 为参与比对的序列个数。 5.6 手工比对方法 手工比对方法在文献中经常看到。因为难免加入一些主观因素，手工比对通常被认为 有很大的随意性。其实，即使用计算机程序进行自动比对，所得结果中的片面性也不能予以 忽视。在运行经过测试并具有比较高的可信度的计算机程序基础上，结合实验结果或文献资 料，对多序列比对结果进行手工修饰，应该说是非常必要的。 多序列比对的软件已经有许多，其中一些带有编辑程序。最好的办法是将自动比对程 序和编辑器整合在一起。为了便于进行交互式手工比对，通常使用不同颜色表示具有不同特 性的残基，以帮助判别序列之间的相似性。颜色的选择十分重要，如果使用不当，看起来不 很直观，就会使比对结果中一些有用的信息丢失。相反，如果选择得当，就能从序列比对结 果中迅速找到某些重要的结构模式和功能位点。例如，如果用某种颜色表示一组高度保守的 残基，则某个序列的某一位点发生突变时，则由于颜色不同，就可以很快找出。颜色的选择 可以根据主观愿望和喜好，但最好和常规方法一致。用来构筑三维模型的按时氨基酸残基组 件和三维分子图形软件所用的颜色分类方法，比较容易为大家接受（表 7.3）。 表 5.3 氨基酸分组方法和代表性颜色 残基种类 残基特性 颜色 Asp (D), Glu (E) 酸性 红色 His (H), Arg (R), Lys (K) 碱性 兰色 Ser (S), Thr (T), Asn (N), Gln (Q) 极性 绿色