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

ABSTRACT: Metagenomic read classification is a fundamental task in computational biology, yet it remains challenging due to the scale, diversity, and complexity of sequencing datasets. We propose a novel, run-length compressed index based on the move structure that enables efficient multi-class metagenomic classification in O(r) space, where r is the number of character runs in the BWT of the reference text. Our method identifies all super-maximal exact matches (SMEMs) of length at least L between a read and the reference dataset and associates each SMEM with one class identifier using a sampled tag array. A consensus algorithm then compacts these SMEMs with their class identifier into a single classification per read. We are the first to perform run-length compressed read classification based on fu

SUBMITTER: Depuydt L 

PROVIDER: S-EPMC11888359 | biostudies-literature | 2025 Mar

REPOSITORIES: biostudies-literature