Space-efficient and exact de Bruijn graph representation based on a Bloom filter.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• The de Bruijn graph is crucial for next-generation sequencing (NGS) data analysis, particularly in de novo genome assembly.
• Existing in-memory de Bruijn graph representations for human genomes demand excessive memory (≥30 GB), limiting scalability.

Purpose of the Study:

• To develop a memory-efficient de Bruijn graph encoding method.
• To reduce the computational resources required for large-scale genome assembly.

Main Methods:

• Introduced a new encoding scheme for the de Bruijn graph.
• Utilized a Bloom filter with a supplementary structure to mitigate false positives.

Main Results:

• The proposed encoding reduces de Bruijn graph representation space by an order of magnitude.
• The Minia assembly software, incorporating this structure, achieved a complete de novo human genome assembly.

Conclusions:

• The novel encoding drastically lowers memory requirements for de Bruijn graphs.
• Minia successfully assembled a human genome using only 5.7 GB of memory within 23 hours, demonstrating practical efficiency.