OBIKmers/obikmer
1
0 Fork 0
Code Issues Pull Requests Actions Packages Projects Releases 34 Wiki Activity
Page: theory kmers_and_superkmers
Pages
Home architecture formats index_layout installation theory encoding theory entropy_filter theory indexing_architecture theory kmer_indexing encoding theory kmer_indexing entropy_filter theory kmer_indexing indexing_architecture theory kmer_indexing kmers theory kmer_indexing minimizer_selection theory kmer_indexing superkmers theory kmers_and_superkmers theory minimizer_selection theory phylogeny kmer_based distance_metrics theory phylogeny kmer_based kmer_set_distances theory phylogeny snp_based central_snp_model theory phylogeny snp_based gamma_rate_heterogeneity theory phylogeny snp_based sampling_design theory phylogeny snp_based sankoff_model usage annotate usage convert usage dump usage estimate usage filter usage index_command usage merge usage pack usage phylo usage predicates usage query usage select usage superkmer usage unitig usage utils
Clone
6
theory kmers_and_superkmers
Eric Coissac edited this page 2026-09-12 14:00:23 +02:00
Table of Contents

Kmers and super-kmers

Kmers

A kmer is a DNA subsequence of fixed length k. Two constraints apply to k, both enforced when a command starts (an invalid value exits immediately with an error):

  • k \in [11, 31]: long enough to be specific, short enough to fit in a single 64-bit word at 2 bits/base (k \le 32 is the hard limit; k < 11 gives insufficient specificity).
  • k is odd: an odd-length sequence can never equal its own reverse complement, so the two orientations of any kmer are always distinct. This is required for the canonical form (see DNA encoding) to be well defined.

Super-kmers

A super-kmer is a maximal run of consecutive, overlapping kmers from a read that share the same canonical minimizer (see Minimizer selection). Each kmer in the run overlaps the next by k-1 nucleotides. A super-kmer is capped at 256 nucleotides; a longer run is split at that boundary.

For a random minimizer of length m over kmers of length k, the expected length of a super-kmer is approximately (Golan & Shur 2025; Zheng et al. 2020):

L_{\text{nt}} \approx \frac{k-m+2}{2} + k - 1

For k=31, m=13 this is about 40 nucleotides; in practice super-kmers rarely exceed a few dozen nucleotides.

Canonical super-kmers

A canonical super-kmer is the lexicographic minimum of a super-kmer and its reverse complement. When a read and its reverse complement are both encountered, they produce super-kmers that are reverse complements of each other; both reduce to the same canonical super-kmer, so a genomic region is represented once regardless of which strand was read.

Super-kmers are the unit of work used throughout construction and querying: sequences are decomposed into super-kmers first, and every downstream step (partition routing, deduplication, counting) operates on them rather than on individual kmers.

Bibliography

Golan, S. & Shur, A.M. (2025). Expected density of random minimizers. In: Lecture Notes in Computer Science, Lecture Notes in Computer Science. Springer Nature Switzerland, Cham, pp. 347–360.

Zheng, H., Kingsford, C. & Marçais, G. (2020). Improved design and analysis of practical minimizers. Bioinformatics (Oxford, England), 36, i119–i127.

Wiki sidebar

Theory

Kmer indexing

Phylogeny

Kmer-based

SNP-based

Usage

Formats