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

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• De Bruijn graph construction is a bottleneck for assembling large genomes, especially with emerging long, high-fidelity (HiFi) reads.
• Previous methods struggle with the computational demands of large k-mer sizes and extensive genomic data.
• Automated, accurate genome assembly is crucial for advancing genomic research and applications.

Purpose of the Study:

• To develop a fast and efficient algorithm for automated genome assembly using long, HiFi reads.
• To overcome the limitations of existing de Bruijn graph construction methods for large-scale genomic data.
• To improve the accuracy and contiguity of genome assemblies.

Main Methods:

• Introduced the La Jolla Assembler (LJA), a novel algorithm incorporating Bloom filters, sparse de Bruijn graphs, and disjointig generation.
• Developed techniques to construct de Bruijn graphs for large genomes and large k-mer sizes.
• Transformed the de Bruijn graph into a multiplex graph with varying k-mer sizes to enhance assembly.

Main Results:

• LJA significantly reduces the error rate in HiFi reads by three orders of magnitude.
• The algorithm successfully constructs de Bruijn graphs for large genomes and large k-mer sizes.
• LJA achieved five-fold fewer misassemblies and more contiguous assemblies compared to state-of-the-art methods.
• Demonstrated utility by automating the assembly of a human genome, including the complete assembly of six chromosomes.

Conclusions:

• The La Jolla Assembler (LJA) provides an effective solution for automated genome assembly from long, HiFi reads.
• LJA's innovative approach addresses key algorithmic challenges in de Bruijn graph construction for large genomes.
• This advancement facilitates more accurate, contiguous, and automated genome assemblies, paving the way for new discoveries.