回顾 | 系统进化树构建的常见方法

构建进化树的方法主要分为

1. 距离矩阵法（含 UPGMA、ME、NJ等）

2. 最大简约法（MP）

3. 极大似然法（ML）

4. 贝叶斯法（Bayesian）

基于距离的进化树构建方法

常用的距离法构建系统树：

1. 不加权算术平均对方法（Unweighted Pair-Group Method using Arithmetic average, UPGMA）

2. 最小进化距离法（Mnimal Evolution Method）

3. 邻接法（Neighbor-Joining Method, NJ）

这一系列方法主要考量参数是：

1. 如何计算距离，节点间的距离；cluster之间的距离；校正的距离

2. 如何聚类？

UPGMA 法

本质上是“自下而上”或者说“聚合”的层次聚类（hclust）法，且距离的计算采用“平均距离法”。一般绘制热图，常见的表达模式聚类方法也是 hclust，往往默认“最长距离法”。两者只是cluster之间距离的计算方式不同。当所有分支的突变率相同，UPGMA效果较好。

最小进化法（ME）

寻找某一进化树的拓扑结构，使得全树枝长总和最短。逻辑上需要对每一个拓扑结构进行评估，当序列增加时，计算量暴增。

这个与后续提到的最大简约法（MP）的最大区别是：（1）ME法直接基于一个距离矩阵，计算的是最终进化树枝长总和最小；（2）MP法直接基于序列，计算的最终是在当前拓扑结构下，所有序列需要发生突变的位点的总和最少。

邻接法（NJ）

与UPGMA几乎相反，UPGMA约等于层次聚类的聚合法；而NJ法从拓扑结构的变化上来看，与层次聚类的分离法比较像。当然还是有比较大的区别。层次聚类的分离实现考量的是分离后两个cluster的内部距离总和最小。NJ法考量的是分离出来的两个leaf node的校正距离最小。这一校正距离综合考量了每个leaf node以及cluster的距离。在距离计算上的实现，逻辑上比层次聚类的分离法要简单一些。简单实现了一下，似乎还是跟UPGMA法类似，NJ法计算逻辑其实还是跟层次聚类的聚合法比较像。最大的区别，仍然是距离的计算。但是，在不少资料中翻阅，图示上似乎不是这个画法。
简单摘菜已报道文稿的NJ法实现逻辑，代码就不摆了。写完之后，感觉跟写TBtools的热图聚类逻辑类似，效率上还是不太行。估计还是要想想办法重构代码。感兴趣的朋友也可以参考Nei老爷子的论文（同样重磅的还有他的NG86算法，计算dnds的....可以说是目前最常用方法之一）。简单来说，就是都挺准，但又容易实现，且很快，着实大神级别。

百度的时候发现国内有不少关于NJ法的小改进，当然都是很多年前。我猛然发现，对于经典算法的实现阐述，新的算法改进论文写得更清晰。当然可能是 typeset 的问题。毕竟现在的印刷和公式编辑都比以前方便得多。

（注：dlk 应是笔误，应为 dik）

最大简约法

距离法的主要特点是距离实质是序列两两之间的距离，在进化树构建的构建的过程中，逻辑上不存在距离重新计算，直接导入一个距离矩阵即可建树。最大简约法考量的距离具体到每条序列的每个位点。拓扑结果改变时，序列两两间两位点的所需的突变次数同样变化。最大简约法遍历所有拓扑结构，并寻求全局位点突变次数最小的一个。

极大似然法

Emmm，突然不想写了。极大似然法确实没时间捋明白，还没做过代码实现。大体认知，拿着进化模型来看不同拓扑结构（进化树）出现的可能性。可能性越大也就越准确。当然，这里的问题就还是哪个模型合适，这个还是要算一算的。拿错模型的话....
ML法跟MP法逻辑上都是要遍历所有树，当然，一般情况下....还是用 UPGMA 或者 NJ 建个树，作为起始树，然后改吧改吧，看看结果是不是更优，直到似乎找不到更优，就认为当前最优。于是，出现局部最优，逻辑合理。

贝叶斯法

至今未用过.... 明明是干一个事情，一定要把方法搞得越复杂越好，参数越多，模型就流弊。当我们把固定参数变成分布，ML就变成bayesian....

写在最后

Emmm.... 今天，就水一文。昨天海边玩累了，今天干活也没力气，只能准备准备课件。