二、de Bruijn图（DBG）算法

DBG算法是二代短读长组装的核心方法，其工作流程如下：
（1）k-mer分解
将所有reads拆分为长度为k的短片段（k-mer）。例如，序列"ATGCGGAT"在k=5时产生：ATGCG、TGCGG、GCGGA、CGGAT。通常k取奇数（如21、31、51、71），且不超过read长度的2/3。
（2）构建DBG
- 每个k-mer作为图中的一个顶点（node）
- 若两个k-mer之间有k-1个碱基重叠，则在它们之间建立一条有向边
- 例如，ATGCG和TGCGG共享TGCG（4个碱基），建立从ATGCG到TGCGG的边
- 将不同reads产生的相同k-mer合并为一个顶点，记录覆盖度
（3）图简化
测序错误会在DBG中产生两类错误结构：
- Tips（死胡同）：由于测序错误产生的低频k-mer连接到主路径后又很快终止。处理：去除长度和覆盖度低于阈值的tips。
- Bubbles（气泡）：由于杂合位点或测序错误，主路径在某处分叉为两条路径，在下游又汇合。处理：保留覆盖度较高的路径，或在杂合组装中保留两条路径。
（4）contig提取
在简化后的DBG中，一条连续的路径（从没有入度的顶点开始到没有出度的顶点结束）对应一个contig。
k-mer大小的选择：
- k值较小：对重复序列的分辨率低（不同重复单元可能共享k-mer），但覆盖度高（每个read产生更多k-mer）
- k值较大：对重复序列的分辨率高，但覆盖度低（要求更大的测序深度才能保证每个k-mer被覆盖）
- 多k-mer策略（如SPAdes）：从较小的k开始组装，逐步增大k值，利用小k的连续性和大k的准确性优势