Sketching methods with small window guarantee using minimum decycling sets.

Area of Science:

• Computational Biology
• Bioinformatics
• Discrete Mathematics

Background:

• Sequence sketching accelerates similarity estimation by using selected k-mers, reducing computational load in bioinformatics.
• Existing sketching methods rely on specific k-mer selection properties like locality and window guarantees.
• Window guarantees ensure comprehensive sequence representation in sketches, preventing loss of information from long regions.

Approach:

• This research connects sketching methods with window guarantees to Decycling Sets, which are unavoidable sets of k-mers.
• The study focuses on Minimum Decycling Sets (MDSs) due to their minimal size and potential for optimized sketching.
• A novel, simple enumeration method for MDSs is presented, allowing exploration of a larger, previously uncharted space of decycling sets.

Key Points:

• The proposed method facilitates the discovery of new sketching algorithms with improved performance, such as smaller window guarantees.
• The enumeration of MDSs allows for optimization based on desirable properties like minimal remaining path length.
• The Mykkeltveit sets are shown to be near-optimal concerning remaining path length, providing a benchmark for new MDS discoveries.

Conclusions:

• The developed MDS enumeration method opens avenues for discovering superior sequence sketching techniques.
• This work expands the toolkit for computational biologists by providing access to a wider range of optimized sketching methods.
• The findings contribute to the theoretical understanding of decycling sets and their practical applications in sequence analysis.