Kaminari: a frugal colored index for approximate <i>k</i>-mer queries

<h4>Motivation</h4>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 <i>k</i>-mers (substrings of fixed length <i>k</i>) in the documents. To answer a query, documents sharing at least a user-prescribed fraction of query <i>k</i>-mers (typically 75%-80%) are returned.<h4>Results</h4>Here, we explore an alternative index design based on <i>k</i>-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.<h4>Availability and implementation</h4>The software is freely available at github.com/yhhshb/kaminari under the MIT license. Reproducibility scripts are available at github.com/vicLeva/benchmarks_kaminari.