henhaobio
Sign in

Nature BiotechnologyBioinformaticsPeer-reviewed journal article

Assembly of Long Error-Prone Reads Using Repeat Graphs

Mikhail KolmogoroviD, Jeffrey YuaniD, Yu LiniD, Pavel A. PevzneriD

PDFDOIPreprint

In-depth summary

Claude Opus 5.5 · xhigh effort · 17 Oct 2026 · from the full text of version 1 (12 Jan 2018) · CC BY-NC-ND 4.0

Building the repeat graph from fast, possibly misassembled contigs lets Flye resolve repeats and produce more contiguous long-read assemblies, with fewer errors than Canu on human and worm genomes.

Most long-read assemblers use overlap-layout-consensus, which gives no explicit picture of genome repeats, while de Bruijn graphs built directly from error-prone reads are so noisy that repeat copies are hard to collapse. Flye instead builds an A-Bruijn assembly graph from contigs rather than raw reads (unlike HINGE) and adds a way to separate unbridged repeat copies, those spanned by no read, using small sequence differences between the copies.

Key results

  1. ShownOn human GM12878 nanopore data, Flye produced more contiguous assemblies with fewer errors than Canu and needed far fewer CPU hours than Canu or a hybrid MaSuRCA assembly.

    HUMAN (30x ONT): NGA50 3.2 Mb with 587 errors vs 2.2 Mb with 748 for Canu; the MaSuRCA hybrid with Illumina reads reached 3.6 Mb but had 8,439 errors. HUMAN+ (adding 5x ultra-long reads): 4.5 Mb (939 errors) vs 3.8 Mb (1,249). CPU hours: 10,000 vs 40,000 (Canu) and 50,000 (MaSuRCA), the latter two as reported by those tools' authors. · Analyzing the HUMAN and HUMAN+ datasets; Datasets

  2. ShownOn the C. elegans PacBio dataset, Flye had the fewest misassemblies and the highest NGA50 of the five assemblers, and ran faster than Canu, HINGE and Falcon but slower than Miniasm+ABruijn.

    Misassemblies 62 vs 70 (Miniasm+ABruijn) up to 126 (HINGE); NGA50 1,682 kb vs 1,588 kb for Miniasm+ABruijn and 1,287 kb for the others; run time 480 min vs 290 (Miniasm+ABruijn), 781 (Canu), 803 (HINGE) and 945 (Falcon). · Analyzing the WORM dataset

  3. ShownOn yeast PacBio reads Flye was among the most accurate assemblers, with contiguity similar to every tool except HINGE; on nanopore reads it was more contiguous than Canu and Miniasm, although Miniasm+ABruijn made fewer nanopore misassemblies.

    YEAST-PB: NGA50 525–567 kb for all tools but HINGE (328 kb), Flye 561 kb; misassemblies 10 for Flye and Miniasm vs 20 (Canu), 26 (Falcon), 25 (HINGE); Flye identity 99.95%; 11 of 16 chromosomes complete. YEAST-ONT: NGA50 769 kb vs 545 kb (Canu) and 542 kb (Miniasm); misassemblies 13 vs 8 (Miniasm+ABruijn) and 16 (Canu). · Analyzing the YEAST dataset

  4. ShownAcross 21 NCTC bacterial datasets, resolving unbridged repeats increased the number of complete and semi-complete assembly graphs, and Flye's graphs agreed with HINGE on all but three datasets.

    Before unbridged-repeat resolution: 4 complete, 1 semi-complete, 16 tangled; after: 6 complete, 3 semi-complete, 12 tangled (tangled graphs had 3 to 25 edges). HINGE reported a complete KS11692 assembly where Flye's graph stayed tangled, and HINGE was better on EC10864; Flye was better on EC9964. · Analyzing the BACTERIA dataset

  5. SuggestedDetecting copy-specific variants inside a 22.0 kb two-copy repeat recovered most substitutions with few false calls, and simulations indicated repeats can be resolved once copies diverge by more than 0.1%.

    R22 repeat in EC9964 (6.9% true divergence): 924 of 943 substitutions, 270 of 346 deletions and 54 of 226 insertions found, 81 false positives (0.4% rate), divergence estimated at 6.0%. Simulated PacBio reads (100X, 15% error) on 10-40 kb repeats with 0.01%-0.45% divergence: every repeat above 0.1% was resolved. · Resolving unbridged repeats; Appendix: Resolving unbridged repeats; Appendix: Defining the minimum divergence…

Methods, data and reproducibility

