Syncmers are more sensitive than minimizers for selecting conserved k‑mers in biological sequences

Abstract

Minimizers are widely used to select subsets of fixed-length substrings (k-mers) from biological sequences in applications ranging from read mapping to taxonomy prediction and indexing of large datasets. The minimizer of a string of w consecutive k-mers is the k-mer with smallest value according to an ordering of all k-mers. Syncmers are defined here as a family of alternative methods which select k-mers by inspecting the position of the smallest-valued substring of length s < k within the k-mer. For example, a closed syncmer is selected if its smallest s-mer is at the start or end of the k-mer. At least one closed syncmer must be found in every window of length (k - s) k-mers. Unlike a minimizer, a syncmer is identified by its sequence alone, and is therefore synchronized in the following sense: if a given k-mer is selected from one sequence, it will also be selected from any other sequence. Also, minimizers can be deleted by mutations in flanking sequence, which cannot happen with syncmers. Experiments on minimizers with parameters used in the minimap2 read mapper and Kraken taxonomy prediction algorithm respectively show that syncmers can simultaneously achieve both lower density and higher conservation compared to minimizers.

Keywords: Alignment-free methods; Minimizers; Sequence analysis; String index; k-mers.

Figure 1. Closed syncmers.

Construction of k = 5, s = 2 closed syncmers with lexicographic coding. A k-mer is a closed syncmer if its smallest s-mer is at the beginning or end of the k-mer sequence. Consider a window of three k-mers (length L = 2k − s − 1 = 7 letters) with the sequence shown in (A). The smallest s-mer is AA (orange background). (B) Shows the six s-mers in the sequence in (A). Each s-mer is shown with a gray background in the k-mer where it appears in the first or last position. (B) Illustrates that every s-mer in the sequence shown in (A) appears at the start or end of a k-mer. Therefore, regardless of which s-mer has the smallest value, there is a k-mer in the window for which this s-mer appears at the first or last position. In this example, AA appears at the end of GGCAA, marked with an asterisk (*) and GGCAA is therefore a syncmer. This shows that every window of length L must contain at least one syncmer. Note that while flanking sequence is shown in the figure, GGCAA is recognized as a syncmer from its sequence alone because its smallest 2-mer appears at the end. Closed syncmers tend to form pairs spaced at the maximum possible distance (k − s) as illustrated in (C). (D) Illustrates how k = 5, s = 2 closed syncmers are identified in a longer string. The smallest s-mer in each k-mer is shaded with a color. Blue background indicates that the smallest s-mer is not at the start or end; if it does appears at the start or end then it has an orange background and the k-mer is a closed syncmer (indicated by an asterisk).

Figure 2. Frequency distribution of distances between consecutive submers.

The histograms show spacing distributions for some representative submer types with k = 8 including (A–C) minimizers, (D–F) modulo submers, (G–I) closed syncmers, (J–L) closed rotated syncmers, (M–O) open syncmers, (P–R) open rotated syncmers, (S–U) open syncmers with offset and (V–X) downsampled closed syncmers. Parameters, for example, s (sub-sequence length) and t (offset), are shown at the top of each chart, together with c (compression) and Cn (fraction of conserved letters at 90% identity) for every chart.

Figure 3. Conservation as a function of identity.

The histograms show fraction of conserved letters at identities from 80% to 90% for closed syncmers and minimizers comparable to those used in minimap2 (A) and Kraken (B). Notice that the large majority of submers are deleted at these identities.