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

Area of Science:

• Bioinformatics
• Computational Biology
• Stringology

Background:

• Pangenomics involves analyzing complex genomic structures beyond linear sequences.
• Variable strings, such as Elastic Degenerate (ED) strings and Elastic Founder (EF) graphs, are crucial for representing acyclic components of pangenomes.
• Pattern matching is a fundamental operation in pangenomic data analysis, but its complexity with variable strings is not fully understood.

Purpose of the Study:

• To establish a comprehensive taxonomy of variable string types, ranging from simple linear strings to complex ED strings and EF graphs.
• To investigate the time complexity of the MATCH(X,Y) problem, which involves matching patterns of type X into texts of type Y, where X and Y are variable strings.
• To provide non-trivial upper bounds or prove conditional lower bounds for all combinations of pattern and text types within the established taxonomy.

Main Methods:

• Development of a clear classification system for variable strings based on their complexity and structure.
• Systematic analysis of the MATCH(X,Y) problem across all pairs of string types in the taxonomy.
• Derivation of time complexity bounds, including sub-quadratic upper bounds and quadratic conditional lower bounds, referencing existing results.

Main Results:

• A taxonomy categorizing variable strings from linear strings to complex ED strings and EF graphs is established.
• For all pattern (X) and text (Y) combinations, non-trivial time complexity bounds for MATCH(X,Y) are provided.
• Sub-quadratic upper bounds or quadratic conditional lower bounds are determined for pattern matching within the variable string taxonomy.

Conclusions:

• The study provides a foundational understanding of pattern matching complexities within various variable string representations relevant to pangenomics.
• The established bounds offer crucial insights for developing efficient algorithms for pangenomic data analysis.
• This work advances the algorithmic toolkit for handling complex genomic structures represented by variable strings.