On the representation of de Bruijn graphs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• De Bruijn graphs are crucial for de novo genome assembly.
• Memory representation of de Bruijn graphs is a significant computational bottleneck for assemblers.
• Existing navigational data structures have limitations in memory efficiency.

Purpose of the Study:

• To theoretically analyze space lower bounds for de Bruijn graph navigational data structures.
• To design and implement a novel, memory-efficient data structure for de Bruijn graphs.
• To demonstrate the practical application and benefits of the new data structure in whole-genome assembly.

Main Methods:

• Proving theoretical space lower bounds for navigational data structures.
• Designing and implementing the dbgfm general data structure.
• Developing frequency-based minimizers for de Bruijn graph path enumeration.
• Integrating the dbgfm structure into the ABySS assembler.

Main Results:

• Established theoretical limitations of existing de Bruijn graph approaches.
• Achieved 1.5 GB space usage on a human whole-genome dataset with dbgfm.
• Demonstrated a 46% improvement in space usage over previous methods.
• Enumerate all maximal simple paths using only 43 MB of memory via frequency-based minimizers.

Conclusions:

• The dbgfm data structure offers significant memory savings for de Bruijn graph representation.
• Frequency-based minimizers provide an efficient method for path enumeration.
• The dbgfm approach is practical and can be integrated into existing assembly software, enhancing performance.