近似算法
很多生物信息学问题是 NP-hard 的，无法在多项式时间内精确求解。近似算法提供了一种实用策略：在可接受的时间内找到足够好的解。
- 先理解什么是 NP-hard 问题，再看近似比的概念会更顺。
- 生物信息学中的很多现实工具本质上都是近似算法或启发式算法。
近似算法（approximation algorithm）用于解决优化问题，特别是 NP-hard 问题。它不追求最优解，而是在多项式时间内找到一个”足够好”的解。
- NP-hard 问题
- 目前没有已知的多项式时间精确算法的问题，如旅行商问题、集合覆盖等。
- 近似比（Approximation Ratio）
- 近似解与最优解的比值，衡量算法的质量。对于最大化问题，$C/C^* leq alpha$；对于最小化问题，$C/C^* leq alpha$。
- 启发式（Heuristic）
- 基于经验规则的算法，通常没有理论保证的近似比，但在实践中效果好。
要解决什么生物信息学问题
Section titled “要解决什么生物信息学问题”生物信息学中很多重要问题都是 NP-hard 的：
- 系统发育树构建：寻找最优的系统发育树
- 多重序列比对：寻找最优的多序列比对
- Motif 发现：寻找最优的保守模式
- 基因组重排：计算最小重排距离
- 图着色：基因表达数据的聚类
- 集合覆盖：选择最小探针集覆盖所有目标
1. NP-hard 问题概览
Section titled “1. NP-hard 问题概览”NP-hard 问题的特点：
- 精确求解
- 在最坏情况下需要指数时间，$O(2^n)$ 或更差。
- 验证
- 给定一个解，可以在多项式时间内验证其正确性。
- 现实约束
- 生物数据规模大（基因组、蛋白质组），精确求解往往不可行。
典型 NP-hard 问题
Section titled “典型 NP-hard 问题”| 问题 | 生物信息学应用 | 精确算法复杂度 |
|---|---|---|
| 旅行商问题（TSP） | 基因组重排、通路优化 | |
| 集合覆盖 | 探针设计、特征选择 | |
| 图着色 | 表达数据聚类 | |
| 最大团 | 蛋白质相互作用网络 | |
| 最小割 | 图分割、社区发现 |
2. 近似算法的基本概念
Section titled “2. 近似算法的基本概念”近似比（Approximation Ratio）
Section titled “近似比（Approximation Ratio）”对于最小化问题：
其中 是近似解的代价， 是最优解的代价， 是近似比（）。
对于最大化问题：
近似比越小，算法质量越好。
近似算法的分类
Section titled “近似算法的分类”- 常数近似比
- 近似比是常数，如 2-approximation。
- 对数近似比
- 近似比是 $O(log n)$，如集合覆盖问题。
- PTAS（多项式时间近似方案）
- 对于任意 $epsilon > 0$，存在 $(1+epsilon)$-approximation，时间复杂度可能是 $O(n^{1/epsilon})$。
- FPTAS（完全多项式时间近似方案）
- PTAS 且时间复杂度是关于 $1/epsilon$ 的多项式。
3. 顶点覆盖问题的 2-近似
Section titled “3. 顶点覆盖问题的 2-近似”顶点覆盖（Vertex Cover）：给定图 ，选择最少的顶点使得每条边至少有一个端点被选中。
这是一个经典的 NP-hard 问题，但有一个简单的 2-approximation 算法。
- 初始化空集合
- 当图中还有边时：
- 任选一条边
- 把 和 都加入
- 删除所有与 或 关联的边
- 返回
考虑图：
A -- B -- D| |C -- E算法执行：
- 选边
(A,B)，加入{A,B}，删除边(A,B)、(A,C)、(B,E) - 剩余边
(C,E)，选边(C,E)，加入{C,E} - 返回
{A,B,C,E}
最优解可能是 {A,B,E} 或 {B,C,D}，大小为 3。
近似解大小为 4，近似比为 。
为什么是 2-approximation
Section titled “为什么是 2-approximation”每条边至少有一个端点在最优解中。我们的算法每次选一条边，把两个端点都加入，最多是最优解的 2 倍。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 蛋白质相互作用网络：找到最小顶点集覆盖所有相互作用
- 基因调控网络：选择最少的关键基因覆盖所有调控关系
4. 集合覆盖的对数近似
Section titled “4. 集合覆盖的对数近似”集合覆盖（Set Cover）：给定全集 和若干子集 ，选择最少的子集覆盖 。
这是一个经典的 NP-hard 问题，贪心算法可以达到 近似比。
- 初始化 ，（剩余未覆盖元素）
- 当 时：
- 选择覆盖 中最多元素的子集
- 把 加入
- 从 中删除 的元素
- 返回
全集
子集：
贪心算法：
- 选择 （覆盖 4 个元素），
- 选择 （覆盖 4 个元素），
- 返回
最优解可能是 或 ，大小为 2。 贪心算法也得到大小为 2 的解。
贪心算法的近似比是 ，其中 是最大子集的大小， 是调和数。
在生物信息学中的应用
Section titled “在生物信息学中的应用”- 探针设计：选择最少探针覆盖所有目标序列
- 特征选择：机器学习中选择最少特征覆盖样本
- 通路分析：选择最少基因覆盖所有通路
5. 系统发育树构建的近似方法
Section titled “5. 系统发育树构建的近似方法”寻找最优系统发育树（如最大简约树、最大似然树）是 NP-hard 的。
- 距离法
- 如 UPGMA、Neighbor-Joining，基于距离矩阵构建树，$O(n^3)$ 或 $O(n^2)$。
- 启发式搜索
- 如树重排（tree bisection and reconnection），在树空间中局部搜索。
- 分支定界
- 精确算法，但通过剪枝加速，适用于小规模数据。
Neighbor-Joining
Section titled “Neighbor-Joining”Neighbor-Joining 是一种流行的距离法：
- 计算所有叶节点的净发散度
- 计算距离矩阵的 Q 矩阵
- 选择 Q 值最小的节点对合并
- 计算新节点的分支长度
- 更新距离矩阵
- 递归直到只剩两个节点
时间复杂度：，可以在合理时间内处理数百个物种。
距离法没有理论保证的近似比，但在实践中效果良好。
6. Motif 发现的近似方法
Section titled “6. Motif 发现的近似方法”寻找最优 motif 是一个困难的组合优化问题。
Gibbs Sampling
Section titled “Gibbs Sampling”Gibbs Sampling 是一种随机化近似算法：
- 随机初始化 motif 位置
- 随机选择一个序列，从其位置矩阵中移除
- 基于剩余序列构建位置权重矩阵（PWM）
- 根据概率采样新的 motif 位置
- 重复直到收敛
假设有 4 条序列，motif 长度为 6：
Seq1: ATGCGATGCGA...Seq2: CGATCGATCGA...Seq3: GATCGATCGAT...Seq4: TCGATCGATCG...- 随机选择位置：[3, 5, 2, 4]
- 移除 Seq1，用 [5, 2, 4] 构建 PWM
- 根据 PWM 计算 Seq1 各位置的概率
- 按概率采样新位置
- 重复多次，取最好结果
Gibbs Sampling 没有理论保证的近似比，但通过多次运行可以提高找到高质量解的概率。
7. 启发式 vs 近似算法
Section titled “7. 启发式 vs 近似算法”- 近似算法
- 有理论保证的近似比，如 2-approximation。
- 启发式
- 没有理论保证，但在实践中效果好，如 BLAST、Gibbs Sampling。
- 现实工具
- 大多数生物信息学工具是启发式的，结合多种策略。
现实工具的混合策略
Section titled “现实工具的混合策略”- BLAST：seed-and-extend（启发式）+ 统计评估
- MAFFT：渐进式比对（启发式）+ 迭代优化
- RAxML：启发式树搜索 + 最大似然评估
8. 近似算法的设计原则
Section titled “8. 近似算法的设计原则”每步做局部最优选择，希望达到全局近似最优。
- 优点：简单、快速
- 缺点：可能陷入局部最优
- 适用：集合覆盖、顶点覆盖等
把整数规划松弛为线性规划，求解后再取整。
- 优点：有理论保证
- 缺点：实现复杂
- 适用：顶点覆盖、设施选址等
引入随机性避免局部最优。
- 优点：跳出局部最优
- 缺点：结果不稳定
- 适用：Motif 发现、树搜索等
与其他算法的连接
Section titled “与其他算法的连接”- 贪心算法：很多近似算法基于贪心策略
- 随机化算法：启发式搜索常使用随机化
- 动态规划：某些近似算法结合 DP 和松弛
- 整数规划：松弛技术来自优化理论
- Approximation Algorithms, Vazirani
- The Design of Approximation Algorithms, Williamson & Shmoys
- Bioinformatics algorithms 相关文献