Taxonomic Classification with Tag Arrays
Abstract
Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a k-mer's credit to the lowest common ancestor of those taxa, SPUMONI~2 labels each position of the read, Tagger gives each maximal exact match (MEM) one label, and Cliffy splits a match's credit evenly over a roughly logarithmic sample of the taxa. We compare these schemes on the same long MEMs, mainly on short 16S rRNA reads classified to genera with SILVA, where credit proportional to the number of occurrences of the MEM in each taxon is the most accurate, by 1.0 to 6.8 percentage points. We compute long MEMs with Boyer--Moore--Li on a run-length compressed suffix array, and count their occurrences in each taxon with a complete, run-length compressed tag array, in time proportional to the number of tag runs in the MEM's BWT interval, without locating any occurrence. We bound the number of tag runs in terms of the BWT runs and of how often suffixes with long common prefixes have different tags, and show that tags constant on d blocks of the text have a macro scheme with at most r + 2d phrases. On SILVA our index takes 1.44\,GB and classifies a read in 66\,μs with one thread at 93.8\% accuracy, about what Cliffy reports for its 9\,GB index; over minimizer digests it takes 0.49\,GB and reaches 92.5\%, against 84.2\% for Cliffy's digested index on the same reads. On nanopore reads from whole genomes, where almost every long MEM occurs in one species, we instead use each read's longest MEMs, found in one pass of a variant of Boyer--Moore--Li with a k-mer filter, which assigns 99.6\% of the reads to their species with no length threshold.
Related
- Advances in 16S Taxonomic Classification: Impacts on Species-Level Resolution of Female Bladder Microbiota
- InsectDCT: A generalized pipeline for detection, taxonomic classification, and tracking of insects in camera-trap recordings
- BoNTax: a curated genome-based framework for taxonomic classification and characterization of Clostridium botulinum Group I and Clostridium sporogenes
- Taxonomic classification cost tracks neither sequencing depth nor community richness at single-sample scale: a measured resource protocol for 16S rRNA amplicon pipelines
- Genome-resolved metagenomics reveals the taxonomic and functional landscape of the rumen microbiome in Japanese Black × Holstein cattle and its associations with carcass traits
BibTeX
@misc{gagie2026taxonomic,
title = {{Taxonomic Classification with Tag Arrays}},
author = {Travis Gagie and Gonzalo Navarro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10500},
eprint = {2610.10500},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10500},
}
RIS
TY - UNPB
TI - Taxonomic Classification with Tag Arrays
AU - Travis Gagie
AU - Gonzalo Navarro
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.10500
UR - https://arxiv.org/abs/2610.10500
AB - Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a k-mer's credit to the lowest common ancestor of those taxa, SPUMONI~2 labels each position of the read, Tagger gives each maximal exact match (MEM) one label, and Cliffy splits a match's credit evenly over a roughly logarithmic sample of the taxa. We compare these schemes on the same long MEMs, mainly on short 16S rRNA reads classified to genera with SILVA, where credit proportional to the number of occurrences of the MEM in each taxon is the most accurate, by 1.0 to 6.8 percentage points. We compute long MEMs with Boyer--Moore--Li on a run-length compressed suffix array, and count their occurrences in each taxon with a complete, run-length compressed tag array, in time proportional to the number of tag runs in the MEM's BWT interval, without locating any occurrence. We bound the number of tag runs in terms of the BWT runs and of how often suffixes with long common prefixes have different tags, and show that tags constant on d blocks of the text have a macro scheme with at most r + 2d phrases. On SILVA our index takes 1.44\,GB and classifies a read in 66\,μs with one thread at 93.8\% accuracy, about what Cliffy reports for its 9\,GB index; over minimizer digests it takes 0.49\,GB and reaches 92.5\%, against 84.2\% for Cliffy's digested index on the same reads. On nanopore reads from whole genomes, where almost every long MEM occurs in one species, we instead use each read's longest MEMs, found in one pass of a variant of Boyer--Moore--Li with a k-mer filter, which assigns 99.6\% of the reads to their species with no length threshold.
ER -