Elastic founder graphs improved and enhanced

DOI10.1016/J.TCS.2023.114269arXiv2303.05336MaRDI QIDQ6199393

Nicola Rizzo, Veli Mäkinen, Tuukka Norri, Massimo Equi

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Indexing labeled graphs for pattern matching is a central challenge of pangenomics. Equi et al. (Algorithmica, 2022) developed the Elastic Founder Graph ($mathsf{EFG}$) representing an alignment of $m$ sequences of length $n$, drawn from alphabet $Sigma$ plus the special gap character: the paths spell the original sequences or their recombination. By enforcing the semi-repeat-free property, the $mathsf{EFG}$ admits a polynomial-space index for linear-time pattern matching, breaking through the conditional lower bounds on indexing labeled graphs (Equi et al., SOFSEM 2021). In this work we improve the space of the $mathsf{EFG}$ index answering pattern matching queries in linear time, from linear in the length of all strings spelled by three consecutive node labels, to linear in the size of the edge labels. Then, we develop linear-time construction algorithms optimizing for different metrics: we improve the existing linearithmic construction algorithms to $O(mn)$, by solving the novel exclusive ancestor set problem on trees; we propose, for the simplified gapless setting, an $O(mn)$-time solution minimizing the maximum block height, that we generalize by substituting block height with prefix-aware height. Finally, to show the versatility of the framework, we develop a BWT-based $mathsf{EFG}$ index and study how to encode and perform document listing queries on a set of paths of the graphs, reporting which paths present a given pattern as a substring. We propose the $mathsf{EFG}$ framework as an improved and enhanced version of the framework for the gapless setting, along with construction methods that are valid in any setting concerned with the segmentation of aligned sequences.

Full work available at URL: https://arxiv.org/abs/2303.05336

zbMATH Keywords

multiple sequence alignmentpattern matchingsegmentation algorithmsuffix treedocument listing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Linear bidirectional on-line construction of affix trees
• On-line construction of suffix trees
• Linear time construction of indexable elastic founder graphs
• The affix array data structure and its applications to RNA secondary structure analysis
• Suffix Arrays: A New Method for On-Line String Searches
• Algorithms on Strings, Trees and Sequences
• Sparse Dynamic Programming on DAGs with Small Width
• Linear-time String Indexing and Analysis in Small Space
• Comparing Degenerate Strings
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Algorithms and complexity on indexing founder graphs
• Tailoring r-index for Document Listing Towards Metagenomics Applications
• Linear time construction of indexable founder block graphs

This page was built for publication: Elastic founder graphs improved and enhanced