Long-Read Genome Assembly
String Graphs & Overlap-Layout-Consensus (OLC)
Interactive exploration of exact all-vs-all read overlaps, Myers' O(V+E) transitive reduction, contained read pruning, and read tiling layout for PacBio HiFi and Nanopore reads.
In raw overlap graphs, if read A overlaps B and B overlaps C, there is often a redundant shortcut edge A → C.
Myers proved that all such transitive shortcuts can be pruned in O(V + E) linear time without losing sequence information, transforming the dense overlap mesh into a clean String Graph.
Contained reads (reads fully covered by a longer read) are pruned beforehand.
OLC vs De Bruijn Graphs
De Bruijn graphs chop reads into k-mers, losing long-range phasing. Overlap-Layout-Consensus (OLC) operates on full-length reads, making it the gold standard for long-read assemblers (PacBio HiFi, Oxford Nanopore).
Contained Reads & Phase Preservation
Reads fully contained inside longer reads provide no additional boundary information and create dead-end cycles. Pruning them leaves only irreducible vertex nodes representing non-redundant long genomic fragments.
Modern OLC Assemblers
State-of-the-art long-read assemblers like Hifiasm, Flye, and Canu use homopolymer compression, all-vs-all minimizer alignment, and string graph transitive reduction to assemble complete telomere-to-telomere (T2T) chromosomes.