LSMA

LONDON SCHOOL OF MULTIOMICS & AI

Free course

Free course

0 of 73 lessons

Lesson 2 of 9

Module 6 · Genome assembly

k-mers and genome size

k-mers and genome size

k-mers and genome size

A k-mer is a short word of k bases. Counting every k-mer in the reads reveals the genome's size, the coverage and the sequencing errors, before you assemble anything.

⏱ 12 min readModule 6 · Genome assemblyFree
Lesson at a glance3 steps · about 12 min
  1. Count every 21-mer
  2. What this does
  3. Reading the output

Count every 21-mer

A k-mer is every overlapping word of length k you can read from a sequence. Slide a window of k letters along a read one letter at a time, and each position of the window gives one k-mer. In this lesson k is 21, so each 21-mer is a run of 21 bases. Counting how often each one occurs, across all the reads, tells you a great deal about the genome before any assembly is attempted.

A small example makes the counting concrete. The 8-base sequence ACGTTGCA with k = 3 gives six 3-mers: ACG, CGT, GTT, TTG, TGC and GCA. In general a sequence of length L holds L − k + 1 k-mers, so a 125-base read holds 125 − 21 + 1 = 105 of them. Working with k-mers rather than whole reads is useful because reads start at random places and never line up exactly, while a given 21-mer from the genome is the same word in every read that covers it. Counting words therefore measures how often each stretch of the genome was sequenced.

In What genome assembly is you worked out a coverage of about 59× by dividing the bases sequenced by the true genome size. In a real project that size is the unknown. This lesson turns the calculation round and uses the reads alone to estimate it.

A k-mer and its reverse complement are the same piece of double-stranded DNA, so each is counted in one canonical form. The spectrum then asks: how many distinct k-mers were seen once, twice, three times, and so on?

The reverse complement is the sequence of the opposite DNA strand, read in its own direction: swap each letter for its partner (A with T, C with G), then reverse the order. Take a 3-mer as a small example: the reverse complement of ACG is CGT. A read may come from either strand, so the same stretch of genome can arrive as ACG in one read and CGT in another. Counting both under one name, here the one that comes first alphabetically (ACG), stops the same DNA from being split across two counts.

K-mers and genome size · LSMA free course A 21-base window slides one base at a time along a 125-base read, giving 105 complete 21-mers. Below, a 21-mer and its reverse complement are shown; the alphabetically smaller one is kept as the canonical form. 1 · A 21-BASE WINDOW SLIDES ALONG ONE READ one read · 125 bases 21-mer 1 21-mer 2 21-mer 3 … 21-mer 105 125 − 21 + 1 = 105 complete 21-mers in each read 2 · ONE K-MER, TWO STRANDS: KEEP THE SMALLER 21-mer reverse complement ACGTTGCAAGGCTTACCGATG CATCGGTAAGCCTTGCAACGT kept: comes first alphabetically same DNA, read from the other strand
Every read contributes one k-mer per window position. Because reads come from both strands, each 21-mer is stored under one canonical name, so the two strands of the same DNA are counted together. The 21-mer shown is an example. Schematic, not to scale.
Python
import gzip
from collections import Counter

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

def canonical(kmer):
    """A k-mer and its reverse complement are the same DNA: keep the smaller."""
    rc = kmer.translate(COMP)[::-1]
    return min(kmer, rc)

def read_fastq_seqs(path):
    with gzip.open(path, "rt") as handle:
        for i, line in enumerate(handle):
            if i % 4 == 1:
                yield line.strip()

k = 21
counts = Counter()
for path in ["data/bact_R1.fastq.gz", "data/bact_R2.fastq.gz"]:
    for seq in read_fastq_seqs(path):
        for i in range(len(seq) - k + 1):
            counts[canonical(seq[i:i + k])] += 1

print(len(counts), "distinct 21-mers")
spectrum = Counter(counts.values())          # how many k-mers were seen 1, 2, 3 ... times
print([(d, spectrum[d]) for d in (1, 2, 3, 4, 5)])

solid = {d: n for d, n in spectrum.items() if d >= 5}       # ignore error k-mers
peak = max(solid, key=solid.get)
print("peak depth", peak)
total = sum(d * n for d, n in solid.items())
print("estimated genome size", round(total / peak))
90544 distinct 21-mers [(1, 60838), (2, 1778), (3, 9), (4, 8), (5, 32)] peak depth 49 estimated genome size 30827

