🧬 07 · 系统发育树入门(UPGMA / 邻接法)¶
进化树描述物种/序列间的演化关系。本节:距离矩阵 → UPGMA 手写建树 (含树的可视化)→ 邻接法(NJ)思想 → bootstrap 评估可靠性。
📋 本节要解决的问题¶
- 从序列怎么得到距离矩阵?(p-distance / Jukes-Cantor)
- UPGMA 怎么把距离矩阵聚成树?(逐步合并最近节点)
- UPGMA 与 NJ 的区别?(分子钟假设 vs 无)
- bootstrap 支持率怎么理解?
1️⃣ 从序列到距离:p-distance 与 Jukes-Cantor¶
p-distance:两条序列不同位点比例。 Jukes-Cantor 校正:$d = -\frac{3}{4}\ln\left(1 - \frac{4}{3}p\right)$ (校正多重替换;饱和时 p 接近 0.75,d 趋于无穷)
import numpy as np
def p_distance(s1, s2):
"p-distance:不一致位点比例(忽略 gap)"
diff = same = 0
for a, b in zip(s1, s2):
if a == '-' or b == '-':
continue
same += (a == b)
diff += (a != b)
return diff / (same + diff)
def jukes_cantor(p):
p = min(p, 0.749)
return -0.75 * np.log(1 - 4/3 * p)
seqs = {
'A': 'ACGTACGT',
'B': 'ACGTAGGT', # 1 处差异 vs A
'C': 'AAGTACGT', # 1 处差异 vs A, 2 vs B
'D': 'TTTTTGGT', # 差异较多
}
pAB = p_distance(seqs['A'], seqs['B'])
print('A vs B p-distance(手算 1/8=0.125) =', pAB)
print('A vs B Jukes-Cantor = %.4f' % jukes_cantor(pAB))
assert abs(pAB - 0.125) < 1e-9
print('✅ p-distance 与 JC 校正计算正确')
A vs B p-distance(手算 1/8=0.125) = 0.125 A vs B Jukes-Cantor = 0.1367 ✅ p-distance 与 JC 校正计算正确
2️⃣ 手算示例:p-distance¶
两序列:A=
ACGTACGT,B=ACGTAGGT逐位比较:8 个位点中 7 个相同、第 6 位 A→G 不同
$$p = \frac{1}{8} = 0.125$$
DNA 四位点随机模型下最大 p ≈ 0.75;p 超过 ~0.3 后序列分化快饱和, 需要用 Jukes-Cantor 等模型校正。
# 验证手算
a = 'ACGTACGT'; b = 'ACGTAGGT'
diff = sum(1 for x, y in zip(a, b) if x != y)
print('不一致位点数(手算 1) =', diff)
print('p(手算 0.125) =', diff / len(a))
assert diff == 1 and diff / len(a) == 0.125
print('✅ p-distance 手算验证通过')
不一致位点数(手算 1) = 1 p(手算 0.125) = 0.125 ✅ p-distance 手算验证通过
3️⃣ UPGMA 建树(手写)¶
UPGMA(非加权组平均法)步骤:
- 从距离矩阵开始,每个分类自成簇
- 找最近两簇合并,新簇位置 = 两簇距离/2
- 更新距离:新簇到其他簇 = 加权平均(各簇大小)
- 重复直到只剩 1 簇
def upgma(names, dist):
"UPGMA 聚类,返回新ick 格式树串(简化)"
import copy
names = list(names)
D = copy.deepcopy(dist)
sizes = {n: 1 for n in names}
tree = {n: '(leaf:%s)' % n for n in names}
cluster = list(names)
step = 0
while len(cluster) > 1:
# 找最近对
best = min(((D[i][j], i, j) for i in range(len(cluster))
for j in range(i+1, len(cluster))), key=lambda x: x[0])
d, ci, cj = best
xi, xj = cluster[ci], cluster[cj]
# 合并:父节点串
node = 'node%d' % step; step += 1
tree[node] = '(%s:%f,%s:%f)' % (tree[xi], d/2, tree[xj], d/2)
cluster += [node]
new_size = sizes[xi] + sizes[xj]
sizes[node] = new_size
# 更新距离:新簇 vs 其余 = (si*dist(i,k) + sj*dist(j,k))/(si+sj)
new_row = []
for idx in range(len(cluster) - 1):
k = cluster[idx]
w = (sizes[xi] * D[ci][idx] + sizes[xj] * D[cj][idx]) / (sizes[xi] + sizes[xj])
new_row.append(w)
# 删除合并的 i,j(先删大索引)
for idx in sorted([ci, cj], reverse=True):
for r in D:
del r[idx]
D.pop(idx)
del cluster[idx]
# 追加新簇行/列(保持 D 方阵)
if len(cluster) > 1:
for r in D:
r.append(new_row.pop(0))
D.append(new_row + [0.0])
return tree[cluster[0]]
names = ['A', 'B', 'C', 'D']
# 距离矩阵:A,B 近;C 居中;D 远
D = [
[0.0, 0.1, 0.3, 0.6],
[0.1, 0.0, 0.3, 0.6],
[0.3, 0.3, 0.0, 0.5],
[0.6, 0.6, 0.5, 0.0],
]
newick = upgma(names, D)
print('UPGMA 树 (新ick):')
print(newick)
assert 'B' in newick and 'A' in newick and 'D' in newick
print('✅ UPGMA 建树完成(A、B 先聚成姐妹支)')
UPGMA 树 (新ick): ((leaf:D):0.100000,((leaf:C):0.025000,((leaf:A):0.050000,(leaf:B):0.050000):0.025000):0.100000) ✅ UPGMA 建树完成(A、B 先聚成姐妹支)
4️⃣ 手算示例:UPGMA 两轮合并¶
四分类 A,B,C,D,距离矩阵
D[0,1]=0.1, D[0,2]=0.3, D[0,3]=0.6, D[1,2]=0.3, D[1,3]=0.6, D[2,3]=0.5
第 1 轮:最近对 A-B(0.1)→ 合并,节点高度 = 0.1/2 = 0.05 更新距离:A/B 到 C = (0.3+0.3)/2 = 0.3;A/B 到 D = (0.6+0.6)/2 = 0.6 第 2 轮:最近 AB-C(0.3) → 合并,节点高度 0.15 第 3 轮:ABC-D(?) → (0.6*2+0.5)/3 ≈ 0.567 → 根高度 ≈ 0.28
启发:UPGMA 假设分子钟(所有谱系速率一致),因此构建的是"超度量树"; 若速率不等(现实中常见),NJ 更稳妥。
# 验证 UPGMA 距离更新逻辑
D2 = [
[0.0, 0.1, 0.3, 0.6],
[0.1, 0.0, 0.3, 0.6],
[0.3, 0.3, 0.0, 0.5],
[0.6, 0.6, 0.5, 0.0],
]
# 第 1 轮: AB 合并, 到 C = (0.3+0.3)/2 = 0.3
w_c = (D2[0][2] + D2[1][2]) / 2
w_d = (D2[0][3] + D2[1][3]) / 2
print('AB 到 C(手算 0.3) =', w_c, ' AB 到 D(手算 0.6) =', w_d)
assert abs(w_c - 0.3) < 1e-9 and abs(w_d - 0.6) < 1e-9
print('✅ UPGMA 距离更新手算验证通过')
AB 到 C(手算 0.3) = 0.3 AB 到 D(手算 0.6) = 0.6 ✅ UPGMA 距离更新手算验证通过
5️⃣ NJ 与 bootstrap¶
NJ(邻接法):
- 不假设分子钟 → 各谱系速率可不同
- 通过"净分化速率"矫正,把长枝吸附问题最小化
- 实际建树(如 RAxML、FastTree、IQ-TREE)常用 ML/Bayesian
bootstrap:对原始比对列有放回重采样建多棵树(如 1000 次), 统计每个节点的支持率;>70% 通常视为可信,>95% 强支持。
print('bootstrap 伪代码流程:')
for step in [
'1. 原始 MSA -> 逐列重采样得到 1000 个新比对',
'2. 每个重采样比对建一棵树',
'3. 统计每棵树的每个节点在所有树中出现的频率',
'4. 把支持率(%)标注到原始树的分支上',
]:
print(step)
print()
print('→ 支持率 100%:该分支在所有重采样中都出现(很稳健)')
print('→ 支持率 <50%:该分支不稳定,结论要谨慎')
print('✅ bootstrap 概念说明完成')
bootstrap 伪代码流程: 1. 原始 MSA -> 逐列重采样得到 1000 个新比对 2. 每个重采样比对建一棵树 3. 统计每棵树的每个节点在所有树中出现的频率 4. 把支持率(%)标注到原始树的分支上 → 支持率 100%:该分支在所有重采样中都出现(很稳健) → 支持率 <50%:该分支不稳定,结论要谨慎 ✅ bootstrap 概念说明完成
✅ 自测清单¶
- 能手算 p-distance 并解释 JC 校正
- 能手写 UPGMA(找最近对 + 加权平均更新)
- 能说出 UPGMA 与 NJ 的核心区别(分子钟假设)
- 能解释 bootstrap 支持率的含义