Contents
43 — Genome assembly Part 9 — Genomics

43 — Genome assembly

Before this: Ch 39 · Ch 40 · Ch 42 · Time: ~55 min

Alignment (Ch 42) assumes you already have the genome and only need to locate reads in it. Assembly is the case where you don't. It is the harder problem, and it is hard for a reason that no amount of engineering removes.

What you'll be able to do

The core idea

You are handed an enormous multiset of short substrings, sampled from unknown positions on unknown strands of an unknown string, with errors. Reconstruct the string.

Framed that way it looks like a shortest-common-superstring problem, and the classical literature treats it as one. That framing is doubly wrong. It is NP-hard, which is annoying; and the shortest superstring is not the right answer, which is fatal — the shortest string consistent with the reads is the one that collapses every repeat into a single copy, so the optimal solution to the stated problem is a wrong genome.

The real content of assembly is this: the reads determine the genome only up to the ambiguity created by repeats longer than the reads. Everything else — graph formalisms, error correction, scaffolding, polishing — is machinery for extracting exactly the information the reads contain and no more. The history of the field is the history of making reads long enough that the ambiguity disappears.


1. The problem, stated precisely

Input: reads r_1 \dots r_n, each a substring of the target with substitution and errors, from an unknown strand, sampled at positions that are approximately uniform but not exactly (GC content, chromatin state and library chemistry all bias ). Output: a set of strings that, laid end to end, reconstruct the target.

Coverage is not the binding . Under Poisson sampling at depth c, the expected fraction of the genome covered by no read is e^{-c} — at 30× that is about 10^{-13}, so sampling gaps are a non-issue at modern depths. The genome is fully observed. It is just not fully determined, and the gap between those two words is the subject of this chapter.

2. Overlap–layout–consensus, and the Hamiltonian framing

The obvious approach:

  1. Overlap. For every pair of reads, find suffix–prefix overlaps above a length and identity threshold.
  2. Layout. Build a graph with reads as nodes and overlaps as edges. A reconstruction uses every read once, so it is a Hamiltonian path.
  3. Consensus. With reads laid out, call each base by majority vote over the column.

Two problems. The framing is NP-hard — Hamiltonian path is the textbook example — though in practice the graph is nearly a path and heuristics do fine. The real killer is step 1: all-pairs overlap is O(n^2) suffix–prefix computations. With n \approx 10^9 short reads that is hopeless, and indexing tricks (minimiser seeding, an over the read set) reduce the candidate set but leave a brutal constant.

There is also an information problem. A 150 bp read overlapping another by 40 bp is weak evidence — not because 40 bp of random sequence recurs by chance (it does not; random sequence becomes expected-unique in a 3 Gb genome at ~17 bp), but because the genome is not random. A 40 bp window sits inside Alu and other repeat families a million times over, and an overlap that short gives no leverage to tell a repeat-driven match from a true adjacency. Sequencing error compounds it. Short reads produce a graph dense with spurious edges.

OLC is the right answer when n is small and overlaps are long and unambiguous — which is to say, for long reads. It was how Sanger-era genomes were built, it was abandoned for short reads, and it came back the moment reads got long again. The formalism did not change; the data did.

3. De Bruijn graphs, and the Eulerian framing

The move that made short-read assembly tractable: stop treating reads as the unit.

Chop every read into all its overlapping substrings of length k (). Build a graph whose nodes are (k−1)-mers and whose edges are k-mers: the k-mer ACGT is an edge from node ACG to node CGT. A reconstruction now uses every k-mer once, so it is an Eulerian path — and Eulerian path is linear-time.

The deeper win is that no pairwise comparison ever happens. Identical sequence collapses to the same node automatically, by hashing. Graph construction is a k-mer count, which is embarrassingly parallel and streams.

The price: read coherence is thrown away. A read spanning three variant positions told you those three co-occur on one molecule; after k-merisation, that information is gone unless k exceeds the span.

A worked graph

Target (unknown to the assembler), 11 bp, and four 7 bp reads:

       position  1234567890 1
       target    TACGGATCAGT
       r1        TACGGAT
       r2         ACGGATC
       r3           GGATCAG
       r4            GATCAGT

Decompose each read into 4-mers (k = 4):

