Creating and Using Minimizer Sketches in Computational Genomics

Abstract

Processing large data sets has become an essential part of computational genomics. Greatly increased availability of sequence data from multiple sources has fueled breakthroughs in genomics and related fields but has led to computational challenges processing large sequencing experiments. The minimizer sketch is a popular method for sequence sketching that underlies core steps in computational genomics such as read mapping, sequence assembling, k-mer counting, and more. In most applications, minimizer sketches are constructed using one of few classical approaches. More recently, efforts have been put into building minimizer sketches with desirable properties compared with the classical constructions. In this survey, we review the history of the minimizer sketch, the theories developed around the concept, and the plethora of applications taking advantage of such sketches. We aim to provide the readers a comprehensive picture of the research landscape involving minimizer sketches, in anticipation of better fusion of theory and application in the future.

Keywords: de Bruijn graphs; k-mer counting; minimizers; read mapping; sketching.

FIG. 1.

Example minimizer sketch with $w=5,k=3$ and $O$ being the lexicographical order. Left-hand side: the sequence $S=AACGTCGATCCG$ at the top, each line below is a window of S with selected k-mer in red. Right-hand side: Resulting sketch of S.

FIG. 2.

Comparing two minimizer sketches that are identical in $w,k$ and S, only differing in the lexicographical ordering $O$. Left: $A<C<G<T$, identical to Figure 1. Middle: $T<G<C<A$ and all other parameters intact. Right: Resulting sketches for both setups.

FIG. 3.

Example for calculating preservation, with setup identical to that in Figure 1. Left-hand side: The original sequence S, its windows, and selected minimizer k-mers. Right-hand side: The mutated sequence $S\prime$ (the single mutated base is marked in purple), its windows, and selected minimizer k-mers (those different from S are marked in purple). The preservation rate is 2/11.

FIG. 4.

Example of using minimizer sketch for read mapping. Left-hand side presents the original sequence, the original read, and the set of potential mappings. Right-hand side presents their minimizer k-mers as colored blocks, and the set of potential mappings that has at least a minimizer match. The second mapping has two minimizer matches, and is usually considered the mapping with highest quality.

FIG. 5.

Example of minimizer-assisted k-mer counting. For counting 5-mers, we use $k_0=2$ and lexicographical order, implying $w_0=4$. Left-top shows the sequence S and its windows (5-mers) grouped into super-k-mers by shared minimizer. Super-k-mers are sent to buckets and the results of 5-mer counting are shown in each bucket. The final tabulation is obtained by concatenation.