Computing k-mers in Graphs

We initiate the study of computational problems on k-mers (strings of length k) in labeled graphs. As a starting point, we consider the problem of counting the number of distinct k-mers found on the walks of a graph. We establish that this is #P-hard, even on connected deterministic DAGs. However, in the class of deterministic Wheeler graphs (Gagie, Manzini, and Siren, TCS 2017), we show that distinct k-mers of such a graph W can be counted using $O(|W|k)$ or O(n⁴ log k) arithmetic operations, where n is the number of vertices of the graph, and $|W|$ is n plus the number of edges. The latter result uses a new generalization of the technique of prefix doubling to Wheeler graphs. To generalize our results beyond Wheeler graphs, we discuss ways to transform a graph into a Wheeler graph in a manner that preserves the k-mers. As an application of our k-mer counting algorithms, we construct a representation of the de Bruijn graph (dBg) of the k-mers in time $O(|dBg| + |W|k)$. Given that the Wheeler graph can be exponentially smaller than the de Bruijn graph, for large k this provides a theoretical improvement over previous de Bruijn graph construction methods from graphs, which must spend $Ω(k)$ time per k-mer in the graph. Our representation occupies O(|dBg| + |W|k log(max1 ≤ ≤ k(n₎)) bits of space, where n_ is the number of distinct l-mers in the Wheeler graph.