WGT

WGT recognizes and analyzes Wheeler graphs to enable generation, recognition, and visualization for efficient indexing and querying of graph-shaped pangenomes.

Key Features:

• Wheeler Graph Recognition: Implements recognition of Wheeler graphs, which are essential for indexing and querying collections of strings and for representing graph-shaped pangenomes.
• Algorithmic Innovation (Wheelie): Includes the Wheelie algorithm with two approaches—Wheelie-PR (a renaming heuristic combined with a permutation solver) and Wheelie-SMT (an approach using a Satisfiability Modulo Theory solver).
• Performance: Addresses the NP-complete Wheeler graph recognition problem and reports the ability to process random and real-world graphs with thousands of nodes in seconds.
• Visualization Tools: Provides complementary visualization capabilities for examining and interpreting Wheeler graphs.

Scientific Applications:

• Graph-shaped pangenome indexing: Supports construction and analysis of graph-based pangenome indexes by identifying Wheeler graph structure within pangenome graphs.
• Indexing and querying string collections: Enables efficient representation and querying of collections of strings via Wheeler graph recognition for downstream genomic analyses.

Methodology:

Wheelie applies a renaming heuristic with a permutation solver (Wheelie-PR) and an SMT-based approach using a Satisfiability Modulo Theory solver (Wheelie-SMT) to address the NP-complete Wheeler graph recognition problem.