r1 -> TACG ACGG CGGA GGAT
r2 ->      ACGG CGGA GGAT GATC
r3 ->                GGAT GATC ATCA TCAG
r4 ->                     GATC ATCA TCAG CAGT

distinct 4-mers: TACG ACGG CGGA GGAT GATC ATCA TCAG CAGT   (8)

Each 4-mer is an edge between its two 3-mers:

 TAC --TACG--> ACG --ACGG--> CGG --CGGA--> GGA --GGAT--> GAT
                                                          |
                                                        GATC
                                                          v
 AGT <--CAGT-- CAG <--TCAG-- TCA <--ATCA-- ATC <----------+

Every node has in-degree = out-degree = 1 except TAC (in 0, out 1) and AGT (in 1, out 0), so the Eulerian path is forced. Read it off by taking the start node and appending the last base of each successive node:

TAC + G + G + A + T + C + A + G + T  =  TACGGATCAGT     ✓ the target

Now break it. Suppose the target contains a sequence R twice, with different flanks — …A R B… and …C R D… — and R is long enough that its internal k-mers are shared. The two paths merge:

   …A ──┐                 ┌── B…
         ├──►[  R  ]──────┤
   …C ──┘                 └── D…

Node R now has in-degree 2 and out-degree 2. Two Eulerian paths exist — (A·R·B, C·R·D) and (A·R·D, C·R·B) — and the k-mer multiset is identical under both. The graph does not prefer one. No traversal heuristic can, because the information is not present.

4. Choosing k

Precisely: two copies of an exact repeat of length r stay separate in the graph only if r ≤ k − 2. At r = k − 1 the repeat is itself a node, and that node acquires the 2-in/2-out structure above. So larger k resolves longer repeats, one base at a time.

Against that, two costs, both quantifiable.

Effective falls. A read of length L yields L − k + 1 , so k-mer coverage is c_k = c \cdot (L-k+1)/L. You cannot spend read length on k and still have it.

Error survival falls exponentially. A single substitution destroys up to k k-mers and creates k spurious ones. The probability a given k-mer is error-free is roughly (1-\varepsilon)^k.

For L = 150, ε = 0.001, read coverage 30×:

kk-mer coverage factor (L-k+1)/Leffective c_k(1-\varepsilon)^k
310.8024×0.970
610.6018×0.941
1010.3310×0.904

At k = 101 you have 10× k-mer coverage, which is no longer comfortably separable from the error k-mers, and 10% of k-mers are corrupted. The trade-off is therefore not "bigger k is better until memory runs out": it is that k must be large enough to break repeats and small enough that true k-mers remain confidently more abundant than error k-mers. That window widens with coverage, widens dramatically with read accuracy, and is why HiFi reads (>99.9% consensus, Ch 40) permit k in the thousands where noisy short reads permit tens.

5. What errors do to the graph, and how to clean it

Three characteristic lesions:

StructureCauseSignature
Tipan error near a read end — the erroneous path runs a few and diesshort dead-end branch, ≈ 1
Bubblean error in a read interior, or a heterozygous sitetwo parallel paths of similar length rejoining
Chimeric linka chimeric read, or an error creating a k-mer that exists elsewherea spurious edge joining unrelated regions

The discriminator is coverage. Plot the k-mer count histogram and it is bimodal: a huge spike at count 1–2 (errors, each unique) and a Poisson-ish peak at c_k (true k-mers). For a there are two true peaks — heterozygous k-mers at c_k/2, homozygous at c_k — and the ratio of their areas estimates heterozygosity while the total estimates genome size. That histogram, computed before any assembly, tells you what you are about to be up against.

Cleaning is then: clip tips, pop bubbles, remove low-coverage edges. The danger is that bubble popping is destruction. Heterozygous bubbles and error bubbles look alike locally, and an aggressive cleaner silently produces a haploid consensus of a diploid organism. Error correction before assembly — reads corrected against a consensus of their overlapping neighbours — moves the same decision earlier, where more evidence is available.

6. String graphs and unitigs

The overlap graph has redundant edges: if A overlaps B, B overlaps C, and A overlaps C consistently, the A→C edge is transitively inferable and carries no information. Remove all such edges, and discard reads wholly contained in others, and what remains is the string graph — the minimal graph representing the same set of reconstructions.

