SubseqHash

SubseqHash selects minimized subsequence seeds to improve seeding and sequence similarity detection for read mapping, sequence alignment, overlap detection, and genome assembly, particularly for high-error long-read sequencing data.

Key Features:

• Subsequence-based seeding: Uses subsequences instead of substrings (k-mers) as seeds to increase tolerance to mutations and sequencing errors.
• Minimized subsequence selection: Transforms a sequence into its smallest subsequence of a specified length k (k < n) to produce deterministic seeds.
• ABC order: Employs the ABC order as the ordering system that guides selection of minimized subsequences.
• Polynomial-time computation: Computes minimized subsequences under the ABC order in polynomial time.
• Hash collision–Jaccard correspondence: Uses a hashing strategy whose collision probability closely approximates the Jaccard index between samples.
• Robustness to high error rates: Produces superior seed matches compared with substring-based methods in datasets with high sequencing error rates.

Scientific Applications:

• Read mapping: Improves seeding for mapping reads to reference sequences, especially for error-prone long reads.
• Sequence alignment: Enhances detection of matching regions used as seeds in alignment algorithms.
• Overlap detection: Facilitates identification of overlaps between reads for assembly and error correction workflows.
• Genome assembly: Provides more error-tolerant seeds that can aid assembly of genomes from long-read sequencing data.

Methodology:

Transform each sequence into its smallest subsequence of length k (k < n) according to the ABC order; compute these minimized subsequences in polynomial time and use a hashing scheme whose collision probability approximates the Jaccard index.