Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads

Anton Bankevich, Andrey V. Bzikadze, Mikhail Kolmogorov, Dmitry Antipov, Pavel A. Pevzner

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

Although most existing genome assemblers are based on de Bruijn graphs, the construction of these graphs for large genomes and large k-mer sizes has remained elusive. This algorithmic challenge has become particularly pressing with the emergence of long, high-fidelity (HiFi) reads that have been recently used to generate a semi-manual telomere-to-telomere assembly of the human genome. To enable automated assemblies of long, HiFi reads, we present the La Jolla Assembler (LJA), a fast algorithm using the Bloom filter, sparse de Bruijn graphs and disjointig generation. LJA reduces the error rate in HiFi reads by three orders of magnitude, constructs the de Bruijn graph for large genomes and large k-mer sizes and transforms it into a multiplex de Bruijn graph with varying k-mer sizes. Compared to state-of-the-art assemblers, our algorithm not only achieves five-fold fewer misassemblies but also generates more contiguous assemblies. We demonstrate the utility of LJA via the automated assembly of a human genome that completely assembled six chromosomes.

Original languageEnglish (US)
Pages (from-to)1075-1081
Number of pages7
JournalNature Biotechnology
Volume40
Issue number7
DOIs
StatePublished - Jul 2022

All Science Journal Classification (ASJC) codes

  • Applied Microbiology and Biotechnology
  • Bioengineering
  • Molecular Medicine
  • Biotechnology
  • Biomedical Engineering

Fingerprint

Dive into the research topics of 'Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads'. Together they form a unique fingerprint.

Cite this