重复序列、分叉与图清理

快速概览

组装图的真正困难在于建图之后：如何区分真实分叉与错误噪声、清理异常结构、保留真实信息，并尽可能为后续分析提供稳定的图结构。

重复序列制造真实分叉，需要长距离信息辅助解析
测序错误制造假分叉（tips、bubbles），需要根据 coverage 和长度识别清理
图清理是做结构判断而非机械删边，需权衡任务目标与数据特征
真实场景中通常需要多轮迭代清理才能收敛

所属板块 核心方法

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

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

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

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

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

是什么

在组装图中，真正困难的地方往往不只是”怎么建图”，而是：图建好之后如何理解分叉、识别错误、清理噪声，并尽可能保留真实结构。重复序列、测序错误和 coverage 波动，都会让图结构偏离理想情况。

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

如果一个 de Bruijn graph 中出现了：

短小的异常分支；
多条相似路径；
覆盖度极不稳定的边；
难以判断哪条路径才是正确重建；

那么组装问题就不再只是”找路径”，而是”先判断图中哪些结构是真信号，哪些是噪声”。

输入与输出

输入

图清理通常建立在以下输入之上：

由 reads 构建出的 de Bruijn graph 或类似组装图；
节点 / 边的 coverage 信息；
k-mer 频率分布；
可选的 paired-end、长读长或其他额外连接证据。

输出

目标输出不是”完全没有分叉的图”，而是：

删除明显由错误造成的低频结构；
合并可简化的线性路径；
保留可能反映真实重复、变异或多倍性结构的分叉；
为后续 contig 构建提供更稳定的图结构。

核心思想 / 图结构直觉

重复序列会制造真实分叉

重复序列会让不同基因组区域共享相同 k-mer，因此在图中形成汇合或再分叉的结构。此时图中的歧义并不是错误，而是原始序列本身无法仅靠局部 k-mer 唯一拆解。

测序错误会制造假分叉

组装图异常结构与清理策略示意图 — 常见的图异常结构：1. Tips (由测序错误产生的死端)；2. Bubbles (由变异或局部错误产生的平行路径)；3. Repeats (由于序列重复导致的路径坍缩与分叉)。

错误碱基往往会制造低频异常 k-mer，进而形成：

tips；
short dead-end branches；
异常 bubbles；
coverage 明显异常的短路径。

这些结构看起来也像”分叉”，但本质上只是观测噪声投影到图结构中的结果。

图清理是在做”结构判断”而不是机械删边

图清理并不是把所有复杂结构都压平，而是根据 coverage、路径长度、局部拓扑和外部证据，区分：

哪些分叉更像错误；
哪些分叉更像真实重复；
哪些结构应保留到后续步骤再解决。

常见清理策略

去掉 tips

当一条很短的分支：

长度很短；
coverage 很低；
很快走到死路；

它往往更像由单个或少量错误 k-mer 引起的假结构，可以优先删除。

处理 bubbles

bubble 指两条短路径从同一点分出、稍后又重新汇合。它们可能来自：

测序错误；
真实等位变异；
重复区域中的局部歧义。

是否要合并 bubble，取决于两条路径在长度、coverage 和序列差异上的表现，以及当前组装目标是否允许保留变异信息。

压缩线性路径

对没有分叉的连续路径，通常可以合并成更长的单元，减少图复杂度。这一步本身不解决重复问题，但能让真正困难的结构更清晰地暴露出来。

借助额外证据跨越分叉

paired-end、mate-pair、长读长或其他长距离连接信息，可以帮助判断两段路径是否应被连接。这些证据在重复区域尤其重要，因为仅靠局部图结构常常无法判定正确路径。

示例

设想一个 de Bruijn graph 中，某个节点分出三条路径：

一条很短、coverage 很低，并迅速终止；
两条较长路径覆盖度接近，并在后方重新汇合。

一个合理判断可能是：

第一条更像 tip，可视为由错误碱基造成；
后两条可能构成 bubble；
如果两条路径只差少量碱基，且 coverage 都合理，它们可能对应真实变异或近似重复；
是否合并它们，要看你的目标是得到单一路径、保留变异信息，还是等待更长距离证据来判定。

