syotti

syotti designs synthetic baits (probes) to cover positions across reference sequences for bait-enriched metagenomic sequencing.

Key Features:

• Problem Formalization: Formalizes bait design as the Minimum Bait Cover problem under an approximate matching model and identifies the problem as NP-hard.
• Heuristic Approach: Addresses the NP-hard problem using an efficient heuristic that leverages succinct data structures.
• Performance Efficiency: Exhibits linear scaling in practice, runs at least an order of magnitude faster than the method of Metsky et al., and produces smaller bait sets that leave fewer positions uncovered.
• Scalability: Can design baits for datasets containing 3 billion nucleotides from 1,000 related bacterial substrains in approximately 25 minutes, while the method of Metsky et al. shows super-linear running time and cannot process a comparable fraction within 24 hours.

Scientific Applications:

• Metagenomic enrichment: Designs baits for bait-enriched sequencing protocols to selectively enrich DNA fragments of interest in metagenomic samples.
• Pathogen detection: Enables genomic enrichment to improve detection of microbial pathogens in complex biological samples.
• Human viral pathogen surveillance: Supports detection of a wide array of human viral pathogens within complex samples, as demonstrated by Metsky et al.

Methodology:

syotti formalizes the Minimum Bait Cover problem under an approximate matching model and solves it using an efficient heuristic that leverages succinct data structures.