🧬 01 · 序列比对入门(Needleman-Wunsch / Smith-Waterman)¶
序列比对是生信的地基:判断两条序列是否同源、找出差异位点、 注释新基因、建进化树都靠它。本节手写两种经典动态规划比对: 全局比对(Needleman-Wunsch,1970)与 局部比对(Smith-Waterman,1981)。
📋 本节要解决的问题¶
- 全局比对 vs 局部比对:各自适用什么场景?
- DW 打分矩阵怎么建?回溯怎么走?
- 空位罚分怎么设?(线性 vs 仿射)
- 比对结果怎么解读(匹配/错配/空位)?
1️⃣ 比对的评分思想¶
给定两条序列,插入**空位(gap)**对齐匹配/错配,得到一个最高总分: $$score = \sum(\text{match:}+\text{奖分},\; \text{mismatch:}0/负分,\; \text{gap:}-\text{罚分})$$
全局比对:整条序列从头到尾最优对齐(同源全长比较,如蛋白家族比对)。 局部比对:找两序列中最相似的子片段(如新序列找已知结构域)。
match, mismatch, gap = 2, -1, -2 # 常用 BLOSUM 简化打分
def nw_align(seq1, seq2, match=2, mismatch=-1, gap=-2):
"Needleman-Wunsch 全局比对,返回 (score, aligned1, aligned2)"
n, m = len(seq1), len(seq2)
# DP 矩阵
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1): dp[i][0] = dp[i-1][0] + gap
for j in range(1, m+1): dp[0][j] = dp[0][j-1] + gap
trace = [['']*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
diag = dp[i-1][j-1] + (match if seq1[i-1]==seq2[j-1] else mismatch)
up = dp[i-1][j] + gap
left = dp[i][j-1] + gap
best = max(diag, up, left)
dp[i][j] = best
if best == diag: trace[i][j] = 'd'
elif best == up: trace[i][j] = 'u'
else: trace[i][j] = 'l'
# 回溯
a1, a2 = [], []
i, j = n, m
while i > 0 or j > 0:
if i > 0 and j > 0 and trace[i][j] == 'd':
a1.append(seq1[i-1]); a2.append(seq2[j-1]); i -= 1; j -= 1
elif i > 0 and trace[i][j] == 'u':
a1.append(seq1[i-1]); a2.append('-'); i -= 1
else:
a1.append('-'); a2.append(seq2[j-1]); j -= 1
return dp[n][m], ''.join(reversed(a1)), ''.join(reversed(a2))
s1, s2 = 'GATTACA', 'GCATGCU'
score, al1, al2 = nw_align(s1, s2)
print('全局比对得分:', score)
print('seq1:', al1)
print('seq2:', al2)
print(' *' if score > 0 else ' 得分<=0')
assert al1 != '' and len(al1) == len(al2)
print('✅ NW 全局比对完成(两条对齐长度一致)')
全局比对得分: 2 seq1: GATTACA seq2: GCATGCU * ✅ NW 全局比对完成(两条对齐长度一致)
2️⃣ 手算示例:2×2 小矩阵逐步推¶
序列:A=
AG,B=AC,打分 match=+2, mismatch=-1, gap=-2
初始化(第 0 行/列累加 gap):
- A C
- 0 -2 -4
A -2
G -4
填 (1,1)=A/A:diag=0+2=2,up=-2-2=-4,left=-2-2=-4 → 2 填 (1,2)=A/C:diag=-2-1=-3,up=-4-2=-6,left=2-2=0 → 0 填 (2,1)=G/A:diag=-2-1=-3,up=-4-2=-6,left=2-2=0 → 0 填 (2,2)=G/C:diag=0-1=-1,up=0-2=-2,left=0-2=-2 → -1
等等——漏算了 (2,2) 的一条路径:上一步 (1,1)=2 走 diag。 重推 (2,2):diag=dp(1,1)−1=2−1=1,up=dp(1,2)−2=−2,left=dp(2,1)−2=−2 → 1
最优全局比对得分 = 1,对应对齐:
AG
AC (A-A 匹配 +2, G-C 错配 -1 → 总分 1)
# 验证手算
import numpy as np
s1, s2 = 'AG', 'AC'
score, a1, a2 = nw_align(s1, s2, match=2, mismatch=-1, gap=-2)
print('手算得分应为 1(A-A 匹配+2, G-C 错配-1),实际 =', score)
print('一个最优比对:')
print(' ', a1)
print(' ', a2)
assert score == 1
print('✅ NW 手算验证通过')
手算得分应为 1(A-A 匹配+2, G-C 错配-1),实际 = 1 一个最优比对: AG AC ✅ NW 手算验证通过
3️⃣ Smith-Waterman 局部比对¶
与 NW 区别:
- 矩阵从 0 初始化(不再累加 gap 到负)
- 转移时若所有来源都 <0,则取 0(重新开始)
- 从最大分值位置回溯到 0,即最优局部片段
def sw_align(seq1, seq2, match=2, mismatch=-1, gap=-2):
"Smith-Waterman 局部比对,返回 (score, sub1, sub2)"
n, m = len(seq1), len(seq2)
dp = [[0]*(m+1) for _ in range(n+1)]
trace = [['']*(m+1) for _ in range(n+1)]
best_i = best_j = best = 0
for i in range(1, n+1):
for j in range(1, m+1):
diag = dp[i-1][j-1] + (match if seq1[i-1]==seq2[j-1] else mismatch)
up = dp[i-1][j] + gap
left = dp[i][j-1] + gap
val = max(0, diag, up, left)
dp[i][j] = val
if val == diag and diag > 0: trace[i][j] = 'd'
elif val == up: trace[i][j] = 'u'
elif val == left: trace[i][j] = 'l'
if val > best:
best, best_i, best_j = val, i, j
a1, a2 = [], []
i, j = best_i, best_j
while i > 0 and j > 0 and dp[i][j] > 0:
t = trace[i][j] or 'd'
if t == 'd':
a1.append(seq1[i-1]); a2.append(seq2[j-1]); i -= 1; j -= 1
elif t == 'u':
a1.append(seq1[i-1]); a2.append('-'); i -= 1
else:
a1.append('-'); a2.append(seq2[j-1]); j -= 1
return best, ''.join(reversed(a1)), ''.join(reversed(a2))
score, a1, a2 = sw_align('ACGTACGT', 'TTACGTTA')
print('局部比对得分:', score, '(最优子片段)')
print('片段1:', a1)
print('片段2:', a2)
print('→ 找到共同片段 ACGT,而非强行全长对齐')
assert score > 0 and a1 == a2
print('✅ SW 局部比对完成')
局部比对得分: 10 (最优子片段) 片段1: TACGT 片段2: TACGT → 找到共同片段 ACGT,而非强行全长对齐 ✅ SW 局部比对完成
4️⃣ 空位罚分:线性 vs 仿射¶
线性罚分:每个空位 -g。 仿射罚分:开空位额外代价(open, e.g. -4)+ 每个延伸空位(extend, e.g. -1)。
仿射更贴近生物学:一个插入/缺失事件往往是一段,而不是一个个孤立的空位。
print('线性罚分: gap_open=gap_extend=-2')
print(' 例: A--T 罚 -2-2-2 = -6')
print('仿射罚分: open=-4, extend=-1')
print(' 例: A--T 罚 -4-1-1 = -6(同一事件更划算)')
print()
print('→ 仿射罚分对"成串空位"更友好,避免把长片段拆成很多小空位')
print('✅ 罚分模型对比说明完成')
线性罚分: gap_open=gap_extend=-2 例: A--T 罚 -2-2-2 = -6 仿射罚分: open=-4, extend=-1 例: A--T 罚 -4-1-1 = -6(同一事件更划算) → 仿射罚分对"成串空位"更友好,避免把长片段拆成很多小空位 ✅ 罚分模型对比说明完成
✅ 自测清单¶
- 能说出全局 vs 局部的适用场景
- 能手写 Needleman-Wunsch(DP 表+回溯)
- 能手写 Smith-Waterman(0 初始化+取最大)
- 能解释线性 vs 仿射空位罚分的区别