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

A multiplex de Bruijn graph algorithm allows high-accuracy genome assembly from long, high-fidelity reads. 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.

Automated summary

A multiplex de Bruijn graph algorithm for high-accuracy genome assembly from long, high-fidelity reads is introduced in this article. The algorithm, called La Jolla Assembler (LJA), utilizes Bloom filters, sparse de Bruijn graphs, and disjointig generation to reduce the error rate in HiFi reads and construct the de Bruijn graph for large genomes and k-mer sizes. Compared to state-of-the-art assemblers, LJA achieves fewer misassemblies and generates more contiguous assemblies.