FlyeWalk extends contigs by jumping to any overlapping read without correctness checks; the contigs are concatenated and self-aligned into a repeat graph, reads are mapped onto it, repeats are untangled by maximum-weight matching of read transitions, and unbridged two-copy repeats are split using copy-specific divergent positions. Assemblies were scored with QUAST against Canu, Falcon, HINGE and Miniasm.

  • BACTERIA: long-read datasets from the National Collection of Type Cultures (NCTC), chosen from 997 because earlier work studied them in detail; compared only with HINGE · bacteria (incl. E. coli NCTC9964) · n = 21 datasets
  • YEAST: S. cerevisiae S288c PacBio reads downsampled from 120x to 31x and ONT reads at 31x; 12.1 Mb genome, 16 chromosomes · S. cerevisiae
  • WORM: C. elegans PacBio reads at 40X coverage; 100 Mb genome, 6 chromosomes · C. elegans
  • HUMAN: ONT reads at 30x from the GM12878 cell line; HUMAN+ adds 5x ultra-long ONT reads (read N50 12.5 kb vs 99.7 kb) · human
  • Simulated PacBio reads (100X, 15% error, 5-15 kb) from two-copy repeats of 10, 20 and 40 kb with 0.01%-0.45% divergence
Methods & tools
Flye 2.3, ABruijn (contig polishing), Canu 1.6 (1.3 on YEAST-ONT), Falcon 0.3.0, HINGE 0.5.0, Miniasm 0.2-r168-dirty with Minimap 0.2-r124-dirty, MaSuRCA (downloaded hybrid assembly), QUAST 5.0-dev, Edmonds' maximum weight matching
Reagents & environment
Flye 2.3 (commit e73884c); Canu 1.6 (1.3 on YEAST-ONT because 1.6 gave no output within 24 hours), Falcon 0.3.0, HINGE 0.5.0, Miniasm 0.2-r168-dirty, QUAST 5.0-dev; default or suggested parameters.
Assay conditions & compute
WORM: 480 min for Flye vs 290 to 945 min for the others. HUMAN: 10,000 CPU hours for Flye vs 40,000 and 50,000 reported for Canu and MaSuRCA. Hardware is not specified in this text.
Reproducibility gaps
The availability section says Flye and the supplementary files, including Flye's assemblies, are freely available, but both links are missing from this text. Read datasets are named (NCTC strains, S288c, GM12878) without accessions.
Limitations (4)
  • By default, unbridged repeats count as resolvable only if copies diverge by more than 0.1% and divergent positions lie within twice the average read length; some resolvable repeats may still be left unresolved. · stated by the authors
  • On two bacterial datasets HINGE did better: it reported a complete KS11692 assembly (mean read length only 3928) where Flye's graph stayed tangled, and it gave the better EC10864 assembly. · stated by the authors
  • Error counts exclude local misassemblies under 6,000 bp, and the human CPU-hour figures for Canu and MaSuRCA come from those tools' authors rather than runs on common hardware. · noted in this summary
  • Divergence thresholds were tuned on the same EC9964 R22 repeat used to illustrate the method, the 0.1% minimum comes from simulation only, and only two-copy repeats are handled in the text. · noted in this summary

Read this if you assemble genomes from PacBio or nanopore reads, want an assembly graph that exposes unresolved repeats for finishing, or need the October 2017 benchmark of Flye against Canu, Falcon, HINGE and Miniasm.

Citations
5,984
FWCI
122.95
Field percentile
top 1%

Abstract

The problem of genome assembly is ultimately linked to the problem of the characterization of all repeat families in a genome as a repeat graph. The key reason the de Bruijn graph emerged as a popular short read assembly approach is because it offered an elegant representation of all repeats in a genome that reveals their mosaic structure. However, most algorithms for assembling long error-prone reads use an alternative overlap-layout-consensus (OLC) approach that does not provide a repeat characterization. We present the Flye algorithm for constructing the A-Bruijn (assembly) graph from long error-prone reads, that, in contrast to the k-mer-based de Bruijn graph, assembles genomes using an alignment-based A-Bruijn graph. In difference from existing assemblers, Flye does not attempt to construct accurate contigs (at least at the initial assembly stage) but instead simply generates arbitrary paths in the (unknown) assembly graph and further constructs an assembly graph from these paths. Counter-intuitively, this fast but seemingly reckless approach results in the same graph as the assembly graph constructed from accurate contigs. Flye constructs (overlapping) contigs with possible assembly errors at the initial stage, combines them into an accurate assembly graph, resolves repeats in the assembly graph using small variations between various repeat instances that were left unresolved during the initial assembly stage, constructs a new, less tangled assembly graph based on resolved repeats, and finally outputs accurate contigs as paths in this graph. We benchmark Flye against several state-of-the-art Single Molecule Sequencing assemblers and demonstrate that it generates better or comparable assemblies for all analyzed datasets.

Reproducibility ledger

Nobody has reported trying to reproduce this paper yet. Did you replicate an experiment or run the code? Your report saves the next lab a week.

Sign in to file a reproducibility report.

Related papers

Similarity Map
SelectedSame fieldCross-field
THISLin '16Bankevich '22Bankevich '20Prybol '24Turner '18Diaz-Domíng '22
84% semantic matchBioinformatics
Yu Lin, Jeffrey Yuan, Mikhail Kolmogorov+2 more·bioRxiv·Apr 13, 2016