In both formalisms, the honest output is the unitig: a maximal path with no branches, i.e. a stretch where the traversal had no choices. Unitigs are what the data determines. A contig is unitigs plus decisions — some of which are wrong.

This is why the assembly graph (usually GFA, Ch 41), not the flattened FASTA, is the real result. The FASTA is a lossy projection that discards exactly the record of where the assembler guessed. The same insight drives the move to graph references in Ch 45.

7. Repeats: an information-theoretic wall

Return to the 2-in/2-out structure. Consider a read lying entirely inside one copy of a repeat. Which copy did it come from? The read is a substring of both. It carries zero bits about its origin. If every read spanning the region is like that, the two arrangements are not merely hard to distinguish — they generate identical data.

A repeat longer than the read length, and identical between copies, cannot be resolved by any algorithm from those reads. This is a statement about the data, not about the software.

The escape hatch is that repeat copies are rarely perfectly identical. Copies diverge, and a read long enough to span two divergent positions is assigned to a copy. So the operative requirement is: reads long enough to reach from one distinguishing variant to the next.

That single fact explains the entire technology history:

Repeat classTypical lengthReads needed
Alu elements (Ch 19)~300 bp> a few hundred bp
up to ~6 kb> 6 kb
, >99% identical10s–100s kb10s–100s kb, high accuracy
Centromeric higher-order repeat arraysmegabasesultra-long reads (>100 kb)
rDNA arrays, acrocentric short armsmegabasesultra-long reads

Short-read assemblies of a mammal fragment at the scale of the interspersed repeat landscape: contig of tens of kb against a mean Alu spacing of ~3 kb (~1.1 million copies over ~3.1 Gb, verified facts). Paired ends and the divergence between copies walk an assembler through many Alus; nothing walks it through the rest, and that is where the information runs out. Nothing in the assembler is at fault.

8. Scaffolding, gap filling, polishing

Scaffolding orders and orients contigs using long-range links, without knowing the intervening sequence. Gaps are written as runs of N whose length is an estimate. A scaffold is a hypothesis about arrangement; a contig is a claim about sequence.

Source of What it givesFailure mode
Mate pairs / jumping librariestwo reads a known distance apart; landing on different contigs gives order, orientation and gap sizechimeric junctions during library construction produce false links
Long readsdirect spanning evidencenone in principle; in practice
Optical mapspositions of a short motif along megabase molecules, matched to an in-silico digest of contigslabel density; no sequence, so only order/orient and large SV detection
frequency of physical contact between loci (Ch 50)joins across ; needs curation

Why Hi-C works is worth stating as a data-analysis fact. Chromatin is a constrained polymer, so the probability that two loci are cross-linked together decays monotonically with the genomic separation between them — roughly inversely with separation over the megabase range — and contacts between are an order of magnitude rarer than contacts within one. So a Hi-C experiment hands you a noisy, monotone-decreasing function of an unknown distance between every pair of contig ends. That is a seriation problem: cluster contigs into chromosomes (block structure of the contact matrix), order them so contact frequency decays with position (a travelling-salesman-flavoured ordering), and orient each by asking which of its two ends contacts its neighbour more. From one experiment you get chromosome-scale scaffolds for an organism with no genetic map and no reference.

Gap filling re-assembles locally: collect reads whose partners anchor into the gap, assemble just those, splice in. Polishing is the consensus step done properly — realign all reads to the draft and recall every base, which is a per-position inference problem identical in structure to (Ch 46). Polishing a long-read assembly with short reads was standard when long reads were noisy, and it has a nasty failure mode: short reads mismap between paralogues and introduce errors into exactly the multi-copy genes that matter clinically. Accurate long reads largely removed the need.

Per-base accuracy is reported as QV = −10 log₁₀(per-base error rate): Q40 is one error per 10 kb, Q50 one per 100 kb, Q60 one per Mb.

9. Measuring an assembly

is the length-weighted median contig length. Operationally: sort contigs descending, walk down accumulating length, and report the length of the contig at which you pass half the assembly total. Equivalently — the framing worth remembering — pick a random base of the assembly; N50 is the median length of the contig containing it. L50 is how many contigs that took.

