Neighbor-Joining算法

快速概览

Neighbor-Joining（NJ）是一种不依赖分子钟假设的距离矩阵建树算法，通过最小化总树长来选择邻居对，是目前最常用的系统发育树构建方法之一。

核心思想是通过Q矩阵找到能最小化总树长的邻居对
不要求分子钟假设，适用于演化速率不均匀的数据
产生无根树，是理解现代系统发育分析的关键算法

所属板块 分析方向与案例

把基础对象与算法方法重新放回真实分析任务与工作流。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

问题定义

Neighbor-Joining系统发育重建问题：

给定一个 $n \times n$ 距离矩阵，构建一棵总树长最小的无根系统发育树。

输入： $n \times n$ 距离矩阵 $D = (d_{ij})$ ，不要求满足分子钟假设

输出：一棵无根树 $T$ ，使得总树长 $\sum_{e \in E(T)} \text{length}(e)$ 最小化，且对于任意两个叶子 $i$ 和 $j$ ，树上路径长度接近 $D_{ij}$

1. Neighbor-Joining 的直觉：寻找真正的”邻居”

与 UPGMA 不同，Neighbor-Joining (NJ) 不要求分子钟假设。它允许不同分支以完全不同的速率演化。

核心动机

在可加性树（Additive Tree）中，一对”邻居”是指连接到同一个内部节点的两个叶子节点。NJ 的目标就是通过一种巧妙的评分方式，在每一步迭代中”捕获”这对真正的邻居。

如何定义”近”？

简单的距离 $D_{ij}$ 可能会误导我们（例如，两个演化极快的物种虽然距离远，但在拓扑上可能是邻居）。因此，NJ 引入了一个衡量标准：两个节点不仅要彼此接近，还要与其他节点尽可能远离。

这导致了 Q 矩阵 的诞生： $Q_{ij} = (n-2)d_{ij} - \sum d_{ik} - \sum d_{jk}$

$d_{ij}$ 小（彼此近）且总偏差大（离别人远）的这对节点将获得最小的 $Q$ 值，成为合并的首选。

2. 算法流程

NJ解决的是：

当不同分支演化速率不均匀时，如何从距离矩阵构建正确的系统发育树
如何避免UPGMA在分子钟假设不满足时产生的错误拓扑
在不引入复杂概率模型的情况下，如何获得鲁棒的系统发育推断

为什么重要

NJ的重要性体现在：

实用性：是目前最常用的距离矩阵建树方法之一
鲁棒性：对分子钟假设不满足的情况表现良好
理论基础：提供了最小化树长的明确优化目标
广泛使用：被集成在PHYLIP、MEGA、RAxML等主流工具中

核心思想

邻居对（neighbor pair）: 在树中直接连接到同一个内部节点的两个叶子节点。
Q矩阵: 用于评估哪一对节点应该成为邻居的评分矩阵，Q值越小表示该对越可能是邻居。
总树长最小化: NJ通过选择使总树长最小的邻居对来逐步构建树，这是其理论依据。

算法直觉

NJ的构建过程可以理解为：

每次迭代选择一对”最像邻居”的节点
将这对节点连接到一个新的内部节点
计算新节点到其他节点的距离，更新距离矩阵
重复直到只剩两个节点

判断”最像邻居”的标准是：如果两个节点是邻居，那么它们到其他所有节点的距离之和应该相对较小。

数学模型

Q矩阵定义

对于距离矩阵D，定义Q矩阵：

Q_{ij} = (n-2) \cdot d_{ij} - \sum_{k=1}^{n} d_{ik} - \sum_{k=1}^{n} d_{jk}

其中：

n是当前节点的数量
$d_{ij}$ 是节点i和j之间的距离
$Q_{ij}$ 越小，表示i和j越可能是邻居

总 divergence 计算

对于每个节点i，计算其总divergence（到其他所有节点的距离之和）：

r_i = \sum_{k=1}^{n} d_{ik}

分支长度计算

当选择节点i和j作为邻居对时：

新节点u到i的分支长度： $L_{ui} = \frac{1}{2} d_{ij} + \frac{1}{2(n-2)} (r_i - r_j)$
新节点u到j的分支长度： $L_{uj} = \frac{1}{2} d_{ij} + \frac{1}{2(n-2)} (r_j - r_i)$

