Exon Chaining 问题

快速概览

Exon Chaining 是通过动态规划解决基因预测中的候选外显子选择问题：在基因组序列中找到权重最大的互不重叠外显子集合。

将候选外显子建模为带权区间（l, r, w）
构建有向无环图，边代表区间兼容关系
用动态规划在 O(n log n) 时间内找到最大链
是剪接比对（Spliced Alignment）的前置步骤

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

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

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

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

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

是什么

Exon Chaining 是基因预测中的关键子问题：给定一组候选外显子（带权区间），选择互不重叠的子集使总权重最大。

这是经典加权区间调度问题的生物信息学应用。

要解决什么生物信息学问题

基因预测的两阶段方法

第一阶段：生成候选外显子

寻找所有潜在剪接位点（AG…GT）
根据序列相似性、密码子使用等打分

第二阶段：选择最佳外显子集合

外显子不能重叠（生物学约束）
最大化总得分（统计目标）

示例场景

已知人类蛋白序列，预测小鼠基因组中的对应基因结构：

小鼠基因组中生成大量候选外显子（可能包含假阳性）
需要选择能拼接成合理蛋白的外显子链

问题形式化

输入

基因组序列 $G = g_1g_2...g_n$
候选外显子集合 $\mathcal{B} = \{B_1, B_2, ..., B_m\}$
每个外显子 $B_i = (l_i, r_i, w_i)$ $B_{i} = (l_{i}, r_{i}, w_{i})$ ：
- $l_i$ ：左端点（起始位置）
- $r_i$ ：右端点（终止位置）
- $w_i$ ：权重（与目标蛋白的相似度）

输出

最大链：互不重叠的外显子子集，总权重最大。

链 $\Gamma = (B_{i_1}, B_{i_2}, ..., B_{i_k})$ 满足： $r_{i_j} < l_{i_{j+1}} \quad \text{对所有 } j$

目标：最大化 $\sum_{j=1}^k w_{i_j}$

图的构建

顶点

创建 $2m + 2$ 个顶点：

$s_{initial} = 0$ （起点）
$s_{final} = n$ （终点，基因组长度）
每个外显子 $B_i$ 的左右端点 $l_i$ 和 $r_i$

边

区间边：对每个外显子 $B_i$ ，边 $(l_i \rightarrow r_i)$ 权重为 $w_i$
连接边：对所有相邻位置，边 $(v_j \rightarrow v_{j+1})$ 权重为 0

图示例

位置:   0    5    10   15   20
        |    |    |    |    |
外显子1:  [====] (2,5,3)
外显子2:       [========] (8,15,7)
外显子3:            [==] (12,13,1)
外显子4:                 [====] (16,18,4)

图结构:
0 →(0)→ 2 →(3)→ 5 →(0)→ 8 →(7)→ 15 →(0)→ 16 →(4)→ 18 →(0)→ 20
              ↘(0)→ 12 →(1)→ 13 ↗

动态规划算法

状态定义

设 $s_i$ 为以顶点 $v_i$ 结尾的最长路径长度。

递推关系

EXONCHAINING(G, m):
    // 初始化
    s[initial] = 0

    // 按位置顺序处理所有 2m+2 个顶点
    for i = 1 to 2m+1:
        s[i] = 0

        if v_i 是某区间 B 的右端点:
            j = B 的左端点索引
            w = B 的权重
            s[i] = max(s[i-1], s[j] + w)
        else:
            s[i] = s[i-1]  // 只继承前一个值

    return s[final]

时间复杂度

排序端点： $O(m \log m)$
动态规划： $O(m)$
总体： $O(m \log m)$

实例演示

输入

位置: 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18

外显子: (2,3,3), (4,8,6), (9,10,1), (11,15,7), (16,18,4)

执行过程

顶点	类型	计算	s[i]
0	起点	0	0
2	左端点	继承 s[0]	0
3	右端点	max(s[2], s[2]+3)=3	3
4	左端点	继承 s[3]=3	3
8	右端点	max(s[7]=3, s[4]+6=9)	9
9	左端点	继承 s[8]=9	9
10	右端点	max(s[9]=9, s[9]+1=10)	10
11	左端点	继承 s[10]=10	10
15	右端点	max(s[14]=10, s[11]+7=17)	17
16	左端点	继承 s[15]=17	17
18	右端点	max(s[17]=17, s[16]+4=21)	21

结果

最优链： $(2,3,3) \rightarrow (4,8,6) \rightarrow (11,15,7) \rightarrow (16,18,4)$

总权重： $3 + 6 + 7 + 4 = 20$ （注意：实际为 20，表格计算中（9,10,1）被跳过）

回溯获得具体外显子组合。

局限性与改进

主要局限

端点不精确：外显子边界可能预测不准
无全局一致性：最优链可能与目标蛋白不对齐

示例问题：

第一个外显子匹配目标蛋白的后缀
第二个外显子匹配目标蛋白的前缀
这样的链无法形成有效全局比对

解决方案：剪接比对

Spliced Alignment 在 Exon Chaining 基础上增加全局比对约束：

确保外显子链与目标蛋白形成有效比对
算法更复杂，但结果更准确

与相似性方法的关系

Exon Chaining 属于相似性基因预测方法：

统计方法（ORF、密码子偏好）
         ↓
候选外显子生成
         ↓
Exon Chaining / Spliced Alignment（选择最佳组合）
         ↓
预测基因结构

常见误区

外显子权重越高，就越应该被选入最优链：
外显子的权重只是链优化的一个因素。一个高权重的外显子如果与链中其他外显子严重重叠，可能被排除；反之，多个权重中等但互不重叠的外显子可能组成总权重更高的链。这正是动态规划而非贪心策略的必要性所在。
Exon Chaining 的结果就是最终的基因预测：
Exon Chaining 只解决了"选择互不重叠的外显子"这一问题，但没有保证选出的外显子链能与目标蛋白形成有效的全局比对。一个外显子可能匹配蛋白的前半段，下一个却匹配后半段的逆序——这在生物学上毫无意义。这一局限正是 Spliced Alignment 要解决的问题。
候选外显子越多，预测结果越好：
更多候选外显子增加了找到真实基因结构的可能性，但也增加了搜索空间和假阳性。过短的候选外显子（如 < 25 bp）尤其危险，它们可能随机匹配目标蛋白的任意片段，导致"马赛克效应"——拼凑出一串高分但无生物学意义的片段链。候选外显子的生成和过滤是预测质量的关键。

总结

Exon Chaining 是加权区间调度问题的生物信息学应用
将外显子选择转化为 DAG 最长路径问题
时间复杂度 $O(m \log m)$ ，适合大规模基因组分析
是剪接比对的基础，后者增加全局比对约束