25 lines
1.9 KiB
Markdown
25 lines
1.9 KiB
Markdown
|
# 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](encoding.md)) 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](minimizer_selection.md)). 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 [@Zheng2020-ji; @Golan2025-xf]:
|
||
|
|
|
||
|
|
$$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.
|