Fast and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3

Area of Science:

• Bioinformatics and Computational Biology
• Genomic Data Analysis
• Algorithm Development

Background:

• The exponential growth of genomic data necessitates scalable algorithms for sequence analysis.
• De Bruijn graphs, especially colored and compacted variants, are crucial for bioinformatics pipelines but challenging to construct at scale.
• Existing methods struggle with the computational demands of constructing these graphs directly from massive datasets.

Purpose of the Study:

• To introduce Cuttlefish 3, a novel parallel, external-memory algorithm for constructing colored compacted de Bruijn graphs.
• To address the limitations of existing methods in terms of speed and scalability for large-scale genomic data analysis.
• To provide a more efficient tool for downstream applications such as genome assembly, indexing, and pan-genomics.

Main Methods:

• Development of Cuttlefish 3, a state-of-the-art parallel, external-memory algorithm.
• Implementation of novel algorithmic improvements including optimized local contractions and parallel list-ranking for joining solutions.
• Inclusion of a sparsification method to reduce data requirements for colored graph computation.

Main Results:

• Cuttlefish 3 demonstrates state-of-the-art performance in constructing compacted de Bruijn graphs.
• The algorithm achieves significant improvements in speed and scalability across diverse genomic datasets.
• It outperforms existing approaches in both colored and uncolored graph construction scenarios.

Conclusions:

• Cuttlefish 3 offers a highly efficient and scalable solution for constructing colored compacted de Bruijn graphs.
• The algorithm's novel strategies effectively handle the challenges posed by large-scale genomic data.
• This advancement is expected to significantly benefit various bioinformatics applications requiring efficient graph construction.