Garance Gourdel
email: garance.gourdel@ens-paris-saclay.fr

Tomasz Kociumaka
email: kociumaka@mimuw.edu.pl

Jakub Radoszewski

Tatiana Starikovskaya
email: tat.starikovskaya@gmail.com

Approximating Longest Common Substring with k mismatches: Theory and Practice

Keywords: 2012 ACM Subject Classification Theory of computation → Pattern matching approximation algorithms, string similarity, LSH, conditional lower bounds Digital Object Identifier 10.4230/LIPIcs.CPM.2020.16

In the problem of the longest common substring with k mismatches we are given two strings X, Y and must find the maximal length such that there is a length-substring of X and a lengthsubstring of Y that differ in at most k positions. The length can be used as a robust measure of similarity between X, Y . In this work, we develop new approximation algorithms for computing that are significantly more efficient that previously known solutions from the theoretical point of view. Our approach is simple and practical, which we confirm via an experimental evaluation, and is probably close to optimal as we demonstrate via a conditional lower bound.

Introduction

For decades, the edit distance and its variants remained the most relevant measure of similarity between biological sequences. However, there is strong evidence that the edit distance cannot be computed in strongly subquadratic time [START_REF] Backurs | Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)[END_REF]. One possible approach to overcoming the quadratic time barrier is computing the edit distance approximately, and last year in the breakthrough paper Chakraborty et al. [START_REF] Chakraborty | Approximating edit distance within constant factor in truly sub-quadratic time[END_REF] showed a constant-factor approximation algorithm that computes the edit distance between two strings of length n in time Õ(n 2-2/7 ). Nevertheless, the algorithm is highly non-trivial and because of that is likely to be impractical.

16:2 Approximating Longest Common Substring with k Mismatches

A different approach is to consider alignment-free measures of similarities. Ideally, we want the measure to be robust and simple enough so that we could compute it efficiently. One candidate for such a measure is the length of the longest common substring with k mismatches. Formally, given two strings X, Y of lengths at most n and an integer k, we want to find the maximal length LCS k (X, Y ) of a substring of X that occurs in Y with at most k mismatches. Computing this value constitutes the LCS with k Mismatches problem.

The LCS with k Mismatches problem was first considered for k = 1 [START_REF] Babenko | Computing the longest common substring with one mismatch[END_REF][START_REF] Flouri | Longest common substrings with k mismatches[END_REF], with current best algorithm taking O(n log n) time and O(n) space. The first algorithm for the general value of k was shown by Flouri et al. [START_REF] Flouri | Longest common substrings with k mismatches[END_REF]. Their simple approach used quadratic time and linear space. Grabowski [START_REF] Grabowski | A note on the longest common substring with k-mismatches problem[END_REF] focused on a data-dependent approach, namely, he showed two linear-space algorithms with running times O(n((k + 1)(LCS + 1)) k ) and O(n 2 k/LCS k ), where LCS is the length of the longest common substring of X and Y and LCS k , similarly to above, is the length of the longest common substring with k mismatches of X and Y . Abboud et al. [START_REF] Abboud | More applications of the polynomial method to algorithm design[END_REF] showed a k 1.5 n 2 /2 Ω( √ (log n)/k) -time randomised solution to the problem via the polynomial method. Thankachan et al. [START_REF] Sharma | A provably efficient algorithm for the k-mismatch average common substring problem[END_REF] presented an O(n log k n)-time, O(n)-space solution for constant k. This approach was recently extended by Charalampopoulos et al. [START_REF] Charalampopoulos | Linear-time algorithm for long LCF with k mismatches[END_REF] to develop an O(n)-time and O(n)-space algorithm for the case of LCS k = Ω(log 2k+2 n).

On the other hand, Kociumaka, Radoszewski, and Starikovskaya [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF] showed that there is k = Θ(log n) such that the LCS with k Mismatches problem cannot be solved in strongly subquadratic time, even for the binary alphabet, unless the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi, and Zane [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] is false. This conditional lower bound implies that there is little hope to improve existing solutions to LCS with k Mismatches. To overcome this barrier, they introduced an approximation approach to LCS with k Mismatches, inspired by the work of Andoni and Indyk [START_REF] Andoni | Efficient algorithms for substring near neighbor problem[END_REF].

