PaperlayerView exact revision on arXiv

Source-linked AI summary

Taxonomic Classification with Complete Tag Arrays

Travis Gagie, Gonzalo Navarro

arXiv:2610.10500v1cs.DSq-bio.GN

TL;DR

Growing reference databases make taxonomic classification harder as shared k-mers become more common and less species-specific. KATKA classifies reads using long maximal exact matches and genus-level occurrence counts. On SILVA, it reaches 93.8% genus-level accuracy with a 1.44 GB index, while minimizer digestion trades accuracy for a smaller, faster index.

  • Problem

    As databases grow, shared k-mers become more common and their LCAs move upward, reducing species-level resolution.

    Source: §1 · p. 2

  • Method

    KATKA finds long MEMs and uses a complete run-length compressed tag array to count their occurrences in each genus and apportion credit accordingly.

    Source: §1 · p. 3, §3.2 · p. 6, §3.3 · p. 7

  • Results

    93.7% accuracy on those reads, with KATKA more accurate than Kraken 2 (79.3%) and Tagger (at most 92.8%).

    Source: §6 · p. 13

  • Takeaways & Limitations

    KATKA’s SILVA index is several times smaller than Cliffy’s reported index and can be built in minutes on a desktop; minimizer digests further trade 1.3 points of accuracy for a three-times-smaller index and 1.7-times-faster classification.

    Source: §1 · p. 3, §6 · p. 13

    The evaluation could not compare KATKA and Cliffy on the same machine and reads because Cliffy’s index could not be built on the test desktop.

    Source: §4 · p. 10, §6 · p. 13

Abstract

from arXiv · show

Taxonomic classifiers such as Kraken assign each $k$-mer of a reference database to the lowest common ancestor (LCA) of the genomes containing it, but this works less well as databases grow, because more and more $k$-mers are shared across species. Cliffy (Ahmed, Boucher and Langmead, 2025) instead uses variable-length exact matches found with an r-index, and can list approximately the genera containing each match; on 16S rRNA it is more accurate than Kraken~2, but its index is large and expensive to build. We present KATKA, which finds the maximal exact matches (MEMs) of at least a given length in each read with Boyer--Moore--Li on a run-length compressed suffix array, counts the occurrences of each MEM in each genus exactly with a complete, run-length compressed tag array, and gives each genus credit in proportion to those counts. On the SILVA 16S rRNA database, KATKA's default index takes 1.44\,GB and can be built in minutes on a desktop computer; it classifies a read in 66\,$\mu$s with one thread and reaches 93.8\% genus-level accuracy, close to what Cliffy reports for its 9\,GB index. Grammar-compressing the runs of the tag array shrinks the index to 1.04\,GB, at 75\,$\mu$s per read. On the same machine and reads, it is more accurate than Kraken~2 (79.3\%) and Tagger (81.7 to 92.8\%, depending on how mates that disagree are scored). Indexing minimizer digests instead of the sequences makes the index three times smaller and classification 1.7 times faster, at a cost of 1.3 points of accuracy. KATKA is available at https://github.com/TravisGagie/KATKA.

1 Introduction

As reference databases grow, shared k-mers can reduce taxonomic resolution. KATKA classifies reads using long exact matches and genus-specific occurrence counts, aiming for Cliffy-like accuracy with a smaller index.

