WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs
Summary: A Wheeler graph represents a collection of strings in a way that is particularly easy to index and query. Such a graph is a practical choice for representing a graph-shaped pangenome, and it is the foundation for current graph-based pangenome indexes. However, there are no practical tools t...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-08-01
|
| Series: | iScience |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2589004223014797 |
| _version_ | 1827877505869021184 |
|---|---|
| author | Kuan-Hao Chao Pei-Wei Chen Sanjit A. Seshia Ben Langmead |
| author_facet | Kuan-Hao Chao Pei-Wei Chen Sanjit A. Seshia Ben Langmead |
| author_sort | Kuan-Hao Chao |
| collection | DOAJ |
| description | Summary: A Wheeler graph represents a collection of strings in a way that is particularly easy to index and query. Such a graph is a practical choice for representing a graph-shaped pangenome, and it is the foundation for current graph-based pangenome indexes. However, there are no practical tools to visualize or to check graphs that may have the Wheeler properties. Here, we present Wheelie, an algorithm that combines a renaming heuristic with a permutation solver (Wheelie-PR) or a Satisfiability Modulo Theory (SMT) solver (Wheelie-SMT) to check whether a given graph has the Wheeler properties, a problem that is NP-complete in general. Wheelie can check a variety of random and real-world graphs in far less time than any algorithm proposed to date. It can check a graph with 1,000s of nodes in seconds. We implement these algorithms together with complementary visualization tools in the WGT toolkit, available as open source software at https://github.com/Kuanhao-Chao/Wheeler_Graph_Toolkit. |
| first_indexed | 2024-03-12T17:38:29Z |
| format | Article |
| id | doaj.art-2a6484f345c243dab7f5c716214b5895 |
| institution | Directory Open Access Journal |
| issn | 2589-0042 |
| language | English |
| last_indexed | 2024-03-12T17:38:29Z |
| publishDate | 2023-08-01 |
| publisher | Elsevier |
| record_format | Article |
| series | iScience |
| spelling | doaj.art-2a6484f345c243dab7f5c716214b58952023-08-04T05:51:02ZengElsevieriScience2589-00422023-08-01268107402WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphsKuan-Hao Chao0Pei-Wei Chen1Sanjit A. Seshia2Ben Langmead3Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA; Corresponding authorDepartment of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA 94720, USADepartment of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA 94720, USADepartment of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA; Corresponding authorSummary: A Wheeler graph represents a collection of strings in a way that is particularly easy to index and query. Such a graph is a practical choice for representing a graph-shaped pangenome, and it is the foundation for current graph-based pangenome indexes. However, there are no practical tools to visualize or to check graphs that may have the Wheeler properties. Here, we present Wheelie, an algorithm that combines a renaming heuristic with a permutation solver (Wheelie-PR) or a Satisfiability Modulo Theory (SMT) solver (Wheelie-SMT) to check whether a given graph has the Wheeler properties, a problem that is NP-complete in general. Wheelie can check a variety of random and real-world graphs in far less time than any algorithm proposed to date. It can check a graph with 1,000s of nodes in seconds. We implement these algorithms together with complementary visualization tools in the WGT toolkit, available as open source software at https://github.com/Kuanhao-Chao/Wheeler_Graph_Toolkit.http://www.sciencedirect.com/science/article/pii/S2589004223014797BioinformaticsAlgorithmsData structure |
| spellingShingle | Kuan-Hao Chao Pei-Wei Chen Sanjit A. Seshia Ben Langmead WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs iScience Bioinformatics Algorithms Data structure |
| title | WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs |
| title_full | WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs |
| title_fullStr | WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs |
| title_full_unstemmed | WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs |
| title_short | WGT: Tools and algorithms for recognizing, visualizing, and generating Wheeler graphs |
| title_sort | wgt tools and algorithms for recognizing visualizing and generating wheeler graphs |
| topic | Bioinformatics Algorithms Data structure |
| url | http://www.sciencedirect.com/science/article/pii/S2589004223014797 |
| work_keys_str_mv | AT kuanhaochao wgttoolsandalgorithmsforrecognizingvisualizingandgeneratingwheelergraphs AT peiweichen wgttoolsandalgorithmsforrecognizingvisualizingandgeneratingwheelergraphs AT sanjitaseshia wgttoolsandalgorithmsforrecognizingvisualizingandgeneratingwheelergraphs AT benlangmead wgttoolsandalgorithmsforrecognizingvisualizingandgeneratingwheelergraphs |