New complexity map charts pattern matching across pangenome string structures

As genome sequencing produces ever larger collections of genomes, biologists increasingly abandon the idea of a single linear reference sequence in favor of a pangenome, a joint representation of many genomes that keeps both shared sequence and variation in one structure. In a paper published in Algorithms for Molecular Biology, Rocco Ascone, Giulia Bernardini, Alessio Conte, Massimo Equi, Esteban Gabory, Roberto Grossi and Nadia Pisanti present a complete taxonomy of pangenome string representations and a comprehensive complexity analysis of the most basic operation performed on them: matching a pattern against a text.

The structures at the heart of the study are elastic-degenerate strings, or ED strings, and elastic-founder graphs, or EF graphs, which the authors collectively call variable strings. Both are ways of compressing acyclic pieces of a pangenome. An ED string is a sequence of segments, where each segment is a set of alternative strings rather than a single character, so one position in the text can stand for several possible genomic variants, including the empty string that explicitly encodes deletions. EF graphs add edges between variants of adjacent segments, connecting them according to haplotype information, which makes them slightly more faithful to how variants co-occur across individual genomes. Both structures generalize the older notion of indeterminate strings, in which each position holds a set of possible letters.

The paper’s first contribution is a clean hierarchy of these representations. At the simplest level sits the ordinary solid string, where every position holds exactly one character. Above it come indeterminate strings, known as 1-D strings, in which each segment holds a set of single letters; these naturally capture the IUPAC encoding of DNA and RNA nucleotide subsets and are widely used to highlight single nucleotide polymorphisms. The class k-D generalizes this by letting every variant have the same length k, while generalised degenerate, or GD, strings only require the variants within each locus to share a length, allowing different loci to differ. GD strings therefore represent gapless multiple sequence alignments of fixed width. At the most general level, ED strings allow variants of any size at any locus, including the empty string, and correspond closely to the VCF file format used to store genomic variants. The same ladder applies to founder graphs, with the addition of haplotype-aware edges and the constraint that EF graphs cannot contain the empty string.

With this taxonomy in place, the authors define the problem match(X, Y): given a pattern of type X and a text of type Y, both drawn from the hierarchy of variable strings, find all positions where a string from the pattern’s language occurs in the text. Because the language of a variable string can be exponentially large in its input size, the output reports only the ending segments of occurrences, not every position within segments. The question the paper answers is deceptively simple: for every possible pairing of pattern type and text type, is matching solvable in truly subquadratic time, or is quadratic time essentially unavoidable?

The answer depends sharply on where the pattern and text sit in the hierarchy. When the pattern is solid and the text is a k-D string, the authors prove a genuinely subquadratic algorithm running in O(N + N log squared m) time, where N is the size of the text and m the length of the pattern. The technique reduces the problem to k instances of subset matching, a problem defined by Cole and Hariharan for which a deterministic O(n log squared m) algorithm is known. For solid patterns against k-F graphs, they achieve O(square root of m times (|E| + N + n log squared m)) time, using an elegant construction called the disentanglement of the graph, which converts the k-F graph into a (2k+1)-D string whose segments encode the edges of the original graph together with a separator symbol.

For solid patterns against GD strings and F graphs, the picture is less settled. The authors show that the classic O(m squared n) algorithm for ED texts, due to earlier work, actually runs in O(mn + N) time on GD texts, because a crucial observation holds there: the cumulative number of occurrences in the pattern of all strings from a single GD segment is bounded by the pattern length. The same improvement carries to F graphs, giving O(mn + N + |E|) time. These bounds are subquadratic only when the average segment width grows with the text size, and the authors explicitly flag it as an open problem whether strongly subquadratic algorithms exist when the average width is constant.

When both pattern and text are variable, the news is largely negative. The authors prove conditional quadratic lower bounds, based on the Orthogonal Vectors Hypothesis, for a sweeping range of combinations: matching a 1-D pattern in a k-D text, a k-D pattern in a 1-D text, and all pairings among 1-D and 1-F structures, all on constant-size alphabets. Strikingly, one of their reductions shows that matching a 2-D pattern in a 2-D text requires quadratic time even when every segment contains strings of length exactly two. The reductions build gadgets that encode each vector of an Orthogonal Vectors instance as a small variable string, arranged so that a pattern match exists precisely when two input vectors are orthogonal. A subquadratic matcher would therefore yield a subquadratic algorithm for Orthogonal Vectors, contradicting the hypothesis, which is itself implied by the Strong Exponential Time Hypothesis.

These lower bounds propagate along the taxonomy. Since a 1-D pattern is a special case of k-D, GD and ED patterns, and a 1-F graph is a special case of k-F, F and EF graphs, the hardness results extend to broad families of combinations, covering essentially every pairing where at least one of the pattern or text is a graph or a general degenerate string. The reductions underlying the k-D results require the segment width to grow faster than logarithmically in the text length, so the authors carefully note that subquadratic algorithms for logarithmic-width segments remain possible; but the 2-D versus 2-D result closes that escape route even for width two.

Perhaps the most technically refined contribution concerns solid patterns against ED texts. A quadratic conditional lower bound for the general case was already known, but the authors strengthen it dramatically: the lower bound holds even for ED strings whose local elasticity is one, meaning the strings within any single segment differ in length by at most one, and whose strings are at most four characters long, on a constant-size alphabet. The construction uses a three-level universal gadget, with upper, middle and lower levels, in which a pattern gadget can thread in exactly three disjoint ways, and a per-vector gadget obtained by pruning the middle level so that it accepts only strings encoding vectors orthogonal to a given vector. This pushes the hardness result as close to GD strings as the definitions allow, since local elasticity zero would collapse the structure to a GD string, where matching is faster.

The work, an extended version of a conference paper presented at WABI 2024, thus paints a nearly complete complexity landscape: for almost every combination of pattern and text types, matching is either truly subquadratic or conditionally requires quadratic time. The remaining gaps are the solid-pattern-versus-GD and solid-pattern-versus-F cases, where the known algorithms are quadratic in the worst case but no lower bound is known, along with the logarithmic-width questions and the possibility of a binary-alphabet lower bound for ED texts with constant local elasticity. For practitioners building pangenomic analysis tools, the message is concrete: the choice between ED strings and EF graphs, and between degenerate and elastic representations, is not merely expressive but computational, and the paper’s tables now tell algorithm designers exactly where fast matching is possible and where it is provably out of reach.

Subject of Research: Algorithmic complexity of pattern matching on pangenome string and graph representations

Article Title: Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs

Article References: Ascone, R., Bernardini, G., Conte, A., Equi, M., Gabory, E., Grossi, R., & Pisanti, N. (2026). Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs. Algorithms for Molecular Biology, 21(1), Article 8. https://doi.org/10.1186/s13015-025-00289-3

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00289-3

Keywords: pangenomics, pattern matching, elastic-degenerate strings, elastic-founder graphs, conditional lower bounds, Strong Exponential Time Hypothesis, Orthogonal Vectors Hypothesis, subquadratic algorithms, computational complexity, suffix trees, indeterminate strings, Algorithms for Molecular Biology