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].
Ascone, Rocco, Bernardini, Giulia, Conte, Alessio et al. Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs. // Algorithms for Molecular Biology. – 2026. – DOI: 10.1186/s13015-025-00289-3. – URL: https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00289-3
Ascone, Rocco, Bernardini, Giulia, Conte, Alessio, Equi, Massimo, Gabory, Esteban, Grossi, Roberto, Pisanti, & Nadia (2026). Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs. Algorithms for Molecular Biology. https://doi.org/10.1186/s13015-025-00289-3
Ascone, et al. “Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs.” Algorithms for Molecular Biology, 2026. doi:10.1186/s13015-025-00289-3.
@article{Ascone2026,
title = {Pattern matching with Elastic-Degenerate strings and Elastic-Founder graphs},
author = {Ascone and Rocco and Bernardini and Giulia and Conte and Alessio and Equi and Massimo and Gabory and Esteban and Grossi and Roberto and Pisanti and Nadia},
journal = {Algorithms for Molecular Biology},
year = {2026},
doi = {10.1186/s13015-025-00289-3},
url = {https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00289-3}
}
Background Aquaculture production of Atlantic salmon is a rapidly growing food sector, offering numerous advantages over terrestrial livestock. However, infectious diseases remain a major constraint, reducing production efficiency and...
The eukaryotic genome is folded into a functionally consequential three-dimensional architecture whose organizing principles have recently attracted substantial interest. Two physical mechanisms dominate current thinking: active loop...
Background The mitochondrial and nuclear genomes must coevolve to ensure cell homeostasis, legacy and consequence of their endosymbiotic origin. Mitonuclear coevolution is central to the oxidative phosphorylation pathway (OXPHOS), where...
Background Intrinsically disordered regions (IDRs) are widespread in proteins and play essential roles in regulation, signaling, and molecular recognition. IDRs of different lengths often exhibit distinct sequence and functional...