Cuttlefish

Cuttlefish constructs compacted de Bruijn graphs from one or more genome references to enable sequence indexing for short- and long-read alignment and comparative genomic analyses.

Key Features:

• Finite-state automata modeling: De Bruijn graph vertices are represented as finite-state automata to track vertex transitioning states.
• State-space constrained representation: Constraining the automata state-space reduces memory usage for graph construction.
• Memory efficiency demonstrated: Constructed a compacted de Bruijn graph for 100 human genomes using approximately 29 GB of memory.
• Speed and parallel scalability: The implementation is fast and highly parallelizable, enabling scaling with increasing numbers and sizes of input references.
• Comparative performance benchmarks: For 11 conifer genomes, Cuttlefish constructed the compacted graph in under 9 hours using around 84 GB of memory versus reported alternatives that required over 16 hours and approximately 289 GB.
• Implementation: Implemented in C++14.

Scientific Applications:

• Sequence indexing: Produces compacted de Bruijn graphs suitable for sequence indexing for short- and long-read alignment.
• Comparative genomics: Facilitates comparative genomic analyses across diverse genomes and large-scale multi-genome projects.
• Colored compacted graph construction: Supports construction of colored compacted de Bruijn graphs for multi-sample or population-level analyses.

Methodology:

The core methodology uses finite-state automata to model de Bruijn graph vertices coupled with state-space constraints to optimize memory usage.