De Novo Sequence Assembly

De novo sequence assembly (from the Latin de novo, meaning "from the beginning") is the computational and graph-theoretic reconstruction of contiguous chromosomal or genome sequences directly from millions of overlapping fragmented DNA sequencing reads, without aligning to any pre-existing reference assembly. Because no sequencing technology can read an intact 50- to 250-megabase eukaryotic chromosome in a single uninterrupted pass, shotgun sequencing mechanically shears genomic DNA into randomly overlapping fragments of length L (ranging from 150 bp in short-read massively parallel sequencing to 15–100 kbp in long-read single-molecule real-time sequencing and nanopore sequencing).

Reconstructing the original genome from these unmapped reads is a core algorithmic challenge in bioinformatics for two reasons: (1) sequencing reads contain base-calling substitutions and indels (quantified by Phred quality scores), and (2) eukaryotic genomes contain repetitive DNA elements—including transposable elements (Alu, LINE-1), segmental duplications, ribosomal DNA arrays, and centromeric α-satellites. Whenever a genomic repeat of length R exceeds the sequencing read length L (R > L), reads internal to the repeat cannot link its flanking sequences, creating branching ambiguities in the assembly graph.

Overlap-Layout-Consensus (OLC), String Graphs, and the Hamiltonian Path Problem

Formulated by Roger Staden (1979), John Kececioglu and Eugene W. Myers (1995), and generalized into the String Graph by Eugene W. Myers (2005), the Overlap-Layout-Consensus (OLC) approach operates directly on intact sequencing reads across three algorithmic phases:

1. Overlap Discovery: All-versus-all pairwise sequence alignment (or minimizer seed-and-extend indexing via Minimap2) identifies every pair of reads (r_i, r_j) where a suffix of read r_i matches a prefix of read r_j above a minimum overlap length and sequence identity threshold.
2. Layout (Graph Construction and Transitive Reduction): An overlap graph G = (V, E) is constructed in which every sequencing read is a vertex (node) v ∈ V and every suffix-prefix overlap is a directed edge e ∈ E. In Myers's String Graph formulation, redundant transitive edges (if read A overlaps B, B overlaps C, and A also overlaps C, the edge A → C is transitive) are algebraically removed, collapsing unbranched chains into unitigs. Formally, visiting every non-redundant read vertex once to reconstruct the genome corresponds to the Hamiltonian Path Problem, which is NP-complete.
3. Consensus: Multiple sequence alignment or partial-order alignment (POA) of all reads tiling each layout unitig computes the polished consensus sequence. OLC and String Graphs power Celera Assembler (which assembled the Drosophila and Venter human genomes), Canu, Flye (repeat graphs), hifiasm (Heng Li and Haoyu Cheng, 2021), and Verkko for long-read assembly.

Comparison of Genome Assembly Graph Architectures and Quality Metrics

De Bruijn Graphs (DBG), k-mers, and the Eulerian Path Formulation

When second-generation sequencing increased read counts from 10⁶ Sanger reads to 10⁹ Illumina short reads, all-versus-all OLC overlap computation became computationally intractable. Building on Ramana Idury and Michael S. Waterman (1995), Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman (2001) reformulated short-read assembly using a De Bruijn Graph (DBG):

1. Instead of aligning whole reads against one another, every sequencing read of length L is shredded into L − k + 1 overlapping substrings of fixed length k, termed k-mers (stored in a hash table or Bloom filter).
2. In the resulting directed De Bruijn graph, every non-redundant (k − 1)-mer is a node (vertex), and every observed k-mer is a directed edge connecting its (k − 1)-mer prefix node to its (k − 1)-mer suffix node. Identical k-mers originating from dozens of overlapping reads collapse automatically into the same edge without pairwise alignment.
3. Reconstructing the genome now requires finding a path that traverses every directed edge once—an Eulerian Path Problem, which Leonhard Euler (1736) and Carl Hierholzer (1873) proved is solvable in linear time O(|*E*|).

