VariMerge

VariMerge constructs and incrementally updates succinct colored de Bruijn graphs using FM-index based representations to represent sequence variation across up to 16,000 genomic strains for scalable genomic and metagenomic analysis.

Key Features:

• Scalability and Updatability: Partitions datasets into subsets to enable construction of colored de Bruijn graphs from datasets comprising 16,000 strains and allows incorporation of new data without a full rebuild.
• Memory Efficiency: Uses FM-index based representation for building and merging colored de Bruijn graphs, reducing working space by up to three-fold when constructing graphs for 8,000 strains.
• Algorithmic Innovation: Solves the challenge of merging succinct representations of de Bruijn graphs to create a single cohesive graph that can be updated without complete reconstruction.
• Competitive Edge: Outperforms existing methods (Vari, Rainbowfish, Mantis, Bloom Filter Trie, Almodaresi et al.) in handling large datasets (16,000 strains) with update flexibility.

Scientific Applications:

• Genomic surveillance: Supports genomic research and surveillance by enabling continuously updated colored de Bruijn graphs for projects such as GenomeTrakr.
• Metagenomic monitoring: Supports metagenomic research and monitoring with frameworks for evolving datasets such as MetaSub.
• Large-scale data analysis: Manages large-scale datasets with reduced memory requirements for analysis of thousands of strains.

Methodology:

Partitions large datasets into subsets, constructs individual colored de Bruijn graphs using FM-index based representation, and merges these succinct representations to form an updatable single graph while optimizing resource usage.