Efficient minimizer orders for large values of k using minimum decycling sets.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Minimizers are crucial for efficient data handling in high-throughput DNA sequencing.
• Current minimizer schemes often select excessive k-mers, limiting performance gains.
• Universal k-mer hitting sets offer improvements but are computationally infeasible for large k.

Purpose of the Study:

• To introduce novel minimizer orders for large k values in DNA sequencing.
• To address the limitations of existing minimizer schemes and universal k-mer hitting sets.
• To enhance the efficiency of data structures and algorithms in bioinformatics.

Main Methods:

• Developed decycling-set-based minimizer orders.
• Implemented a method for on-the-fly minimizer computation without storing decycling sets.
• Evaluated performance against universal k-mer hitting set-based orders.

Main Results:

• Decycling-set-based minimizer orders select a comparable number of k-mers to universal hitting sets.
• The new orders scale effectively for large k values.
• On-the-fly computation enables use for any k, improving runtime and memory efficiency.

Conclusions:

• Decycling-set-based minimizer orders provide an efficient solution for large k in DNA sequencing.
• The on-the-fly computation method makes these orders broadly applicable.
• Expect significant improvements in bioinformatics algorithms and data structures.