Data Set-Adaptive Minimizer Order Reduces Memory Usage in k-Mer Counting

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Deep sequencing experiments generate massive datasets, necessitating efficient bioinformatic tools for analysis.
• Memory reduction techniques like sequence binning using minimizer schemes are crucial for handling large sequencing data.
• The performance of binning heavily depends on the chosen order of minimizers.

Purpose of the Study:

• To develop a data-tailored method for optimizing minimizer order in bioinformatic applications.
• To improve the memory efficiency of k-mer counting and assembly tools.
• To reduce the memory footprint of Gerbil, a state-of-the-art k-mer counter.

Main Methods:

• A novel method was developed to repeatedly sample and modify the minimizer order.
• The objective was to flatten the k-mer load distribution across minimizers.
• The method was integrated into the Gerbil k-mer counter.

Main Results:

• Memory footprint reduction of 30%-50% was achieved for large k values in Gerbil.
• Runtime increased only marginally, demonstrating computational efficiency.
• Optimized orders showed superior performance when transferred across datasets from the same species.

Conclusions:

• The data-tailoring method effectively reduces memory usage in bioinformatic applications like k-mer counting.
• This approach offers significant memory savings with minimal impact on runtime.
• The optimized minimizer orders are robust and transferable within the same species, enabling efficient large-scale genomic data analysis.