数据挖掘研究院( China Data Mining Research ,ChinaKDD)

　　【 以下文字转载自 Board_Apply 讨论区 】
发信人: chevalier (burn myself to warm her), 信区: Board_Apply
标  题: [范文]多序列比对与进化树间的关系
发信站: 水木社区 (Thu Sep  8 12:45:57 2005), 站内


简单回答一下polyhedron的疑问 ：）

首先，多序列比对的结果是不确定的，没有一个最终正确的解，而是根据不同的算法
和条件，会有不同的最优解(optimal)；

Clustal的算法，简单来说，是这样子的

1. 把所有n个sequences两两比对；
2. 根据Neighbor-Joining的原则以及上述计算结果，生成一个NJ Tree

接下来的步骤是源于一个技巧，就是：

每个对比后的sequence pair (alignment)都可以跟第三条序列或者另一个新的alignment
比对，这是算法上可以实现的。

所以，第三步是这样的：

假定NJ Tree 是这样的： (A,B),(C,D)

3. 首先，比对closest pair: AB；然后，比对second closest pair: CD
   最后，比对AB 和 CD， 这样得出最终的alignment结果

如果 NJ Tree 是这样的： ((A,B),C),D
那么，首先比对A,B, 然后比对 AB,C； 最后，比对ABC,D

显然，第二步得到的NJ Tree起到指导的作用，按照距离远近，用来决定下一个参与
比对的sequence 或者 alignment

4. 根据最终的alignment结果，便可以做ML(Maximum Likelihood) or MP (Maximum
 Pasimony) 进化树了。它们又有不同的算法，具体来讲，MP的原则是亲缘关系近的
序列具有较小的序列变化；而ML，顾名思义，便是具有较大的likelihood.