Multi-context seeds enable fast and high-accuracy read mapping

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• Sequence similarity search is crucial for analyzing biological sequences.
• A tradeoff exists between seed length, search speed, and sensitivity in variable regions.
• Existing methods struggle to balance speed and sensitivity effectively.

Purpose of the Study:

• To introduce a novel seeding strategy, multi-context seeds (MCS), for improved sequence similarity searches.
• To address the inherent tradeoff between seed length, search speed, and sensitivity.
• To enhance the performance of sequence alignment tools by integrating MCS.

Main Methods:

• Developed a new data structure to store seeds of varying lengths within a single index.
• Implemented multi-context seeds (MCS) into the strobealign software.
• Evaluated the performance of strobealign with MCS against its previous version.

Main Results:

• MCS allows the storage of seeds with different lengths in the same index structure.
• Strobealign with MCS demonstrated substantial improvements in accuracy.
• The enhanced strobealign maintained comparable runtime and no additional memory overhead.

Conclusions:

• Multi-context seeds (MCS) effectively combine the advantages of short and long seeds.
• MCS represent a significant advancement in sequence similarity search methodology.
• The implementation in strobealign validates the practical utility and efficiency of MCS.