k-mer Spectrum

The spectrum plots the multiplicity (frequency of occurrence) of each distinct k-mer against the number of k-mers with that multiplicity. For a diploid genome sequenced at uniform coverage, this produces a characteristic Poisson-like distribution with a distinct homozygous peak at the expected sequencing depth and a heterozygous peak at half that depth.

• Homozygous peak: Represents k-mers from unique, non-repetitive regions of the genome
• Heterozygous peak: Arises from heterozygous variant sites where k-mers spanning the variant appear at half the expected coverage
• Error tail: Low-frequency k-mers (multiplicity 1-3) primarily represent sequencing errors
• Repeat peaks: Multiplicities at integer multiples of the main peak indicate repetitive genomic elements

The total number of k-mers in the spectrum divided by the modal coverage depth provides a direct, assembly-free estimate of genome size. This is a foundational step in de novo assembly projects and is implemented in tools like GenomeScope and Jellyfish.

• Formula: Genome Size ≈ (Total k-mer count) / (Peak coverage depth)
• Accounts for sequencing error by excluding low-frequency k-mers below a defined threshold
• Heterozygosity correction: The relative heights of the homozygous and heterozygous peaks quantify the genome-wide heterozygosity rate
• Works robustly even with moderate-coverage short-read data (20-30x)

The relative abundances of specific k-mers are non-random and reflect species-specific genomic signatures shaped by evolutionary pressures including dinucleotide stacking energies, codon usage bias, and restriction-modification systems. This compositional bias is the basis for metagenomic binning algorithms.

• Tetranucleotide frequency (TNF) vectors are the most widely used compositional feature for binning
• GC content alone is insufficient; the distribution of k-mers at a fixed GC level provides discriminatory power
• Palindromic k-mers (e.g., GATC, CTAG) are often under-represented due to restriction enzyme avoidance
• Principal Component Analysis (PCA) of k-mer frequency vectors separates genomes by phylogenetic lineage

Direct comparison of full k-mer sets is computationally prohibitive for large datasets. MinHash reduces each k-mer set to a compact sketch of fixed size by applying multiple hash functions and retaining only the minimum hash value for each, enabling rapid estimation of Jaccard similarity.

• Jaccard Index = |A ∩ B| / |A ∪ B|, estimated from the fraction of matching minimum hashes
• Mash and sourmash implement MinHash for genomic distance estimation at terabase scale
• FracMinHash extends this by selecting only k-mers whose hash values fall below a fraction threshold, enabling containment index estimation
• Enables all-vs-all comparison of tens of thousands of genomes in minutes

The k-mer spectrum is the raw material for constructing a de Bruijn graph, the core data structure underlying modern short-read assemblers. Each distinct k-mer becomes a vertex (or edge, depending on formulation), and a directed edge connects k-mers that overlap by k-1 nucleotides.

• Nodes: All distinct k-mers present in the sequencing reads
• Edges: Connect k-mer A to k-mer B if the (k-1)-length suffix of A matches the (k-1)-length prefix of B
• Contigs: Non-branching paths through the graph represent contiguous genomic sequences
• Bubble structures: Arise from heterozygous variants or sequencing errors and must be resolved by the assembler
• Tools like MEGAHIT and metaSPAdes build de Bruijn graphs directly from the k-mer spectrum for metagenomic assembly

Sequencing errors introduce spurious k-mers that appear at very low frequencies in the spectrum, while true genomic k-mers appear at high frequency. This property enables spectrum-based error correction without a reference genome.

• BayesHammer (SPAdes pipeline): Uses Hamming graph clustering of k-mers to identify and correct errors
• BFCounter and BLESS: Count k-mer frequencies and correct low-frequency k-mers by finding high-frequency neighbors within a small edit distance
• Lighter: Employs a Bloom filter to efficiently store the k-mer spectrum and correct errors in a single pass
• The solid k-mer threshold distinguishes true genomic k-mers from errors; typically set at frequency ≥ 3 for moderate-coverage data

A directed graph where nodes represent k-mers and edges represent overlaps of k-1 nucleotides. This structure is the algorithmic backbone of short-read assemblers like MetaSPAdes and Velvet. By decomposing reads into their constituent k-mers, the assembler constructs a graph that models the genome's repeat structure. The choice of k directly determines the graph's connectivity: a k-mer that is too short creates unresolvable branching at repeats, while a k-mer that is too long fails to overlap in low-coverage regions.

Locality-sensitive hashing techniques that compress a k-mer spectrum into a compact sketch for rapid similarity estimation. MinHash selects the smallest hash values from a set to estimate the Jaccard index between two genomes. FracMinHash extends this by selecting only hash values below a fraction of the maximum possible value, enabling scalable estimation of containment and Average Nucleotide Identity (ANI) without storing the full k-mer set. Tools like Mash and sourmash use these sketches for large-scale taxonomic clustering.

A plot of k-mer multiplicity versus the number of distinct k-mers with that exact count. This histogram reveals critical properties of the underlying genome and sequencing run:

• Homozygous peak: The main peak at high coverage representing unique genomic sequence
• Heterozygous peak: A secondary peak at half the coverage depth indicating diploid variation
• Error peak: A spike at very low multiplicity (1-3x) caused by sequencing errors
• Repeat peaks: Multiples of the main peak indicating collapsed repeats Tools like GenomeScope fit statistical models to this histogram to estimate genome size, heterozygosity, and repeat content directly from unassembled reads.

A standardized encoding that collapses a k-mer and its reverse complement into a single lexicographically smaller sequence. Since DNA is double-stranded and sequencing reads originate from either strand, a k-mer and its reverse complement represent the same genomic locus. Canonicalization ensures that strand ambiguity does not inflate the feature space. For example, the 3-mer 'ACG' and its reverse complement 'CGT' are both stored as 'ACG' (the lexicographically smaller). This is essential for tools like Jellyfish and KMC.

Algorithms that assign taxonomic labels by matching query k-mers against a pre-indexed database of reference genomes. Kraken2 uses an exact-match approach with a compact hash table mapping every k-mer to a Lowest Common Ancestor (LCA) taxon. CLARK uses discriminative k-mers unique to specific taxa. These methods achieve high throughput by avoiding full alignment, instead treating classification as a fast k-mer lookup problem. The k-mer size (typically 31-35 bp) balances specificity against sensitivity to sequencing errors.

Efficient data structures for storing and querying k-mer spectra from high-volume sequencing data. Bloom filters provide memory-efficient probabilistic membership queries. Counting quotient filters and hash tables (used in Jellyfish and KMC3) enable exact frequency counting. These tools use lock-free parallel algorithms and disk-based storage to process terabases of sequencing data. The choice of hash function (e.g., MurmurHash3, xxHash) and encoding scheme (2-bit nucleotide representation) critically impacts both memory footprint and runtime performance.