CAS

CAS implements a context-aware seeding framework that optimizes NGS read mapping by attaching per-seed confidence radii so that all valid mappings within an edit distance threshold t are detected.

Key Features:

• Fewer and Longer Seeds: Uses fewer, longer seeds to reduce seed hits and seed frequencies, improving mapper efficiency for reads with higher error rates such as long reads.
• Confidence Radius Attachment: Attaches a confidence radius to each seed in the reference genome and guarantees detection of valid mappings when the sum of seed confidence radii exceeds the edit distance threshold t.
• Generalization of Existing Schemes: Generalizes pigeonhole-principle-based seeding schemes by allowing adaptive confidence radii instead of the implicit fixed radius of one.
• Efficient Algorithm Design: Includes an algorithm that constructs the confidence radius database in linear time.

Scientific Applications:

• Long-read sequencing mapping: Improves mapping of long-read sequencing data prone to higher error rates by reducing seed frequencies by up to 20.3% compared to the Optimal Seed Solver.
• NGS read mapper optimization: Enhances the ability of NGS read mappers to identify valid mappings under specified edit distance thresholds t with fewer seed hits.

Methodology:

Constructs a confidence radius database in linear time and attaches per-seed confidence radii to fewer, longer seeds so that their summed radii exceed the edit distance threshold t to guarantee detection of all valid mappings.