  Most sequence sketching methods work by selecting specific $k$-mers from
sequences so that the similarity between two sequences can be estimated using
only the sketches. Estimating sequence similarity is much faster using sketches
than using sequence alignment, hence sketching methods are used to reduce the
computational requirements of computational biology software packages.
Applications using sketches often rely on properties of the $k$-mer selection
procedure to ensure that using a sketch does not degrade the quality of the
results compared with using sequence alignment. In particular the window
guarantee ensures that no long region of the sequence goes unrepresented in the
sketch.
  A sketching method with a window guarantee corresponds to a Decycling Set,
aka an unavoidable sets of $k$-mers. Any long enough sequence must contain a
$k$-mer from any decycling set (hence, it is unavoidable). Conversely, a
decycling set defines a sketching method by selecting the $k$-mers from the
set. Although current methods use one of a small number of sketching method
families, the space of decycling sets is much larger, and largely unexplored.
Finding decycling sets with desirable characteristics is a promising approach
to discovering new sketching methods with improved performance (e.g., with
small window guarantee).
  The Minimum Decycling Sets (MDSs) are of particular interest because of their
small size. Only two algorithms, by Mykkeltveit and Champarnaud, are known to
generate two particular MDSs, although there is a vast number of alternative
MDSs. We provide a simple method that allows one to explore the space of MDSs
and to find sets optimized for desirable properties. We give evidence that the
Mykkeltveit sets are close to optimal regarding one particular property, the
remaining path length.
