🧬 03 · BLAST 与序列搜索¶
BLAST(Basic Local Alignment Search Tool)是生信最常用工具: 拿一条查询序列去数据库里找同源序列。核心思想不是穷举比对, 而是 k-mer seed → 命中 → 延伸,把搜索从 O(n·m) 降到接近 O(n)。 本节手写一个简化版 BLAST:k-mer 索引、seed 命中、左右延伸、E-value 直觉。
📋 本节要解决的问题¶
- 为什么不能对每条数据库序列都做完整比对?(太慢)
- seed 是什么?怎么用 k-mer 索引加速?
- seed 命中后怎么延伸成高分段对(HSP)?
- E-value 是什么?越小越好吗?
1️⃣ 朴素搜索 vs 索引搜索¶
朴素:查询序列与每条数据库序列做 Smith-Waterman → 数据库大(百万条)时不可行。
BLAST 思路:首先把查询序列拆成 k-mer(常用 k=11 DNA / 3 氨基酸), 在数据库的 k-mer 索引表里 O(1) 定位命中位置;命中点称为 seed, 再向两侧延伸,直到得分下降过多——得到 HSP(高分段对)。
Copied!
# k-mer 索引:数据库 -> {kmer: [出现位置]}
def build_index(db_seq, k=4):
index = {}
for i in range(len(db_seq) - k + 1):
kmer = db_seq[i:i+k]
index.setdefault(kmer, []).append(i)
return index
db = 'ACGTACGTGAATTCCGACGT'
idx = build_index(db, 4)
print('k=4 索引条目数:', len(idx))
print('ACGT 出现在位置:', idx.get('ACGT'))
assert idx['ACGT'] == [0, 4, 16]
print('✅ k-mer 索引构建正确(O(n) 构建, O(L) 查询)')
# k-mer 索引:数据库 -> {kmer: [出现位置]}
def build_index(db_seq, k=4):
index = {}
for i in range(len(db_seq) - k + 1):
kmer = db_seq[i:i+k]
index.setdefault(kmer, []).append(i)
return index
db = 'ACGTACGTGAATTCCGACGT'
idx = build_index(db, 4)
print('k=4 索引条目数:', len(idx))
print('ACGT 出现在位置:', idx.get('ACGT'))
assert idx['ACGT'] == [0, 4, 16]
print('✅ k-mer 索引构建正确(O(n) 构建, O(L) 查询)')
k=4 索引条目数: 15 ACGT 出现在位置: [0, 4, 16] ✅ k-mer 索引构建正确(O(n) 构建, O(L) 查询)
2️⃣ seed 命中 + 延伸(简化 BLAST)¶
流程:
- 查询序列拆 k-mer
- 每个 k-mer 查索引得到命中位置
- 从命中位置向右延伸,逐位比较,匹配加分、错配减分
- 记录得分最高的延伸片段(HSP)
Copied!
def simple_blast(query, db_seq, k=4, match=1, mismatch=-1):
"简化 BLAST:返回 [(score, q_start, db_start, length)] 降序"
idx = build_index(db_seq, k)
hits = []
for i in range(len(query) - k + 1):
kmer = query[i:i+k]
for j in idx.get(kmer, []):
# 从 seed 向右延伸
score = k * match # seed 本身全部匹配
ext = k
q, d = i + k, j + k
while q < len(query) and d < len(db_seq):
score += match if query[q] == db_seq[d] else mismatch
ext += 1
q += 1; d += 1
hits.append((score, i, j, ext))
return sorted(hits, reverse=True)
query = 'ACGTAC'
best = simple_blast(query, db, k=4)
print('数据库:', db)
print('查询 :', query)
for sc, qi, dj, ln in best[:3]:
print(' 得分=%d 查询位置%d 库位置%d 延伸长度%d 命中:%s' %
(sc, qi, dj, ln, db[dj:dj+ln]))
print('→ 与 ACGTACGT... 的 ACGTAC 区域(库位置 0/4)得分最高')
# 最优 HSP 得分 = 6,库位置 ∈ {0, 4}(两处同源区域各延伸满 6 位)
assert best[0][0] == 6 and best[0][3] == 6 and best[0][2] in (0, 4)
print('✅ 简化 BLAST seed-extend 完成')
def simple_blast(query, db_seq, k=4, match=1, mismatch=-1):
"简化 BLAST:返回 [(score, q_start, db_start, length)] 降序"
idx = build_index(db_seq, k)
hits = []
for i in range(len(query) - k + 1):
kmer = query[i:i+k]
for j in idx.get(kmer, []):
# 从 seed 向右延伸
score = k * match # seed 本身全部匹配
ext = k
q, d = i + k, j + k
while q < len(query) and d < len(db_seq):
score += match if query[q] == db_seq[d] else mismatch
ext += 1
q += 1; d += 1
hits.append((score, i, j, ext))
return sorted(hits, reverse=True)
query = 'ACGTAC'
best = simple_blast(query, db, k=4)
print('数据库:', db)
print('查询 :', query)
for sc, qi, dj, ln in best[:3]:
print(' 得分=%d 查询位置%d 库位置%d 延伸长度%d 命中:%s' %
(sc, qi, dj, ln, db[dj:dj+ln]))
print('→ 与 ACGTACGT... 的 ACGTAC 区域(库位置 0/4)得分最高')
# 最优 HSP 得分 = 6,库位置 ∈ {0, 4}(两处同源区域各延伸满 6 位)
assert best[0][0] == 6 and best[0][3] == 6 and best[0][2] in (0, 4)
print('✅ 简化 BLAST seed-extend 完成')
数据库: ACGTACGTGAATTCCGACGT 查询 : ACGTAC 得分=6 查询位置0 库位置0 延伸长度6 命中:ACGTAC 得分=5 查询位置1 库位置1 延伸长度5 命中:CGTAC 得分=4 查询位置2 库位置2 延伸长度4 命中:GTAC → 与 ACGTACGT... 的 ACGTAC 区域(库位置 0/4)得分最高 ✅ 简化 BLAST seed-extend 完成
3️⃣ 手算示例:延伸打分¶
查询
ACGTAC,数据库位置 0 的ACGTAC...,k=4 seed=ACGT,match=+1, mismatch=-1
seed:4 个碱基全匹配 → 得分 4
延伸第 1 位:查询 A vs 库 A → +1 → 5
延伸第 2 位:查询 C vs 库 C → +1 → 6
共延伸到 6 位,总分 = 6
这就是
simple_blast返回的最优 HSP(查询位置 0、库位置 0、延伸长度 6); 若延伸到错配,得分下降,BLAST 在低于阈值时停止延伸。
Copied!
# 验证手算:查询 ACGTAC 对库位置 0 的延伸
db_seg = db[0:6] # ACGTAC
q = 'ACGTAC'
score = 0
for a, b in zip(q, db_seg):
score += 1 if a == b else -1
print('对齐片段:', db_seg, ' 手算/代码得分 =', score)
assert score == 6
print('✅ 延伸打分手算验证通过')
# 验证手算:查询 ACGTAC 对库位置 0 的延伸
db_seg = db[0:6] # ACGTAC
q = 'ACGTAC'
score = 0
for a, b in zip(q, db_seg):
score += 1 if a == b else -1
print('对齐片段:', db_seg, ' 手算/代码得分 =', score)
assert score == 6
print('✅ 延伸打分手算验证通过')
对齐片段: ACGTAC 手算/代码得分 = 6 ✅ 延伸打分手算验证通过
4️⃣ E-value 直觉¶
E-value:在随机序列数据库中,期望出现得分不低于当前 HSP 的命中次数。
- E-value = 0.05 → 每 20 次搜索随机出现 1 次类似命中(阈值常用)
- E-value 越小越显著,但取决于数据库大小:库越大,同样得分 E 越大
- 与 p-value 区别:p 是"这一条的显著性",E 是"整库搜索里期望出现的次数"
- 远超阈值的 E(如 1e-50)表示几乎不可能随机出现 → 真同源
Copied!
def _poisson_evalue_raw(n_db_kmers, score, match_prob=0.25):
"极简 E-value 估计:随机匹配单碱基概率 p,命中 seed 概率 p^k(示意)"
# 真实 BLAST 使用 Karlin-Altschul 统计;这里演示数量级直觉
k = 4
p_seed = match_prob ** k # 随机出现 4-mer 全匹配概率
return n_db_kmers * p_seed
n_kmers_db = len(db) - 3 # 约 20 个窗口
for sc in [6, 10]:
ev = _poisson_evalue_raw(n_kmers_db, sc)
print('得分 %2d → E≈%.4f(同分在不同库中 E 会变)' % (sc, ev))
print()
print('→ 直觉:得分越高、库越小,E 越小;E < 0.05 常视为显著同源')
print('✅ E-value 概念演示完成')
def _poisson_evalue_raw(n_db_kmers, score, match_prob=0.25):
"极简 E-value 估计:随机匹配单碱基概率 p,命中 seed 概率 p^k(示意)"
# 真实 BLAST 使用 Karlin-Altschul 统计;这里演示数量级直觉
k = 4
p_seed = match_prob ** k # 随机出现 4-mer 全匹配概率
return n_db_kmers * p_seed
n_kmers_db = len(db) - 3 # 约 20 个窗口
for sc in [6, 10]:
ev = _poisson_evalue_raw(n_kmers_db, sc)
print('得分 %2d → E≈%.4f(同分在不同库中 E 会变)' % (sc, ev))
print()
print('→ 直觉:得分越高、库越小,E 越小;E < 0.05 常视为显著同源')
print('✅ E-value 概念演示完成')
得分 6 → E≈0.0664(同分在不同库中 E 会变) 得分 10 → E≈0.0664(同分在不同库中 E 会变) → 直觉:得分越高、库越小,E 越小;E < 0.05 常视为显著同源 ✅ E-value 概念演示完成
✅ 自测清单¶
- 能解释为什么 BLAST 用 k-mer seed 加速
- 能手写 k-mer 索引与 seed-extend
- 能图解延伸过程并手算延伸得分
- 能解释 E-value 与数据库大小的关系