非加权组平均法（UPGMA）

快速概览

UPGMA（Unweighted Pair Group Method with Arithmetic Mean）是一种层次聚类算法，通过不断合并最近的类群来构建系统发育树，适用于满足分子钟假设的数据。

• 核心思想是每次合并距离最近的两个类群，用算术平均更新距离
• 依赖分子钟假设：所有分支以相同速率演化
• 是理解层次聚类和系统发育树构建的经典入门算法

前置知识

• 系统发育树概览
• 距离方法概览
• 聚类算法（层次聚类）

问题定义

UPGMA 系统发育重建问题：

给定一个满足分子钟假设的 $n \times n$ 距离矩阵，构建一棵有根的 ultrametric 树。

输入：$n \times n$ 距离矩阵 $D = (d_{ij})$，假设存在一个分子钟（所有叶子到根的距离相等）

输出：一棵有根树 $T$ 和高度函数 $h(v)$，使得：

• 对于任意两个叶子 $i$ 和 $j$，路径长度 $d_{ij}(T) = D_{ij}$
• 所有叶子到根的距离相等（满足分子钟）

1. UPGMA 的直觉：演化作为聚类

UPGMA (Unweighted Pair Group Method with Arithmetic Mean) 是最直观的建树方法之一。它将系统发育树的构建看作是一个层次聚类（Hierarchical Clustering） 的过程。

核心假设：分子钟（Molecular Clock）

UPGMA 建立在一个非常强的假设之上：分子钟假设。它认为所有的生物谱系都以相同的速率演化。

• 结果：由此产生的树是一棵 超度量树（Ultrametric Tree），即从根节点到任何一个叶子节点的距离（代表时间）都是完全相等的。

2. 算法流程：合并与平均

UPGMA 解决的是：

• 给定一组样本之间的距离矩阵，如何构建一棵反映它们进化关系的树
• 当演化速率相对恒定时，如何从序列相似性推断物种或基因的分化历史

为什么重要

UPGMA 的重要性体现在：

• 教学价值：是理解层次聚类和系统发育树构建的经典算法
• 直观性：算法思路简单易懂，适合作为系统发育分析的入门
• 计算效率：时间复杂度相对较低，适合中等规模数据
• 与其他方法对比：为理解更复杂的 Neighbor-Joining 等算法奠定基础

核心思想

层次聚类

从单个样本开始，逐步合并最近的类群，直到所有样本合并成一棵树。

平均距离

两个类群之间的距离定义为它们所有成员对之间距离的算术平均值。

分子钟假设

假设所有分支以相同的速率演化，因此所有叶子到根的距离相等。

算法直觉

UPGMA 的构建过程可以想象为：

1. 初始时，每个样本都是一个独立的类群
2. 找到距离最近的两个类群，将它们合并成一个新的类群
3. 计算新类群与其他类群之间的平均距离
4. 更新距离矩阵
5. 重复上述过程，直到所有样本合并成一个类群

数学模型

距离矩阵定义

给定 n 个样本，距离矩阵 D 是一个 n×n 的对称矩阵：

$$D = \begin{bmatrix} 0 & d_{12} & d_{13} & \cdots & d_{1n} \\ d_{21} & 0 & d_{23} & \cdots & d_{2n} \\ d_{31} & d_{32} & 0 & \cdots & d_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_{n1} & d_{n2} & d_{n3} & \cdots & 0 \end{bmatrix}$$

其中 $d_{ij} = d_{ji}$ 表示样本 i 和样本 j 之间的距离，$d_{ii} = 0$。

类群间距离定义

当类群 A 包含 $n_A$ 个成员，类群 B 包含 $n_B$ 个成员时，它们之间的距离定义为：

$$d_{AB} = \frac{1}{n_A \cdot n_B} \sum_{i \in A} \sum_{j \in B} d_{ij}$$

即：A 中所有成员与 B 中所有成员距离的算术平均值。

新类群距离更新

当合并类群 A 和类群 B 形成新类群 C 后，新类群 C 与其他类群 D 的距离为：

$$d_{CD} = \frac{n_A \cdot d_{AD} + n_B \cdot d_{BD}}{n_A + n_B}$$