Problem 1 (LCS with Approximately k Mismatches). Two strings X, Y of length at most n, an integer k, and a constant ε > 0 are given. Return a substring of X of length at least LCS k (X, Y ) that occurs in Y with at most (1 + ε) • k mismatches. Kociumaka,Radoszewski,and Starikovskaya [19] also showed that for any ε ∈ (0, 2) the LCS with Approximately k Mismatches problem can be solved in O(n 1+1/(1+ε) log 2 n) time and O(n 1+1/(1+ε) ) space. Besides for superlinear space, their solution uses a very complex class of hash functions which requires n 4/3+o(1) -time preprocessing, and that is the underlying reason for the bounds on ε. In this work, we significantly improve the complexity of the LCS with Approximately k Mismatches problem and show the following results. Theorem 2. Let ε > 0 be an arbitrary constant. The LCS with Approximately k Mismatches problem can be solved correctly with high probability: 1) In O(n 1+1/(1+2ε)+o (1) ) time and O(n 1+1/(1+2ε)+o (1) ) space assuming a constant-size alphabet; 2) In O(n 1+1/(1+ε) log 3 n) time and O(n) space for alphabets of arbitrary size.

Our first solution uses the Approximate Nearest Neighbour data structure [5] as a black box. The definition of this data structure is extremely involved, and we view this result as more of a theoretical interest. On the other hand, our second solution is simple and practical, which we confirm by experimental evaluation (see Section 4 for details).

As a final remark, we note that a construction similar to the one used to show a lower bound for the LCS with k Mismatches problem [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF] gives a lower bound for LCS with Approximately k Mismatches. A proof of the following fact can be found in Section 5. Fact 3. Assuming SETH, for every constant δ > 0, there exists a constant ε = ε(δ) 1 such that any randomised algorithm that solves the LCS with Approximately k Mismatches problem for given X and Y of length at most n correctly with constant probability uses Ω(n 2-δ ) time.

Related work.

In 2014, Leimester and Morgenstern [START_REF] Leimeister | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison[END_REF] introduced a related similarity measure, the k-macs distance.

Let LCP k (X i , Y j ) = max{ : d H (X[i, i+ -1], Y [j, j + -1]) ≤ k},
where d H stands for Hamming distance, i.e. the number of mismatches between two strings. We have LCS k = max i,j LCP k (X i , Y j ). The k-macs distance, on the other hand, is defined as a normalised average of these values. Leimeister and Morgenstern [START_REF] Leimeister | kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison[END_REF] showed a heuristic algorithm for computing the k-macs distance, with no theoretical guarantees for the precision of the approximation; other heuristic approaches for computing the k-macs distance include [25,26]. The only algorithm with provable theoretical guarantees is [START_REF] Sharma | A provably efficient algorithm for the k-mismatch average common substring problem[END_REF] and it computes the k-macs distance in O(n log k n) time and O(n) space.

Preliminaries

We assume that the alphabet of the strings X, Y is Σ = {1, . . . , σ}, where σ = n O (1) .

Karp-Rabin fingerprints. The Karp-Rabin fingerprint [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF] of a string S = s 1 s 2 . . . s is defined as

ϕ(S) = i=1 r i-1 s i mod q,
where q = Ω(max{n 5 , σ}) is a prime number, and r ∈ F q is chosen uniformly at random. Obviously, if S 1 = S 2 , then ϕ(S 1 ) = ϕ(S 2 ). Furthermore, for any ≤ n, if the fingerprints of two -length strings S 1 , S 2 are equal, then S 1 , S 2 are equal with probability at least 1 -1/n 4 (for a proof, see e.g. [START_REF] Porat | Exact and approximate pattern matching in the streaming model[END_REF]).

Dimension reduction. We will exploit a computationally efficient variant of the Johnson-Lindenstrauss lemma [START_REF] Johnson | Extensions of Lipschitz mappings into a Hilbert space[END_REF] which describes a low-distortion embedding from a high-dimensional Euclidean space into a low-dimensional one. Let • be the Euclidean (L 2 ) norm of a vector. We will exploit the following claim which follows immediately from [2, Theorem 1.1]:

Lemma 4. Let P be a set of n vectors in R , where ≤ n. Given α = α(n) > 0 and a constant β > 0, there is d = Θ(α -2 log n) and a scalar c > 0 such that the following holds. Let M be a d × matrix filled with i.u.d. ±1 random variables. For all

U ∈ P , define sk α (U ) = c • M U . Then for all U, V ∈ P there is U -V 2 ≤ sk α (U ) -sk α (V ) 2 ≤ (1 + α) U -V 2 with probability at least 1 -n -β .
Since the Hamming distance between binary strings U, V is equal to U -V 2 , the matrix M defines a low-distortion embedding from an -dimensional into a d-dimensional Hamming space as well. For non-binary strings, an extra step is required. Let the alphabet be Σ = {1, 2, . . . , σ} and consider a morphism µ : Σ → {0, 1} σ , where µ(a) = 0 a-1 10 σ-a for all a ∈ Σ. We extend µ to strings in a natural way. Note that for two strings U, V over the alphabet Σ the Hamming distance between µ(U ), µ(V ) is exactly twice the Hamming distance between U, V . We therefore obtain:

1 Here δ is a function of ε for which the explicit form is not known (a condition inherited from [START_REF] Rubinstein | Hardness of approximate nearest neighbor search[END_REF]).

