Lesson 3 of 9
Module 6 · Genome assembly
Short-read assemblers build a de Bruijn graph from k-mers and then walk through it. Building a tiny one by hand shows exactly where and why assemblies break.
A genome with a repeat
The 22-base “genome” below contains GACTGA twice. We cut it into overlapping 8-base reads, then build the graph: every k-mer (here k = 4) becomes an edge joining its first three bases to its last three.
A graph, in this sense, is a set of nodes (points) joined by edges (arrows). In a de Bruijn graph the nodes are all the words of length k − 1 and each k-mer is an arrow from its first k − 1 letters to its last k − 1 letters. Take the first 4-mer of the genome, TTAC: it becomes an arrow from TTA to TAC. The next 4-mer, TACG, is an arrow from TAC to ACG. Consecutive k-mers share k − 1 letters, so the arrows link up into a path, and following that path while writing down one new letter per step spells the genome out again.
The useful property is that the graph never needs to know where a read came from. It only needs the k-mers, and k-mers that occur in several reads collapse onto the same arrow. That is what makes it efficient for millions of reads, and also what makes repeats visible: two copies of the same sequence become one shared stretch of the graph.
Real reads add a complication the toy example leaves out: errors. In K-mers and genome size you saw that a single wrong base creates up to k new k-mers that are seen only once. In the graph they become small side branches. An error near the end of a read makes a short dead end, called a tip. An error in the middle makes a bubble: a second path that leaves the main one and rejoins it k − 1 nodes later. Assemblers remove tips and bubbles whose k-mers have very low counts, which is why the k-mer spectrum matters here. In a diploid organism a heterozygous site also makes a bubble, but both paths are well covered, so the assembler has to treat it differently from an error.
from collections import defaultdict
genome = "TTACGACTGATTCCGACTGAGG" # GACTGA occurs twice: a repeat
reads = [genome[i:i + 8] for i in range(0, len(genome) - 7, 2)] # overlapping 8-base "reads"
print(reads)
k = 4
graph = defaultdict(set) # node = (k-1)-mer, edge = k-mer
incoming = defaultdict(set)
for read in reads:
for i in range(len(read) - k + 1):
kmer = read[i:i + k]
graph[kmer[:-1]].add(kmer[1:])
incoming[kmer[1:]].add(kmer[:-1])
for node in sorted(set(graph) | set(incoming)):
if len(graph[node]) > 1:
print("splits at", node, "->", sorted(graph[node]))
if len(incoming[node]) > 1:
print("joins at ", node, "<-", sorted(incoming[node]))What this does
- The reads.
range(0, len(genome) - 7, 2)gives start positions 0, 2, 4 … 14, and each read is the 8 letters from that start. Neighbouring reads therefore overlap by 6 letters, like real shotgun reads that overlap at random. - The graph.
graphmaps each node to the set of nodes its arrows point to;incomingrecords the reverse, which nodes point into it.defaultdict(set)creates an empty set the first time a node is mentioned, so no node needs to be declared in advance. - The inner loop takes every 4-mer of every read.
kmer[:-1]is its first three letters andkmer[1:]its last three, so each 4-mer adds one arrow. Because these are sets, a k-mer seen in several reads, or in both copies of the repeat, is stored once. This is exactly where the two repeat copies merge into one. - The last loop visits every node in alphabetical order and reports any node with more than one way out ("splits") or more than one way in ("joins").
Reading the output
- The first line is the list of eight reads, in genome order. You can check the overlap by eye: TTACGACT ends in ACGACT, and the next read, ACGACTGA, starts with it.
- joins at CGA: two different nodes, ACG and CCG, both lead into CGA. These are the letters immediately before each copy of the repeat.
- splits at TGA: from TGA the path can continue to GAG or to GAT. These are the letters immediately after each copy.
Only two nodes are flagged, one at each end of the repeat. Every other node has exactly one way in and one way out.
Everywhere else the graph is a single path. At the repeat it is not: two routes lead into CGA (from ACG and from CCG), and two lead out of TGA. The graph alone cannot say which entrance goes with which exit.
In this tiny genome you could guess the answer, because one exit leads back into the repeat and the other leads to the end. In a real genome with hundreds of branches, several different routes through the graph spell sequences that are all consistent with the reads. Choosing one at random would risk joining pieces that are not neighbours in the real genome, an error called a misassembly. Assemblers prefer to stop.
A misassembly does more harm than a gap. Imagine a bacterial genome with two copies of an insertion sequence. If the assembler joins the sequence before the first copy to the sequence after the second, the contig places genes next to neighbours they do not have in the cell, and an analysis of which genes sit together, or of where a resistance gene was inserted, will be wrong without any warning. A gap, by contrast, is visible: you know the sequence is incomplete. On real data you can look at the graph yourself. SPAdes writes its graph alongside the contigs in the GFA format (graphical fragment assembly), and a viewer such as Bandage draws it, so that branches, loops and repeats show up as tangles between long clean stretches.
The de Bruijn graph approach to assembly was introduced by Pevzner, Tang and Waterman (2001, PNAS), who framed assembly as finding a path that uses every edge once. Velvet, one of the first assemblers for short reads, is Zerbino and Birney (2008, Genome Research). The string graph used by many long-read assemblers comes from Myers (2005, Bioinformatics). These papers describe the ideas; real assemblers add error correction and many practical rules on top. When you write about an assembly, cite the assembler you actually used and its version, not only the graph method behind it.
Walking until the path is ambiguous
An assembler outputs each unambiguous stretch, a unitig, and stops where the graph branches.
The name is short for "unique contig": a stretch of the graph with no choices along it, so there is only one way to spell it. The function below follows the arrows from a starting node and stops as soon as a choice appears.
def walk(start):
"""Follow the graph from start until a branch or a dead end."""
path, node, seen = start, start, {start}
while len(graph[node]) == 1:
node = next(iter(graph[node]))
if node in seen or len(incoming[node]) > 1:
break
seen.add(node)
path += node[-1]
return path
print(walk("TTA"))What this does
pathstarts as the three letters of the starting node,nodeis where the walk currently is, andseenremembers the nodes already visited.- The
whileloop continues only while the current node has exactly one way out. At a split, the loop ends. next(iter(graph[node]))takes the single node in that set and moves there.- Before using the new node, the function checks two things: has the walk been here already (a loop), and does the new node have more than one way in (a join)? Either one stops the walk.
- Otherwise the new node's last letter,
node[-1], is added to the path, because consecutive nodes overlap in all but one letter.
Reading the output. TTACG is the first unitig. It is only five letters long because the very next node, CGA, is the join at the start of the repeat.
The seen check is not decoration. Bacterial chromosomes and plasmids are circular, so in a complete graph the path from any node eventually comes back to where it started. Without the check, a walk around a circle with no branches would never stop.
On real bacterial data, unitigs are usually far longer than five letters: most run for thousands to hundreds of thousands of bases between repeats. The output of an assembler is not quite the list of unitigs, though. A contig is what the assembler reports after it has used extra evidence, such as read pairs and coverage, to resolve some of the branches. So contigs are at least as long as unitigs and usually longer, and the remaining breaks are the branches it could not resolve safely.
Worked example · why the contig stops
the repeat CGACTGA becomes its own piece, used twice in the genome
so the genome falls into: TTACG · CGACTGA (×2) · GATTCCG · GAGG
Real assemblers also use read pairs and coverage to resolve some branches: a repeat contig has about twice the coverage of its neighbours, a clue you will see in Short-read assembly with SPAdes.
Step by step. Start at TTA; the path is TTA. It has one way out, to TAC, which has one way in, so add C: TTAC. TAC has one way out, to ACG, which has one way in, so add G: TTACG. ACG has one way out, to CGA, but CGA has two ways in, so the walk stops and returns TTACG.
What the answer means. Neighbouring pieces overlap by two letters, k − 2, because each piece ends and the next begins on shared nodes: TTACG and CGACTGA share CG. Laid end to end with those overlaps, TTACG · CGACTGA · GATTCCG · CGACTGA · GAGG spells the 22-base genome exactly. The assembler cannot produce that order itself; it has four pieces and no way of knowing that the repeat is used twice or where.
Two ways to build an assembly graph
The de Bruijn graph is one of two families of assembly method. The older one is overlap–layout–consensus (OLC), and it works with whole reads. It compares the reads with each other to find where they overlap, arranges the overlapping reads into an order, the layout, and then takes a vote at each position across the stacked reads to write the final sequence, the consensus. This was the method for the long, accurate Sanger reads of the first genome projects, including the Human Genome Project.
Comparing every read with every other stops being practical for the hundreds of millions of short reads in a modern run, because the work grows with the square of the number of reads: ten times more reads means about a hundred times more comparisons. The de Bruijn graph avoids this. It never compares reads directly; it only collects their k-mers, as you did above. That is why it became the standard for short reads, and why SPAdes, in Short-read assembly with SPAdes, uses it.
The de Bruijn graph has its own cost: memory. The graph must hold every distinct k-mer, and in K-mers and genome size you saw that most distinct k-mers are errors, almost three times as many as the genome contains in the practice data. That is why short-read assemblers usually correct read errors first. SPAdes, for example, runs an error-correction step before it builds its graph, so that far fewer false k-mers reach it.
With long reads the balance has swung back. A long-read run has far fewer reads, each one thousands of bases long, so finding overlaps is affordable again, and a single overlap can span a repeat that no short k-mer could. Many long-read assemblers therefore build an overlap graph, often a simplified form called a string graph. Others keep the k-mer idea but use very long k-mers, which only accurate long reads make possible. Long reads and repeats returns to them.
How to read the table below
Each row compares one property of the two methods. Read across a row to see how they differ; read down a column to build a picture of one method. The last row names a few well-known assemblers of each kind, as examples only.
| Overlap–layout–consensus | de Bruijn graph | |
|---|---|---|
| Works with | Whole reads | k-mers cut from the reads |
| In the graph | A node is a read; an arrow joins two reads that overlap | A node is a (k − 1)-mer; an arrow is a k-mer |
| Suited to | Long reads: Sanger then, PacBio and nanopore now | Short reads, in very large numbers |
| Main cost | Finding overlaps between pairs of reads | Memory to hold every distinct k-mer |
| Repeats | Resolved when a read spans the whole repeat | Resolved only when the nodes are longer than the repeat |
| Examples | Canu, hifiasm | SPAdes, Velvet |
Go deeper: why one problem is easy and the other hard
In an overlap graph each read is a node, and rebuilding the genome means finding a route that visits every node exactly once. Mathematicians call this a Hamiltonian path, and no fast general method for finding one is known: the work can explode as the graph grows. In a de Bruijn graph each k-mer is an edge, so the task becomes finding a route that uses every edge exactly once, an Eulerian path. Euler showed in 1736 how to tell whether such a path exists, and one can be found in time proportional to the number of edges.
This is the neat argument of Pevzner and colleagues, but it has a catch. A genome with repeats usually allows many different Eulerian paths, only one of them true. That is why real assemblers do not output a single path; they output the unitigs and leave the branches unresolved, as you saw above.
Key point
Larger k resolves more repeats but needs more coverage and fewer errors, which is why assemblers such as SPAdes try several k values and combine them.
You can see the limit in the toy genome. The exact shared stretch is CGACTGA, seven letters. The nodes would only become unique if each were longer than that, eight letters, which means k = 9. But the reads are only 8 letters long, so no 9-mer fits inside any read and k = 9 is impossible here. The read length sets the ceiling on k, and therefore on which repeats a short-read graph can resolve.
Further reading · Module 6Why 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. · The SPAdes manual: modes, options and output files. · All reading for this course
Check your understanding
1. In this de Bruijn graph, what is an edge?
2. Why does the walk stop at CGA ?
3. A contig has three times the coverage of the others. What might it be?
Up next
Lesson 4
Short-read assembly with SPAdes