Building large updatable colored de Bruijn graphs via merging

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Large-scale genomic and metagenomic data collection efforts like GenomeTrakr and MetaSub are continuously growing.
• Existing memory-efficient methods for constructing colored de Bruijn graphs lack scalability and update capabilities for dynamic datasets.

Purpose of the Study:

• To develop a scalable method for constructing colored de Bruijn graphs that allows for efficient updates without complete reconstruction.
• To address the challenge of building and maintaining large graphs from continuously accumulating genomic data.

Main Methods:

• Introduced VariMerge, a novel method that partitions data, builds FM-index based representations of subgraphs, and succinctly merges them.
• The core innovation lies in the succinct merging algorithm, enabling scalable graph construction.

Main Results:

• VariMerge achieved a three-fold reduction in working space for 8000 strains.
• It is the only method capable of constructing and updating a colored de Bruijn graph for 16,000 strains, unlike competing methods that failed to scale or update.

Conclusions:

• VariMerge offers a scalable and updatable solution for constructing colored de Bruijn graphs from large genomic datasets.
• This method is crucial for managing and analyzing the ever-increasing volume of public genomic data.