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^kpossible k-mers. Fork = 3that is 64, fork = 21it 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
kfake 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.