这个例子说明：图清理不是统一规则，而是把结构、coverage 和任务目标一起考虑。

复杂度与适用前提

图清理策略的效果依赖于若干前提：

coverage 不能过于稀疏，否则真实低丰度路径容易被误删；
错误率不能高到让图被大量假 k-mer 淹没；
k 值选择会显著影响图拓扑；
在高重复、高多态或混样场景中，真实分叉与错误分叉更难分开。

因此，图清理不是一个与数据无关的固定步骤，而是和 read length、coverage、错误模型以及样本复杂度共同决定的。

与真实工具或流程的连接

真实组装流程里，图清理通常发生在：

error correction 之后或同时；
contig 提取之前；
组装参数迭代调整过程中。

很多组装器的效果差异，并不只来自”图建得对不对”，还来自它们怎样处理：

低频边；
bubble resolution；
repeat resolution；
coverage 异常路径；
外部长距离证据的整合。

算法细节

Tip Removal 算法

Tip 识别

Tip 是指图中短小的死端分支，通常由测序错误引起。

定义：一个 tip 是满足以下条件的路径 $P = (v_1, v_2, ..., v_t)$ ：

$v_1$ 的入度为 0 或出度 $\geq 2$
$v_t$ 的出度为 0
路径长度 $t \leq L_{max}$ （最大 tip 长度阈值）
路径上边的平均 coverage $\leq C_{min}$ （最小 coverage 阈值）

算法 1：Tip 识别与删除

输入：de Bruijn Graph G = (V, E)，边权重 w（coverage）
      最大 tip 长度 L_max，最小 coverage 阈值 C_min
输出：清理后的图 G'

1. G' = G
2. 对于每个顶点 v ∈ V：
   a. 如果 v 的出度 = 0（死端）：
      - 从 v 开始反向 BFS，构建路径 P
      - 如果 |P| ≤ L_max 且 avg_coverage(P) ≤ C_min：
         * 删除 P 中所有边和孤立顶点
   b. 如果 v 的入度 = 0（起始端）：
      - 从 v 开始正向 BFS，构建路径 P
      - 如果 |P| ≤ L_max 且 avg_coverage(P) ≤ C_min：
         * 删除 P 中所有边和孤立顶点
3. 返回 G'

时间复杂度： $O(|V| + |E|)$ ，每个顶点和边只访问常数次

空间复杂度： $O(L_{max})$ ，BFS 队列最大长度

阈值选择

启发式规则：

$L_{max}$ 通常设置为 read 长度的 2-3 倍
$C_{min}$ 通常设置为平均 coverage 的 10-20%
可以使用 k-mer 频率分布的拐点自动确定 $C_{min}$

Bubble Resolution 算法

Bubble 识别

Bubble 是指从同一点分出、稍后又重新汇合的两条短路径。

定义：一个 bubble 是满足以下条件的结构：

存在起点 $s$ 和终点 $t$
存在两条不相交（除 $s, t$ 外）的路径 $P_1, P_2$ 从 $s$ 到 $t$
$|P_1| \leq L_{bubble}$ 且 $|P_2| \leq L_{bubble}$
两条路径的序列相似度高于阈值 $S_{min}$

算法 2：Bubble 识别

输入：de Bruijn Graph G = (V, E)
      最大 bubble 长度 L_bubble，相似度阈值 S_min
输出：bubble 集合 B

1. B = ∅
2. 对于每个顶点 s ∈ V：
   a. 如果 outdegree(s) ≥ 2：
      - 对于每对出边（s, u₁）, (s, u₂)：
         * 从 u₁ 开始 BFS，限制深度为 L_bubble
         * 从 u₂ 开始 BFS，限制深度为 L_bubble
         * 如果在深度限制内找到共同汇合点 t：
            - 提取路径 P₁: s → ... → t
            - 提取路径 P₂: s → ... → t
            - 如果 similarity(P₁, P₂) ≥ S_min：
               * 将（P₁, P₂） 加入 B
3. 返回 B