1 Introduction

  • As databases grow, shared k-mers become more common and their LCAs move higher in the taxonomy, reducing species-level resolution.K-mer classifiers rely on taxon-specific k-mers, which become rarer as databases grow.Source: §1 · p. 2
  • Listing gives credit only to genera containing a match, unlike LCA-based voting that can include taxa without the match.KATKA weights genera in proportion to their occurrence counts, about 3.5 points more accurate than even splitting.Source: §1 · pp. 2–3
  • KATKA indexes genus-grouped reference sequences and their reverse complements with a run-length compressed suffix array and a 10-mer search-state table.The section distinguishes the present design from two earlier KATKA projects.Source: §1 · pp. 2–3
  • KATKA finds MEMs of at least 30 bases with Boyer–Moore–Li and counts each match’s occurrences per genus using a run-length compressed tag array.The tag array stores the genus of each reference suffix in suffix-array order.Source: §1 · p. 3
  • 93.8% genus-level accuracy with a 1.44 GB index and 66 µs per read makes KATKA close to Cliffy’s reported accuracy with its 9.01 GB index.The index can be built in minutes on a desktop computer.Source: §1 · p. 3
  • KATKA counts all tags in a match interval, whereas Tagger assigns a match to the genus of its last BWT occurrence.Other r-index classifiers such as SPUMONI 2 and col-BWT target pangenome identification rather than short-read taxonomy.Source: §1 · pp. 3–4

2 Background

Cliffy classifies 16S rRNA reads by matching variable-length exact substrings and querying which genera contain each match. Its listing approach improves accuracy over LCA queries, while its index construction and size are substantial.

16S rRNA classification

  • 16S rRNA reads cover short, similar regions of a roughly 1,500-base gene, so classification is usually only to genus level.SILVA 138.1 contains about 400,000 genus-annotated sequences from about 9,000 unevenly represented genera.Source: §2 · p. 4

Cliffy

  • Cliffy parses each read backward into consecutive phrases, each the longest string ending at its position that occurs in the database.The parsing proceeds from the read’s end and starts a new backward search where the prior match fails.Source: §2 · p. 4
  • Cliffy stores compressed document-array profiles to identify documents containing each match and estimate their leftmost and rightmost positions.Its LCA query spreads weight across the intervening documents, while approximate listing assigns weight to documents in its reported list.Source: §2 · p. 5
  • Cliffy can index minimizer digests, encoding each selected minimizer as one byte by default, and digest reads before searching them.The default uses minimizers of length 4 selected from windows of 11 bases, making indexed text about 4.5 times shorter.Source: §2 · p. 5
  • Approximate document listing is 4.5–6.5 percentage points more accurate at genus level than LCA queries, while minimizer digestion costs 0.5–1.7 points and roughly halves the index size.The undigested index is 9.01 GB and the digested index is 4.27 GB; construction uses 1.2–2.3 TB of temporary disk space.Source: §2 · p. 5, Table 1 · p. 5

3 KATKA

KATKA indexes both strands with a run-length compressed suffix array, finds only long MEMs, and uses a complete run-length compressed tag array to count each MEM’s occurrences by genus. It assigns proportional credit from those counts to classify read pairs.

3.1 The index

  • The reference index contains each genus’s sequences and reverse complements; the RLCSA supports backward search, and a lookup table initializes searches with one lookup.The table stores the first t search steps for every length-t string; when a string is absent, the search falls back to base-by-base steps.Source: §3.1 · p. 6

3.2 Finding long MEMs

  • Boyer–Moore–Li finds MEMs of at least L bases by backward-searching windows, skipping starts ruled out by a failed extension, then extending matches maximally in both directions.After reporting a MEM ending at e − 1, it continues at x = e − L + 1; accuracy hardly changes for L between 15 and 30, then drops slowly as classification becomes faster.Source: §3.2 · pp. 6–7, Figure 2 · p. 7

3.3 Listing genera with a tag array

  • A complete tag array stores each BWT position’s genus, enabling exact per-genus MEM counts by scanning only overlapping runs rather than locating every occurrence.On SILVA, locating occurrences with an r-index took 125 µs per read, versus 66 µs with the tag array; the tag array has 359 million runs and uses 0.86 GB.Source: §3.3 · pp. 7–8
  • Run-length compressing the tag array exploits neighboring BWT positions from the same genus; Muthukrishnan’s document-listing algorithm can list distinct genera without storing its previous-run array C.The listing recursion stops when a range minimum belongs to an already reported genus, provided it recurses on the left before the right.Source: §3.3 · p. 7, Figure 3 · p. 8
  • Grammar-compressing the genera of the tag-array runs reduces their storage from 0.63 GB to 0.23 GB and the default index from 1.44 GB to 1.04 GB, with per-read time rising from 66.0 to 75.0 µs.Counting decodes consecutive runs from the grammar; this configuration returns identical answers.Source: §3.3 · pp. 8–9

