概率、图与动态规划预备

快速概览

如果把生物信息学看作计算问题，那么其核心抽象几乎可以归结为三类模型。它们不是孤立的章节分类，而是贯穿整个学科的通用语言，用于处理高噪音、大规模且具有复杂结构的生物数据。

概率模型：处理观测与真实状态之间的不确定性（如 HMM、PWM）
图模型：处理生物对象间的连接、路径与网络关系（如 de Bruijn 图、演化树）
动态规划：在重叠子问题中寻找全局最优解释（如序列比对、Viterbi 解码）
理解三者如何交织解决真实的生物信息学挑战

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

1. 概率模型：处理不确定性

生物数据（如测序 Reads）充满了噪音和不确定性。我们看到的观测值（Observations）并不直接等于真实状态（Hidden States）。

核心思想

概率模型将”确定性的回答”转变为”在给定数据下，某种解释有多大的可能性”。这一转变是生物信息学方法论的基石。具体而言，我们不再问”这是否正确”，而是问”在给定观测下，这种解释的概率是多少”。

条件概率与贝叶斯推断

概率模型的核心工具是条件概率和贝叶斯定理（Bayes’ Theorem）：

$P(H \mid D) = \frac{P(D \mid H) \cdot P(H)}{P(D)}$

其中 $H$ 代表假设（Hypothesis）， $D$ 代表观测数据（Data）。在生物信息学中：

$P(H \mid D)$ 是后验概率（Posterior Probability）：看到数据后，假设成立的概率。例如，某个基因组位点存在真实变异的概率。
$P(D \mid H)$ 是似然（Likelihood）：如果假设成立，产生当前观测数据的概率。例如，如果该位点确实存在变异，测序数据呈现当前模式的概率。
$P(H)$ 是先验概率（Prior Probability）：在不看数据时，假设成立的概率。例如，根据已知突变率估计的变异概率。

典型应用

HMM（隐马尔可夫模型，Hidden Markov Model）：根据 DNA 序列特征预测隐藏的外显子/内含子结构。HMM 假设系统在有限个离散状态之间转移，每个状态以一定的概率产生观测符号。详见隐马尔可夫模型。
位置权重矩阵（Position Weight Matrix, PWM）：描述转录因子结合位点（Transcription Factor Binding Site, TFBS）的统计偏好。PWM 的每一列记录了对应位置上各碱基出现的频率或对数几率。
变异检测：利用贝叶斯推断判断一个位点是真实变异还是测序错误。工具如 GATK 的 HaplotypeCaller 内部即使用了贝叶斯基因型推断模型。

2. 图模型：处理结构与连接

图（Graph, $G = (V, E)$ ）是描述生物对象间关系的理想工具。在生物信息学中，图的顶点和边可以承载不同的生物学含义。

基础定义

顶点（Vertex, 复数 Vertices）: 图中的节点，代表一个生物对象。例如：一条 Read、一个基因、一个物种、一个 k-mer。
边（Edge）: 连接两个顶点的关系。可以是有向的（如 de Bruijn 图中的 k-mer 拓展方向）或无向的（如蛋白质互作网络）。
权重（Weight）: 边上的数值，表示关系的强度。例如：比对得分、进化距离、覆盖度。
路径（Path）: 从起点到终点经过的一系列顶点和边，代表一个连续的序列或演化过程。

生物信息学中的图论问题

图论在生物信息学中无处不在，不同类型的图服务于不同的分析目的：

图的类型	顶点含义	边含义	典型问题	应用实例
de Bruijn 图	k-mer	k-1 重叠	欧拉路径	基因组组装（SPAdes, Velvet）
重叠-布局-一致性图	Read	Read 间的重叠	哈密顿路径	长读长组装（Canu, Flye）
系统发育树	物种/序列	祖先-后代关系	树的搜索与评分	物种进化分析（MEGA, RAxML）
蛋白质互作网络	蛋白质	物理/功能互作	社区检测	功能注释与通路分析
序列比对图	碱基对齐位置	匹配/插入/删除	最长路径	Needleman-Wunsch, Smith-Waterman

从 SBH 到 de Bruijn 图

早期的杂交测序（Sequencing by Hybridization, SBH）通过构建图并寻找欧拉路径（Eulerian Path）来重构序列。这一思想被现代组装算法继承和发展：

欧拉路径：经过图中每条边恰好一次的路径。de Bruijn 图中的欧拉路径等价于一条由所有 k-mer 拼接而成的基因组序列。
优势：寻找欧拉路径的复杂度为 $O(|E|)$ ，远低于哈密顿路径的 $O(2^{|V|})$ ，这是 de Bruijn 图方法比重叠图方法更高效的理论基础。

3. 动态规划：寻找最优解释

动态规划（Dynamic Programming, DP）适用于具有最优子结构（Optimal Substructure）和重叠子问题（Overlapping Subproblems）的优化任务。