Three ways it lies:

  1. It rewards long contigs regardless of correctness. Concatenating two contigs incorrectly raises N50.
  2. It is normalised by the assembly's own size. A fragmented assembly that also lost 20% of the genome divides by a smaller denominator and scores better than it deserves. NG50 fixes this by walking to half of the estimated genome size, making assemblies of the same organism comparable.
  3. Scaffold N50 is not contig N50. Scaffold N50 counts gap Ns as though they were sequence. An assembly can have a 50 Mb scaffold N50 and a 200 kb contig N50; report both or the number is meaningless.

The correctness-aware variant, NGA50, aligns the assembly to a trusted reference, breaks contigs at every structural disagreement, and computes NG50 on the fragments — so a misjoin lowers it.

Completeness is assessed with conserved single-copy — genes expected exactly once in every member of a clade (the idea). Search the assembly for them and report complete / duplicated / fragmented / missing. The duplicated fraction is the diagnostic that matters most: a high value usually means both were retained as separate contigs rather than merged, not that the organism has extra genes. Caveat: this measures gene space only. An assembly can be 99% BUSCO-complete and contain no at all.

Reference-free evaluation avoids assuming a reference exists. Count in the raw reads; those seen often enough to be real but absent from the assembly indicate missing sequence or consensus errors, and their rate converts directly to a QV. The reciprocal check — assembly k-mers absent from reads — fabricated sequence. Add: map the reads back and look for anomalies and clipped-read pileups.

Assembly errors and their signatures, since detection is mostly coverage arithmetic:

ErrorWhat happenedSignature
Misjoinfalse adjacency between distant regionsclipped reads piling up at one point; off-diagonal block; long reads span the junction in neither direction
Collapsed repeatn copies represented as one~n× coverage over the region; excess heterozygous calls that look like a repeat's paralogous differences
False duplicationone region represented twice (unmerged haplotypes)~0.5× coverage on both copies; duplicated BUSCOs
Haplotype switchthe contig jumps between parental haplotypes discordance against parental or Hi-C data

10. A diploid genome is two genomes

Human cells contain two genomes that differ at millions of sites. The traditional "primary assembly" is a single sequence that switches arbitrarily between them — a mosaic that exists in no cell and that systematically misrepresents any region where the differ structurally.

Two ways to properly:

Trio binning. Sequence both parents. Find present in one parent and absent from the other; these mark paternal and maternal haplotypes. Assign each child read to a bin by which marker k-mers it contains, then assemble the bins separately. The result is two haplotype assemblies with essentially no switch errors — and the elegance is that the hard problem (phasing) is solved by counting before any assembly happens. Regions where the parents carry the same have no markers, but they also have nothing to switch.

phasing. No parents required. A Hi-C read pair mostly links two loci on the same physical , therefore the same haplotype. Heterozygous sites linked by many such pairs are in phase, and phase blocks extend chromosome-scale. Modern assemblers keep both haplotype paths in the graph and use trio or Hi-C signal to partition them, producing hap1/hap2 assemblies rather than a mosaic. This is how the human 's haplotype-resolved assemblies are built (Ch 45).

11. Telomere-to-telomere

closed the human reference. It required three things simultaneously:

The result resolved ~8% of the genome that had been inaccessible, including all and the entire short arms of the five acrocentric (verified facts). Those regions were not "difficult" in the earlier references — they were absent, represented by multi-megabase runs of N. That the human reference went from "complete" in 2003 to actually complete in 2022 is the clearest possible demonstration of §7.

12. Metagenomes

Assembling a community adds difficulties that are not merely quantitative:

The standard response is assemble-then-bin: cluster contigs into metagenome-assembled genomes using tetranucleotide composition (species-characteristic) plus the vector of coverages across multiple samples (co-varying contigs are the same organism). That is unsupervised clustering in a composition-plus-abundance space, and it is where a reader with a machine-learning background has an immediate advantage. Quality is then judged by single-copy marker genes, with the widely used convention for a high-quality draft being >90% complete and <5% contaminated.

13. Choosing an approach