C P M 2 0 2 0 16:4 Approximating Longest Common Substring with k Mismatches Corollary 5. Let P be a set of n strings in Σ , where ≤ n. Given α = α(n) > 0 and a constant β > 0, there is d = Θ(α -2 log n) and a scalar c > 0 such that the following holds. Let M be a d × (σ • ) matrix filled with i.u.d. ±1 random variables. For all U ∈ P , define

sk α (U ) = c • M µ(U ). Then for all U, V ∈ P there is d H (U, V ) ≤ sk α (U ) -sk α (V ) 2 ≤ (1 + α)d H (U, V ) with probability at least 1 -n -β .
We will use the corollary for dimension reduction, and also to design a simple test that checks whether the Hamming distance between two strings is at most k. Corollary 6. Let P be a set of n strings in Σ , where ≤ n. With probability at least 1 -n -β , for all U, V ∈ P :

1) if sk α (U ) -sk α (V ) 2 ≤ (1 + α)k, then d H (U, V ) ≤ (1 + α) • k; 2) if sk α (U ) -sk α (V ) 2 > (1 + α)k, then d H (U, V ) ≥ k.

The Twenty Questions game

Consider the following version of the classic game "Twenty Questions". There are two players: Paul and Carole; Carole thinks of two numbers A, B between 0 and N , and Paul must return some number in [A, B]. He is allowed to ask questions of form "Is x ≤ A?", for any x ∈ [0, N ]. If x ≤ A, Carole must return YES; If A < x ≤ B, she can return anything; and if B < x, she must return NO. Paul must return the answer after having asked at most Q questions where Carole can tell at most ρQ lies, and only in the case when x ≤ A.

We show that Paul has a winning strategy for Q = Θ(log n) and any ρ < 1/3 by a black-box reduction to the result of Dhagat, Gács, and Winkler [START_REF] Dhagat | On playing "Twenty questions" with a liar[END_REF] who showed a winning strategy for A = B. Theorem 7 ([11]). For A = B, Paul has a winning strategy for all ρ < 1 3 asking Q = 8 log N

(1-3ρ) 2 questions. This result is obtained by maintaining a stack of trusted intervals. Once Paul knows that A is between and r, where ≤ r, he checks whether A is in the left or the right half of the interval [ , r]. If no inconsistencies appear (like A < or r < A), he pushes the new interval to the stack, else he removes the interval [ , r] from the stack of trusted intervals. After Q rounds, Paul returns the only number in the top interval in the stack, which is guaranteed to have length 1 and to contain A. We give the pseudocode of Paul's strategy in Algorithm 1. By Carole(x), we denote the answer of Carole for a question "Is x ≤ A?".

Algorithm 1

The Twenty Questions game.

1: Q ← 8 log N (1-3ρ) 2 2: S ← {[0, N ]} 3: for i = 1, 2, . . . , Q/2 do 4: I = [ , r] ← S.top() 5: mid ← +r 2 6: if Carole(mid) then 7: if Carole(r) then S.pop()
The answer is inconsistent with I; remove I.

else S.pop()

The answer is inconsistent with I; remove I.

We now a show a winning strategy for our variant of the game.

16:5

Corollary 8. For A ≤ B, Paul has a winning strategy for all ρ < 1 3 asking Q = 8 log N

(1-3ρ) 2 questions.

Proof. We introduce just one change to Algorithm 1, namely, we return the argument of the largest YES obtained in the course of the algorithm. From the problem statement it follows that the answer is at most B. We shall now prove that the answer is at least A. If Carole ever returned YES for A < x ≤ B, then it is obviously the case. Otherwise, Carole actually behaved as if she had A = B in mind: apart from the small fraction of erroneous answers, she returned YES for x ≤ A, and NO for x > A. Thus, the strategy of Dhagat, Gács, and Winkler ends up with A as the answer (and this must be due to a YES for x = A).

LCS with Approximately k Mismatches

In this section, we prove Theorem 2. Let us first introduce a decision variant of the LCS with Approximately k Mismatches problem.

Problem 9. Two strings X, Y of length at most n, integers k, , and a constant ε > 0 are given. We must return:

1. YES if ≤ LCS k (X, Y ); 2. Anything if LCS k (X, Y ) < ≤ LCS (1+ε)k (X, Y ); 3. NO if LCS (1+ε)k (X, Y ) < .
If we return YES, we must also give a witness pair of length-substrings S 1 and S 2 of X and Y , respectively, such that d

H (S 1 , S 2 ) ≤ (1 + ε)k.
The decision variant of the LCS with Approximately k Mismatches problem can be reduced to the following (c, r)-Approximate Near Neighbour problem. Problem 10. In the (c, r)-Approximate Near Neighbour problem with failure probability f , the aim is, given a set P of n points in R d , to construct a data structure supporting the following queries: given any point q ∈ R d , if there exists p ∈ P such that p -q ≤ r, then return some point p ∈ P such that p -q ≤ cr with probability at least 1 -f .

