Chao Kuan-Hao, Chen Pei-Wei, Seshia Sanjit A, Langmead Ben
Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, USA.
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA 94720, USA.
iScience. 2023 Jul 14;26(8):107402. doi: 10.1016/j.isci.2023.107402. eCollection 2023 Aug 18.
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 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.
惠勒图以一种特别易于索引和查询的方式表示字符串集合。这样的图是表示图状泛基因组的实际选择，并且是当前基于图的泛基因组索引的基础。然而，目前没有实用的工具来可视化或检查可能具有惠勒属性的图。在这里，我们提出了Wheelie算法，它结合了一个[此处原文缺失内容]与一个排列求解器（Wheelie-PR）或一个可满足性模理论（SMT）求解器（Wheelie-SMT），以检查给定的图是否具有惠勒属性，该问题一般来说是NP完全问题。Wheelie能够在比迄今为止提出的任何算法都少得多的时间内检查各种随机和现实世界的图。它可以在几秒钟内检查一个具有数千个节点的图。我们将这些算法与互补的可视化工具一起实现在WGT工具包中，该工具包可作为开源软件在https://github.com/Kuanhao-Chao/Wheeler_Graph_Toolkit上获取。
