Taxonomic Classification with Maximal Exact Matches in KATKA Kernels and Minimizer Digests

Dominika Draesslerova, Omar Ahmed, Travis Gagie, Jan Holub, Benjamin Langmead, Giovanni Manzini, and Gonzalo Navarro.

For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain the genome from which that read was drawn. Although popular classifiers such as Kraken use k-mers, recent research indicates that using maximal exact matches (MEMs) can lead to better classifications. For example, we can

build an augmented FM-index over the the genomes in the tree concatenated in left-to-right order;
for each MEM in a read, find the interval in the suffix array containing the starting positions of that MEM’s occurrences in those genomes;
find the minimum and maximum values stored in that interval;
take the lowest common ancestor (LCA) of the genomes containing the characters at those positions.

This solution is practical, however, only when the total size of the genomes in the tree is fairly small. In this paper we consider applying the same solution to three lossily compressed representations of the genomes’ concatenation:

a KATKA kernel, which discards characters that are not in the first or last occurrence of any kmax-tuple, for a parameter kmax;
a minimizer digest;
a KATKA kernel of a minimizer digest.

With a test dataset and these three representations of it, simulated reads and various parameter settings, we checked how many reads’ longest MEMs occurred only in the sequences from which those reads were generated ("true positive" reads). For some parameter settings we achieved significant compression while only slightly decreasing the true-positive rate.