Skip to the content ForoHackers
Log inJoin

Counting k-mers: the smallest useful bioinformatics program

AlgorithmsBioinformaticsPython
#1117 · bayes_and_bagels · · Report

A k-mer is just a substring of length k of a DNA sequence. Counting them is the first step of many tools: genome assemblers, species classifiers, error correctors. And the code fits on a postcard.

from collections import Counter

def kmers(seq, k):
    return (seq[i:i + k] for i in range(len(seq) - k + 1))

COMP = str.maketrans("ACGT", "TGCA")

def canonical(s):
    rc = s.translate(COMP)[::-1]       # reverse complement
    return min(s, rc)

seq = "ACGTTGCAACGT"
counts = Counter(canonical(m) for m in kmers(seq, 3))
print(counts)
# Counter({'ACG': 4, 'AAC': 2, 'CAA': 2, 'GCA': 2})

Why canonical? DNA has two strands, and a read may come from either one. The k-mer GTT on one strand is AAC on the other. Counting both separately splits the evidence in two, so we keep the lexicographically smaller of the k-mer and its reverse complement.

Two numbers worth knowing:

  • There are 4^k possible k-mers. For k = 3 that is 64, for k = 21 it is about 4.4 x 10^12. You cannot make an array for that, so real tools use hash tables or Bloom filters.
  • The count histogram has a shape: a spike near 1 (sequencing errors, each makes up to k fake k-mers) and a hump at the coverage depth. Where the valley between them sits tells you a good cut-off.

Reads with errors are the reason this is statistics and not just string handling. Which is why a statistician is writing this post.

#1805 · SiestaDeAlgoritmos · · Report

Muy bien explicado lo de la canónica. Para k impar hay un detalle bonito: un k-mer nunca es igual a su complementario inverso, porque el símbolo central tendría que ser su propio complemento, y eso no existe en ACGT. Con k par sí puede pasar (palíndromos), y hay que tenerlo en cuenta al contar.

#1806 · bayes_and_bagels · · Report

Right, and a great observation. That is why many tools stick to odd k values. Bonus: it avoids a special case in the code, which is the best kind of bonus.

#1807 · gradient_descent_hiker · · Report

Small tip from the ML side: if you feed k-mer counts into a classifier, normalise by total count per sample first. Otherwise the model just learns "which sample had more reads", and you get a beautiful accuracy that dies on the next batch.

Log in or join to reply.