泛基因组时代中的序列到图映射算法综述

1 背景与意义

传统线性参考基因组存在参考偏倚问题，导致非参考等位基因被遗漏或错误映射。泛基因组（Pangenome）通过整合多个个体基因组构建图结构，提供更全面的遗传多样性参考。序列到图映射（Sequence-to-Graph Mapping, S2G） 是泛基因组分析的核心技术，支撑变异检测、基因分型、长读长纠错等应用。近年来已有20余种S2G算法开发，但此前尚无系统性综述。

2 泛基因组图的表示形式

1. De Bruijn图（DBG）
   • 节点为固定长度k-mer，边表示k-mer重叠关系。紧凑化DBG（cDBG）合并非分支路径（unitig）以减少规模，彩色DBG（cDBG）标记不同单倍型。
2. 序列图（Sequence Graph）
   • 节点代表序列，边表示连接关系，常用于有向无环图（DAG）表达变异分支。
3. 变异图（Variation Graph）
   • 双向图结构，节点包含正反链序列，边可双向遍历，支持嵌入路径表示单倍型。
4. 弹性表示（Elastic Representation）
   • 弹性创始图（EFG）：将多序列比对（MSA）分块合并节点，实现高效模式匹配索引。
   • 弹性退化字符串（ED-string）：用非确定性字符串表示小变异（如SNV、indel）。

3 S2G映射策略：种子-过滤-扩展

主流算法采用种子-过滤-扩展三步策略（图2），平衡效率与精度：

1. 种子生成（Seeding）

   • 静态种子：固定长度k-mer（如GenomeMapper）、最小化子（minimizer，如minigraph）、间隔种子（spaced seeding）等。
   • 动态种子：如最大精确匹配（MEM/SMEM，如GraphAligner），根据序列特性动态选择。
   • 索引方法：
     • 哈希索引：快速查询但内存开销大（如BGREAT）。
     • 基于压缩的索引：BWT（如VG giraffe的GBWT）、GCSA2（支持长k-mer索引）。
     • 草图索引：MG-SKETCH结合Tensor Sketching与HNSW，加速大规模数据匹配。

2. 过滤（Filtering）

   • 经典方法：筛选（去除低质量锚点）、聚类（合并相似锚点）、链化（构建有序锚点链）。
   • 图特异性方法：构建全局/局部坐标系（如minigraph的稳定坐标编码），解决图结构复杂性导致的定位难题。

3. 扩展（Extension）

   • 动态规划（DP）算法：带状DP（banded DP）、Smith-Waterman（SW）优化（如SIMD加速）。
   • 图拓扑优化：A*搜索（ASTARIX）、Bit-parallel NW（GraphAligner）、GWFA（结合WFA算法）。
   • 高性能计算：向量化处理（如DP的反斜向量计算，图2d）。

4 算法工具比较与趋势

• 代表性工具（表1）：
  • 短读长优先：GenomeMapper（k-mer+DP）、VG giraffe（minimizer+GBWT）。
  • 长读长优化：GraphAligner（minimizer链+Bit-parallel DP）、minigraph（minimizer链+SIMD SW）。
  • 特殊图支持：GED-MAP（ED-string）、deBGA（DBG）。
• 技术趋势：
  • 索引优化：从哈希表转向压缩索引（如GBWT、GCSA2）及草图技术。
  • 长读长适配：动态种子（MEM）与链化策略提升长序列比对效率。
  • 跨物种应用：逐步扩展至物种间泛基因组（如结核杆菌、茄科植物）。

5 挑战与未来方向

1. 复杂区域处理：重复序列、高变区易导致错误锚点，需改进索引与过滤策略。
2. 长读长优化：平衡精度与速度，探索神经网络辅助预测。
3. 跨物种泛基因组：需统一表示不同物种间的保守与变异区域。
4. 计算资源优化：降低内存占用（如弹性索引），支持大规模数据实时分析。
5. 端到端学习：利用深度学习模型（如Transformer）替代传统启发式策略。

6 结论

该综述系统梳理了S2G映射算法的发展现状，强调了泛基因组时代对高效、精确比对技术的需求。未来算法需结合压缩索引、动态种子、高性能计算等多领域技术，推动泛基因组在临床医学、进化研究等场景的应用。