3.4 Classifying a read pair

  • Each read pair’s MEMs give genera weight proportional to the MEM length and its occurrence count in that genus; proportional credit was about 3.5 points more accurate than equal credit.Counts include occurrences on both strands; the pair is assigned to the genus with the largest total weight.Source: §3.4 · p. 9

4 Experiments

On simulated SILVA 16S rRNA read pairs, KATKA’s default configuration achieved 93.77% strict genus-level accuracy and outscored Kraken 2 and Tagger under the reported scoring choices. Experiments also assessed configuration trade-offs, including minimizer digestion, which reduced index size and classification time at an accuracy cost.

Setup

  • The experiment used simulated reads from four SILVA 16S rRNA regions and reported mean genus-level accuracy; strict scoring counts ties and unclassified pairs as wrong.Accuracy was measured on 200,000 read pairs per region for KATKA’s strict result; time was measured on 2,000 reads per region.Source: §4 · pp. 9–10

The default configuration

  • 144,800 reads per second with 12 threads on six cores was 7.7 times the one-thread throughput; with one thread, KATKA classified a read in 66 µs.The 66 µs excludes loading the index and reading the reads.Source: §4 · p. 10

The effect of each choice

  • L from 15 to 30 hardly changes accuracy, while equal credit is 3.2 to 3.6 points less accurate than proportional credit.Increasing L makes classification faster because BML skips more of each read and finds fewer MEMs; L = 30 is the largest threshold with the best accuracy.Source: §4 · p. 10, Table 3 · p. 11

The default configuration

  • 93.77% strict genus-level accuracy; KATKA outscored Kraken 2 (79.3%) and Tagger (81.7–92.8%, depending on how mate disagreements are scored).KATKA was faster than Tagger with one or 12 threads; the 93.77% result is reported over 200,000 read pairs per region.Source: §4 · p. 10, Table 2 · p. 11

The effect of each choice

  • The default configuration lies on the time–space–accuracy Pareto surface; the lookup table saves 30% of the time for 18 MB, while a 12-mer table saves another 5% for 0.27 GB more.Subsampled r-indexes were smaller but 2 to 7 times slower; grammar-compressing the tag-array runs yielded indexes both smaller and faster than the sampled-tag alternatives.Source: §4 · p. 11
  • Table 4 compares classification over minimizer digests (k = 4, w = 11), using tags and proportional credit, against the default configuration and Cliffy’s digested index.Lookup tables use t = 2 digest symbols with digestion and t = 10 bases without.Source: Table 4 · p. 12

5 Minimizer digests

KATKA can index minimizer digests instead of sequences, mapping digest matches back to their spans in bases. On SILVA, digestion trades accuracy for a smaller index and faster classification.

5 Minimizer digests

  • KATKA digests sequences and reverse complements symmetrically, using canonical minimizers with k = 4 and w = 11, and collapses equal consecutive minimizers.The minimizers are byte-encoded; six rare codes share a byte because terminators and a separator reserve four values.Source: §5 · p. 12
  • BML searches digest-symbol ranges, maps maximal digested matches back to spans in bases, and reports matches of at least L bases that are not contained in another match.The threshold stays in bases because consecutive digest symbols can represent different numbers of bases.Source: §5 · p. 12
  • 0.49 GB digested KATKA classifies 1.7 times faster (39.3 vs 66.0 µs) at 1.3 points lower accuracy (92.48 vs 93.77%) than the 1.44 GB undigested index.The comparison uses L = 30 and an explicit RLCSA with tags.Source: §5 · p. 12
  • The digested index takes about 3 minutes to build; Cliffy’s digested index is almost 9 times larger and about twice as slow per read on its server.Cliffy reports 92.8 to 93.4% accuracy on its own reads and with its own scoring, against KATKA’s 92.5% on its reads.Source: §5 · p. 13