SituationApproachWhy
Bacterial isolatelong reads alone, circularisegenome < 10 Mb, few long repeats; complete circular are routine
Small, low-repeat eukaryoteHiFi + graph assemblyrepeats mostly shorter than reads
Large repeat-rich plant, often polyploidHiFi + ultra-long + many near-identical subgenomes; phasing is the whole problem
Human, research-gradeHiFi + ONT ultra-long + Hi-C or trio, phased output-resolved is now the standard, not the luxury
Human, clinicaldo not assemble — align to a reference or assembly answers a question the clinic is not asking, at far higher cost
Metagenomelong reads if biomass permits; assemble, then binrecovers more full-length genes and fewer inter-species chimeras
Ancient or degraded DNAreference-guided onlyfragments of tens of bp carry too little overlap information

The decision rule underneath the table: compare the read length distribution you can obtain with the repeat length distribution of the target. Everything else is secondary.


Common misconceptions

What people thinkWhat's actually true
Assembly finds the shortest string consistent with the readsThe shortest superstring collapses every repeat. The correct genome is longer than the optimum of that objective, so the "optimal" answer is wrong by construction
More fixes fragmentationCoverage saturates. At 30× essentially every base is observed; contiguity is limited by read length versus repeat length, and adding depth changes neither
De Bruijn assembly is better than overlap assemblyIt is better for many short reads, because it avoids all-pairs overlap. For few long reads, overlap and string-graph methods are better — they keep read coherence, which de Bruijn discards
A bigger k always gives a better assemblyBigger k resolves longer repeats but cuts effective coverage and lets errors destroy more k-mers. There is an optimum, and it depends on coverage and accuracy
A high means a good assemblyN50 rewards long contigs whether or not they are correct — a misjoin raises it. Report contig N50, NG50, an error-aware metric, and a completeness measure together
A finished genome is one sequence per A has two per chromosome. A single merged sequence is a mosaic that exists in no cell
Gaps in an assembly are random unlucky regionsThey are overwhelmingly the repeats — , satellite arrays, . The missing 8% of the human genome before T2T was not a random 8%
-complete means the genome is completeBUSCO samples conserved single-copy genes. It is blind to repeats, so an assembly missing every centromere can still score ~99%

Worked example: contiguity metrics, and how a mistake improves them

An assembly of an organism whose genome size is estimated at 160 Mb produces ten contigs (lengths in Mb):

40, 30, 20, 15, 10, 5, 4, 3, 2, 1        total = 130 Mb

. Half the assembly total is 130/2 = 65 Mb. Walk the sorted lengths:

contig   length   cumulative
  1        40         40        < 65
  2        30         70        ≥ 65   ← stop

N50 = 30 Mb, L50 = 2.

NG50. Now walk to half the estimated genome size: 160/2 = 80 Mb.

  1        40         40        < 80
  2        30         70        < 80
  3        20         90        ≥ 80   ← stop

NG50 = 20 Mb, LG50 = 3.

NG50 < N50 because the assembly recovered only 130 of 160 Mb. N50 divided by what was assembled; NG50 divided by what exists. The 30 Mb of missing sequence — almost certainly repeats — is invisible to N50 and penalised by NG50. This is why NG50 is the metric to quote whenever a genome size estimate is available, and the histogram of §5 gives you one without a reference.

Now introduce an error. Suppose the scaffolder wrongly joins the 40 Mb and 30 Mb contigs:

70, 20, 15, 10, 5, 4, 3, 2, 1            total = 130 Mb

half = 65 Mb:   contig 1 = 70 ≥ 65      ← stop immediately

N50 = 70 Mb, L50 = 1 — the headline contiguity metric more than doubled, and the assembly got worse. NG50, by contrast, does not move: walking to 80 Mb, the 70 Mb contig alone falls short, so the walk takes the next one and NG50 = 20 Mb, LG50 = 2 — exactly its value before the misjoin. Read that as luck, not protection. NG50 is normalised by genome size, not by correctness; it happened to be insensitive here only because 70 < 80, and had the scaffolder swallowed the 20 Mb contig as well, the resulting 90 Mb piece would have carried NG50 to 90 Mb. Only a correctness-aware metric is designed to catch this: NGA50 aligns to a trusted reference, breaks the contig at the false junction back into its 40 and 30 Mb pieces, and so refuses to credit the join at all.

The check that would have caught it. At the false junction, long reads span it in neither direction, soft-clipped reads pile up at a single coordinate, and the contact matrix shows the two halves of the 70 Mb contig with near-background contact frequency between them — when §8 says contact frequency between adjacent sequence should be at its maximum. Three independent signals, all available before publication.

Connections