Comparing fixed sampling with minimizer sampling when using k-mer indexes to find maximal exact matches

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• K-mer indexes are crucial for sequence similarity searches in bioinformatics.
• Large memory requirements and query times are significant challenges for k-mer indexes.
• Fixed sampling and minimizer sampling are common methods to reduce index size and speed up queries.

Purpose of the Study:

• To systematically compare the performance of fixed sampling and minimizer sampling for k-mer indexes.
• To verify assumptions about index size and query speed for both sampling methods.
• To determine the optimal sampling strategy for sequence similarity searches.

Main Methods:

• A comparative analysis of fixed and minimizer sampling techniques was performed.
• The human genome served as the primary database for constructing k-mer indexes.
• Maximal exact matches were identified between the human genome and query sets (mouse genome, chimp genome, NGS data).

Main Results:

• Larger k-mer sizes reduce query time but increase index space for both methods.
• Fixed sampling typically requires half the space of minimizer sampling at comparable k-mer sizes.
• Minimizer sampling offers only marginal query speed improvements over fixed sampling when k-mer sizes are equal.
• When k-mer sizes can be optimized independently, fixed sampling can be both more space-efficient and faster than minimizer sampling.

Conclusions:

• Fixed sampling is generally more memory-efficient than minimizer sampling.
• Minimizer sampling's query speed advantage is often offset by a larger number of k-mer occurrences to process.
• Fixed sampling is recommended for applications requiring processing of each shared k-mer occurrence.