6 Conclusions

KATKA combines long MEMs, a complete run-length compressed tag array, and occurrence-proportional genus credit for 16S rRNA classification. Its reported results are competitive on SILVA, while broader comparisons and testing remain future work.

6 Conclusions

  • 93.7% accuracy on the same machine and reads exceeded Kraken 2 (79.3%) and Tagger (at most 92.8%); KATKA was also faster than Tagger.The conclusion identifies a same-setting comparison with Cliffy as the most important next step.Source: §6 · p. 13
  • The evaluation is bounded to SILVA 16S rRNA reads; testing on independently sampled, whole-genome, or database-absent species reads remains future work.The authors also report that a same-way comparison with Cliffy requires access to a machine capable of building its index.Source: §6 · p. 13

A Implementation and experimental details

The appendix documents KATKA’s implementation, evaluation procedures, and reproducibility scripts, along with alternatives considered for the SILVA setting.

A Implementation and experimental details

  • The repository scripts fetch dependencies, build the SILVA reference and indexes, and run experiments; reference sequences are grouped by genus in taxonomy tree order and reverse-complemented.Each genus is treated as a document, with a text-position-to-document mapping.Source: A Implementation and experimental… · pp. 16–17
  • Experiments simulated 10 million pairs of 250-base reads for each of four SILVA regions, then regularly subsampled pairs for accuracy and timing.Each mate was classified separately; both strands were in the index.Source: A Implementation and experimental… · p. 17
  • For digests, k = 4 and w = 11 minimizers are byte-coded; the six rarest codes share a byte because reserved symbols limit available values.The digest is formed in text order, with equal consecutive symbols collapsed.Source: A Implementation and experimental… · p. 17
  • The RLCSA or RLBWT supports backward search, while a genus tag for each suffix is run-length compressed; optional sampling and lookup tables configure the index.Lookup tables store search states for strings of a chosen length and are built when classification starts.Source: A Implementation and experimental… · pp. 17–18
  • Undigested BML searches read runs backward and extends successful matches to MEMs; digested BML maps maximal digest matches back to base spans and removes contained matches.The digest procedure uses monotonically moving ranges of symbols selected by read windows.Source: A Implementation and experimental… · p. 18
  • Scoring weights a MEM by its span, then gives genus credit equally or in proportion to occurrence counts; mate weights are summed for each genus.The appendix also specifies an LCA scoring alternative and how ties and ambiguous truth labels are treated.Source: A Implementation and experimental… · p. 18
  • Kraken 2 and Tagger used the same reads and machine; Tagger mates voted separately, timing excluded index loading, and systems tuning beyond parallelism remained future work.The authors identify cache-miss latency and TLB misses among potential systems optimizations.Source: A Implementation and experimental… · pp. 18–20

B Alternatives we considered

  • The authors report that most alternatives they considered performed worse on SILVA’s short, highly conserved sequences, while some might suit whole genomes better.They note that match occurrence counts and tag-array compressibility could differ on other datasets.Source: B Alternatives we considered · p. 20

B.1 Which matches

The section compares match-finding and credit-assignment choices, including the threshold for BML and the costs of listing short MEMs. Its reported results favor listing over LCA scoring in the tested setting.

B.1 Which matches

  • All MEMs were 0.4 to 1.3 points more accurate than Ziv–Merhav phrases, but listing occurrences of short MEMs took 35 to 78 ms per read.The accuracy comparison used Cliffy’s scoring, with and without digestion.Source: §B.1 · p. 20
  • Accuracy is almost unchanged through L = 30, drops about 2 points at L = 50, then collapses at larger thresholds as reads lack MEMs that long.The table reports genus-level accuracy across four regions and the fraction of unclassified pairs.Source: §B.1 · p. 20, Table 5 · p. 21
  • At L = 15, listing with an sr-index took 289 µs per read versus 35 to 78 ms for locating all MEMs, while LCA accuracy (87.3%) matched all-MEM forward–backward search (87.2%).The accuracy comparison uses Cliffy’s scoring; the table covers listing with equal credit.Source: §B.1 · p. 20, Table 5 · p. 21
  • Listing exceeded LCA accuracy by 3.5 points without digestion and 3.6 points with digestion at L = 15 using equal credit.These are strict-accuracy comparisons.Source: §B.1 · p. 20, Table 5 · p. 21
  • Table 6 compares equal genus credit with credit proportional to occurrence counts and to the fraction of each genus’s sequences containing a match.The supplied table description gives the compared scoring schemes but not their results.Source: Table 6 · p. 21

