Centrifuger: Lossless Compression of Microbial Genomes for Efficient and Accurate Metagenomic Sequence Classification

Abstract

Centrifuger is an efficient taxonomic classification method that compares sequencing reads against a microbial genome database. Due to the increasing availability of microbial genomes, classification methods tend to store the genome database in an approximate way, keeping the memory footprint within a practical range. In contrast, Centrifuger losslessly compresses the Burrows-Wheeler transformed (BWT) sequence from microbial genomes using a novel compression algorithm called run-block compression. We prove that the run-block compression achieves sublinear space complexity, $O(\frac{n}{\sqrt{l}})$ words, where $n$ is the sequence length and $l$ is the average run length. This space complexity falls between the no-compression wavelet tree representation using $O\left(n\right)$ words and the run-length compression representation using $O(\frac{n}{l})$ words. Run-block compression is effective at compressing microbial databases like RefSeq, where the average run length of the BWT sequence is low, e.g., about 6.8. Combining this compression method with other strategies for compacting the Ferragina-Manzini (FM) index, Centrifuger reduces the index size by half compared to its predecessor, Centrifuge. Lossless compression helps Centrifuger achieve greater accuracy than competing methods at lower taxonomic levels such as species and genus. Additionally, run-block compression supports rapid rank queries in $O\left(log\sigma \right)\mathrm{ time}$, the same order as the wavelet-tree rank query. Despite its use of a compressed data structure, Centrifuger is as fast as Centrifuge in terms of processing speed.