Using the reduction, we will show our first solution to the LCS with Approximately k Mismatches decision problem based on the result of Andoni and Razenshteyn [5], who showed that for any constant f , there is a data structure for the (c, r)-Approximate Near Neighbour problem that has O(n 1+ρ+o (1) (1) ) query time, and O(d • n 1+ρ+o (1) ) preprocessing time, where ρ = 1/(2c 2 -1).

+ d • n) size, O(d • n ρ+o

Lemma 11. Assume an alphabet of constant size σ. The decision variant of the LCS with

Approximately k Mismatches problem can be solved in space O(n 1+1/(1+2ε)+o (1) ) and time O(n 1+1/(1+2ε)+o (1) ). The answer is correct with constant probability.

Proof. Let P be the set of all length-substrings of X and Q be the set of all lengthsubstrings of Y , all encoded in binary using the morphism µ (see Section 2). We start by applying the dimension reduction procedure of Corollary 5 to P and Q with α = 1/(log log n) Θ (1) and β = 2 to obtain sets P and Q . We can implement the procedure in O(σn log 2 n(log log n) Θ(1) ) = O(n log 2+o(1) n) time by encoding X, Y using µ and running the FFT algorithm [START_REF] Michael | String matching and other products[END_REF] for each of the O(log 1+o(1) n) rows of the matrix and µ(X), µ(Y ).

To solve the decision variant of LCS with Approximately k Mismatches, we build the data structure of Andoni and Razenshteyn [5] for ( (1 + ε)(1 -α), (1 + α)k)-Approximate Near Neighbour over Q . We make a query for each string in P . If, queried for sk α (S 1 ) ∈ P , where S 1 is a length-substring of X, the data structure outputs sk α (S 2 ) ∈ Q , where S 2 is C P M 2 0 2 0 16:6 Approximating Longest Common Substring with k Mismatches a length-substring of Y , then we compute sk α (S 1 ) -sk α (S 2 ) 2 . If it is at most (1 + ε)k, we output YES and the witness pair (S 1 , S 2 ) of substrings. As the length of vectors in P , Q is d = O(log 1+o(1) n), we obtain the desired complexity.

To show that the algorithm is correct, suppose that there are length-substrings S 1 and S 2 of X and Y , respectively, with d H (S 1 , S 2 ) ≤ k. By Corollary 5, sk α (S 1 ), sk α (S 2 ) ≤

(1 + α)k holds with probability at least 1 -1/n. Then, when querying for sk α (S 1 ), with constant probability the data structure will output a string sk α (S 2 ) such that sk α (S 1 ) -

sk α (S 2 ) 2 ≤ (1 + ε)(1 -α 2 )k ≤ (1 + ε)k.
Then, our algorithm will return YES.

On the other hand, if we output YES with a witness pair (S 1 , S 2 ), then sk α (S 1 ) -

sk α (S 2 ) 2 ≤ (1 + ε)k implies d H (S 1 , S 2 ) ≤ (1 + ε)k with high probability by Corollary 5.
While this solution is very fast, it uses quite a lot of space. Furthermore, the data structure of [5] that we use as a black box applies highly non-trivial techniques. To overcome these two disadvantages, we will show a different solution based on a careful implementation of ideas first introduced in [START_REF] Andoni | Efficient algorithms for substring near neighbor problem[END_REF] that showed a data structure for approximate text indexing with mismatches. In [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF], the authors developed these ideas further to show an algorithm that solves the LCS with Approximately k Mismatches problem in O(n 1+1/(1+ε) ) space and O(n 1+1/(1+ε) log 2 n) time for ε ∈ (0, 2) with constant error probability. In this work, we significantly improve and simplify the approach to show the following result: Proof of Theorem 2. We will rely on the modified version of the Twenty Questions game that we described in Section 2.1. In our case, A = LCS k (X, Y ) and B = LCS (1+ε)k (X, Y ). For Carole, we use either the algorithm of Lemma 11, or the algorithm of Theorem 12, with an additional procedure verifying the witness pair (S 1 , S 2 ) character by character to check that it indeed satisfies d H (S 1 , S 2 ) ≤ (1 + ε)k. We output the longest pair of (honest) witness substrings found across all iterations. We will return a correct answer assuming that the fraction of errors is ρ < 1 3 . Recall that the algorithm solves the decision variant of the LCS with Approximately k Mismatches problem incorrectly with probability not exceeding a constant δ, and we can ensure δ < 1 3 by repeating it a constant number of times. It means that Carole can answer an individual question erroneously with probability less than 1 3 . Therefore, for a sufficiently large constant in the number of queries Q = Θ(log n), the fraction of erroneous answers is ρ < 1 3 with high probability by Chernoff-Hoeffding bounds. The claim of the theorem follows immediately from Lemma 11 and Theorem 12.

Proof of Theorem 12

We first give an algorithm for the decision version of the LCS with Approximately k Mismatches problem that uses O(n log n) space and O(n 1+1/(1+ε) log n + σn log 2 n) time, and then we improve the space and time complexity.

We assume to have fixed a Karp-Rabin fingerprinting function ϕ for a prime q = Ω(max{n 5 , σ}) and an integer r ∈ Z q . With error probability inverse polynomial in n, we can find such q in O(log O(1) n) time; see [START_REF] Tao | Deterministic methods to find primes[END_REF][START_REF] Agrawal | PRIMES is in P[END_REF].

Let Π be the set of all projections of strings of length onto a single position, i.e., the value π i (S) of the i-th projection on a string S of length is simply its i-th character S[i]. More generally, for a length-string S and a function h = (π a1 , . . . , π am ) ∈ Π m , we define

h(S) as S[a 1 ]S[a 2 ] • • • S[a m ]. Let p 1 = 1 -k/ and p 2 = 1 -(1 + ε)k/ . We assume that (1 + ε)k < in order to guarantee p 1 > p 2 > 0; the problem is trivial if (1 + ε)k ≥ . Further, let m = log p2 1 n .
We choose a set H of L = Θ(n 1/(1+ε) ) hash functions in Π m uniformly at random. Let C H be the mutliset of all collisions of length-substrings of X and Y under the functions from

H, i.e. C H = {(X[i, i + -1], Y [j, j + -1], h) : ϕ(h(X[i, i + -1])) = ϕ(h(Y [j, j + -1])), 1 ≤ i ≤ |X| -, 1 ≤ j ≤ |Y | -}.
We will perform two tests. The first test chooses an arbitrary subset

C ⊆ C H of size |C | = min{4nL, |C H |} and, for each collision (S 1 , S 2 , h) ∈ C , computes sk ε (S 1 )-sk ε (S 2 ) 2 .
If this value is at most (1 + ε)k, then the algorithm returns YES and the pair (S 1 , S 2 ) as a witness. The second test chooses a collision (S 1 , S 2 , h) ∈ C H uniformly at random and computes the Hamming distance between S 1 and S 2 character by character in O( ) = O(n) time. If the Hamming distance is at most (1 + ε)k, the algorithm returns YES and the witness pair (S 1 , S 2 ). Otherwise, the algorithm returns NO. See Algorithm 2.

Algorithm 2 LCS with Approximately k Mismatches (decision variant).

1: Choose a set H of L functions from Π m uniformly at random

2: C H = {(S 1 , S 2 , h) : S 1 , S 2 -length-substrings of X, Y resp. and ϕ(h(S 1 )) = ϕ(h(S 2 ))} 3: Choose an arbitrary subset C ⊆ C H of size min{4nL, |C H |} 4: Compute sk ε (•) sketches for all length-substrings of X, Y 5: for (S 1 , S 2 , h) ∈ C do 6: if sk ε (S 1 ) -sk ε (S 2 ) 2 ≤ (1 + ε)k then return (YES, (S 1 , S 2 )) 7: Draw a collision (S 1 , S 2 , h) ∈ C H uniformly at random 8: if d H (S 1 , S 2 ) ≤ (1 + ε)k then return (YES, (S 1 , S 2 )) 9: return NO
We must explain how we compute C H and choose the collisions that we test. We consider each hash function h ∈ H in turn. Let h = (π a1 , . . . , π am ). Recall that for a string S of length we define h(S) as

S[a 1 ]S[a 2 ] • • • S[a m ]. Consequently, ϕ(h(S)) = ( m i=1 r i-1 S[a i ]) mod q.
We create a vector U of length where each entry is initialised with 0. For each i, we add r i-1 mod q to the a i -th entry of U . Finally, we run the FFT algorithm [START_REF] Michael | String matching and other products[END_REF] for U and X, Y in the field Z q , and sort the resulting values. We obtain a list of sorted values that we can use to generate the collisions. Namely, consider some fixed value z. Assume that there are x substrings of X and y substrings of Y of length such that the fingerprint of their projection is equal to z. The value z then gives xy collisions, and we can generate each one of them in constant time. This explains how to choose the subset C in O(nL log n) time.

To draw a collision from C H uniformly at random, we could simply compute the total number of collisions across all functions h ∈ H, draw a number in [1, |C H |], and generate the corresponding collision. However, this would require to generate the collisions twice. Instead, we use the weighted reservoir sampling algorithm [START_REF] Chao | A general purpose unequal probability sampling plan[END_REF]. We divide all collisions into subsets according to the values of fingerprints. We assume that the weighted reservoir sampling algorithm receives the fingerprint values one-by-one, as well as the number of corresponding collisions. At all times, the algorithm maintains a "reservoir" containing one fingerprint value and a random collision corresponding to this value. When a new value z with xy collisions arrives, the algorithm replaces the value in the reservoir with z and a random collision with none of the existing algorithms has been implemented. We implemented the solution to LCS with k Mismatches by Flouri et al., which we refer to as FGKU [START_REF] Flouri | Longest common substrings with k mismatches[END_REF]. (The other algorithms seem too complex to be efficient in practice.) The main idea of the algorithm of Flouri et al. is that if we know that the longest common substring with k mismatches is obtained by a substring of X that starts at a position p and a substring of Y that starts at a position p + i, then we can find it by scanning X and Y [i, |Y |] in linear time.

Details of implementation.

We made several adjustments to the theoretical algorithm we described. First, we use the fact that A = LCS(X, Y ) + k ≤ LCS k (X, Y ) ≤ B = (k + 1) • LCS(X, Y ) + k to bound the interval in the Twenty Questions game. We also treated the number of questions in the Twenty Questions game and L, the size of the set of hash functions H, as parameters that trade time for accuracy, and put the number of questions to 2 log(B -A) in the Twenty Questions game and L = n 1/(1+ε) /16. In Line 6 of Algorithm 2, we used sketches to estimate the Hamming distance. In practice, we computed the Hamming distance via character-by-character comparison when is small compared to k and via kangaroo jumps [START_REF] Galil | Improved string matching with k mismatches[END_REF] otherwise. Also, when ≤ 2 log n in Algorithm 2, we computed the hash values of the length-substrings of S 1 and S 2 naively, instead of using the FFT algorithm [START_REF] Michael | String matching and other products[END_REF].

Data sets and results. We considered k ∈ {10, 25, 50} and ε ∈ {1.0, 1.25, 1.5, 1.75, 2.0}. We tested the algorithms on pairs of random strings (each character is selected independently and uniformly from a four-character alphabet {A, T, G, C}) and on pairs of strings extracted at random from the E. coli genome. The lengths of the strings in each pair are equal and vary from 0 to 60000 with a step of 5000. All timings reported are averaged over ten runs. Figures 123show the results for k = 10, 25, 50. We note that for ε = 1 and k = 10, 25, the standard deviation of the running time on the E. coli data set is quite large, which is probably caused by our choice of the method to compute the Hamming distance between substrings, but for all other parameter combinations it is within the standard range. We can see that the time decreases when ε grows, which is coherent with the theoretical complexity.

As for the accuracy, note that our algorithm cannot return a pair of strings at Hamming distance more than (1 + ε)k, and so the only risk is returning strings which are too short. Consequently, we measured the accuracy of our implementation by the ratio of the length ) 2 , we will have at least one more mismatch from the alignment of the copy of H in Y and the copies of H in X that surround U i . Therefore, in total there are at least d + 1 > k mismatches, a contradiction. To conclude, both cases are impossible, and hence s = 0. The lemma follows as explained above.

