随着测序技术的普及，公共基因组数据库如SRA和GenBank的数据量呈现指数级增长，仅细菌基因组就已超过120万条记录。然而，传统比对工具如BLAST面临巨大计算压力，而现有草图方法如sourmash在 divergent datasets（差异数据集）上表现欠佳。法国国家科研中心等机构的研究团队在《Algorithms for Molecular Biology》发表研究，提出Fractional Hitting Sets(FHS)新范式，通过概率化覆盖k-mer空间实现高效基因组草图构建。

关键技术包括：1）建立FHS理论框架，证明其密度上限为2f/(w+1)+o(1/w)；2）开发super-k-mer编码技术，将k-mer存储压缩至4(k-m)/(k-m+1)比特/mer；3）设计分区索引策略，利用minimizer（最小哈希子串）实现快速比对；4）基于100X模拟测序数据验证，使用1,024个Salmonella和细菌基因组进行基准测试。

研究结果显示：在k=31时，supersampler内存消耗仅为sourmash的1/5，磁盘空间减少16倍，比对速度提升50倍（差异样本）。理论分析证实：当亚采样率>100时，99% super-k-mer达到maximal（最大长度），存储效率接近理论下限。Angular similarity（角度相似性）分析表明，该方法在保持精度的同时，将abundance（丰度）数据存储压缩10倍。

讨论部分指出，FHS通过放宽Universal Hitting Sets(UHS)的全覆盖约束，实现密度因子从2降至1.04（亚采样率1000时）。该工作为处理TB级基因组数据提供新思路，未来可结合sorted fingerprints（排序指纹）进一步优化。研究获得法国国家科研局AGATE ANR-21-CE45-0012和欧盟ERC IndexThePlanet项目支持，代码已开源。

这项研究的创新性体现在三个方面：首先，理论层面突破minimizer scheme的1.5/(w+1)密度下限；其次，工程实现上通过maximal super-k-mer将存储效率提升至传统方法的1/50；最后，首次证明分区比对策略可将时间复杂度从O(n²)降至近线性。这些进展使得在普通笔记本电脑上处理百万级基因组比较成为可能，为元基因组快速筛查提供重要工具。

打赏

下载安捷伦电子书《通过细胞代谢揭示新的药物靶点》探索如何通过代谢分析促进您的药物发现研究

10x Genomics新品Visium HD 开启单细胞分辨率的全转录组空间分析！

欢迎下载Twist《不断变化的CRISPR筛选格局》电子书

单细胞测序入门大讲堂 - 深入了解从第一个单细胞实验设计到数据质控与可视化解析

下载《细胞内蛋白质互作分析方法电子书》