The open-closed mod-minimizer algorithm.

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Design

Background:

• Deterministic k-mer sampling is crucial for DNA indexing and sequence comparison.
• The random minimizer is a common but suboptimal sampling scheme with density 1/w.
• Existing methods like mod-minimizer and miniception offer improvements for specific k ranges.

Purpose of the Study:

• To develop novel k-mer sampling algorithms with improved density and efficiency.
• To address limitations of existing methods, particularly for small k values.
• To create a versatile algorithm effective across a wide range of k.

Main Methods:

• Introduced the open-closed minimizer, extending miniception to prioritize open syncmers.
• Developed the open-closed mod-minimizer by integrating open-closed concepts with mod-minimizer.
• Analyzed algorithm density and computational performance.

Main Results:

• The open-closed minimizer achieves significantly better density than random minimizers for small k.
• This new method is computationally as efficient as the random minimizer.
• The open-closed mod-minimizer demonstrates improved density over mod-minimizer for all k.
• Achieved comparable density to decycling sets with simpler computation.

Conclusions:

• The open-closed minimizer provides a practical and efficient solution for k-mer sampling in the small-k regime.
• The open-closed mod-minimizer offers a universally applicable and superior alternative to existing methods.
• These advancements enhance the speed and reduce the index size in bioinformatics applications.