Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs

Elastic Degenerate (ED) strings and Elastic Founder (EF) graphs, here collectively named variable strings, are two representations of acyclic components of pangenomes which extend the well-known notion of indeterminate string. Recent studies have focused extensively on algorithmic tasks involving these structures and other forms of variable strings that they generalize. Among such tasks, the basic operation of matching a pattern into a text, a fundamental toolkit for pangenomic data analysis, deserves special attention. In this paper, (1) we establish a clear taxonomy across ED strings and EF graphs, categorizing types of variable strings from the simplest linear (solid) string to the most complex general cases; (2) we consider the problem match(X,Y) of matching a solid or variable pattern of type X into a variable text of type Y, and investigate its time complexity when X and Y are chosen from types of variable strings in the taxonomy of (1). For all possible X and Y, we either provide a non-trivial, often sub-quadratic, upper bound for match(X,Y), or we prove a quadratic conditional lower bound, taking as a reference the existing quadratic conditional lower bounds for match(solid,ED) and match(solid,EF). A preliminary version of this work appeared in [Ascone et al., WABI 2024].

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 3mb )