What this does

  • The setup. gzip opens the compressed FASTQ files and Counter is a dictionary that counts things. COMP is a translation table that swaps A↔T and C↔G.
  • canonical(kmer) builds the reverse complement in two moves: translate(COMP) swaps each letter for its partner, and [::-1] reverses the string. min then returns whichever of the two comes first alphabetically.
  • read_fastq_seqs(path) uses the fact that every FASTQ record is exactly four lines: a header, the sequence, a + line and the qualities. Counting lines from 0, the sequence is line 1, 5, 9 and so on, which is what i % 4 == 1 picks out. yield hands back one sequence at a time, so the whole file never has to sit in memory.
  • The counting loop goes through both files and, for each read, every start position i from 0 to len(seq) - k. The slice seq[i:i + k] is the 21-mer starting there; its canonical form gets one more count.
  • The spectrum. counts.values() is how often each distinct 21-mer was seen; counting those numbers gives, for each depth d, how many distinct k-mers had depth d.
  • The estimate. solid keeps depths of 5 and above, setting the error k-mers aside. peak is the depth shared by the largest number of distinct k-mers. total adds up depth × number of k-mers, which is every k-mer occurrence in the solid part, and dividing it by the peak depth estimates how many different positions the genome has.

Reading the output

  • 90544 distinct 21-mers. A genome of 31,950 bases can hold at most about 32,000 different 21-mers, one per starting position. Seeing almost three times that many tells you that most of the distinct k-mers are not in the genome at all; they were made by sequencing errors.
  • The list of pairs is the start of the spectrum, written as (depth, number of distinct k-mers). (1, 60838) means 60,838 different 21-mers were seen exactly once. The counts fall sharply to 9 and 8 at depths 3 and 4, the valley between the error spike and the genome peak, and start rising again at depth 5.
  • peak depth 49 is the depth at which the most distinct k-mers sit: a typical genome 21-mer was seen 49 times.
  • estimated genome size 30827 is the result of the division, in bases.

Why do errors make k-mers seen only once? A single wrong base in a read changes every 21-mer that overlaps it, up to 21 of them. Those new words almost never occur anywhere else, because another read would need the same error at the same place. A genuine k-mer, by contrast, is read again by every read that covers that stretch of the genome.

This is where the base qualities from Quality control come back. A base at Q30 has a one-in-1,000 chance of being wrong, so even good reads carry an error every few hundred to thousand bases, and across 15,000 reads that adds up to tens of thousands of error k-mers. That is why the count of k-mers seen once is so large even in clean data.

The cut-off of 5 in the code was chosen by looking at this spectrum: it sits in the valley at depths 3 and 4, where very few k-mers fall. It is not a universal number. With low coverage, say 10×, the genome peak moves down towards the error spike and the valley can disappear; a fixed cut-off of 5 would then throw away real genome k-mers and shrink the estimate. Always look at your own spectrum and place the cut-off at its valley. Two other features are worth recognising on real data. Adapter left in the reads, which Trimming and filtering removes, produces a few k-mers with counts far above the main peak, because the same adapter sequence turns up in many reads. And the Python dictionary used here holds every distinct k-mer in memory, which works for 90,544 of them but not for the billions in a human dataset; that is why dedicated counters store each base in two bits and can spill counts to disk.

051015Normalised expressionGene AGene BGene CGene DGene EGene FNormalTumour
A k-mer spectrum has two parts: a spike of error k-mers seen once or twice, and a peak at the typical depth. Illustrative shape.

Worked example · reading the spectrum

60,838 k-mers seen once → almost all contain a sequencing error
peak at depth 49 → a typical genome k-mer was seen 49 times
genome size ≈ k-mers in the genome part ÷ peak = 30,827 bases (true size 31,950: within 4%)

The k-mer depth (49) is lower than the base coverage (59×) because a 125-base read contains only 125 − 21 + 1 = 105 complete 21-mers: 59 × 105 ÷ 125 ≈ 49.

Step by step. The logic is the same as for coverage, run backwards. Coverage is total bases ÷ genome size, so genome size is total ÷ coverage. Here the "total" is every 21-mer occurrence in the solid part of the spectrum, and the "coverage" is the k-mer depth, 49. Their ratio is 30,827. To check it against the truth: 31,950 − 30,827 = 1,123, and 1,123 ÷ 31,950 = 0.035, an error of 3.5%, which is within 4%.

The two depths. There are 15,000 reads, each giving 105 complete 21-mers, so 15,000 × 105 = 1,575,000 k-mer occurrences were counted in all, compared with 1,875,000 bases. Every base is read about 59 times, but a 21-mer is only counted when the whole of it fits inside one read, so only 105 of every 125 positions can start one: 58.7 × 105 ÷ 125 = 49.3, which is the peak at 49.

What the answer means. Without assembling anything, and without knowing the true size, you have learned that the genome is about 31 kb and that the data cover it about 49 times at the k-mer level. In a real project this is how you check that you have sequenced enough before starting a long assembly.