With this lemma, we can now proceed to prove Fact 3. Define ε = γ/3 and consider all k = 1, (1 + ε), (1 + ε) 2 , (1 + ε) 3 , . . . until d/(1 + ε). For each k, we run log log n independent instances of an algorithm for LCS with Approximately k Mismatches. Let k 0 be the smallest k such that the identified longest common substring with approximately k mismatches has length at least 2(d + 1) 2 + d.

By the definition of k 0 , Observation 19 and Lemma 20, there do not exist i, j ∈ [1, N ] such that d H (U i , V j ) ≤ k 0 /(1 + ε), but there exist i, j ∈ [1, N ] such that d H (U i , V j ) ≤ k 0 (1 + ε). In the (1 + γ)-approximate Bichromatic Closest Pair problem, this translates to k 0 /(1 + ε) < h ≤ k 0 (1 + ε), where h is the minimal distance between all pairs U i , V j . This is equivalent to

h ≤ k 0 (1 + ε) < h(1 + ε) 2 = h(1 + 2 3 γ + 1 9 γ 2 ) ≤ h(1 + γ),
which means that the pair (U i , V j ) found by the algorithm for k 0 is a valid solution for

Theorem 12 .

 12 Assume an alphabet of arbitrary size σ = n O(1) . The decision variant of LCS with Approximately k Mismatches can be solved in O(n 1+1/(1+ε) log 2 n) time and O(n) space. The answer is correct with constant probability. Let us defer the proof of the theorem until Section 3.1 and start by explaining how we use Lemma 11 and Theorem 12 and the Twenty Questions game to show Theorem 2.

