Finimizers: Variable-Length Bounded-Frequency Minimizers for $k$-mer Sets

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures and Algorithms

Background:

• Minimizers are crucial for k-mer indexing in metagenomics and pangenomics, but frequent minimizers degrade performance.
• Existing heuristics for frequent minimizers in alignment tools often compromise other metrics like recall or space usage.
• There is a need for indexing methods that guarantee predictable query times without sacrificing efficiency.

Purpose of the Study:

• To introduce frequency-bounded minimizers (finimizers) as a novel approach for indexing sets of k-mers.
• To address the issue of frequent minimizers and provide worst-case query time guarantees.
• To develop an efficient implementation of finimizers using advanced data structures.

Main Methods:

• Introduced finimizers, a new type of minimizer where m-mer length varies to bound frequency below a threshold 't'.
• Utilized the Spectral Burrows-Wheeler Transform (SBWT) augmented with longest common suffix information for efficient finimizer implementation.
• Investigated the special case where t=1, simplifying the index structure and making the scheme parameter-free (except for k).

Main Results:

• Finimizers effectively solve the problem of very frequent minimizers, providing a worst-case guarantee for query time.
• The SBWT-based implementation is efficient, with a prototype achieving k-mer localization times comparable to or faster than state-of-the-art minimizer schemes.
• The t=1 finimizer scheme demonstrates competitive performance and simplicity, requiring minimal parameter tuning.

Conclusions:

• Frequency-bounded minimizers (finimizers) offer a robust and efficient alternative to traditional minimizer-based indexing.
• The proposed method improves query time predictability and performance in k-mer indexing tasks.
• Finimizers represent a significant advancement for indexing in large-scale genomic applications like metagenomics and pangenomics.