Bifrost

Bifrost constructs and manipulates compacted de Bruijn graphs to enable memory-efficient analysis of k-mer relationships across genomes for genome sequencing and comparative genomics.

Key Features:

• Compacted de Bruijn graph construction: Constructs compacted de Bruijn graphs directly without first building uncompacted graphs to reduce intermediate memory usage.
• Parallel, memory-efficient algorithm: Implements a parallel and memory-efficient algorithm to decrease computational burden and memory consumption for large datasets.
• Graph coloring: Maps each k-mer in the graph to specific genomes where it occurs to record presence/absence across samples.
• Indexing: Provides functionality to index graph elements for downstream retrieval and analysis.
• Editing: Supports editing operations on the graph structure.
• Querying: Offers querying capabilities over the graph and associated color information.

Scientific Applications:

• Genome sequencing: Facilitates representation and analysis of sequencing data using de Bruijn graph models.
• Comparative genomics: Uses graph coloring and k-mer mappings to compare genomic content across multiple genomes.
• Genetic variation analysis: Enables identification and characterization of variation by linking k-mers to genomes.
• Large-scale genomic data handling: Applies parallel, memory-efficient methods to process large genomic datasets.

Methodology:

Direct construction of compacted de Bruijn graphs, use of a parallel memory-efficient algorithm, graph coloring that maps each k-mer to genomes, and support for indexing, editing, and querying of the graph.