浅谈 Neighbor-joining

在生物信息学中，邻连法（Neighbor-joining）是由 Naruya saiitou 和 Masatoshi Nei 于1987年提出的一种自下而上(聚集性)的聚类方法，用于创建系统发育树。该算法构建树通常用于基于 DNA 或蛋白质序列数据，需要知道每对类群(例如，物种或序列)之间的距离，以形成树。

邻接法以距离矩阵作为输入，表示每对类群之间的距离。该算法从一个完全未解析的树（A）开始，它的拓扑结构对应于星形网络，并迭代以下步骤，直到树完全解析并知道所有分支长度：

1. 基于当前的距离矩阵计算矩阵Q （n为taxa个数）；

img

1. 在Q(i,j)种寻找到最小值，并将两个点（taxa）连接到一个新的中间节点（u）；例如将f,g连接到新的u，u为中间节点；
2. 计算每个类群到这个新节点的距离；例如计算a-e节点到新节点u之间的距离
3. 计算taxa之外的一些节点到新节点的距离；例如计算w到v的距离
4. 迭代上述过程，用新节点替换连接的邻居对，并使用前一步计算的距离。

img

示例介绍

假设有5个taxa（a，b，c，d，e），得到每个类群之间的距离矩阵 D。

第一步

第一次连接

计算矩阵Q1 ，得到每一对类群的Q值，找到最小的值将其连接为一个新的节点。其中Q1(a,b)是最小的，我们将 a 和 b 连接。

img

img

第一个分支长度的估计

将 a 和 b 的连接点称为 u；计算 a 和 b 到 u 的分支长度。

img

第一次更新距离矩阵

重新计算其他所有taxa点到新的节点u的距离，将距离矩阵 D 更新为距离矩阵 D'。

img

第二步

计算Q2矩阵

根据第一步的公式计算得到Q2矩阵，如下图，将值最小的点连接起来。我们将连接 u 和 c 或者 d 和 e。

img

计算分支长度

将 u 和 c连接起来得到新的中间节点 v ，计算分支长度。

img

更新距离矩阵

根据新的中间节点 v 更新每个taxa点到v的距离，得到新的距离矩阵 D2。

img

迭代直到得到树的拓扑结构

这个简单的树我们迭代到第三次就得到了树的拓扑结构。计算新的矩阵Q3，找到矩阵的最小值，将其连接。如下矩阵Q3，我们将 v 与 d 连接得到最后的节点 w 。在计算 v和 d 到 w 的分支长度。最终完成树的构建。

img

img