Movi Color: fast and accurate taxonomic classification with the move structure

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Advances in long-read sequencing increase reference genome availability, necessitating efficient compressed indexes for classification.
• Current k-mer methods (e.g., Kraken 2) are fast but inflexible with fixed k-mer lengths, impacting accuracy.
• Existing compressed full-text index methods (e.g., SPUMONI2, Cliffy) are slower and have limitations in scalability and reporting.

Purpose of the Study:

• To develop novel algorithms and methods for multi-class and taxonomic classification using compressed full-text indexes.
• To improve the efficiency and accuracy of genomic classification, particularly for large and repetitive reference databases.
• To introduce Movi Color, a method leveraging the Burrows-Wheeler Transform's move structure for faster classification.

Main Methods:

• Developed Movi Color, which augments the Movi index by assigning 'colors' to Burrows-Wheeler Transform runs based on genome origin.
• Utilized the locality of reference in the move structure for high-speed processing.
• Applied the method to taxonomic classification at species and genus levels.

Main Results:

• Movi Color achieved over 1.9x higher positive predictive value (PPV) and 3x higher sensitivity than Kraken 2 and Metabuli at the species level.
• At the genus level, Movi Color demonstrated 75% higher PPV than Metabuli and over 50% higher sensitivity than Kraken 2.
• Read processing was 7-20x faster than Metabuli and comparable to Kraken 2, despite higher memory usage.

Conclusions:

• Movi Color offers a significant speed-accuracy trade-off, making it suitable for real-time and high-throughput genomic classification.
• The 'coloring' approach effectively compresses indexes for repetitive reference data, enhancing classification performance.
• This method addresses limitations of existing tools, enabling more sensitive and specific taxonomic identification.