de Bruijn graph 组装

快速概览

de Bruijn graph 组装把 read 的局部重叠信息压缩成统一的图结构，是理解短读长组装和图清理问题的最经典入口之一。

先理解顶点和边分别表示什么，再去看 tips、bubbles、repeats 等复杂结构。
它不是单纯的欧拉路径题，而是一整套"建图 + 清理 + 路径恢复"的思路。

所属板块 核心方法

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

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

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

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

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

是什么

de Bruijn graph 是短读长组装中的经典模型。它的核心思想不是直接比较每一对 read 是否重叠，而是先把 reads 分解成 k-mer，再把这些局部片段组织成图。

最常见的构造方式是：

顶点表示 (k-1)-mer；
边表示 k-mer；
如果一个 k-mer 的前缀和后缀分别对应两个 (k-1)-mer，就在这两个顶点之间连一条边。

这样，序列重建问题就被转成了图中的路径问题。

为什么重要

组装的目标是：从大量局部 read 中恢复原始基因组或转录本序列。

如果直接判断每一对 read 是否重叠，代价会非常高；而 de Bruijn graph 的价值就在于：它把大量局部重叠信息压缩到了统一的图结构中。

这使得我们可以更系统地处理：

read 数量巨大；
重复序列很多；
测序错误会制造伪连接；
coverage 不均匀导致图结构复杂。

核心概念

顶点与边的定义

de Bruijn graph 构建与干扰结构示意图 — 左：从序列到 k-mer 的滑动窗口分解；右：顶点（（k-1）-mer）与边（k-mer）的映射关系；下：图中常见的错误结构（Tip 和 Bubble）。

设一个 k-mer 为 x_1x_2...x_k，则：

它的前缀顶点为 x_1x_2...x_{k-1}；
它的后缀顶点为 x_2x_3...x_k。

于是每个 k-mer 对应一条从前缀顶点到后缀顶点的有向边。

图上的路径

如果原始序列中相邻的 k-mer 共享 k-1 个字符，那么在图中就会自然地接起来。组装的目标之一，就是在图上找到合理路径，把这些局部片段重新串成更长序列。

图中的主要干扰

真实数据里常见三类问题（见上方示意图）：

测序错误：制造低频异常 k-mer，在图中表现为 Tips（短小分支）或孤立的低覆盖边。
重复序列：多个区域共享相同 k-mer，导致图中出现复杂分叉和交叉。
SNP/测序微小错误：在图中形成 Bubbles（气泡结构），即两条路径发散后又很快合并。
Coverage 不均匀：图清理时不能只靠单一阈值，否则容易误删真实边。

k 的选择

k 的取值会极大影响图结构：

k 较小	k 较大
图更连通，更敏感	图更稀疏，更有区分力
更容易跨过错误和低覆盖区域	更容易被错误打断
重复更难分解	内存和数据要求更高

因此，选择合适的 k 实际上是在连通性、区分力和噪声鲁棒性之间做平衡。

示例

de Bruijn graph 图结构示意图 — 把 k-mer 映射成边、把（k-1）-mer 映射成顶点之后，组装问题就转成图上的路径与图清理问题。

考虑序列：

AAGATTCTCTA

取 k = 4，得到一组 4-mer：

AAGA
AGAT
GATT
ATTC
TTCT
TCTC
CTCT
TCTA

例如：

AAGA 对应 AAG -> AGA
AGAT 对应 AGA -> GAT
GATT 对应 GAT -> ATT

把所有边连起来后，就能在图中看到一条重建原始序列的路径。

与真实工具或流程的连接

de Bruijn graph 常让人联想到欧拉路径问题，因为理想情况下我们希望找到一条遍历边的合理路径，把所有 k-mer 串回原始序列。

但真实组装通常并不是简单地”直接找欧拉路径”就结束，还需要：

图清理；
错误校正；
coverage 统计；
重复解析；
contig / scaffold 构建。

很多经典短读长组装器都在某种意义上建立在 de Bruijn graph 思想上。即使具体实现不同，它们通常都要面对相同问题：

如何过滤低频错误 k-mer；
如何简化图；
如何处理 bubbles 和 repeats；
如何从图导出 contig。

算法细节

de Bruijn Graph 构建算法

基本构建方法

算法 1：从 k-mer 构建 de Bruijn Graph

输入：k-mer 集合 K = \{k₁, k₂, ..., k_m\}
输出：de Bruijn Graph G = (V, E)

1. V = ∅, E = ∅
2. 对于每个 k-mer k_i = x₁x₂...x_k ∈ K：
   a. 前缀顶点 u = x₁x₂...x_\{k-1\}
   b. 后缀顶点 v = x₂x₃...x_k
   c. 如果 u ∉ V，将 u 加入 V
   d. 如果 v ∉ V，将 v 加入 V
   e. 添加有向边 e = (u, v) 到 E
3. 返回 G = (V, E)

时间复杂度： $O(m \cdot k)$ ，其中 $m$ 为 k-mer 数量， $k$ 为 k-mer 长度

空间复杂度： $O(m \cdot k)$

