K-mer Analysis

K-mers are contiguous subsequences of length k extracted from a longer sequence. They are foundational to many bioinformatics algorithms including genome assembly, sequence comparison, metagenomic classification, and error correction. BioLang provides optimized k-mer functions that use 2-bit encoding for k ≤ 32, enabling memory-efficient counting of billions of k-mers.

kmer_encode / kmer_decode

Convert between k-mer strings and their integer encodings. Each base is encoded as 2 bits (A=00, C=01, G=10, T=11), so a k-mer of length k requires 2k bits:

# Encode a k-mer to its integer representation
# kmer_encode(sequence, k)
let code = kmer_encode(dna"ATCG", 4)     # => Kmer (encodes as 27)
code = kmer_encode(dna"AAAA", 4)     # => 0
code = kmer_encode(dna"TTTT", 4)     # => 255

# Decode back to a string
let seq = kmer_decode(kmer_encode(dna"ATCG", 4))   # => "ATCG"
seq = kmer_decode(kmer_encode(dna"AAAA", 4))    # => "AAAA"

kmer_count

Count all k-mer occurrences in a sequence, list, table, or stream. Returns a Table with kmer and count columns, sorted by count descending. Accepts DNA, RNA, strings, lists of sequences, records with a seq field, and FASTQ streams.

let seq = dna"ATCGATCGATCGATCG"

# Count all 4-mers — returns a Table sorted by count (descending)
let counts = kmer_count(seq, 4)
print(counts)   # Table: kmer | count

# Stream mode — constant memory for large FASTQ files
read_fastq("data/reads.fastq")
  |> kmer_count(21)
  |> head(10)
  |> print()

kmer_spectrum

The k-mer spectrum (frequency-of-frequencies) shows how many k-mers appear exactly 1 time, 2 times, etc. This is useful for genome size estimation and error rate analysis. Pass a counts map from kmer_count:

let seq = dna"ATCGATCGATCGATCGATCG"

# Compute k-mer frequency spectrum
let spectrum = kmer_spectrum(kmer_count(seq, 4))
# => Table with frequency and count columns

spectrum |> print()

minimizers

Minimizers are a subsampling scheme that selects the lexicographically smallest k-mer within each window of size w. They are used in minimap2, Kraken, and many other tools for efficient sequence comparison and indexing:

let seq = dna"ATCGATCGATCGATCGATCGATCG"

# Extract minimizers: minimizers(seq, k, window)
let mins = minimizers(seq, 7, 11)
# Returns a list of { kmer, pos } records

mins |> map(|m| print(m.pos, m.kmer))

# Minimizer density (minimizers per base)
let density = float(len(mins)) / float(seq_len(seq))
print("Minimizer density:", density)

kmer_encode / kmer_decode

Convert between k-mer strings and their compact integer encodings, useful for efficient storage and comparison:

# Encode a k-mer to its 2-bit integer representation
let code = kmer_encode(dna"ATCG", 4)
print(code)   # integer encoding

# Decode back to string
let seq = kmer_decode(code)
print(seq)

Practical Example: Metagenomic Classification

K-mer analysis enables fast taxonomic classification without alignment:

# Top 21-mers across all reads — streaming, bounded memory
read_fastq("data/reads.fastq")
  |> kmer_count(21, 50)
  |> print()

# Or full k-mer profile (auto-spills to disk for large datasets)
read_fastq("data/reads.fastq")
  |> kmer_count(21)
  |> head(20)
  |> bar_chart("Top 21-mers")

kmer_index

Build an index from every k-mer in a sequence to the sorted list of all positions where it starts. Returns Map<Str, List<Int>>. This is particularly useful for repeat detection, seed-and-extend alignment, and any workflow that needs to know where a k-mer occurs rather than just how often.

Signature: kmer_index(seq, k) → Map<Str, List<Int>>

let seq = dna"ATCGATCGATCG"
let idx = kmer_index(seq, 3)

# idx is {ATC: [0, 3, 6], TCG: [1, 4, 7], CGA: [2, 5], GAT: [3], ...}
# Look up positions of a specific k-mer
println(idx["ATC"])    # => [0, 3, 6]
println(idx["TCG"])    # => [1, 4, 7]

# Count occurrences
println(len(idx["ATC"]))  # => 3

# Find k-mers appearing more than once (repeat elements)
let repeats = keys(idx) |> filter(|kmer| len(idx[kmer]) > 1)
println(len(repeats), "k-mers appear more than once")

# Build a k-mer index for a FASTA file and detect shared k-mers
let genome_record = fasta("genome.fa") |> first()
let genome = genome_record.seq
let k = 21
let genome_idx = kmer_index(genome, k)
println("Unique 21-mers:", len(genome_idx))

# Find positions of a specific 21-mer
let target = "ATCGATCGATCGATCGATCGA"
let positions = genome_idx[target] ?? []
println("Target k-mer at positions:", positions)