Chaining of Maximal Exact Matches in Graphs
share
We study the problem of finding maximal exact matches (MEMs) between a query string Q and a labeled directed acyclic graph (DAG) G=(V,E,ℓ) and subsequently co-linearly chaining these matches. We show that it suffices to compute MEMs between node labels and Q (node MEMs) to encode full MEMs. Node MEMs can be computed in linear time and we show how to co-linearly chain them to solve the Longest Common Subsequence (LCS) problem between Q and G. Our chaining algorithm is the first to consider a symmetric formulation of the chaining problem in graphs and runs in O(k^2|V| + |E| + kNlog N) time, where k is the width (minimum number of paths covering the nodes) of G, and N is the number of node MEMs. We then consider the problem of finding MEMs when the input graph is an indexable elastic founder graph (subclass of labeled DAGs studied by Equi et al., Algorithmica 2022). For arbitrary input graphs, the problem cannot be solved in truly sub-quadratic time under SETH (Equi et al., ICALP 2019). We show that we can report all MEMs between Q and an indexable elastic founder graph in time O(nH^2 + m + M_κ), where n is the total length of node labels, H is the maximum number of nodes in a block of the graph, m = |Q|, and M_κ is the number of MEMs of length at least κ. The results extend to the indexing problem, where the graph is preprocessed and a set of queries is processed as a batch.
READ FULL TEXT