A second, smaller peak at about twice or three times the main depth means repeated sequence, or in a diploid organism the two copies of each chromosome. Tools such as Jellyfish or KMC count k-mers in billions of reads, and GenomeScope fits a model to the spectrum.

In bacteria, which carry one copy of their chromosome, extra peaks usually have a different cause. A plasmid may be present in several copies per cell, so its k-mers are read more often than the chromosome's and form a peak at a higher depth. A small peak at two or three times the main depth in a bacterial spectrum is therefore often a plasmid or a repeated element such as the ribosomal RNA genes, not a sign of a problem.

The diploid case needs a word of explanation. A diploid organism, such as a human, carries two copies of each chromosome, one from each parent. Where the two copies are identical, a k-mer is read from both, so it appears at the full depth. Where they differ at a base, a heterozygous site, each version of the k-mer comes from only one copy and appears at about half the depth. In a diploid spectrum the main peak therefore sits at twice the depth of a smaller "half" peak, and the height of that smaller peak tells you how much the two copies differ. GenomeScope fits exactly these peaks to estimate genome size, heterozygosity and repeat content together.

The current version, GenomeScope 2.0, extends the same model to polyploid genomes, which carry more than two copies of each chromosome, as many crop plants do. A companion plot, Smudgeplot, uses pairs of k-mers that differ at a single base to suggest how many copies there are. In larger projects the k-mer estimate is often checked against flow cytometry, a laboratory method that measures the amount of DNA in stained cell nuclei. When the two disagree badly, the cause is worth finding before you assemble: it may be contamination, very high repeat content, or too little coverage for a clear peak.

Why 21? The value of k is a compromise. If k is too small, many different places in the genome share the same k-mer by chance, and the counts stop being specific. If k is too large, more k-mers contain at least one error and fewer fit inside each read, so the genome peak becomes lower and harder to see. Values around 21 are a common choice for k-mer spectra of short reads.

The k-mer counts are not only a check before assembly; they are also the raw material of it. Most short-read assemblers, including the one used later in this module, break reads into k-mers, keep the solid ones and discard those seen only once or twice as likely errors. The spectrum you have drawn is therefore a preview of what the assembler will see. Assembly graphs, the next lesson, shows how those solid k-mers are joined into longer sequences.

Go deeper: why k is odd, and how errors eat k-mers

k is almost always an odd number, such as 21 or 31. With an odd k, no k-mer can be its own reverse complement, because the middle letter would have to be its own partner and no base pairs with itself. So every k-mer and its reverse complement are always two different words. With an even k, a palindrome such as ACGT is its own reverse complement.

There are 4 to the power of 21, about 4.4 trillion, possible 21-mers, so in a bacterial genome of a few million bases a 21-mer that occurs twice almost always does so because of a real repeat, not by chance. Errors set the upper limit on k. With one error per 1,000 bases, a 21-mer is error-free with probability 0.999 to the power of 21, about 98%. With one error per 100 bases it is about 81%, and a 51-mer at that error rate only about 60%.

Jellyfish is described by Marçais and Kingsford (2011, Bioinformatics) and KMC 3 by Kokot, Długosz and Deorowicz (2017, Bioinformatics). GenomeScope is Vurture et al. (2017, Bioinformatics); GenomeScope 2.0 and Smudgeplot are Ranallo-Benavidez, Jaron and Schatz (2020, Nature Communications). A k-mer estimate is a model fit, not a measurement. It depends on k, on the coverage and on where the error spike is cut off, and it tends to underestimate genomes with many long, near-identical repeats, whose copies share the same k-mers. Report k, the tool versions and the fitted values with the range the tool gives.

Key point

Look at the k-mer spectrum before assembling. A missing peak, or several unexpected ones, warns of low coverage, contamination or a mixed sample.

For a second example, imagine a bacterial culture contaminated with a small amount of a second species. The contaminant's genome is read far less often, so its k-mers form their own peak at a much lower depth, for instance near 10 instead of 49. A spectrum with an extra peak where no repeat or second chromosome copy could explain it is a reason to check the culture before you assemble.

Further reading · Module 6GenomeScope 2.0: the k-mer model for genome size, heterozygosity and ploidy. · Jellyfish: fast k-mer counting. · Why are de Bruijn graphs useful for genome assembly?: a short, open-access primer on assembly graphs. Read this one even if you read nothing else. · All reading for this course

Check your understanding

1. Why are most k-mers seen only once?

2. Solid k-mers total 2,000,000 and the peak is at depth 40. Estimated genome size?

3. Why count canonical k-mers?

Up next

Lesson 3

Assembly graphs

Ask BioTutor

Create a free website with Framer, the website builder loved by startups, designers and agencies.