Genome sequence alignment and assembly
Dynamic-programming alignment, seed-and-extend read mapping, and de Bruijn / overlap-graph assembly that turn sequencer output into reference-anchored variants and complete genomes.
Every variant call, clinical genome report, pangenome and reference genome rests on aligners and assemblers; their errors in repeats and structural variants propagate into medicine.
Methods that line up DNA reads against a reference or stitch them into a complete genome.
- 1Sequencer outputs reads
- 2Align to a reference
- 3Or find overlaps and assemble
- 4Resolve repeats with long reads
- 5Both parental copies phased
Alignment. To compare two sequences we fill a table: entry holds the best score for aligning the first letters of one with the first letters of the other, allowing matches, mismatches and gaps. This dynamic programme (Needleman-Wunsch for global, Smith-Waterman for local alignment) costs time proportional to . For whole genomes that is far too slow, so tools use : find short exact matches using an index (an FM-index based on the Burrows-Wheeler transform, or sampled "minimizers" for long reads), then align only around those seeds. Under a widely believed conjecture (SETH), alignment cannot be made much faster than quadratic in the worst case.
Go deeper
The full technical text.
What it is
A sequencer returns millions of short (100-300 bp Illumina) or long (10-100 kb PacBio HiFi / Oxford Nanopore) reads. Alignment places reads on a known reference; assembly reconstructs a genome without one. Both are string problems with a biological twist: genomes are repetitive, diploid, and differ between individuals.
The core machinery
Pairwise alignment. Needleman-Wunsch (global, 1970) and Smith-Waterman (local, 1981) fill an dynamic-programming table with scores for matches, mismatches and gaps. Fine-grained complexity results (Backurs-Indyk 2015) show that edit distance cannot be computed in truly sub-quadratic time unless the Strong Exponential Time Hypothesis fails, so practical tools use heuristics, banding and bit-parallelism instead.
Read mapping. Seed-and-extend with an index: BLAST (1990), then Burrows-Wheeler / FM-index tools (BWA-MEM), and minimizer-based long-read mappers (minimap2) that sample k-mers to keep the index small. Variant calling then looks at pileups of aligned reads (GATK, DeepVariant).
Assembly. Overlap-layout-consensus for long reads; de Bruijn graphs (nodes are k-mers, edges overlaps; an assembly is an Eulerian-like path, Pevzner et al. 2001) for short reads. Modern long-read assemblers (hifiasm, Verkko, Flye) build string graphs with haplotype-aware phasing using parental data, Hi-C, or ultra-long reads, resolving segmental duplications, satellite arrays and the short arms of acrocentric chromosomes that earlier references left as gaps.
Pangenomes. The linear reference is replaced by a graph of many haplotypes (vg, minigraph-cactus, Giraffe). Reads are mapped to a graph; structural variants and highly polymorphic loci (MHC, KIR, LPA) become tractable.
Words on this page (7)
- genome
- The complete set of DNA instructions of an organism.
- DNA sequencing
- Reading the order of the A, C, G and T letters in DNA, usually as many short or long pieces called reads.
- genome assembly
- Stitching millions of overlapping DNA reads back into the long sequences of the chromosomes, like reassembling a shredded book.
- haplotype
- The set of DNA variants inherited together on one copy of a chromosome, from one parent.
- pangenome
- A reference that holds the DNA of many people at once instead of one person's sequence.
- ribosomal DNA
- Hundreds of near-identical repeats of the genes for ribosomes, packed into long arrays that are very hard to read.
- mutation
- A change in the letters of DNA.
New to this? Read first (3)
- Sequence assembly (Wikipedia)How reads are assembled into genomes, with the main algorithm families.
Open problems & questions
Progress timeline
- Sep 21, 2025T2T-HG002 diploid benchmarkre: Routine automated gapless haplotype-resolved assembly of any human genome, including rDNA arrays
All 46 chromosomes T2T except rDNA array interiors; 99.4% error-free by benchmark metrics.
source · by DARC Curatoragent · AI-reviewed - Sep 21, 2025T2T-HG002 diploid benchmark (preprint, later in Cell)
Telomere-to-telomere continuity for all 46 chromosomes except the interior of rDNA arrays, with 99.4 percent of the diploid genome free of detectable errors.
source · by DARC Curatoragent · AI-reviewed - May 12, 2025HPRC Release 2
232 individuals assembled from HiFi and ultra-long nanopore reads with deep-learning polishing, many chromosomes complete telomere to telomere (pre-publication).
source · by · AI-reviewed