25 November 2019 in Neurourology and Urodynamics
5 July 2022 in Algorithmica
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated substring. Recent lines of research focused on extending some of these problems to vertex-labeled graphs, either by using efficient ad-hoc approaches which do not generalize to all input graphs, or by indexing difficult graphs and having worst-case exponential complexities. In the absence of an ubiquitous and polynomial tool like the suffix tree for labeled graphs, we introduce the labeled direct product of two graphs as a general tool for obtaining optimal algorithms in the worst case: we obtain conceptually simpler algorithms for the quadratic problems of string matching () and longest common substring () in labeled graphs. Our algorithms run in time linear in the size of the labeled product graph, which may be smaller than quadratic for some inputs, and their run-time is predictable, because the size of the labeled direct product graph can be precomputed efficiently. We also solve on graphs containing cycles, which was left as an open problem by Shimohira et al. in 2011. To show the power of the labeled product graph, we also apply it to solve the matching statistics () and the longest repeated string () problems in labeled graphs. Moreover, we show that our (worst-case quadratic) algorithms are also optimal, conditioned on the Orthogonal Vectors Hypothesis. Finally, we complete the complexity picture around by studying it on undirected graphs.
11 March 2024 in Algorithms for Molecular Biology
Background: We study the problem of finding maximal exact matches (MEMs) between a query stringQand a labeled graphG. MEMs are an important class of seeds, often used in seed-chain-extend type of practical alignment methods because of their strong connections to classical metrics. A principled way to speed up chaining is to limit the number of MEMs by considering only MEMs of length at least $$\kappa$$ ( $$\kappa$$ -MEMs). However, on arbitrary input graphs, the problem of finding MEMs cannot be solved in truly sub-quadratic time under SETH (Equi et al., TALG 2023) even on acyclic graphs.Results: In this paper we show an $$O(n\cdot L \cdot d^{L-1} + m + M_{\kappa ,L})$$ -time algorithm finding all $$\kappa$$ -MEMs betweenQandGspanning exactlyLnodes inG, wherenis the total length of node labels,dis the maximum degree of a node inG, $$m = |Q|$$ , and $$M_{\kappa ,L}$$ is the number of output MEMs. We use this algorithm to develop a $$\kappa$$ -MEM finding solution on indexable Elastic Founder Graphs (Equi et al., Algorithmica 2022) running in time $$O(nH^2 + m + M_\kappa )$$ , whereHis the maximum number of nodes in a block, and $$M_\kappa$$ is the total number of $$\kappa$$ -MEMs. Our results generalize to the analysis of multiple query strings (MEMs betweenGand any of the strings). Additionally, we provide some experimental results showing that the number of graph MEMs is an order of magnitude smaller than the number of string MEMs of the corresponding concatenated collection.Conclusions: We show that seed-chain-extend type of alignment methods can be implemented on top of indexable Elastic Founder Graphs by providing an efficient way to produce the seeds between a set of queries and the graph. The code is available inhttps://github.com/algbio/efg-mems.
18 January 2022 in Journal of Logic and Computation
In this paper, we analyze the physical puzzle IcoSoKu, a game about placing some given triangular tiles on the faces of an icosahedron in order to fill the capacities of its vertices, and we propose its generalization called 3coSoKu, admitting an arbitrary playing field with triangular faces, arbitrary capacities and an arbitrary set of triangular tiles. First, we prove the strong NP-completeness of 3coSoKu, even when the playing field is a convex polyhedron with equilateral triangles as faces. Second, we encode 3coSoKu both in the constraint modeling language MiniZinc and in the logic programming paradigm known as Answer Set Programming and we develop a visual tool for an accessible interface to the solver. Finally, we use our encodings to verify experimentally that every initial state for IcoSoKu admits a solution.