Run-length compressed metagenomic read classification with SMEM-finding and tagging

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Metagenomic read classification is crucial but challenging due to large, diverse, and complex sequencing data.
• Existing methods struggle with efficiency and accuracy across various datasets.

Purpose of the Study:

• To introduce a novel, efficient, and accurate metagenomic read classification method.
• To leverage run-length compression and super-maximal exact matches (SMEMs) for improved classification.
• To provide a versatile tool balancing accuracy, runtime, and memory usage.

Main Methods:

• Utilizing a run-length compressed index based on the BWT move structure.
• Identifying all super-maximal exact matches (SMEMs) of a minimum length.
• Employing a sampled tag array for class identification and a consensus algorithm for final classification.

Main Results:

• The method achieves efficient multi-class metagenomic classification in compressed space.
• It consistently outperforms SPUMONI 2 in accuracy and runtime.
• Demonstrates superior memory efficiency compared to Cliffy on simpler datasets and comparable performance on complex ones.

Conclusions:

• The novel approach offers a versatile and efficient solution for metagenomic classification.
• It effectively balances accuracy, runtime, and memory usage for diverse sequencing datasets.
• An open-source C++11 implementation is publicly available for broader adoption.