图算法基础
图算法是理解组装、系统发育树和许多序列分析问题的基础工具。这一页从最基础的遍历和路径问题出发，建立图算法的直觉。
- 先理解 BFS/DFS 的差异，再看最短路径和连通性问题会更顺。
- 很多生物信息学问题都可以抽象成图问题，理解图算法能帮你看到不同任务之间的共性。
图（graph）由顶点（vertex）和边（edge）组成。在生物信息学中，图无处不在：
- de Bruijn graph：顶点是 k-1-mer，边是 k-mer，用于基因组组装
- overlap graph：顶点是 reads，边表示 reads 之间的重叠关系
- 系统发育树：一种特殊的树状图，表示物种间的进化关系
- HMM 状态图：顶点是隐藏状态，边是状态转移概率
- 比对网格图：二维网格上的路径问题
图算法的目标通常是：
- 遍历所有顶点或边
- 找到两点间的最短路径
- 判断图的连通性
- 找到特定结构（如环、树、连通分量）
要解决什么生物信息学问题
Section titled “要解决什么生物信息学问题”理解图算法能帮助我们解决：
- 组装中的路径问题：如何在 de Bruijn graph 中找到代表基因组的路径
- 系统发育树构建：如何遍历和评估不同的树拓扑
- 序列比对：如何在网格图中找到最优路径（动态规划的图视角）
- 错误校正：如何在图中识别异常路径或结构
- 聚类分析：如何在图中识别连通分量或社区结构
图算法的核心是把生物问题转成图问题，然后用成熟的图算法工具求解：
- 建模：把序列、reads、物种等对象抽象成顶点
- 建边：根据相似性、重叠、进化关系等建立边
- 求解：应用 BFS、DFS、最短路径等算法
- 解释：把图算法的结果解释回生物意义
这种抽象的价值在于：很多看似不同的生物任务，在图层面共享相同的算法直觉。
1. 广度优先搜索（BFS）
Section titled “1. 广度优先搜索（BFS）”BFS 从起始顶点开始，逐层向外探索。
- 数据结构
- 使用队列（queue）实现，先进先出。
- 访问顺序
- 先访问所有距离为 1 的顶点，再访问距离为 2 的顶点，以此类推。
- 保证性质
- 第一次到达某个顶点时，一定是最短路径。
- 时间复杂度
- $O(V + E)$，V 是顶点数，E 是边数。
考虑一个简单的图，其中 A 与 B、C 相连，B 与 D、E 相连，C 与 E 相连。
从 A 开始 BFS：
- 访问 A，队列：[B, C]
- 访问 B，队列：[C, D, E]
- 访问 C，队列：[D, E]
- 访问 D，队列：[E]
- 访问 E，队列：[空]
BFS 保证我们按距离 A 的层数顺序访问顶点。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 最短 k-mer 距径：在 de Bruijn graph 中找两点间的最短路径
- 层次聚类：按相似度层次聚类序列或物种
- 错误传播分析：分析错误在组装图中的传播范围
2. 深度优先搜索（DFS）
Section titled “2. 深度优先搜索（DFS）”DFS 从起始顶点开始，沿一条路径走到底，再回溯。
- 数据结构
- 使用栈（stack）或递归实现，后进先出。
- 访问顺序
- 沿一条路径深入，遇到死胡同后回溯，探索其他分支。
- 保证性质
- 能遍历所有可达顶点，适合找连通分量。
- 时间复杂度
- $O(V + E)$。
同样的图（A-B, A-C, B-D, B-E, C-E）：
从 A 开始 DFS（假设按字母顺序）：
- 访问 A，去 B
- 访问 B，去 D
- 访问 D，无未访问邻居，回溯到 B
- 从 B 去E
- 访问 E，无未访问邻居，回溯到 B
- 从 B 回溯到 A
- 从 A 去C
- 访问 C，去E（已访问），回溯
- 回溯到 A，结束
DFS 会深入探索一条路径，适合找连通分量和环检测。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 连通分量检测：在组装图中识别独立的 contigs
- 环检测：检测图中的循环结构（在组装中可能指示重复序列）
- 拓扑排序：在有向无环图（DAG）中排序（如依赖关系）
- 系统发育树遍历：深度遍历树结构进行后序分析
3. 最短路径算法
Section titled “3. 最短路径算法”Dijkstra 算法
Section titled “Dijkstra 算法”Dijkstra 算法用于在带权图中找到单源最短路径。
- 适用条件
- 边权必须非负。
- 核心思想
- 贪心策略：每次选择距离源点最近的未访问顶点。
- 数据结构
- 优先队列（priority queue）实现。
- 时间复杂度
- $O((V + E) log V)$ 使用二叉堆。
考虑带权图：A→B(1), A→C(3), B→D(2), B→E(1), C→E(1)。
从 A 到各点的最短距离：
- 初始化：dist[A]=0, 其他=∞
- 选 A，更新 B=1, C=3
- 选 B，更新 D=1+2=3, E=1+1=2
- 选 E，更新 C=2+1=3（不改善）
- 选 C 或 D，无更新
最短路径：A→B→E (距离2), A→B→D (距离3), A→C (距离3)
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 编辑距离的图视角：在比对网格图中找最小代价路径
- 组装路径优化：在 de Bruijn graph 中找最优覆盖路径
- 进化距离：在系统发育图中找最小进化距离
Bellman-Ford 算法
Section titled “Bellman-Ford 算法”当边权可能为负时，使用 Bellman-Ford 算法。
- 适用条件
- 允许负权边，能检测负权环。
- 时间复杂度
- $O(VE)$，比 Dijkstra 慢。
- 应用场景
- 生物信息学中较少直接使用，但在某些优化问题中有用。
4. 连通性与分量
Section titled “4. 连通性与分量”无向图的连通分量
Section titled “无向图的连通分量”使用 BFS 或 DFS 可以找到所有连通分量。
- 方法
- 对每个未访问顶点启动 BFS/DFS，标记所有可达顶点为一个分量。
- 时间复杂度
- $O(V + E)$。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 组装质量评估：独立的连通分量可能代表组装断裂或污染
- 基因组片段聚类：把相似的序列片段聚类成组
有向图的强连通分量
Section titled “有向图的强连通分量”强连通分量（SCC）是有向图中任意两顶点互相可达的最大子图。
- 算法
- Kosaraju 或 Tarjan 算法。
- 时间复杂度
- $O(V + E)$。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 代谢网络分析：识别代谢通路中的强连通模块
- 基因调控网络：分析调控回路的稳定性
5. 哈密顿回路（Hamiltonian Cycle）
Section titled “5. 哈密顿回路（Hamiltonian Cycle）”哈密顿回路：访问图中每个顶点恰好一次并回到起点的回路。
- 与 Eulerian Cycle 的区别
- Eulerian Cycle 访问每条边恰好一次，Hamiltonian Cycle 访问每个顶点恰好一次。
- 计算复杂性
- 判定图是否有 Hamiltonian Cycle 是 NP-complete 的。
- 与旅行商问题（TSP）的关系
- TSP 是带权图上的 Hamiltonian Cycle，寻找总权重最小的回路。
在生物信息学中的应用
Section titled “在生物信息学中的应用”1. 基因组重排
Section titled “1. 基因组重排”在基因组重排问题中，可以将问题建模为寻找 Hamiltonian Cycle：
- 顶点：基因组片段或同源区块
- 边：片段之间的邻接关系
- 目标：找到一条路径访问所有片段，对应于原始基因组顺序
2. 蛋白质折叠
Section titled “2. 蛋白质折叠”蛋白质折叠问题可以抽象为在构象空间中寻找最优路径：
- 顶点：可能的蛋白质构象
- 边：构象之间的转换
- 目标：寻找能量最低的折叠路径
3. 序列组装
Section titled “3. 序列组装”某些组装方法（如 Overlap-Layout-Consensus）可以看作 Hamiltonian Path 问题：
- 顶点：reads
- 边：reads 之间的重叠关系
- 目标：找到一条路径覆盖所有 reads
近似与启发式方法
Section titled “近似与启发式方法”由于 Hamiltonian Cycle 是 NP-complete 的，实际中常用：
- 启发式搜索：贪心、局部搜索
- 近似算法：对于特殊情况的近似
- 随机化算法：模拟退火、遗传算法
- 约束满足：SAT 求解器
Dirac 定理
Section titled “Dirac 定理”对于简单无向图 G（n ≥ 3），如果每个顶点的度数 ≥ n/2，则 G 必有 Hamiltonian Cycle。
这为某些特殊情况提供了充分条件。
6. 最小生成树（MST）
Section titled “6. 最小生成树（MST）”最小生成树是连接所有顶点的边权总和最小的树。
- Prim 算法
- 从任意顶点开始，每次添加最小权边连接新顶点。时间复杂度 $O((V + E) log V)$。
- Kruskal 算法
- 按边权排序，用并查集避免环。时间复杂度 $O(E log E)$。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 序列相似性网络：构建序列间的最小相似性连接
- 进化树构建：某些距离法构建树的变种
与其他算法的连接
Section titled “与其他算法的连接”- 动态规划：序列比对可以看作在网格图上的最短路径
- 贪心算法：Prim 和 Kruskal 算法是贪心策略的典型应用
- 随机化算法：在大图搜索中，随机游走（random walk）常用于采样
- Introduction to Algorithms (CLRS), 第 22-24 章
- Algorithm Design, Kleinberg & Tardos
- Bioinformatics Algorithms: An Active Learning Approach