Elastic-degenerate string matching with 1 error

DOI10.1007/978-3-031-20624-5_2MaRDI QIDQ6163960zbMATH OpenFDO

Authors Giulia Bernardini, Esteban Gabory, Solon P. Pissis, L. Stougie, Michelle Sweering, Wiktor Zuba

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

approximate string matchingdegenerate stringsedit distanceelastic-degenerate stringsstring algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: An elastic-degenerate string is a sequence of $n$ finite sets of strings of total length $N$, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length $m$ in an ED text. This problem has recently received some attention by the combinatorial pattern matching community, culminating in an $ildemathcalO(n{m}^{omega-1})+mathcalO(N)$-time algorithm [Bernardini et al., SIAM J. Comput. 2022], where $omega$ denotes the matrix multiplication exponent and the $ildemathcalO(cdot)$ notation suppresses polylog factors. In the $k$-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most $k$ errors. $k$-EDSM can be solved in $mathcalO(k^{2}mG+kN)$ time, under edit distance, or $mathcalO(kmG+kN)$ time, under Hamming distance, where $G$ denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, $G$ is only bounded by $N$, and so even for $k=1$, the existing algorithms run in $Omega(mN)$ time in the worst case. In this paper we show that $1$-EDSM can be solved in $mathcalO((n{m}^2+N)logm)$ or $mathcalO(n{m}^3+N)$ time under edit distance. For the decision version, we present a faster $mathcalO(n{m}^{2}sqrtlogm+Nloglogm)$-time algorithm. We also show that $1$-EDSM can be solved in $mathcalO(n{m}^2+Nlogm)$ time under Hamming distance. Our algorithms for edit distance rely on non-trivial reductions from $1$-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or 2d range emptiness), which we show how to solve efficiently. In order to obtain an even faster algorithm for Hamming distance, we rely on employing and adapting the $k$-errata trees for indexing with errors [Cole et al., STOC 2004].

Cites work

• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Algorithms on Strings
• Approximate pattern matching on elastic-degenerate text
• Approximate String Matching: A Simpler Faster Algorithm
• Comparing Degenerate Strings
• Constructing Efficient Dictionaries in Close to Sorting Time
• Degenerate string comparison and applications
• Dictionary matching and indexing with errors and don't cares
• Efficient string matching with k mismatches
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Fast string matching with k differences
• Faster algorithms for string matching with k mismatches
• Faster Online Elastic Degenerate String Matching
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry
• On Indeterminate Strings Matching.
• On-line pattern matching on similar texts
• Orthogonal range searching on the RAM, revisited
• Pattern matching on elastic-degenerate text with errors
• Property Suffix Array with Applications in Indexing Weighted Sequences
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Text Indexing and Dictionary Matching with One Error
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Truncated suffix trees and their application to data compression.

Cited in

(6)

• Approximate pattern matching on elastic-degenerate text
• Elastic-degenerate string matching with 1 error or mismatch
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• Reconstructing general matching graphs
• Elastic-degenerate string comparison
• Faster approximate elastic-degenerate string matching. Part A

This page was built for publication: Elastic-degenerate string matching with 1 error

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163960)