Elastic-Degenerate String Matching with 1 Error or Mismatch

Abstract An elastic-degenerate (ED) 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. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an $$\mathcal {\tilde{O}}(nm^{\omega -1})+\mathcal {O}(N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>m</mml:mi> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> denotes the matrix multiplication exponent and the $$\mathcal {\tilde{O}}(\cdot )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>·</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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 $$\mathcal {O}(k^2mG+kN)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>m</mml:mi> <mml:mi>G</mml:mi> <mml:mo>+</mml:mo> <mml:mi>k</mml:mi> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time, under edit distance, or $$\mathcal {O}(kmG+kN)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mi>m</mml:mi> <mml:mi>G</mml:mi> <mml:mo>+</mml:mo> <mml:mi>k</mml:mi> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , the existing algorithms run in $$\varOmega (mN)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time in the worst case. In this paper we make progress in this direction. We show that 1-EDSM can be solved in $$\mathcal {O}((nm^2 + N)\log m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> or $$\mathcal {O}(nm^3 + N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time under edit distance. For the decision version of the problem, we present a faster $$\mathcal {O}(nm^2\sqrt{\log m} + N\log \log m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>+</mml:mo> <mml:mi>N</mml:mi> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -time algorithm. We also show that 1-EDSM can be solved in $$\mathcal {O}(nm^2 + N\log m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>N</mml:mi> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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]. This is an extended version of a paper presented at LATIN 2022.