核心直觉

如果我们要找到从 A 到 C 的最优路径，且必须经过 B，那么整条路径的最优性必然包含 A 到 B 的最优路径。这不是一个假设，而是一个数学上可以严格证明的性质（最优性原理，Principle of Optimality）。

动态规划的具体做法是：

定义子问题：将原问题分解为规模更小的子问题。
建立递推关系：用子问题的解来表达当前问题的解。
确定计算顺序：确保计算某个子问题时，它所依赖的更小子问题已经被求解。
存储中间结果：避免重复计算（记忆化，Memoization）。

生物信息学中的 DP 应用

动态规划在生物信息学中有极为广泛的应用，几乎涵盖了序列分析的所有核心任务：

问题	DP 的作用	代表算法
全局序列比对	在所有对齐方案中找得分最高者	Needleman-Wunsch
局部序列比对	寻找两序列间最佳局部相似片段	Smith-Waterman
HMM 解码	在状态网格中找概率最大的路径	Viterbi Algorithm
RNA 二级结构	在不交叉的碱基配对中找自由能最低者	Nussinov Algorithm
基因组比对	跨大范围间隔的种子-扩展策略	Cactus, minimap2 的内部 DP
多序列比对	逐步将序列加入已有比对	Progressive Alignment

4. 三者的交织

在真实的生物信息学工具中，概率模型、图模型和动态规划往往是深度耦合的。理解这种交织关系，是掌握现代生物信息学方法的关键。

HMM：概率与 DP 的深度融合

HMM 既是概率模型（定义了状态转移概率和发射概率），又利用动态规划（Viterbi 算法）进行求解：

前向算法（Forward Algorithm）：使用 DP 计算观测序列在模型下的概率 $P(O \mid \lambda)$ ，用于模型评估。
Viterbi 算法：使用 DP 寻找产生观测序列的最可能状态路径，用于解码（如基因结构预测）。
前向-后向算法（Forward-Backward Algorithm）：计算每个位置处于每种状态的后验概率，用于参数学习（Baum-Welch 训练）。

基因组组装：图问题与统计模型的结合

组装算法既是图问题（在 de Bruijn 图或重叠图中寻找路径），又需要利用统计模型来处理噪音：

覆盖度统计：利用泊松分布（Poisson Distribution）估计期望覆盖度，识别覆盖度异常的区域（重复序列或缺失）。
错误修剪：利用边的覆盖度（k-mer 频率）来判断边是真实连接还是测序错误产生的假边。低频 k-mer 通常对应测序错误。
气泡简化：在 de Bruijn 图中，两条相近的路径（“气泡”）通常由杂合变异产生，需要被合并。

比对软件：索引加速与 DP 精化

比对软件（如 BWA、minimap2）既利用索引结构（后缀数组、最小完美哈希等图/树结构）加速搜索，又利用动态规划进行局部精化：

索引阶段：将参考基因组构建为索引（如 FM-Index），实现快速种子查找。
种子-扩展阶段：找到候选匹配区域后，使用带仿射空隙罚分（Affine Gap Penalty）的 DP 进行精确对齐。
评分与过滤阶段：利用概率模型（如映射质量 MapQ）评估比对结果的可信度。

5. 一个统一视角：概率图模型

从更高层次来看，这三类模型可以被统一在**概率图模型（Probabilistic Graphical Model, PGM）**的框架下：

贝叶斯网络（Bayesian Network）：有向无环图（DAG），节点代表随机变量，有向边代表条件依赖关系。
马尔可夫随机场（Markov Random Field, MRF）：无向图，边代表变量间的对称依赖关系。
HMM 是一种特殊的贝叶斯网络：状态变量沿时间轴（或序列位置）形成链式结构。

在生物信息学中，许多看似不同的方法都可以被理解为概率图模型的特例或近似。理解这一统一视角，有助于在面对新问题时选择合适的建模策略。

常见误区

误区一：认为概率模型只在"有噪音"时才需要。实际上，即使数据完美，概率模型仍然提供了处理不确定性的统一框架。例如，多序列比对中的保守性评估本质上就是一个概率问题。
误区二：将图模型等同于可视化工具。图模型是数学抽象，其价值在于将关系结构形式化，从而使得算法可以在其上操作（如寻路、社区检测），而非仅仅用于画图。
误区三：认为动态规划只适用于"路径"问题。DP 的本质是"通过存储子问题解来避免重复计算"。除了路径问题，DP 还适用于区间划分（如 RNA 结构预测）、背包问题（如选择最优的 SNP 集合）等多种问题类型。
误区四：混淆"贪心"与"动态规划"。贪心算法每步做局部最优选择且不回溯；动态规划则系统地探索所有可能，通过存储中间结果保证全局最优。参见 [贪心算法](./greedy-algorithms.mdx)。