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

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• Identifying DNA documents containing query strings is crucial in computational biology.
• Current methods often use Bloom filters to index k-mers, but can be memory-intensive.

Purpose of the Study:

• To develop a more efficient indexing method for DNA sequence retrieval.
• To improve upon existing Bloom filter-based approaches for handling k-mers.

Main Methods:

• Designed a novel index utilizing k-mer minimizers and integer compression.
• Implemented the index in C++17 for performance optimization.

Main Results:

• The new index demonstrates a lower memory footprint than Bloom filters.
• Achieved significantly faster query times across diverse genomic datasets.
• False positive matches had minimal impact on document ranking.

Conclusions:

• The k-mer minimizer index offers a superior alternative to Bloom filters for DNA sequence searching.
• This approach provides robust performance for various genomic data and query types.