Buffering updates enables efficient dynamic de Bruijn graphs.

Area of Science:

• Bioinformatics
• Computational Biology
• Graph Theory

Background:

• The de Bruijn graph is a key data structure in bioinformatics, widely used for genome assembly, variant detection, and genome storage.
• Numerous methods exist for constructing and representing de Bruijn graphs efficiently.
• Existing compressed de Bruijn graphs often lack efficient dynamic update capabilities (addition/deletion).

Purpose of the Study:

• To develop a novel compressed dynamic de Bruijn graph that allows for efficient data updates.
• To overcome the performance limitations of existing dynamic de Bruijn graph structures, particularly those relying on slow dynamic bit vectors.
• To present a practical and efficient solution for dynamic de Bruijn graph construction and maintenance.

Main Methods:

• Introduced BufBOSS, a compressed dynamic de Bruijn graph approach.
• Implemented a buffering strategy to handle data additions and deletions, eliminating the need for dynamic bit vectors.
• Compared BufBOSS performance against established tools like Bifrost, DynamicBOSS, and FDBG.

Main Results:

• BufBOSS demonstrates competitive performance in terms of time, memory, and disk usage.
• BufBOSS achieves an order of magnitude improvement in deletion performance compared to existing methods.
• The buffering approach effectively addresses the limitations of dynamic bit vectors in compressed de Bruijn graphs.

Conclusions:

• BufBOSS offers an attractive trade-off between efficiency and dynamic update capabilities for de Bruijn graphs.
• The method provides a significant advancement in handling dynamic data within compressed graph structures.
• BufBOSS represents a practical and high-performing solution for bioinformatics applications requiring dynamic de Bruijn graph manipulation.