Efficient seeding for error-prone sequences with SubseqHash2

Xiang Li

doi:10.1093/bioinformatics/btaf418

Efficient seeding for error-prone sequences with SubseqHash2

2025-08-01

0

OA

AI

DOI：10.1093/bioinformatics/btaf418

原文链接

原文求助

摘要

En 中文

Motivation Seeding is an essential preparatory step for many fundamental computational tasks that require large-scale sequence comparison. Substring-based seeding methods such as kmers are ideal for sequences with low error rates but struggle to achieve high sensitivity while maintaining a reasonable precision for error-prone long reads. SubseqHash, a novel subsequence-based seeding method we recently developed, achieves superior accuracy to substring-based methods in seeding sequences with high mutation/error rates, while the only drawback is its computation speed.Results We propose SubseqHash2, an improved algorithm that can compute multiple sets of seeds in one run, by defining k orders over all length-k subsequences and finding the optimal subsequence under each of the k orders in a single dynamic programming framework. The algorithm is further accelerated using single instruction, multiple data instructions for parallel computing. The design of SubseqHash2 also allows it to generate the same sets of seeds for a string and its reverse complement by using symmetric random tables. We demonstrate that SubseqHash2 drastically outperforms popular substring-based methods including kmers, minimizers, syncmers, and Strobemers for three fundamental applications. In read mapping, SubseqHash2 can generate adequate seed matches for aligning hard reads that minimap2 fails on. In sequence alignment, SubseqHash2 achieves high coverage of correct seeds and low coverage of incorrect seeds. In overlap detection, seeds produced by SubseqHash2 lead to more correct overlapping pairs at the same false-positive rate. In all experiments, SubseqHash2 achieves a 10-50x speedup over SubseqHash while maintaining nearly identical high accuracy. With all the algorithmic breakthroughs of SubseqHash2, we clear the path for the wide adoption of subsequence-based seeds in long-read analysis.Availability and implementation SubseqHash2 is available at https://github.com/Shao-Group/SubseqHash2 and have also been archived on Software Heritage (swh:1:dir:86738fc4b919eb6a9a26f7f533c25eb69f9a96d5).

Keyword:

LONG

Efficient seeding for error-prone sequences with SubseqHash2

摘要

期刊

机构

引用论文