利用可索引弹性创始人图实现高效种子链延伸比对：解决泛基因组序列比对难题的新方法

研究人员针对泛基因组计算中序列到图比对的难题，开发了基于可索引弹性创始人图(iEFG)的种子链延伸比对工作流。该研究通过构建支持线性时间精确搜索的iEFG，结合创新的半无重复(srf)种子发现和ChainX-block-graph算法，实现了比GraphAligner快4.5倍的染色体规模比对，为减少虚假重组提供了理论基础。

　　

在基因组学领域，参考基因组偏倚问题长期制约着遗传变异的准确分析。随着千人基因组计划等大型项目产生海量变异数据，传统线性参考基因组已无法满足研究需求，催生了泛基因组计算这一新兴方向。当前主流方法存在两难困境：基于字符串集合的方法缺乏变异位点信息，而基于图的方法又面临计算复杂度高的问题。特别是在长读长测序时代，序列到图比对这一核心操作的理论复杂性（已知不存在亚二次时间算法）成为制约分析效率的瓶颈。

赫尔辛基大学（University of Helsinki）的Nicola Rizzo团队在《Bioinformatics》发表的研究中，创新性地利用可索引弹性创始人图(iEFG)的特殊性质，开发了完整的种子链延伸比对流程。iEFG通过强制变异单倍型在独特基因组片段后才能重组，既保留了图结构的生物学合理性，又具备线性时间精确搜索的数学特性。研究人员构建了端粒到端粒组装的人类染色体规模iEFG，开发了efg-locate工具实现快速定位，提出半无重复种子发现算法，并改造ChainX算法实现平均O(n·OPT+n log n)时间的锚点链化，最终通过GraphAligner完成比对延伸。实验显示，该方法在保持95.49%路径准确率（δ=0.1标准）的同时，速度达到GraphAligner的4.5倍。

关键技术包括：（1）从T2T-CHM13参考基因组和千人基因组变异数据构建iEFG；（2）基于边标签串联序列T_edges的精确匹配算法；（3）利用Aho-Corasick自动机发现半无重复种子；（4）将ChainX算法适配到弹性退化字符串(EDS)的链化场景；（5）使用BadRead模拟器生成30x覆盖度的15kb长读长进行验证。

主要研究结果
1. 可索引EFG的构建与特性
通过两种策略构建人类22号染色体iEFG：策略(a)严格遵循理论算法计算半无重复块，策略(b)采用并行近似优化。结果显示iEFG相比vg工具构建的图将路径数量从10⁴⁰¹⁷³⁰量级降至10²⁶⁵⁴²⁴，显著减少虚假重组路径。

2. 精确搜索的实现
开发的efg-locate工具在706万条reads的定位测试中，仅比bwa慢23分钟（1h11min vs 48min），证实iEFG支持近似字符串索引的查询效率。而vg和br-index在相同测试中均超时。

3. 半无重复种子质量
比较全量srf种子（7833万）与SRFAligner选取的子集（2282万），后者保留88.13%的δ=0.1准确率，证明贪婪算法能有效筛选高质量种子。

4. 比对性能对比
在模拟读长测试中，SRFAligner-o50模式以6.46分钟运行时间达到97.25%路径准确率，显著优于minigraph（17.76%）和minichain（54.23%）。内存消耗仅13.767GB，是GraphChainer的44%。

这项研究的重要意义在于：首次将iEFG的理论优势转化为完整的分析流程，通过数学约束（半无重复性）平衡生物学合理性与计算效率。其种子发现和链化算法为其他图表示提供了可迁移的技术思路，而构建的T2T-CHM13+1KGP染色体资源为群体遗传学研究提供了新工具。作者指出，未来可将该方法扩展到基于创始人序列的简化MSA构建，并探索srf种子在其他图结构中的普适性应用。