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.

距离方法概览

UPGMA 所属的距离矩阵建树方法族

延伸阅读

Neighbor-Joining 算法

不依赖分子钟假设的建树方法

延伸阅读

层次聚类

UPGMA 的算法本质

延伸阅读

加法系统发育

UPGMA 正确性的理论基础

延伸阅读