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
Pages (from-to)1075-1081
Number of pages7
JournalNature Biotechnology
Volume40
Issue number7
DOIs
StatePublished - Jul 2022

    Scopus subject areas

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

    Research areas

  • Algorithms, Genome, Human/genetics, High-Throughput Nucleotide Sequencing, Humans, Sequence Analysis, DNA, Software

ID: 100863933