Syotti: scalable bait design for DNA enrichment

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Bait enrichment is a crucial technique for amplifying specific DNA regions in metagenomic samples.
• Existing bait design methods can be computationally intensive and may produce suboptimal results.

Purpose of the Study:

• To address the computational challenges in designing effective bait sets for metagenomic analysis.
• To develop a novel, efficient heuristic for the Minimum Bait Cover problem.

Main Methods:

• Formalized the Minimum Bait Cover problem, proving its NP-hard nature.
• Developed Syotti, an efficient heuristic utilizing succinct data structures for bait design.
• Benchmarked Syotti against state-of-the-art methods, including Metsky et al.

Main Results:

• Syotti demonstrates linear time complexity in practice, significantly outperforming existing methods.
• Syotti generates smaller bait sets with fewer uncovered positions compared to competitors.
• Syotti designed baits for a large dataset in 25 minutes, while a competing method failed to process a fraction of the data in 72 hours.

Conclusions:

• Syotti provides a computationally efficient and effective solution for designing DNA baits for metagenomic applications.
• The method offers substantial improvements in speed and resource utilization for bait enrichment protocols.
• Syotti enables faster and more comprehensive analysis of complex metagenomic samples.