B.2 How to give credit

Proportional credit outperformed equal credit, while the authors note that its advantage may partly reflect how genera are represented in SILVA. They leave a direct test of that possible prior effect for future work.

B.2 How to give credit

  • About 3.5 points more accurate than equal credit, proportional credit performed better both with and without digestion.It also almost eliminates ties.Source: §B.2 · p. 21
  • About 2.5 points of strict accuracy over equal credit came from normalized credit, which was about 1 point below proportional credit.Normalized credit divides each genus’s match count by twice its number of sequences.Source: §B.2 · p. 21
  • Proportional credit favors genera with more SILVA sequences, acting as a prior that may hurt when sample composition differs from the database.The authors suggest normalization or correction toward a known or estimated sample composition as alternatives in that setting.Source: §B.2 · p. 21
  • A uniform-genus simulation would test whether proportional credit’s advantage shrinks when genus abundance is independent of database representation.The authors leave this test for future work.Source: §B.2 · pp. 21–22

B.3 How to list and count

The section compares index structures for listing or counting genera across time, space, and accuracy. Tag arrays are fastest without digestion, while different structures occupy distinct positions on the Pareto surface.

B.3 How to list and count

  • The undigested sr-index with s = 16 used 0.41 GB, classified a read in 477 µs, and was the smallest undigested index on the Pareto surface.Building it from sequences took under 9 minutes on the desktop.Source: §B.3 · p. 22
  • An explicit RLCSA made every tested configuration two to four times faster than the RLBWT, while its construction from the BWT took a few seconds.The difference matters especially for minimizer digests, whose alphabet has 256 symbols.Source: §B.3 · p. 22
  • Tag arrays count matches using runs overlapping the interval rather than locating every occurrence, making them faster but larger than locating-based structures.They store the genus of each suffix in suffix-array order.Source: §B.3 · p. 22
  • Sampling reduced digest tag storage from 0.19 GB to 0.09 GB at s = 4 or 0.06 GB at s = 16, but did not help much overall.LF recovery requires an RLBWT, which cancels much of the space saving unless it is already used for backward search; counting also recovers every run’s genus by following LF.Source: §B.3 · p. 22
  • No configuration with L < 30 is on the Pareto surface; without digestion, sr-indexes are smallest, tag arrays fastest, and grammar-compressed runs often lie between them.With digestion, only tag arrays appear on the surface.Source: §B.3 · p. 23, Table 7 · p. 23

B.4 LCAs without locating: the rz-index

The rz-index finds the leftmost and rightmost occurrences needed for LCA classification without locating every occurrence. Its digested BML configuration was fast and compact, but tag-array LCA queries were faster and more accurate in the reported comparison.

B.4 LCAs without locating: the rz-index

  • The rz-index combines an RLBWT with LZ77 phrase-boundary grids to find the leftmost and rightmost occurrences without locating the others.It uses one grid for each direction; because the index contains both strands, the reverse-complement prefix intervals are available in the same index.Source: §B.4 · pp. 23–24
  • With BML MEMs and L = 50, the digested rz-index classified a read in 66 µs, faster than Cliffy’s reported digested LCA query, with an index 4.4 times smaller and similar accuracy.Table 8 compares LCA classification with Cliffy’s query; the prose reports this result for the digested configuration.Source: §B.4 · p. 24, Table 8 · p. 24
  • The rz-index was not on the Pareto surface: tag-array LCA queries gave the same answers about three times faster and were about 3.5 points more accurate even with equal credit.For digests with L = 30 and an explicit RLCSA, tag-array LCA took about 40 µs per read versus 131 µs.Source: §B.4 · p. 24
  • The rz-index may remain useful when listing documents is not an option, such as when there are too many documents to list economically.Source: §B.4 · p. 25

