Seeding with minimized subsequence.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Sequence analysis relies on seeding methods for efficient computation-intensive tasks.
• Kmer-based seeding is effective for low-error sequencing data but fails with high error rates.
• Growing data volumes necessitate robust seeding strategies for diverse sequencing applications.

Purpose of the Study:

• To develop a novel seeding strategy, SubseqHash, that overcomes limitations of kmer-based methods for high-error sequencing data.
• To introduce an efficient algorithmic framework for generating subsequence seeds.
• To evaluate SubseqHash's performance in critical genomics applications.

Main Methods:

• Proposed SubseqHash, a strategy using subsequences instead of substrings as seeds.
• Developed a novel algorithmic framework with a specific order (ABC order) to compute minimized subsequences in polynomial time.
• Analyzed hash collision probability and demonstrated its relation to the Jaccard index.

Main Results:

• SubseqHash effectively handles high error rates in sequencing data, unlike kmer methods.
• The proposed ABC order ensures desired properties for subsequence seeding.
• SubseqHash significantly outperforms substring-based seeding in read mapping, sequence alignment, and overlap detection.
• Achieved high-quality seed-matches crucial for accurate long-read analysis.

Conclusions:

• SubseqHash represents a major algorithmic advancement for sequence analysis with high error rates.
• The method is expected to be widely adopted for long-read sequencing data analysis.
• SubseqHash offers a robust and efficient solution for critical genomics tasks.