计算机工程

作者：高佳, 徐云

单位：1. 中国科学技术大学计算机科学与技术学院，安徽 合肥 2300272. 安徽省高性能计算重点实验室，安徽 合肥 230027

关键词：泛基因组图,序列比对,种子与扩展策略,minimizer种子

基金：国家自然科学基金面上项目(61672480); 高等学校学科创新引智计划(BP0719016)

随着测序技术的发展和应用，人类基因组序列的研究已从个体分析逐步扩展到群体分析。为更好地展示种群不同样本之间的遗传变异信息，泛基因组图模型开始取代传统的线性多序列参考基因组模型，序列到图的比对成为生物序列分析的关键问题之一。现有比对算法通常采用种子与扩展策略，但由于图中组合的路径较多，定位和验证阶段的时间成本高，需要进一步优化单种子选取方法，减少候选位置的数量。为此，提出一种基于组合minimizer种子的序列比对算法，在定位阶段通过对minimizer种子的组合hash，扩展单个种子的覆盖范围。同时，通过序列和相对位置两方面信息查找种子，减少假阳性匹配位置的数量，从而降低后续筛选和验证的工作量。实验结果表明，与主流算法相比，该算法能够减少约80%的候选位置，时间性能提升1~3倍，同时保持相当的索引内存占用和精确比对能力。

来源：2025年第8期

《计算机工程》期刊编辑部

查看计算机工程杂志2025年第8期