时间复杂度： $O(|V| \cdot d^2 \cdot L_{bubble})$ ，其中 $d$ 为平均出度

Bubble 合并策略

算法 3：基于 Coverage 的 Bubble 合并

输入：bubble 集合 B，边权重 w
输出：合并后的图 G'

1. G' = G
2. 对于每个 bubble (P₁, P₂) ∈ B：
   a. 计算 coverage(P₁) 和 coverage(P₂)
   b. 如果 coverage(P₁) >> coverage(P₂)（例如比值 > 3）：
      - 删除 P₂，保留 P₁
   c. 否则如果 coverage(P₂) >> coverage(P₁)：
      - 删除 P₁，保留 P₂
   d. 否则（coverage 接近）：
      - 如果序列差异很小（≤ 1-2 个碱基）：
         * 保留 coverage 更高的路径
      - 否则：
         * 保留两条路径（可能代表真实变异）
3. 返回 G'

算法 4：基于序列相似度的 Bubble 合并

输入：bubble 集合 B，相似度阈值 S_merge
输出：合并后的图 G'

1. G' = G
2. 对于每个 bubble (P₁, P₂) ∈ B：
   a. 将 P₁ 和 P₂ 转换为序列 S₁, S₂
   b. 计算 S₁ 和 S₂ 的编辑距离 d
   c. 如果 d / min(|S₁|, |S₂|) ≤ (1 - S_merge)：
      - 合并两条路径为 consensus 序列
      - 用 consensus 替换原 bubble
   d. 否则：
      - 保留两条路径
3. 返回 G'

线性路径压缩

算法 5：线性路径压缩

输入：de Bruijn Graph G = (V, E)
输出：压缩后的图 G'

1. G' = G
2. 对于每个顶点 v ∈ V：
   a. 如果 indegree(v) = 1 且 outdegree(v) = 1：
      - 设入边为（u, v），出边为（v, w）
      - 合并（u, v） 和（v, w） 为新边（u, w'）
      - w' 为合并后的顶点（序列拼接）
      - 删除顶点 v
3. 返回 G'

时间复杂度： $O(|V| + |E|)$

效果：减少图复杂度，突出真正的分叉结构

基于统计的异常检测

算法 6：基于 Z-score 的异常边检测

输入：de Bruijn Graph G = (V, E)，边权重 w
      Z-score 阈值 Z_thresh
输出：异常边集合 E_abnormal

1. 计算所有边权重的均值 μ 和标准差 σ
2. E_abnormal = ∅
3. 对于每条边 e ∈ E：
   a. 计算 z = (w(e) - μ) / σ
   b. 如果 |z| > Z_thresh（通常取 2-3）：
      - 将 e 加入 E_abnormal
4. 返回 E_abnormal

注意：这种方法假设 coverage 近似正态分布，在 coverage 不均匀时效果有限。

复杂度总结

算法	时间复杂度	空间复杂度	主要参数
Tip Removal	O(V+E)	O(L_max)	L_max, C_min
Bubble 识别	O(V · d² · L_bubble)	O(L_bubble)	L_bubble, S_min
Bubble 合并	O(B · L_bubble)	O(L_bubble)	coverage 比值
线性压缩	O(V+E)	O(1)	无
异常检测	O(E)	O(1)	Z_thresh

其中 $d$ 为平均顶点出度， $|B|$ 为 bubble 数量。

迭代清理策略

实际应用中，图清理通常需要多轮迭代：

算法 7：迭代图清理

输入：初始图 G₀，最大迭代次数 T
输出：清理后的图 G_T

1. G_current = G₀
2. 对于 t = 1 到 T：
   a. G_current = TipRemoval(G_current)
   b. G_current = BubbleResolution(G_current)
   c. G_current = LinearCompression(G_current)
   d. 如果 G_current ≈ G(t-1)（收敛）：
      - break
3. 返回 G_current

收敛判断：当连续两轮清理后，图的边数变化小于阈值（如 1%）时认为收敛。

参考资料

组装图与 de Bruijn graph 相关教材和综述
与 coverage、error model、repeat resolution 相关文献
常见组装器关于 graph simplification 的实现说明