( a )

 a Random, k = 10. (b) E. coli, k = 10.

Figure 1 Figure 4

 14 Figure 1 Comparison of the FGKU algorithm versus our algorithm for k = 10 and different values of ε. Large standard deviation for length 60000 is caused by an outlier with very long longest common substring with k mismatches.

( 1 +

 1 γ)-approximate Bichromatic Closest Pair. It follows that, for some k, the algorithm for LCS with Approximately k Mismatches must spend Ω(N 2-δ / log 1+ε log N ) time. We haven = |X| = |Y | = O(d 2 N ) = O(N log 2 N ), which implies N = Ω(n/ log 2 n). Fact 3 follows.

Impagliazzo, Paturi, and Zane [16] stated the hypothesis for deterministic algorithms only, but nowadays it is common to extend SETH to allow randomisation. If we condition on the classic version of the hypothesis, we will obtain a lower bound for deterministic algorithms. See [27] for more discussion.

Sharma V. Thankachan, Sriram P. Chockalingam, Yongchao Liu, Alberto Apostolico, and Srinivas Aluru. ALFRED: A practical method for alignment-free distance computation. Journal of Computational Biology, 23(6):452-460, 2016. doi:10.1089/cmb.2015.0217.

Sharma V. Thankachan, Sriram P. Chockalingam, Yongchao Liu, Ambujam Krishnan, and Srinivas Aluru. A greedy alignment-free distance estimator for phylogenetic inference. BMC Bioinformatics, 18(8):238, June 2017. doi:10.1186/s12859-017-1658-0.

Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In ICM'18, pages 3447-3487, 2018. doi:10.1142/9789813272880_0188.

