Kaminari: a frugal colored index for approximate k-mer queries

Identifying which documents in a large database contain a query string is a fundamental problem in Information Retrieval and Computational Biology. We focus on the approximate version of this problem for genomic sequences: the result set may contain false positive matches but no false negatives. State-of-the-art solutions rely on Bloom filters to index all k-mers (substrings of fixed length k) in the documents. To answer a query, documents sharing at least a user-prescribed fraction of query k-mers (typically 75%-80%) are returned.

Here, we explore an alternative index design based on k-mer minimizers and integer compression methods. We show that a careful implementation of this design outperforms previous solutions based on Bloom filters by a wide margin: the index has lower memory footprint and faster query times, while false positive matches have only a minor impact on the ranking of the documents reported. This trend is robust across genomic datasets of different complexity and query workloads.

The software is freely available at github.com/yhhshb/kaminari under the MIT license. Reproducibility scripts are available at github.com/vicLeva/benchmarks_kaminari.