B.5 Verifying digested matches

The authors tested verifying digested MEM occurrences against DNA and extending them to exact matches. Verification worked, but the digested matches were less specific and the verification step was slower than the compared undigested classification configurations.

B.5 Verifying digested matches

  • Verification of each digested MEM occurrence against DNA and extension to an exact match worked, using a Relative Lempel–Ziv representation and minimizer positions.Source: §B.5 · p. 25
  • With L = 30, digested MEMs occurred in 6.0 genera on average, compared with 3.8 for DNA MEMs.Source: §B.5 · p. 25
  • Checking digested MEM occurrences took 850 µs per read, versus 125 to 253 µs for classification with the compared undigested sr-index configurations.Source: §B.5 · p. 25

B.6 Combining LCAs and listing

The section tests hybrid LCA/listing rules and k-mer filtering as ways to reduce classification time. Hybrid rules gave little benefit with tag arrays, while filtering k-mers did not approach digest speed on these reads.

B.6 Combining LCAs and listing

  • With tag arrays, listing was as fast as computing the LCA, while hybrid rules offered limited benefits for BML and added grid space.An occurrence threshold saved 25 to 45% of time over digests but required 0.42 GB more; the α rule sent fewer than 1% of MEMs to LCA but required computing each MEM’s LCA.Source: §B.6 · p. 25

B.7 Filtering k-mers instead of digesting

  • Exact k-mer membership before undigested BML preserved answers, but 94 to 97% of bases remained in pseudo-MEMs.For L = 30, time fell from 92–99 to 72–83 µs per read; for L = 15, it fell by 7 to 9%, compared with 42 µs using digests and an index one third the size.Source: §B.7 · p. 25
  • Filtering offered little speedup because almost every k-mer in these short, accurate reads occurs in the database, leaving BML to extend long MEMs.KeBaB is designed for long, error-prone reads.Source: §B.7 · p. 25

B.8 Matching whole phrases

A one-level phrase index can match whole phrases at about digest-matching cost, but loses MEM ends that carry substantial genus-discriminating information. The section also outlines untried indexing and counting alternatives, whose benefits depend on data and implementation costs.

B.8 Matching whole phrases

  • Trimming MEMs to phrase-index matches removed 18.5 bases on average and reduced strict accuracy by 2.3 points on V1–V2 and 3.3 points on V4.Even trimming 2 bases from each end cost 0.3 to 0.5 points; MEM middles occurred in 219 genera on average, versus 4 for whole MEMs.Source: §B.8 · p. 26
  • A one-level parse index replaces parsed phrases with identifiers and matches whole phrases exactly, but loses up to about a phrase at each MEM end.The authors conclude it is no substitute for digests on SILVA, though it might suit datasets where matches carry less information at their ends.Source: §B.8 · pp. 25–26

B.9 Ideas we have not tried

  • A two-level parse index could extend matches phrase by phrase, then base by base near the ends, avoiding one-level end loss with fewer search steps.It requires occurrences of each string to be cut consistently, and its space and time costs depend on the parse index and phrase-step cost.Source: §B.9 · p. 26
  • Rank queries could count each listed genus in time proportional to the number of genera, but need rank support on the run-length compressed tag array.The authors did not expect a benefit on SILVA because long MEM intervals have few runs; datasets with more runs per interval could differ.Source: §B.9 · p. 26
  • Suffixient indexes might speed MEM finding while retaining the tag array for listing, since KATKA spends most of its time finding MEMs.The authors note that the RLCSA, like BWT-based indexes generally, has poor cache locality.Source: §B.9 · p. 26
Loading 2610.10500v1…