构建进化树的方法主要分为
距离矩阵法(含 UPGMA、ME、NJ等)
最大简约法(MP)
极大似然法(ML)
贝叶斯法(Bayesian)
常用的距离法构建系统树:
不加权算术平均对方法(Unweighted Pair-Group Method using Arithmetic average, UPGMA)
最小进化距离法(Mnimal Evolution Method)
邻接法(Neighbor-Joining Method, NJ)
这一系列方法主要考量参数是:
如何计算距离,节点间的距离;cluster之间的距离;校正的距离
如何聚类?
本质上是“自下而上”或者说“聚合”的层次聚类(hclust)法,且距离的计算采用“平均距离法”。一般绘制热图,常见的表达模式聚类方法也是 hclust,往往默认“最长距离法”。两者只是cluster之间距离的计算方式不同。当所有分支的突变率相同,UPGMA效果较好。
寻找某一进化树的拓扑结构,使得全树枝长总和最短。逻辑上需要对每一个拓扑结构进行评估,当序列增加时,计算量暴增。
这个与后续提到的最大简约法(MP)的最大区别是:(1)ME法直接基于一个距离矩阵,计算的是最终进化树枝长总和最小;(2)MP法直接基于序列,计算的最终是在当前拓扑结构下,所有序列需要发生突变的位点的总和最少。
与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.... 今天,就水一文。昨天海边玩累了,今天干活也没力气,只能准备准备课件。
联系客服