从 Reads 直接构建

实际应用中，通常直接从 reads 构建，避免显式枚举所有 k-mer：

算法 2：滑动窗口构建

输入：read 集合 R = \{r₁, r₂, ..., r_n\}，k-mer 长度 k
输出：de Bruijn Graph G = (V, E)

1. V = ∅, E = ∅
2. 对于每个 read r_i ∈ R：
   a. 如果 |r_i| < k，跳过
   b. 对于 j = 0 到 |r_i| - k：
      - 提取 k-mer s = r_i[j:j+k]
      - u = s[0:k-1]（前缀）
      - v = s[1:k]（后缀）
      - 将 u, v 加入 V
      - 添加边（u, v） 到 E（或增加权重）
3. 返回 G

时间复杂度： $O(N \cdot L)$ ，其中 $N$ 为 read 数量， $L$ 为平均 read 长度

k-mer 计数与错误过滤

在构建图之前，通常需要过滤低频错误 k-mer：

算法 3：基于频次的 k-mer 过滤

输入：read 集合 R，k-mer 长度 k，最小频次阈值 f_min
输出：过滤后的 k-mer 集合 K'

1. 构建哈希表 H：k-mer → 计数
2. 对于每个 read r ∈ R：
   a. 提取所有 k-mer
   b. 对于每个 k-mer k'：H[k']++
3. K' = \{k' | H[k'] ≥ f_min\}
4. 返回 K'

时间复杂度： $O(N \cdot L)$ 构建， $O(m)$ 过滤，其中 $m$ 为唯一 k-mer 数量

Eulerian Path 算法

Eulerian Path 存在条件

对于有向图 $G = (V, E)$ ，Eulerian path 存在当且仅当：

图是连通的（在忽略边的方向后）
最多一个顶点的出度比入度大 1（起点）
最多一个顶点的入度比出度大 1（终点）
所有其他顶点的入度等于出度

Hierholzer 算法

算法 4：Hierholzer 算法寻找 Eulerian Circuit

输入：连通有向图 G = (V, E)，满足 Eulerian circuit 条件
输出：Eulerian circuit（顶点序列）

1. 选择任意起始顶点 v_start
2. 初始化空路径 P
3. stack = [v_start]
4. while stack 不为空：
   a. v = stack.top()
   b. 如果 v 有未访问的出边 e = (v, u)：
      - 标记 e 为已访问
      - 将 u 压入 stack
   c. 否则：
      - 将 v 从 stack 弹出
      - 将 v 加入 P 的开头
5. 返回 P

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

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

适应组装场景的变体

实际组装中，图往往不满足严格的 Eulerian path 条件。需要使用启发式方法：

算法 5：贪心路径延伸（启发式）

输入：de Bruijn Graph G = (V, E)，边权重 w（coverage）
输出：路径集合 P

1. P = ∅
2. 标记所有边为未访问
3. while 存在未访问边：
   a. 选择未访问边中权重最大的边（u, v） 作为起点
   b. path = [u, v]
   c. 标记（u, v） 为已访问
   d. 当前顶点 cur = v
   e. while cur 有未访问出边：
      - 选择权重最大的未访问出边（cur, next）
      - 如果 next ∈ path（形成环）：
         * 停止当前路径延伸
      - 否则：
         * 将 next 加入 path
         * 标记（cur, next） 为已访问
         * cur = next
   f. 将 path 加入 P
4. 返回 P

时间复杂度： $O(|E| \log |E|)$ ，如果使用优先队列选择最大权重边

从路径恢复序列

算法 6：路径到序列转换

输入：顶点路径 P = [v₁, v₂, ..., v_t]，其中每个 v_i 是（k-1）-mer
输出：重建序列 S

1. S = v₁（完整（k-1）-mer）
2. 对于 i = 2 到 t：
   a. 取 v_i 的最后一个字符 c
   b. S += c
3. 返回 S

时间复杂度： $O(|S|)$

正确性：由于相邻顶点共享 k-2 个字符，只需追加每个新顶点的最后一个字符即可重建完整序列。

复杂度与优化

空间优化：使用边表示

为减少内存，可以不显式存储顶点，而只存储边（k-mer）：

数据结构：使用最小完美哈希或布隆过滤器存储 k-mer

优势：空间复杂度从 $O(m \cdot k)$ 降低到接近理论下界

并行化策略

k-mer 计数：使用分布式哈希表
图构建：按 k-mer 分片并行处理
路径寻找：按连通分量并行延伸

复杂度总结

阶段	主要算法	时间复杂度	空间复杂度
k-mer 提取	滑动窗口	$O(N \cdot L)$	$O(m \cdot k)$
k-mer 过滤	频次统计	$O(N \cdot L)$	$O(m)$
图构建	顶点-边映射	$O(m)$	$O(m \cdot k)$
Eulerian Path	Hierholzer	$O(	E
序列恢复	路径拼接	$O(	S

其中 $N$ 为 read 数量， $L$ 为平均 read 长度， $m$ 为 k-mer 数量， $|S|$ 为输出序列长度。