Efficient Seeding for Error-Prone Sequences with SubseqHash2.

ABSTRACT: Seeding is an essential preparatory step for large-scale sequence comparisons. 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. In this paper, 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 identifying the optimal subsequence under each of the k orders in a single dynamic programming framework. The algorith

SUBMITTER: Li X 

PROVIDER: S-EPMC11185578 | biostudies-literature | 2024 Jun

REPOSITORIES: biostudies-literature