这是加权平均，权重是原类群的成员数量。

分支长度计算

当合并类群 A 和 B 时：

• 新节点到 A 的距离：$L_A = \frac{d_{AB}}{2}$
• 新节点到 B 的距离：$L_B = \frac{d_{AB}}{2}$
• 新节点的高度：$h_{new} = \frac{d_{AB}}{2}$

算法步骤

算法 1：UPGMA

输入：距离矩阵 D（n个样本）
输出：有根系统发育树

1. 初始化：每个样本 i 是一个独立的类群 C_i，包含一个成员
2. while 类群数量 > 1:
   a. 在当前距离矩阵中找到最小距离 d_{min} = min(d_{ij})
   b. 选择对应的类群 A 和 B 进行合并
   c. 创建新节点 u，连接 A 和 B
   d. 计算分支长度：
      - u 到 A 的长度：L_A = d_{min} / 2
      - u 到 B 的长度：L_B = d_{min} / 2
   e. 创建新类群 C = A ∪ B，成员数 n_C = n_A + n_B
   f. 更新距离矩阵：
      - 删除 A 和 B 的行和列
      - 添加新类群 C 的行和列
      - 对于每个其他类群 D，计算 d_{CD} = (n_A·d_{AD} + n_B·d_{BD}) / (n_A + n_B)
3. 返回构建的树

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

• 每次迭代需要 $O(n^2)$ 时间找到最小距离
• 共有 n-1 次迭代
• 每次更新距离矩阵需要 $O(n)$ 时间

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

示例

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

| | A | B | C | D | |---|---|---|---|---| | A | 0 | 2 | 8 | 8 | | B | 2 | 0 | 8 | 8 | | C | 8 | 8 | 0 | 3 | | D | 8 | 8 | 3 | 0 |

迭代 1

步骤 1：找到最小距离

• 最小距离是 $d_{AB} = 2$

步骤 2：合并 A 和 B

• 创建新节点 u1
• 分支长度：$L_A = L_B = 2/2 = 1$
• 新类群 AB 包含 2 个成员

步骤 3：更新距离矩阵 计算类群 AB 与其他类群的距离：

• $d_{AB,C} = \frac{d_{AC} + d_{BC}}{2} = \frac{8 + 8}{2} = 8$
• $d_{AB,D} = \frac{d_{AD} + d_{BD}}{2} = \frac{8 + 8}{2} = 8$

新距离矩阵：

| | AB | C | D | |------|----|---|---| | AB | 0 | 8 | 8 | | C | 8 | 0 | 3 | | D | 8 | 3 | 0 |

迭代 2

步骤 1：找到最小距离

• 最小距离是 $d_{CD} = 3$

步骤 2：合并 C 和 D

• 创建新节点 u2
• 分支长度：$L_C = L_D = 3/2 = 1.5$
• 新类群 CD 包含 2 个成员

步骤 3：更新距离矩阵 计算类群 CD 与类群 AB 的距离：

• $d_{CD,AB} = \frac{d_{CA} + d_{CB} + d_{DA} + d_{DB}}{4} = \frac{8 + 8 + 8 + 8}{4} = 8$

新距离矩阵：

| | AB | CD | |------|----|----| | AB | 0 | 8 | | CD | 8 | 0 |

迭代 3

步骤 1：找到最小距离

• 最小距离是 $d_{AB,CD} = 8$

步骤 2：合并 AB 和 CD

• 创建新节点 u3（根节点）
• 分支长度：$L_{AB} = L_{CD} = 8/2 = 4$

最终树结构

         u3
        /  \
       4    4
      /      \
    u1       u2
   /  \     /  \
  1    1   1.5  1.5
 A    B   C    D

验证分子钟假设：

• A 到根的距离：1 + 4 = 5
• B 到根的距离：1 + 4 = 5
• C 到根的距离：1.5 + 4 = 5.5
• D 到根的距离：1.5 + 4 = 5.5

注意：由于原始距离矩阵不完全满足分子钟假设，C 和 D 到根的距离略大于 A 和 B。

复杂度分析

时间复杂度

