生物信息学算法实战：序列比对与动态规划

课程简介

本课程以「序列比对」为线索，带你在编程与生物的交叉地带建立扎实的算法直觉。我们将从最朴素的动态规划（Dynamic Programming）思想出发，亲手实现编辑距离、全局比对与局部比对，再理解工业级工具 BLAST 背后的启发式加速策略。学完你不仅能写出可运行的序列比对代码，更能看穿各类「字符串相似度」问题的共同骨架。

学习目标

• 掌握动态规划的状态定义与转移方程写法，独立推导二维 DP 表
• 理解 Needleman-Wunsch（全局）与 Smith-Waterman（局部）比对的核心差异与适用场景
• 能用 Python 实现基础比对，并对比对结果做回溯还原对齐路径
• 讲清楚 BLAST 用「字种子 + 局部扩展」做到秒级搜索的原理与权衡

章节概览

1. 第一章：动态规划入门——状态、转移与填表
2. 第二章：编辑距离与字符串相似度的统一视角
3. 第三章：全局比对（Needleman-Wunsch）与回溯
4. 第四章：局部比对（Smith-Waterman）与保守区域发现
5. 第五章：BLAST 的启发式——从暴力到秒级
6. 第六章：实战——用 Python 比对两条真实 DNA 序列

图1：根据「是否整体对齐」「数据规模」选择 NW / SW / BLAST