距离矩阵更新

创建新节点u后，u到其他节点k的距离为：

d_{uk} = \frac{1}{2} (d_{ik} + d_{jk} - d_{ij})

算法步骤

算法1：Neighbor-Joining

输入：距离矩阵 D（n个节点）
输出：无根系统发育树

1. 初始化：每个节点 i 是一个叶子节点
2. while 节点数量 > 2:
   a. 计算每个节点的总divergence：r_i = sum(d_ij for all j)
   b. 计算Q矩阵：Q_ij = (n-2)·d_ij - r_i - r_j
   c. 找到Q矩阵中的最小值Q_min = min(Q_ij)
   d. 选择对应的节点对（i, j） 作为邻居
   e. 创建新节点 u
   f. 计算分支长度：
      - L_ui = 0.5·d_ij + (r_i - r_j) / (2·(n-2))
      - L_uj = 0.5·d_ij + (r_j - r_i) / (2·(n-2))
   g. 更新距离矩阵：
      - 删除节点 i 和 j
      - 添加新节点 u
      - 对于每个其他节点 k，计算 d_uk = 0.5·(d_ik + d_jk - d_ij)
   h. n = n - 1
3. 连接最后两个节点，完成树的构建
4. 返回构建的无根树

时间复杂度： $O(n^3)$

每次迭代计算Q矩阵： $O(n^2)$
每次迭代更新距离矩阵： $O(n)$
共有 n-2 次迭代

空间复杂度： $O(n^2)$ 用于存储距离矩阵

示例

考虑4个样本A、B、C、D，距离矩阵如下：

	A	B	C	D
A	0	7	11	14
B	7	0	6	9
C	11	6	0	7
D	14	9	7	0

迭代1（n=4）

步骤1：计算总divergence

$r_A = 0 + 7 + 11 + 14 = 32$
$r_B = 7 + 0 + 6 + 9 = 22$
$r_C = 11 + 6 + 0 + 7 = 24$
$r_D = 14 + 9 + 7 + 0 = 30$

步骤2：计算Q矩阵

对于每对节点，计算 $Q_{ij} = (n-2)·d_{ij} - r_i - r_j = 2·d_{ij} - r_i - r_j$

$Q_{AB} = 2·7 - 32 - 22 = 14 - 54 = -40$
$Q_{AC} = 2·11 - 32 - 24 = 22 - 56 = -34$
$Q_{AD} = 2·14 - 32 - 30 = 28 - 62 = -34$
$Q_{BC} = 2·6 - 22 - 24 = 12 - 46 = -34$
$Q_{BD} = 2·9 - 22 - 30 = 18 - 52 = -34$
$Q_{CD} = 2·7 - 24 - 30 = 14 - 54 = -40$

Q矩阵：

	A	B	C	D
A	-	-40	-34	-34
B	-40	-	-34	-34
C	-34	-34	-	-40
D	-34	-34	-40	-

步骤3：找到最小Q值

最小值是-40，对应的邻居对是（A, B）和（C, D）
选择（A, B）作为第一个邻居对（任意选择）

步骤4：计算分支长度

$L_{uA} = 0.5·7 + (32 - 22) / (2·2) = 3.5 + 2.5 = 6$
$L_{uB} = 0.5·7 + (22 - 32) / (2·2) = 3.5 - 2.5 = 1$

步骤5：更新距离矩阵

创建新节点u，计算u到其他节点的距离：

$d_{uC} = 0.5·(11 + 6 - 7) = 0.5·10 = 5$
$d_{uD} = 0.5·(14 + 9 - 7) = 0.5·16 = 8$

新距离矩阵：

	u	C	D
u	0	5	8
C	5	0	7
D	8	7	0

迭代2（n=3）

步骤1：计算总divergence

$r_u = 0 + 5 + 8 = 13$
$r_C = 5 + 0 + 7 = 12$
$r_D = 8 + 7 + 0 = 15$

步骤2：计算Q矩阵

对于n=3， $Q_{ij} = (n-2)·d_{ij} - r_i - r_j = 1·d_{ij} - r_i - r_j$

$Q_{uC} = 5 - 13 - 12 = -20$
$Q_{uD} = 8 - 13 - 15 = -20$
$Q_{CD} = 7 - 12 - 15 = -20$

步骤3：找到最小Q值