• 初始化：$O(n^2)$ 构建距离矩阵
• 每次迭代：
  • 寻找最小距离：$O(k^2)$，其中 k 是当前类群数
  • 更新距离矩阵：$O(k)$
• 总时间复杂度：$O(n^3)$

空间复杂度

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

分子钟假设

UPGMA 的一个关键假设是分子钟假设：所有分支以相同的速率演化。

什么是分子钟假设

分子钟假设认为：

• 不同谱系中的分子演化速率大致相同
• 因此，两个序列之间的分歧时间与它们之间的遗传距离成正比

UPGMA 如何体现分子钟假设

在 UPGMA 构建的树中：

• 所有叶子节点到根节点的距离相等
• 这意味着所有样本从共同祖先开始演化，经历了相同的时间
• 距离的差异反映了演化过程中积累的替换数量

当分子钟假设不满足时

如果不同分支的演化速率差异很大：

• UPGMA 会产生错误的拓扑结构
• 演化快的物种会被错误地放置在树的基部
• 这种现象称为"长枝吸引"（long-branch attraction）

与其他算法的比较

| 算法 | 分子钟假设 | 树的类型 | 适用场景 | |------|-----------|---------|---------| | UPGMA | 要求 | 有根树 | 演化速率相对恒定 | | Neighbor-Joining | 不要求 | 无根树 | 通用，更灵活 | | Maximum Likelihood | 不要求 | 有根/无根 | 模型驱动，更准确 |

适用场景

适合使用 UPGMA 的情况

• 序列演化速率相对恒定
• 样本之间的分化时间相近
• 需要快速构建系统发育树的初步结果
• 教学演示层次聚类原理

不适合使用 UPGMA 的情况

• 不同分支演化速率差异很大
• 存在明显的长枝吸引现象
• 需要精确的无根树拓扑
• 序列差异过大，距离估计不可靠

优缺点总结

优点

• 算法简单直观，易于理解和实现
• 计算效率相对较高
• 产生有根树，直接表示分化时间
• 适合作为系统发育分析的入门算法

缺点

• 依赖分子钟假设，限制适用范围
• 当演化速率不均匀时，可能产生错误拓扑
• 只使用距离信息，丢失了位点级别的细节
• 对距离矩阵的质量和准确性高度依赖

常见误区

• UPGMA 总是能得到正确的树：
• 不是。UPGMA 只有在满足分子钟假设时才能保证正确性。当演化速率不均匀时，结果可能不准确。
• UPGMA 的距离矩阵必须是 additive：
• 不是。UPGMA 可以对任意距离矩阵进行聚类，但只有当距离矩阵满足 additive 条件时，结果才是最优的。
• UPGMA 产生的树一定是无根树：
• 不是。UPGMA 产生的是有根树，根节点对应于所有样本的共同祖先。

与真实工具的连接

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

• PHYLIP：包含 UPGMA 实现（程序 neighbor）
• MEGA：提供 UPGMA 作为构建系统发育树的选项
• R 语言：ape 包中的upgma()函数
• 初步分析：常用于快速探索数据结构，然后再用更复杂的方法精化

现代系统发育分析中，UPGMA 更多用于：

• 快速预览样本关系
• 作为其他算法的初始化
• 教学和演示目的

算法变体

WPGMA（Weighted Pair Group Method with Arithmetic Mean）

与 UPGMA 的区别在于：

• UPGMA：按类群成员数量加权
• WPGMA：不按成员数量加权，直接平均

WPGMA 在某些情况下可能更稳定，但 UPGMA 更常用。

加速 UPGMA

对于大规模数据，可以使用：

• 优先队列优化最小距离查找
• 近似算法减少计算量
• 并行化处理

参考资料

• Sokal, R. R., & Michener, C. D. (1958). A statistical method for evaluating systematic relationships. University of Kansas science bulletin, 38(1409-1444), 22.
• Sneath, P. H., & Sokal, R. R. (1973). Numerical taxonomy: the principles and practice of numerical classification.
• Felsenstein, J. (2004). Inferring phylogenies. Sinauer associates.

距离方法概览

延伸阅读

Neighbor-Joining 算法

延伸阅读

聚类算法（层次聚类）

延伸阅读

加法系统发育

延伸阅读