Funding Tomasz Kociumaka: Supported by ISF grants no. 1278/16 and 1926/19, a BSF grant no. 2018364, and an ERC grant MPM (no. 683064) under the EU's Horizon 2020 Research and Innovation Programme. Jakub Radoszewski: Supported by the Polish National Science Center, grant number 2018/31/D/ST6/ 03991.

To ensure the reproducibility of our results, our complete experimental setup, including data files, is available at https://github.com/fnareoh/LCS_Approx_k_mis.

Approximating Longest Common Substring with k Mismatches some probability. Note that to select a random collision it suffices to choose a pair from [1, x] × [1, y] uniformly at random. It is guaranteed that if for a value z we have xy collisions, the algorithm will select z with probability xy/|C H |. Consequently, after processing all values, the reservoir will contain a collision chosen from C H uniformly at random. Lemma 14. Let S 1 and S 2 be two length-substrings of X and Y , respectively, with

) is large enough, then, with probability at least 3/4, there exists a function h ∈ H such that h(S 1 ) = h(S 2 ).

Proof. Consider a function h = (π a1 , . . . , π am ) drawn from Π m uniformly at random. The probability of h(S 1 ) = h(S 2 ) is at least p m 1 . Due to p 1 ≤ 1, we have

Moreover,

Hence, we can choose the constant in L = |H| so that the claim of the lemma holds.

Proof. Consider length-substrings S 1 , S

In total, we have n 2 |H| possible triples (S 1 , S 2 , h) so by linearity of expectation, we conclude that the expected number of such triples is at most 2 n n 2 L = 2nL. Therefore the probability to hit a triple (S 1 , S 2 , h)

Below, we combine the previous results to prove that, with constant probability, Algorithm 2 correctly solves the decision variant of the LCS with Approximately k Mismatches problem. Note that we can reduce the error probability to an arbitrarily small constant δ > 0: it suffices to repeat the algorithm a constant number of times.

Corollary 16. With non-zero constant probability, Algorithm 2 solves the decision variant of LCS with Approximately k Mismatches correctly.

Proof. Suppose first that ≤ LCS k (X, Y ), which means that there are two length-substrings S 1 , S 2 of X, Y such that d H (S 1 , S 2 ) ≤ k. By Lemma 14, with probability at least 3/4, there exists a function h ∈ H such that h(S 1 ) = h(S 2 ). In other words, (S 1 , S 2 , h) ∈ C H with probability at least 3 4 . If |C H | < 4nL, we will find this triple and it will pass the test with probability at least 1 -n -6 . If |C H | ≥ 4nL, then by Lemma 15 the Hamming distance between S 1 , S 2 , where (S 1 , S 2 , h) was drawn from C H uniformly at random, is at most (1 + ε)k with probability ≥ 1/2, and therefore this pair will pass the test with probability ≥ 1/2. It follows that in this case the algorithm outputs YES with constant probability.

Suppose now that > LCS (1+ε)k (X, Y ). In this case, the Hamming distance between any pair of length-substrings of X and Y is at least (1 + ε)k, so none of them will ever pass the second test and none of them will pass the first test with constant probability.

We now improve the space of the algorithm to linear. Note that the only reason why we needed O(n log n) space is that we precompute and store the sketches for the Hamming distance. Below we explain how to overcome this technicality.