In real sequencing datasets, De Bruijn graphs are complicated by three topological motifs that assemblers (Velvet by Daniel Zerbino and Ewan Birney, SPAdes by Pavel Pevzner's group, and MEGAHIT for metagenomics) resolve via graph simplification: (a) dead-end "tips" (short dangling branches caused by sequencing errors near the 3′ end of a read, pruned by low coverage); (b) parallel "bubbles" (bulges) (two diverging and reconverging paths of length ~*k* caused by a middle-read sequencing error or a heterozygous SNP/indel between maternal and paternal chromosomes); and (c) converging/diverging "braids" (whirls) caused by genomic repeats longer than k, which motivated multi-k-mer assembly in SPAdes (k = 21, 33, 55, 77, 99, 127).

Haplotype-Resolved Diploid Assembly (Trio-Binning, Hi-C, and Verkko / hifiasm)

Historically, genome assemblers collapsed the maternal and paternal homologous chromosomes of a diploid organism into a single mosaic "haploid consensus" reference, occasionally switching phase between alleles or retaining uncollapsed heterozygous bubbles as duplicate haplotigs. Long-read assemblers—such as hifiasm and Verkko (developed by Sergey Nurk, Mikko Rautiainen, Sergey Koren, and Adam Phillippy)—achieve telomere-to-telomere, haplotype-resolved diploid assembly using two phasing strategies:

• Trio-Binning: Short Illumina reads from the mother and father are decomposed into parent-specific k-mers (hap-mers). Long PacBio HiFi and ultra-long Oxford Nanopore reads from the offspring are partitioned into maternal and paternal read buckets prior to (or during) string-graph construction, assembling both parental haplotypes independently.
• Hi-C Chromatin Conformation Phasing: Without parental DNA, proximity ligation (Hi-C) cross-links spatially adjacent DNA strands inside intact nuclei. Because homologous chromosomes occupy separate nuclear territories, cis intrachromosomal Hi-C contacts outnumber trans inter-homolog contacts by >10-fold, allowing hifiasm and Verkko to phase heterozygous bubbles across whole chromosomes including centromeres.

Evaluating Assembly Contiguity (N50 / NG50 / auN) and Completeness (BUSCO & QV)

A de novo genome assembly is benchmarked along three orthogonal axes—contiguity, completeness, and base-level correctness ("The 3 Cs"):

1. Contiguity (N50, NG50, L50, and auN): If all assembled contigs are sorted from longest to shortest, the N50 is the length of the shortest contig at which the cumulative sum of contig lengths reaches ≥50% of the assembly length (NG50 normalizes to the haploid genome size G rather than assembly length, while auN integrates the area under the N(x) curve from x = 0 to 100 to avoid threshold jumps). L50 is the integer number of contigs whose lengths sum to the N50 threshold.
2. Gene Completeness (BUSCO): Benchmarking Universal Single-Copy Orthologs searches the assembly for evolutionarily conserved genes expected to be present as single copies in >90% of species within a taxonomic clade (e.g., Mammalia or Embryophyta), reporting the percentage of Single-Copy, Duplicated (indicating unpurged haplotigs), Fragmented, and Missing genes.
3. Consensus Accuracy (Merqury QV): By comparing the k-mer spectrum of the finished assembly against an independent PCR-free short-read dataset from the same individual, Merqury calculates the consensus Phred quality score (QV), where QV 50 corresponds to 99.999% accuracy (≤1 error per 100 kb) and QV 60 corresponds to 99.9999% accuracy (≤1 error per 1 Mb).

What is the trade-off when selecting the k-mer size k in a De Bruijn Graph assembler, and why does SPAdes iterate across multiple k values?

In a De Bruijn Graph, choosing a small k-mer size (e.g., k = 21) increases sensitivity in low-coverage regions because short k-mers require less read overlap and have a higher probability of containing zero sequencing errors, (1 − p_e)^k; however, small k-mers collapse every genomic repeat longer than 21 bp into a tangled knot. Conversely, choosing a large k-mer size (e.g., k = 127 on 150-bp reads) spans and resolves short repeats up to 126 bp, but reduces effective overlap coverage and breaks contigs wherever read depth drops. SPAdes solves this trade-off by building an iterative multisized De Bruijn graph (k = 21 → 33 → 55 → 77 → 127), using small k to bridge low-coverage gaps and large k to untangle repeats.

Why should N50 never be maximized blindly without checking BUSCO and k-mer completeness?

Because N50 measures only the length distribution of contigs or scaffolds and ignores sequence accuracy, an aggressive assembler can artificially inflate N50 by concatenating non-adjacent genomic regions across repeats (chimeras / misassemblies), filling unresolved gaps with runs of arbitrary N characters, or discarding short contigs (which shrinks the assembly denominator and artificially boosts N50, which is why NG50 with a fixed genome-size denominator is preferred). Tools such as QUAST (against a reference) and Inspector / Craq (reference-free) quantify structural misassemblies, while BUSCO and Merqury verify that gene content and k-mer completeness are preserved.

How did the hybrid Verkko algorithm combine PacBio HiFi and ultra-long Oxford Nanopore reads to assemble gapless human chromosomes?

Neither long-read technology alone could assemble a gapless human genome automatically: PacBio HiFi reads (15–25 kb at >99.9% Q33 accuracy) distinguish single-nucleotide differences between nearly identical copies of segmental duplications and centromeric α-satellite higher-order repeats, building a high-resolution homopolymer-compressed De Bruijn / string graph, but cannot span repeats >25 kb. Conversely, ultra-long Oxford Nanopore reads (100 kb to >1 Mb at ~98%–99% accuracy) span multi-megabase repeat arrays, but are slightly too noisy to build the initial repeat graph alone. Verkko builds the high-resolution repeat graph from PacBio HiFi reads first, then aligns the >100 kb ultra-long Nanopore reads as unbroken paths through the tangled HiFi graph—untying centromeres and acrocentric chromosomes into single telomere-to-telomere contigs.

1. Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). "An Eulerian Path Approach to DNA Fragment Assembly." Proceedings of the National Academy of Sciences, 98(17), 9748–9753. https://doi.org/10.1073/pnas.171285098
2. Myers, E. W. (2005). "The Fragment Assembly String Graph." Bioinformatics, 21(Suppl 2), ii79–ii85. https://doi.org/10.1093/bioinformatics/bti1114
3. Bankevich, A., Nurk, S., Antipov, D., Gurevich, A. A., Dvorkin, M., Kulikov, A. S., Lesin, V. M., Nikolenko, S. I., Pham, S., Prjibelski, A. D., et al. (2012). "SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing." Journal of Computational Biology, 19(5), 455–477. https://doi.org/10.1089/cmb.2012.0021
4. Cheng, H., Concepcion, G. T., Feng, X., Zhang, H., & Li, H. (2021). "Haplotype-Resolved de Novo Assembly Using Phased Assembly Graphs with Hifiasm." Nature Methods, 18(2), 170–175. https://doi.org/10.1038/s41592-020-01056-5