SplitMEM

SplitMEM constructs compressed de Bruijn graphs to represent shared genomic segments and genetic variation, including single-nucleotide polymorphisms (SNPs) and structural variations, across multiple genomes for pan-genome analysis.

Key Features:

• Compressed de Bruijn Graph Construction: Constructs compressed de Bruijn graphs directly from genomic sequences to encode shared segments, SNPs, and structural variations across genomes.
• Linear Time and Space Complexity: Operates with time and space complexity linear in the total number of genomes for a specified maximum genome size.
• Suffix Tree and Graph Topology Integration: Leverages topological relationships between suffix trees and compressed de Bruijn graphs to improve representation of complex genomic variation.
• Suffix Skips: Introduces suffix skips to traverse multiple suffix links simultaneously, optimizing decomposition of maximal exact matches into graph nodes.

Scientific Applications:

• Pan-genome Analysis: Represents multiple genomes collectively to analyze population-level genetic diversity and evolutionary relationships.
• Core-genome Property Exploration: Analyzes core-genome properties across strains, demonstrated on datasets such as a nine-strain Bacillus anthracis pan-genome and up to 62 Escherichia coli strains.

Methodology:

Constructs compressed de Bruijn graphs from genomic data by integrating suffix tree structures and compressed de Bruijn graph topology, using suffix skips to traverse suffix links and decomposing maximal exact matches into graph nodes.