First, we do not precompute the sketches. Second, we process the collisions in C in batches of size n. Consider one of the batches, B. For each collision (S 1 , S 2 , h) ∈ B we must compute sk ε (S 1 ) -sk ε (S 2 ) 2 . We initialize a counter for every collision, setting it to zero initially. The number of rounds in the algorithm will be equal to the length of the sketches, and, in round i, the counter for a collision (S 1 , S 2 , h) ∈ B will contain the squared L 2 distance between the length-i prefixes of sk ε (S 1 ) and sk ε (S 2 ). In more detail, let S be the set of all substrings of X, Y that participate in the collisions in B. Recall that all these substrings have length . At round i, we compute the i-th coordinate of the sketches of the substrings in S. By definition, the i-th coordinate is the dot product of the i-th row of c • M , where c and M are as in Corollary 5, and a substring encoded using µ. Hence, we can compute the coordinate using the FFT algorithm [START_REF] Michael | String matching and other products[END_REF] in O(σn log n) time and O(n) space. When we have the coordinate i computed, we update the counters for the collisions and repeat.

At any time, the algorithm uses O(n) space. Compared to the time consumption proven in Lemma 13, the algorithm spends an additional O(σn 1+1/(1+ε) log 2 n) time for computing the coordinates of the sketches. Therefore, in total the algorithm uses O(σn 1+1/(1+ε) log 2 n) = O(n 1+1/(1+ε) log 2 n) time and O(n) space. For constant-size alphabets, this completes the proof of Theorem 12. For alphabets of arbitrary size, we replace the sketches from Section 2 with the sketches defined in [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF] to achieve the desired complexity. We note that we could use the sketches [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF] for small-size alphabets as well, but their lengths hide a large constant.

Experiments

We now present results of experimental evaluation of the second solution of Theorem 2.

Methodology and test environment. The baselines and our solution are written in C++11 and compiled with optimizations using gcc 7.4.0. The experimental results were generated on an Intel Xeon E5-2630 CPU using 128 GiB RAM. To ensure the reproducibility of our results, our complete experimental setup, including data files, is available at https: //github.com/fnareoh/LCS_Approx_k_mis.

Baseline. The only other solution to the LCS with Approximately k Mismatches problem was presented in [START_REF] Kociumaka | Longest common substring with approximately k mismatches[END_REF]. However, it has a worse complexity and is likely to be unpractical because it uses a very complex class of hash functions. We therefore chose to compare our algorithm against algorithms for the LCS with k Mismatches problem. To the best of our knowledge,

) by computing LCS k(X, Y ) and LCS k (X, Y ) for 10 pairs of strings for each length from 5000 to 60000 with step of 5000, as well as the error rate, i.e., the percentage of experiments where LCS k(X, Y ) < LCS k (X, Y ) (see Table 1). Not surprisingly, r min and r max grow as k and ε grow, while the error rate drops. Even though there is no theoretical upper bound on r max , the latter is at most 2.24 at all times. We also note that even in the cases when the error rate is non-negligible, LCS k ≥ 0.86 • LCS k ; in other words, our algorithm returns a reasonable approximation of LCS k .

Proof of Fact 3

We now show the lower bound of Fact 3 by a reduction from the (1 + γ)-approximate Bichromatic Closest Pair problem.

Problem 17 ((1 + γ)-approximate Bichromatic Closest Pair). Given a constant γ > 0 and two sets of binary strings (U i ) i∈ [1,N ] and (V j ) j∈ [1,N ] , each of length d = O(log N ), if the smallest Hamming distance between a pair (U i , V j ) i,j∈ [1,N ] is h, we must output (possibly another) pair of binary strings (U i , V j ) with Hamming distance in [h, (1 + γ)h].

Rubinstein [START_REF] Rubinstein | Hardness of approximate nearest neighbor search[END_REF] proved that for every constant δ > 0, there exists γ = γ(δ) such that any randomised algorithm that solves (1 + γ)-approximate Bichromatic Closest Pair correctly with constant probability requires O(N 2-δ ) time assuming SETH: Hypothesis 18 (SETH). For every δ > 0, there exists an integer q such that SAT on q-CNF formulas with m clauses and n variables cannot be solved in m O(1) 2 (1-δ)n time even by a Monte-Carlo randomised algorithm (with error probability bounded by a small constant) 2 .

We show the lower bound by reducing a single instance of (1 + γ)-approximate Bichromatic Closest Pair to a polylogarithmic number of instances of LCS with Approximately k Mismatches. We assume that U i , V j are over the alphabet {0, The substring S 2 contains either HV j or V j H for some j. Without loss of generality, we can assume that S 2 contains a copy of H followed by V j for some j. Let us consider the substring S of X aligned with the copy of H in S 2 . Below we will prove that S = H, and since S is followed by U i for some i, this will imply that d H (HU i H, HV j H) ≤ k.