Genome Assembly

Genome assembly is the process of reconstructing a genome's sequence from a large collection of shorter sequencing reads that overlap one another, without any prior knowledge of the true sequence — hence de novo assembly, as opposed to reference-guided mapping. The reads themselves come from randomly sheared or randomly primed fragments of the genome, sequenced independently, so any two reads that sample overlapping genomic positions will share a stretch of identical sequence (barring sequencing errors). The assembler's job is to detect these shared stretches and use them to infer which reads sit next to each other in the original molecule. Two mathematical abstractions dominate the field. In an overlap graph (also called overlap-layout-consensus, OLC), each read is a node, and an edge connects two reads if they share a sufficiently long, sufficiently exact overlap; walking through this graph traces out the genome. In a de Bruijn graph, reads are first broken into all overlapping substrings of fixed length k, called k-mers; each unique k-mer becomes a node, and edges connect k-mers that overlap by k−1 bases (i.e., are adjacent in some read). Assembly then becomes the search for a path — ideally an Eulerian path, traversing every edge exactly once — through this graph that reconstructs the genome. The de Bruijn approach sidesteps the need for pairwise read-to-read comparison (which scales quadratically with read number) and is the dominant method for short-read data. Whichever graph is used, the raw output is a set of contigs — contiguous, gap-free sequences representing unambiguous paths through the graph. Because repeats create branch points and ambiguous paths, contigs typically end at repeat boundaries; they almost never span an entire chromosome. Scaffolding uses longer-range information — paired-end reads spanning a known insert size, mate pairs, optical maps, or long reads — to determine the order and orientation of contigs and to estimate the size of gaps between them, producing scaffolds that may contain stretches of unknown sequence (denoted by N's) bridging two contigs of known sequence.

Step 1 — Sequencing generates reads. Following the transition described in From Sanger to Next-Generation Sequencing, a genome is fragmented and sequenced, producing millions of reads. Short-read platforms (e.g., Illumina) yield reads of roughly 100–300 bp with per-base error rates near 0.1–1%, mostly substitutions. Long-read platforms (PacBio, Oxford Nanopore) yield reads from a few kilobases to over a megabase, with higher raw error rates (historically 5–15%, now much lower with improved chemistries) but errors that are more randomly distributed and less biased by sequence context.

Step 2 — Overlap detection. For OLC assembly, every read is compared against every other read (or against an index of the read set) to find overlaps above a minimum length and identity threshold. This overlap-finding step is what allows Sequence Alignment Fundamentals — the same edit-distance and seed-and-extend logic used in read mapping — to be repurposed for assembly, since read-vs-read comparison is itself a pairwise alignment problem. For de Bruijn assembly, this pairwise step is avoided entirely: reads are decomposed into k-mers, and overlap is implicit whenever two k-mers share a (k−1)-mer suffix/prefix.

Step 3 — Graph construction and simplification. In the de Bruijn graph, each distinct k-mer observed in the reads is a node; sequencing errors create rare, low-coverage k-mers that appear as short dead-end branches ("tips") or small bubbles, which assemblers prune using coverage-based heuristics. In the overlap graph, transitive edges (an overlap that is implied by two others) are removed to leave a simplified layout graph. Both simplifications aim to leave only the edges that reflect true genomic adjacency.

Step 4 — Path resolution and contig generation. The assembler traces non-branching paths through the simplified graph; each such path is emitted as a contig. Wherever the genome contains a repeat longer than the read length (OLC) or longer than k bases (de Bruijn), multiple genomic loci collapse onto the same graph path, creating a branch point where the correct path cannot be determined locally. This is the central, unavoidable limitation of assembly from short evidence: assembly is fundamentally limited by the length of repeats relative to the length of reads (or k-mers), not merely by sequencing error.

Step 5 — Scaffolding. Paired-end or mate-pair reads — two reads from the ends of the same DNA fragment, separated by a known approximate distance — let assemblers link contigs that could not be joined directly, because if one read of a pair lands in contig A and its partner lands in contig B, then A and B must be adjacent and oriented consistently with the known insert size. Long reads and optical/Hi-C maps extend this same logic over much larger distances, often resolving repeats that defeated short-read assembly entirely.

Step 6 — Gap filling and polishing. Remaining gaps between scaffolded contigs are represented as strings of N's; some pipelines attempt to fill them using overlapping long reads. A final polishing step corrects remaining base-level errors by realigning reads back to the draft assembly and majority-voting the consensus base at each position.

The repeat problem, quantified. If a genome contains a repeated element of length R present in n copies, any assembler using reads or k-mers shorter than R will merge all n copies into a single graph structure — a branch point or cycle — losing information about copy number and flanking context. Human genomes are roughly half repetitive sequence by length (interspersed repeats like Alu elements at ~300 bp, LINE-1 elements up to ~6 kb, and satellite arrays that can span megabases), which is precisely why short-read (100–300 bp) human assemblies remained fragmented into tens of thousands of contigs for two decades, while long-read technologies spanning tens of kilobases have enabled telomere-to-telomere assemblies only in the last several years.

The overlap-graph paradigm and the shotgun sequencing bet (Sanger, Fleischmann, Venter, 1995). The idea of assembling a genome purely from randomly sheared, overlapping fragments — "shotgun sequencing" — was mathematically plausible but had never been demonstrated on a complete organism when Craig Venter, Hamilton Smith, and colleagues at TIGR sequenced Haemophilus influenzae in 1995. They sheared genomic DNA into random fragments, sequenced roughly 24,000 reads by Sanger capillary sequencing, and used an overlap-layout-consensus assembler (TIGR Assembler) to reconstruct the full 1.83-megabase genome — the first complete genome of a free-living organism, published in Science. The result validated whole-genome shotgun assembly as a viable strategy at genome scale, not just for small plasmids or phages, and it directly justified the shotgun approach later scaled up for the Human Genome Project (with Celera Genomics applying the same OLC logic to the far larger and more repetitive human genome).

Coverage statistics: the Lander–Waterman model (1988). Eric Lander and Michael Waterman derived a probabilistic model, before shotgun sequencing was applied to large genomes, predicting how many contigs and gaps to expect given a genome size, read length, and number of reads, treating read start positions as a Poisson process along the genome. Their key result — that the expected proportion of the genome left completely unsequenced (in gaps) is approximately e^(−C), where C is coverage depth — is still the formula used today to decide how much sequencing to order for a target level of completeness, and it explained quantitatively why early shotgun projects needed roughly 8–10× coverage to close most gaps.

De Bruijn graphs formally introduced to assembly (Pevzner, Tanner, Waterman, 2001; Idury & Waterman, 1995). Pavel Pevzner and colleagues proved that reformulating assembly as an Eulerian path problem on a de Bruijn graph built from k-mers, rather than a Hamiltonian path problem on an overlap graph of reads, made the computation tractable at scale — Eulerian path existence and construction can be solved in time linear in the number of edges, whereas the Hamiltonian path problem (visiting every read-node exactly once) is NP-hard in general. This theoretical reframing became essential once short-read sequencers (starting with Solexa/Illumina around 2006) produced hundreds of millions of reads too short and too numerous for pairwise overlap computation to remain feasible, and de Bruijn-graph assemblers (Velvet, ABySS, SOAPdenovo, and later SPAdes) became the standard tools for short-read genome and metagenome assembly.

Long reads resolving repeats directly (Koren, Phillippy, and the "complete" human genome, 2021–2022). Short-read and even early long-read assemblies of the human genome left hundreds of gaps, concentrated in centromeric satellite arrays and segmental duplications too long for any read to span uniquely. The Telomere-to-Telomere (T2T) Consortium, using ultra-long Oxford Nanopore reads (some exceeding 100 kb) combined with highly accurate PacBio HiFi reads, assembled the CHM13 cell line into a gapless sequence for every chromosome, published in Science in 2022. This directly demonstrated the mechanistic prediction of the repeat problem: once read length exceeded the length of essentially all repeat elements in the genome, including the centromeric alpha-satellite arrays, unambiguous paths through the assembly graph became possible where short reads had only produced tangled, unresolvable graph structure.

Example 1 — Computing coverage and predicting contig count. A researcher sequences a newly discovered bacterial genome of size G = 4.6 Mb using paired-end short reads. The sequencing run produces 46 million reads, each 100 bp long. Step 1: Compute coverage using the Lander-Waterman formula. C = (N × L) / G = (46,000,000 × 100) / 4,600,000 = 4,600,000,000 / 4,600,000 = 1,000× That is an unusually high coverage for a bacterial genome (typical targets are 50–100×), so consider a more realistic scenario: only 2.3 million reads were actually usable after quality filtering. C = (2,300,000 × 100) / 4,600,000 = 230,000,000 / 4,600,000 = 50× Step 2: Estimate the expected fraction of the genome missed entirely (zero coverage), using e^(−C). At C = 50, e^(−50) ≈ 2 × 10⁻²², essentially zero — at this depth, gaps from random sampling alone are negligible, and any remaining gaps are attributable to repeats or GC-bias in sequencing, not insufficient sampling. Step 3: Reasoning about contig count. Suppose this bacterial genome contains four copies of a 1.2 kb ribosomal RNA operon repeat, each far exceeding the 100 bp read length. Because reads cannot span the full repeat, the de Bruijn graph collapses all four copies into a single repetitive node with four-way branching, breaking the assembly into at least five contigs at minimum around that single repeat family (one contig approaching each side of the repeat, plus the collapsed repeat itself as an ambiguous unit) — even though the rest of the genome, being largely unique sequence at 50× coverage, assembles into very few additional contigs. This illustrates the general principle: contig count is driven far more by repeat structure than by coverage, once coverage is comfortably above the gap-avoidance threshold.

Example 2 — Calculating and interpreting N50 from real contig lengths. An assembly of a small genome (total assembled length 1,000,000 bp) produced the following contigs, sorted largest to smallest (in bp):

N50 is defined as the length of the contig at which the cumulative sum of contig lengths (sorted largest to smallest) first reaches 50% of the total assembly length. Step 1: Total assembly length = 1,000,000 bp. Half of that is 500,000 bp. Step 2: Walk down the cumulative column until it reaches or exceeds 500,000. After contig 1 (300,000), cumulative is 300,000 — not yet 500,000. After contig 2 (250,000), cumulative is 550,000 — this exceeds 500,000. Step 3: N50 is the length of the contig at which this threshold was crossed: N50 = 250,000 bp (contig 2's length), even though only two contigs were needed to reach halfway. Contrast this with a second assembly of the same total length built from 100 contigs of 10,000 bp each: cumulative length reaches 500,000 bp after the 50th contig, so N50 = 10,000 bp. Both assemblies total exactly 1 Mb, but the first is far more contiguous and more useful for downstream annotation and structural-variant detection — this is exactly why total assembly length alone is a poor quality metric, and N50 (or the analogous L50, the number of contigs needed to reach 50%) is reported instead.

Eugene Myers, a computer scientist and computational biologist, developed much of the algorithmic machinery that made large-scale overlap-based genome assembly practical, including core alignment and overlap-detection algorithms and the whole-genome assembler used by Celera Genomics for the Drosophila and human genome shotgun assemblies. Working alongside biologists like Craig Venter and mathematicians like Granger Sutton, Myers helped prove — against considerable skepticism from parts of the genomics community — that whole-genome shotgun sequencing could scale from small bacterial genomes to the 3-billion-base human genome, provided assembly algorithms and computing infrastructure could keep pace with the combinatorics of overlap detection at that scale.

Genome assembly underlies nearly every modern application of sequencing. In clinical genomics, long-read assembly is now used to resolve disease-associated structural variants and repeat expansions (such as those underlying fragile X syndrome or certain ataxias) that short-read assemblies systematically miss because the repeats exceed short-read span. In agriculture and plant breeding, de novo assembly of crop genomes — often large and highly repetitive, like maize or wheat — enables marker-assisted selection and identification of genes controlling yield and stress tolerance, feeding directly into the annotation pipelines covered under Genome Annotation. In infectious disease and public health, rapid de novo assembly of bacterial and viral genomes from clinical or environmental samples (including outbreak strains and antimicrobial-resistant pathogens) supports genomic surveillance, allowing investigators to track transmission chains and resistance gene acquisition in near real time using portable long-read sequencers. In conservation biology, reference-quality assemblies of endangered species genomes (as pursued by consortia like the Vertebrate Genomes Project) provide the baseline needed to measure genetic diversity, inbreeding, and adaptive potential in shrinking populations. In biotechnology, metagenomic assembly of microbial communities from soil, gut, or industrial samples recovers genomes of uncultured organisms directly from mixed-sample sequencing, revealing metabolic pathways for novel enzymes or antibiotics without ever isolating the organism in pure culture.

Ask the tutor: How do assemblers decide where to break a contig when they hit a repeat, and how do scaffolding algorithms estimate the size of the gap between two contigs?