Sketching Methods with Small Window Guarantee Using Minimum Decycling Sets.

Area of Science:

• Computational Biology
• Graph Theory
• Bioinformatics Algorithms

Background:

• Sequence sketching methods accelerate similarity estimation by using selected k-mers.
• These methods are crucial for reducing computational demands in bioinformatics software.
• Key properties like locality and window guarantees ensure sketch quality compared to sequence alignment.

Purpose of the Study:

• To explore the largely uncharted space of decycling sets for novel sequence sketching methods.
• To develop a method for enumerating Minimum Decycling Sets (MDSs) with desirable characteristics.
• To identify new sketching algorithms with improved performance, such as smaller window guarantees.

Main Methods:

• Connecting sketching methods with window guarantees to decycling sets of de Bruijn graphs.
• Developing a simple enumeration method for MDSs.
• Analyzing properties of MDSs, such as remaining path length, to assess sketching performance.

Main Results:

• A novel, simple method for enumerating MDSs is presented.
• This method allows for the exploration and optimization of decycling sets for sketching.
• Evidence suggests existing Mykkeltveit sets are near-optimal for remaining path length.

Conclusions:

• The enumeration of MDSs opens avenues for discovering new, high-performance sequence sketching algorithms.
• Optimizing decycling sets can lead to significant improvements in computational biology software.
• The study provides theoretical and computational support for conjectures regarding MDS properties.