KATKA: A KRAKEN-like tool with $k$ given at query time

Abstract

We describe a new tool, KATKA, that stores a phylogenetic tree $T$ such that later, given a pattern $P[\mathrm{1..}m]$ and an integer $k$, it can quickly return the root of the smallest subtree of $T$ containing all the genomes in which the $k$-mer $P[i..i+k-1]$ occurs, for $1\le i\le m-k+1$. This is similar to KRAKEN's functionality but with $k$ given at query time instead of at construction time.