BLAST：基本局部比对搜索工具

1. 背景

1990 年前，序列比对只能通过 Smith-Waterman DP（O(mn)）完成。随数据库增长，这已不可接受。BLAST 引入了一套启发式加速策略，在可接受的敏感性损失下将速度提升数十倍。BLAST 的 seed-and-extend 范式直接影响了后来的 BLAT、BWA-SW 和 BWA-MEM。

2. 原始 BLAST（1990）

1. 种子生成： 查询序列中取所有长度 k 的子串（k-mer）
2. 命中检测： 数据库中找与种子匹配且分数 ≥ T 的命中
3. 无空位延伸： 向两端无空位延伸至分数下降超 X（X-dropoff）
4. 显著性评估： 统计评估延伸结果的显著性

3. Gapped BLAST（1997）

• 双命中策略： 同对角线需要两个非重叠种子才启动延伸，大幅减少不必要延伸
• 空位延伸： 命中延伸阶段允许 gap，使用 Smith-Waterman DP

4. X-dropoff 与 Z-dropoff 对比

Z-dropoff 是 X-dropoff 的改进：加入 |x−y|×p_gapExt 后，坐标差增大时阈值自动放宽，允许一方有长插入。

5. Seed-and-Extend 演进