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

这篇综述系统梳理了泛基因组（pangenome）时代序列到图（S2G）映射算法的研究进展，重点探讨了种子延伸（seed-and-extend）策略中的种子生成、过滤和延伸三大关键技术，并分析了不同图结构（如De Bruijn图、变异图）对算法设计的影响。文章总结了当前挑战（如循环结构处理、标准化文件格式）和未来方向（高性能计算优化），为基因组分析提供了从线性参考到图参考的范式转换视角。

　　

泛基因组图：超越线性参考的新范式

现代基因组学中，参考基因组是许多分析（如读段比对、变异检测）的基线。然而，当前主流参考基因组（如GRCh38）基于少数个体，可能引入参考偏倚（reference bias），导致非参考等位基因在比对中被低估或错误映射。泛基因组通过整合多个个体基因组，以图结构同时表征不同单倍型，为解决这一问题提供了新思路。

泛基因组图通常由节点（序列）和边（序列邻接关系）构成，共享序列被合并为同一节点，个体特异性变异则表现为分支。这种结构能更全面地捕捉基因组多样性，例如人类泛基因组项目（Human Pangenome Project）通过94个单倍型构建的图参考，显著提升了结构变异（SV）的检测灵敏度。

序列到图映射的核心挑战

序列到图（S2G）映射是泛基因组分析的基础任务，其目标是在图中定位查询序列的最可能路径。与线性参考比对不同，图的复杂拓扑结构（如分支、循环）带来了独特挑战：

1. 种子生成：静态种子（如k-mer、minimizer）和动态种子（如SMEM）各有优劣。例如，GraphAligner利用节点特异性minimizer提升长读段比对效率，而deBGA通过Uni-MEM在单元ig中寻找长匹配区域。
2. 索引优化：哈希表适合k-mer查询，而基于BWT的GCSA2索引能处理256 bp的k-mer，但面临组合爆炸问题。新兴方法如MG-SKETCH结合张量草图（Tensor Sketching）和HNSW索引，显著提升了大规模数据集的处理速度。
3. 坐标系统：图的非线性结构需重新定义坐标。minigraph采用稳定的序列偏移编码，而VG系列工具通过超气泡（superbubble）分解图拓扑，实现局部排序。

算法创新与性能突破

动态规划（DP）的延伸优化：传统DP算法（如Smith-Waterman）在图结构中的时间复杂度为O(NM)，难以扩展。GWFA算法（Graph Wavefront Alignment）将波前对齐扩展到图结构，对高相似序列实现接近线性的时间复杂度。

共线性链（co-linear chaining）：Minichain和GraphChainer通过稀疏动态编程框架，在DAG上实现O(kNlogN)时间复杂度的最优链求解。PanAligner进一步引入循环感知的间隙惩罚函数，支持复杂拓扑的精准比对。

并行计算加速：SeGraM利用高带宽内存消除瓶颈，而NVIDIA Clara Parabricks通过GPU加速VG giraffe，使泛基因组比对速度提升数个数量级。

未来方向：标准化与跨学科融合

当前挑战包括：

• 文件格式不统一：GFA和GAF格式逐渐成为主流，但下游工具兼容性仍需改进。
• 循环区域处理：VG的"展开"方法和Rautiainen的位并行算法提供了部分解决方案，但计算成本仍高。
• 高性能计算：硬件专用优化（如FPGA）与通用算法的平衡是关键。

随着泛基因组资源（如中国人群泛基因组）的丰富，S2G映射算法将持续推动精准医学和群体遗传学的发展，最终实现"一个物种，一个图参考"的愿景。