所有Q值都是-20，选择（u, C）作为邻居对

步骤4：计算分支长度

$L_{vu} = 0.5·5 + (13 - 12) / (2·1) = 2.5 + 0.5 = 3$
$L_{vC} = 0.5·5 + (12 - 13) / (2·1) = 2.5 - 0.5 = 2$

步骤5：更新距离矩阵

创建新节点v，计算v到D的距离：

$d_{vD} = 0.5·(8 + 7 - 5) = 0.5·10 = 5$

迭代3（n=2）

连接最后两个节点v和D：

$L_{vD} = 5$

最终树结构

这是一棵无根树，可以任意选择根节点来获得有根树。

复杂度分析

时间复杂度

初始化： $O(n^2)$
每次迭代：
- 计算divergence： $O(n^2)$
- 计算Q矩阵： $O(n^2)$
- 寻找最小值： $O(n^2)$
- 更新距离矩阵： $O(n)$
总时间复杂度： $O(n^3)$

空间复杂度

存储距离矩阵： $O(n^2)$
存储Q矩阵： $O(n^2)$
存储树结构： $O(n)$
总空间复杂度： $O(n^2)$

与UPGMA的比较

维度	UPGMA	Neighbor-Joining
分子钟假设	要求	不要求
树的类型	有根树	无根树
优化目标	层次聚类	最小化总树长
适用场景	演化速率恒定	演化速率不均匀
计算复杂度	O(n³)	O(n³)
鲁棒性	较差	较好

为什么NJ不依赖分子钟假设

NJ通过分支长度的调整来处理演化速率不均匀的问题：

当两个节点的divergence差异较大时，说明其中之一演化较快
NJ通过调整分支长度来补偿这种差异
Q矩阵的设计使得算法能识别真正的邻居关系，而不受演化速率差异的影响

适用场景

适合使用NJ的情况

不同分支演化速率差异较大
需要无根树拓扑
距离矩阵不完全满足additive条件
需要鲁棒的系统发育推断

不适合使用NJ的情况

数据量非常大（NJ的O(n³)复杂度可能成为瓶颈）
需要考虑更复杂的演化模型
位点级别的信息很重要（此时应考虑Maximum Likelihood或Bayesian方法）

优缺点总结

优点

不依赖分子钟假设，适用范围广
产生无根树，灵活性高
最小化树长的理论依据明确
对噪声和距离估计误差相对鲁棒
实现简单，广泛可用

缺点

时间复杂度O(n³)，对大规模数据较慢
只使用距离信息，丢失位点级细节
当距离矩阵质量差时，结果可能不准确
无法直接处理缺失数据

与真实工具的连接

NJ在真实生物信息学工具中的应用：

PHYLIP：neighbor程序实现NJ算法
MEGA：提供NJ作为主要的建树方法
RAxML：虽然主要是ML方法，但也支持快速NJ作为初始化
FastME：针对NJ的优化实现，支持大规模数据

现代系统发育分析中，NJ常用于：

快速构建初步系统发育树
作为Maximum Likelihood的初始化
大规模数据集的快速分析

算法变体

FastNJ

FastNJ是NJ的优化版本，通过：

使用更高效的数据结构
近似计算Q矩阵
并行化处理

将时间复杂度降低到接近O(n²)。

BioNJ

BioNJ是对NJ的改进，主要改进：

使用更精确的分支长度估计
在距离矩阵更新时考虑方差信息
通常产生更准确的树

WEIGHBOR

WEIGHBOR是另一种距离矩阵建树方法，使用加权的最小二乘准则，在某些情况下可能比NJ更准确。

从NJ到Maximum Likelihood

NJ和Maximum Likelihood（ML）的关系：

NJ：基于距离的快速方法，适合初步分析
ML：基于模型的精确方法，适合最终分析

实际工作流程中，常先用NJ快速构建树，然后用ML在NJ树的拓扑基础上优化参数。

参考资料

Saitou, N., & Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular biology and evolution, 4(4), 406-425.
Studier, J. A., & Keppler, K. J. (1988). A note on the neighbor-joining algorithm of Saitou and Nei. Molecular biology and evolution, 5(6), 729-731.
Gascuel, O., & Steel, M. (2006). Neighbor-joining revealed. Molecular biology and evolution, 23(11), 1997-2000.