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.
翻译:用于模式匹配的标签图形是全基因组学的核心挑战 。 Equi 等人( Agorithmica, 2022 ) 开发了 Elastic 开源器图 ($\ mathsf{EFG}$), 代表了以美元为单位的长度序列, 由字母 $\Sigma$ 和特殊差距字符绘制: 路径将原始序列拼写成或重新组合。 通过执行半不留位的属性, $\mathfsf{EFG} 等 (Algorial- 等) 加入一个用于线性模式匹配的多数字空间指数。 Equiet al. (Algorthm, 2022) 开发了一个线性阵列模式, 打破了刻度图的底线性轨道路径(Equile Grix), 开始简化了线性结构, 显示我们目前总结点标签的线性长度线性框架的长度线性, 发展了线性构造框架, 发展了不固定的基数值 。</s>