A compressive seeding algorithm in conjunction with reordering-based compression

文献类型： 外文期刊

第一作者： Ji, Fahu

作者： Ji, Fahu;Liu, Xianming;Zhou, Qian;Liu, Xianming;Ruan, Jue;Zhu, Zexuan

作者机构：

期刊名称：BIOINFORMATICS （ 影响因子：5.8； 五年影响因子：8.3 ）

ISSN： 1367-4803

年卷期： 2024 年 40 卷 3 期

页码：

收录情况： SCI

摘要： Motivation Seeding is a rate-limiting stage in sequence alignment for next-generation sequencing reads. The existing optimization algorithms typically utilize hardware and machine-learning techniques to accelerate seeding. However, an efficient solution provided by professional next-generation sequencing compressors has been largely overlooked by far. In addition to achieving remarkable compression ratios by reordering reads, these compressors provide valuable insights for downstream alignment that reveal the repetitive computations accounting for more than 50% of seeding procedure in commonly used short read aligner BWA-MEM at typical sequencing coverage. Nevertheless, the exploited redundancy information is not fully realized or utilized.Results In this study, we present a compressive seeding algorithm, named CompSeed, to fill the gap. CompSeed, in collaboration with the existing reordering-based compression tools, finishes the BWA-MEM seeding process in about half the time by caching all intermediate seeding results in compact trie structures to directly answer repetitive inquiries that frequently cause random memory accesses. Furthermore, CompSeed demonstrates better performance as sequencing coverage increases, as it focuses solely on the small informative portion of sequencing reads after compression. The innovative strategy highlights the promising potential of integrating sequence compression and alignment to tackle the ever-growing volume of sequencing data.Availability and implementation CompSeed is available at https://github.com/i-xiaohu/CompSeed.

分类号：

  • 相关文献
作者其他论文 更多>>

微信小程序