Assembly of long error-prone reads using de Bruijn graphs

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Recent genome assembly breakthroughs primarily use the overlap-layout-consensus (OLC) method.
• The de Bruijn graph approach is often incorrectly perceived as limited to short, accurate reads.
• This overlooks the potential of de Bruijn graphs for complex genomic data.

Purpose of the Study:

• To demonstrate the generalization of de Bruijn graphs for assembling long, error-prone reads.
• To introduce the ABruijn assembler, integrating de Bruijn graph and OLC methodologies.
• To achieve accurate genome reconstructions using an improved assembly strategy.

Main Methods:

• Generalizing de Bruijn graph algorithms to accommodate longer, error-prone sequencing reads.
• Developing the ABruijn software, which synergistically combines de Bruijn graph and OLC principles.
• Evaluating the assembler's performance on complex genome reconstruction tasks.

Main Results:

• Successfully generalized de Bruijn graphs for long-read assembly challenges.
• The ABruijn assembler demonstrated accurate genome reconstructions.
• This work refutes the notion that de Bruijn graphs are unsuitable for long-read data.

Conclusions:

• De Bruijn graphs can be effectively applied to assemble long, error-prone reads.
• The ABruijn assembler provides a powerful new tool for high-accuracy genome reconstruction.
• This research expands the utility of graph-based methods in bioinformatics.