序列比对：多序列比对与MAFFT

序列比对

当研究一条DNA或蛋白质序列时，主要关注的是其包含的遗传信息；当研究两条或多条DNA或蛋白质序列时，则主要关注不同序列之间的差别与联系。在生物信息学中，对生物大分子的序列比对是非常基本的工作。

上一篇文章双序列比对与BLAST介绍了两条序列之间进行比对的算法原理及其实现方法，双序列比对常用于同源分析、蛋白质结构推断、相似片段搜寻与数据库比对检索、基因注释等。当我们对三条及三条以上的序列进行合并分析时，则常需要进行多序列比对，多序列比对是系统发育分析、祖先序列重建、寻找蛋白结构域等分析的基础。

多序列比对是指三个或三个以上序列字符同步分析，通过插入空格等方法使字符对齐，并逐列比较其字符的异同，以发现其共同的结构特征的方法。需要注意的是多序列比对问题是双序列比对问题的推广，并非多条序列之间两两比对。

多序列比对的目标是使得参与比对的序列中有尽可能多的列具有相同的字符，以便于发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系，主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。

多序列比对算法

相比于双序列比对，多序列比对涉及的记分方法、替换记分矩阵、比对算法等都要更为复杂。多序列比对有以下四个要素：

A择一组能进行比对的序列（要求是同源序列），例如不同物种的16S rDNA或是其他同类型的基因；

B选择一个实现比对与计分的算法与软件；

C确定软件的参数；

D合理地解释比对的结果；

⑴动态规划算法

标准动态规划算法可以直接由二维的双序列比对推广到多维，且能够确保全局比对产生最优的解。考虑m个长度为n的序列进行多序列比对，首先基于二维的推广其算法复杂度有一个O(nm)项；其次在关于最优得分S的推导时其有m个序列则有2m-1个前导项，例如对于三序列（u、v、w）比对有以下7个前导项：

因此标准动态规划法多序列比对的算法复杂度高达O(nm2m)，这使得标准动态规划算法进行大量较长的多序列比对十分困难。因此，后续研究开发了该算法的多种变体，来对比对进行优化。

S. Altschul等人在1989年提出了基于动态规划算法的一个变体，它能极大地缩小k维动态规划表的搜索空间。该算法通常采用SP记分法（SP，sum of pairs，其定义为列中所有字符的配对记分的和），并使用动态规划法搜索子空间的交汇来找到多序列比对在k维空间中的路径，对程序采用启发式算法，以降低运算复杂度。

⑵渐进多序列比对

渐进多序列比对（progressive multiple alignment）又称步进法，从动态规划算法优化而来，实质上也是一种启发式算法。渐进多序列比对首先使用动态规划算法构建全部k个序列的个双序列配对比对，然后以记分最高的配对比对作为多序列比对的种子，按记分高低依次选择序列，逐渐向已构造的多序列比对中加入序列，形成一个树状结构的多序列比对结果。该方法的优点是允许高达数百个序列的比对，计算步骤如下：

①使用动态规划法构建序列之间的两两比对，使用距离矩阵来描述序列之间的关联性；

②由距离矩阵构造指导树（guide tree），反映了参与比对的序列之间的关联，用来确定向多序列比对中添加新序列的次序；

③以计分最高的配对比对作为多序列比对的种子，并根据指导树向这对序列的比对中插入序列，一步步构建完整的多序列比对。

该方法的思想就是先分析序列之间的两两关系，然后由近及远依次引入新序列构造多序列比对，在引入新序列的过程中，其原则为空格一旦引入则始终保存，因此最终结果取决于序列加入的次序，具有比对的最优性不受保证的缺点。并且，渐进多序列比对可能会被一些伪强的、实际上是坏的种子所误导。如果一开始选择的两条序列比对与实际上的最优多序列比对不一致，那么初始的配对比对中的错误在整个多序列比对构造中始终存在并持续传播；在比对的任何阶段出现的失配时，这些失配不会被纠正而是被传播到最终结果；最糟糕的情况是配对比对可能无法组成一个相容的多序列比对，如下所示：

以上因素使渐进多序列比对对于距离较近的序列效果很好，而当序列间的距离较远时效果不佳。后期的渐进多序列比对软件对这些缺陷进行了改进。

⑶迭代法

在渐进多序列比对中，一个序列一经加入其构造的比对结果便不再重新处理，因此在渐进比对过程中出现的错误或不适当的计分没有机会进行更正，这提高比对效率的同时牺牲了准确性。迭代法则能克服这个不足，其基本过程是先用渐进多序列比对产生一个初始结果，再对序列的不同子集进行反复比对并利用这些结果重新进行多序列比对，目标是改进多序列比对的总记分值。迭代法常常使用随机搜索或者通过对比对结果进行重排来寻找更优的解，迭代持续到比对记分值不再提高。迭代法能够克服渐进多序列比对的缺陷，但需要耗费更多运算。

⑷基于一致性的方法

一致性指的是对于序列x、y和z，如果xi比对于zk且zk比对于yj，则xi应比对于yj。此算法的基本特点是充分利用多个序列间的比对信息对配对比对进行更合理的计分，也即根据xi和yj同时比对于zk而调整xi和yj的比对计分，如果序列x中的字符xi比对于序列y中的字符yj的似然率（likelihood）为P(xi~yj|x, y)，则有：

P(xi~yj|x, y, z)≈∑P(xi~zk|x, z) P(yj~ zk|y, z)

基于一致性的方法在多序列比对中对每对序列中的每对字符计算如上的似然率，得到似然率矩阵。根据基准测试数据的研究基于一致性方法的多序列比对产生的结果经常比渐进多序列比对更加准确。

除了以上算法外，多序列比对算法还有隐马尔可夫模型（Hidden Markov models）、遗传算法（Genetic algorithms）、模拟退火算法（simulated annealing）、仿真量子计算（Simulated quantum computing）、基于结构比对等。

多序列比对工具

动态规划算法的工具有MSA；渐进多序列比对算法的工具有Clustal家族（包括Clustalx和Clustalw；迭代法工具有PRRN/PRRP、DIALIGN、MUSCLE以及目前最常用的MAFFT；基于一致性算法的工具有ProbCons和MergeAlign，此外还有T-Coffee系列软件。

MAFFT（http://mafft.cbrc.jp/alignment/software/）为常用的多序列比对工具，最简单的使用方法如下所示：

mafft multi_protein.faa > multi_protein.align

该软件参数众多，但提供了精确度不同的三个常用模式，以适用不同数据集大小、序列保守性的场景：

mafft --maxiterate 1000 --localpair  in > out
#最准确的方法，适合小于200条，且长度小于2000aa/nt的序列
mafft --maxiterate 1000 --genafpair  in > out
#长度相似的保守序列的比对，适合小于200条，且长度小于2000aa/nt的序列
mafft --maxiterate 1000 --globalpair in > out
#包含较大非匹配区域的非保守序列的比对，适合小于200条，且长度小于2000aa/nt的序列

以上序列条数和长度要求非绝对，超过界限则需要很多计算量。对保守性较强的核糖体蛋白序列进行比对：

mafft --maxiterate 1000 --thread 21 --genafpair rpL14.faa > rpL14.align

END