Giulia Bernardini

Nadia Pisanti

Solon P Pissis

Giovanna Rosone

Pattern Matching on Elastic-Degenerate Text with Errors

Keywords: uncertain strings, elastic-degenerate strings, degenerate strings, pan-genome, pattern matching

An elastic-degenerate string is a sequence of n sets of strings of total length N . It has been introduced to represent a multiple alignment of several closely-related sequences (e.g. pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists an O(nm 2 + N )-time algorithm to solve this problem on-line after a pre-processing stage with time and space O(m). In this paper, we study the same problem under the edit distance model and present an O(k 2 mG + kN )-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG + kN )-time and O(m)-space algorithm for Hamming distance.

Introduction

There is a growing interest in the notion of pan-genome [START_REF]The Computational Pan-Genomics Consortium: Computational pan-genomics: status, promises and challenges[END_REF]. In the last ten years, with faster and cheaper sequencing technologies, re-sequencing (that is, sequencing the genome of yet another individual of a species) became more and more a common task in modern genome analysis workflows. By now, a huge amount of genomic variations within the same population has been detected (e.g. in humans for medical applications, but not only), and this is only the beginning. With this, new challenges of functional annotation and comparative analysis have been raised. Traditionally, a single annotated reference genome is used as a control sequence. The reference genome is a representative example of the genomic sequence of a species. It serves as a reference text to which, for example, fragments of newly sequenced genomes of individuals are mapped. Although a single reference genome provides a good approximation of any individual genome, in loci with polymorphic variations, mapping and comparisons easily fail their purposes. This is where a multiple genome, i.e. a pan-genome, would be a better reference text [START_REF] Huang | Short read alignment with populations of genomes[END_REF].

In the literature, many different (compressed) representations and thus algorithms have been considered for pattern matching on a set of similar texts [START_REF] Bille | Random access to grammar-compressed strings[END_REF][START_REF] Gagie | Faster approximate pattern matching in compressed repetitive texts[END_REF][START_REF] Navarro | Indexing highly repetitive collections[END_REF][START_REF] Wandelt | String searching in referentially compressed genomes[END_REF][START_REF] Gagie | Searching and indexing genomic databases via kernelization[END_REF][START_REF] Barton | On-line pattern matching on uncertain sequences and applications[END_REF][START_REF] Kociumaka | Pattern Matching and Consensus Problems on Weighted Sequences and Profiles[END_REF]. A natural representation of pan-genomes, or fragments of them, that we consider here are elastic-degenerate texts [START_REF] Iliopoulos | Efficient pattern matching in elasticdegenerate texts[END_REF]. An elastic-degenerate text is a sequence which compactly represents a multiple alignment of several closely-related sequences. In this representation, substrings that match exactly are collapsed, while in positions where the sequences differ (by means of substitutions, insertions, and deletions of substrings), all possible variants observed at that location are listed. Elastic-degenerate texts correspond to the Variant Call Format (VCF), that is, the standard for storing gene sequence variations [START_REF]The 1000 Genomes Project Consortium: A global reference for human genetic variation[END_REF].

Consider, for example, the following multiple sequence alignment of three closely-related sequences: GAAAGTGAGCA GAGACAAA-CA G--A-ACAGCA These sequences can be compacted into the single elastic-degenerate string:

T = {G} •      AA AG ε      • {A} •      GTG CAA AC      • {A} • G ε • {CA}.
The total number of segments is the length of T and the total number of letters is the size of T . The natural problem that arises is finding all matches of a deterministic pattern P in text T . We call this the Elastic-Degenerate String Matching (EDSM) problem. The simplest version of this problem assumes that a degenerate (sometimes called indeterminate) segment can contain only single letters [START_REF] Holub | Fast pattern-matching on indeterminate strings[END_REF]. Due to the application of cataloguing human genetic variation [START_REF]The 1000 Genomes Project Consortium: A global reference for human genetic variation[END_REF], there has been ample work in the literature on the off-line (indexing) version of the pattern matching problem [START_REF] Huang | Short read alignment with populations of genomes[END_REF][START_REF] Rahn | Journaled string tree -a scalable data structure for analyzing thousands of similar genomes on your laptop[END_REF][START_REF] Maciuca | A natural encoding of genetic variation in a Burrows-Wheeler transform to enable mapping and genome inference[END_REF][START_REF] Sirén | Indexing variation graphs[END_REF][START_REF] Na | FM-index of alignment: A compressed index for similar strings[END_REF]. The on-line, more fundamental, version of the EDSM problem has not been studied as much as indexing approaches. Solutions to the on-line version can be beneficial for a number of reasons: (a) efficient on-line solutions can be used in combination with partial indexes as practical trade-offs; (b) efficient on-line solutions for exact pattern matching can be applied for fast average-case approximate pattern matching similar to standard strings [START_REF] Baeza-Yates | Fast and practical approximate string matching[END_REF]; (c) on-line solutions can be useful when one wants to search for a few patterns in many degenerate texts similar to standard strings [START_REF] Altschul | Basic local alignment search tool[END_REF].

Previous Results. Let us denote by m the length of pattern P , by n the length of T , and by N > m the size of T . A few results exist on the (exact) EDSM problem. In [START_REF] Iliopoulos | Efficient pattern matching in elasticdegenerate texts[END_REF], an algorithm for solving the EDSM problem in time O(αγmn + N ) and space O(N ) was presented; where α and γ are parameters, respectively representing the maximum number of strings in any degenerate segment of the text and the maximum number of degenerate segments spanned by any occurrence of the pattern in the text. In [START_REF] Grossi | On-Line Pattern Matching on Similar Texts[END_REF], two new algorithms to solve the same problem in an on-line manner 1 were presented: the first one requires time O(nm 2 + N ) after a pre-processing stage with time and space O(m); the second requires time O(N • m w ) after a pre-processing stage with time and space O(m • m w ), where w is the size of the computer word in the RAM model. Our Contribution. Since genomic sequences are endowed with polymorphisms and sequencing errors, the existence of an exact match can result into a strong assumption. The aim of this work is to generalize the studies of [START_REF] Iliopoulos | Efficient pattern matching in elasticdegenerate texts[END_REF] and [START_REF] Grossi | On-Line Pattern Matching on Similar Texts[END_REF] for the exact case, allowing some approximation in the occurrences of the input pattern. We suggest a simple on-line O(kmG + kN )-time and O(m)-space algorithm, G being the total number of strings in T and k > 0 the maximum number of allowed substitutions in a pattern's occurrence, that is nonzero Hamming distance. Our main contribution is an on-line O(k 2 mG + kN )-time and O(m)-space algorithm where the type of edit operations allowed is extended to insertions and deletions as well, that is nonzero edit distance. These results are good in the sense that for small values of k the algorithms incur (essentially) no increase in time complexity with respect to the O(nm 2 +N )-time and O(m)-space algorithm presented in [START_REF] Grossi | On-Line Pattern Matching on Similar Texts[END_REF].

Structure of the Paper. Section 2 provides some preliminary definitions and facts as well as the formal statements of the problems we address. Section 3 describes our solution under the edit distance model, while Section 4 describes the algorithm under the Hamming distance model.

Preliminaries

An alphabet Σ is a non-empty finite set of letters of size |Σ|. We consider the case of a constant-sized alphabet, i.e. |Σ| = O(1). A string S on an alphabet Σ is a sequence of elements of Σ. The set of all strings on an alphabet Σ, including the empty string ε of length 0, is denoted by Σ * . For any string S, we denote by S[i . . . j] the substring of S that starts at position i and ends at position j. In particular, S[0 . . . j] is the prefix of S that ends at position j, and S[i . . . |S| -1] is the suffix of S that begins at position i, where |S| denotes the length of S.

Definition 1 ([7]

). An elastic-degenerate (ED) string T = T [0] T [START_REF] Altschul | Basic local alignment search tool[END_REF] . . . T [n -1] of length n on alphabet Σ, is a finite sequence of n degenerate letters. Every degenerate letter T [i] is a finite non-empty set of strings

T [i][j] ∈ Σ * , with 0 ≤ j < | T [i]|. The size N of T is defined as N = n-1 i=0 | T [i]|-1 j=0 | T [i][j]|
assuming (for representation purposes only) that |ε|=1. 1 On-line refers to the fact that the algorithm reads the elastic-degenerate text set-by-set in a serial manner.

Definition 2. The total number of strings in T is defined as

G = n-1 i=0 | T [i]|.
Notice that n ≤ G ≤ N . A deterministic string is simply a string in Σ * . The Hamming distance is defined between two deterministic strings of equal length as the number of positions at which the two strings have different letters. The edit distance between two deterministic strings is defined as the minimum total cost of a sequence of edit operations (that is, substitution, insertion, or deletion of a letter) required to transform one string into the other. Here we only count the number of edit operations, considering the cost of each to be 1. In [START_REF] Grossi | On-Line Pattern Matching on Similar Texts[END_REF] the authors give a definition of a match between a deterministic string P and an ED text T ; here we extend their definition to deal with errors. Definition 3. Given an integer k > 0, we say that a string

P ∈ Σ m k H -matches (resp. k E -matches) an ED string T = T [0] T [1] . . . T [n -1] of length n > 1 if all of the following hold:
there exists a non-empty suffix X of some string S ∈ T [0];

-if n > 2, there exist strings Y 1 ∈ T [1],. . . ,Y t ∈ T [t], for 1 ≤ t ≤ n -2;
there exists a non-empty prefix Z of some string S ∈ T [n -1]; the Hamming (resp. edit) distance between P and XY 1 . . . Y t Z (note that Y 1 . . . Y t can be equal to ε) is no more than k.

We say that P has a k H -occurrence (resp. k E -) ending at position j in an ED string T of length n if either there exists a k H -match (resp. k E -) between P and T [i . . . j] for some 0 ≤ i < j ≤ n -1 or P is at Hamming (resp. edit) distance of at most k from a substring of some string S ∈ T [j].

T = {G} •      AA AG ε      • {A} •      GTG CAA AC      • {A} • G ε • {CA}
A suffix tree ST X for a string X of length m is a tree data structure where edge-labels of paths from the root to the (terminal) node labelled i spell out suffix X[i . . . m -1] of X. ST X can be built in time and space O(m). The suffix tree can be generalized to represent the suffixes of a set of strings {X 1 , . . . , X n } (denoted by GST X1,...,Xn ) with time and space costs still linear in the length of the input strings (see [START_REF] Gusfield | Algorithms on strings, trees, and sequences[END_REF], for details).

Given two strings X and Y and a pair (i, j), with 0 ≤ i ≤ |X| -1 and 0 ≤ j ≤ |Y | -1, the longest common extension at (i, j), denoted by lce X,Y (i, j), is the length of the longest substring of X starting at position i that matches a substring of Y starting at position j. For instance, for X = CGCGT and Y = ACG, we have that lce X,Y (2, 1) = 2, corresponding to the substring CG.

Fact 1 ([8]

) Given a string X and its ST X , and a set of strings W = {Y 1 , . . . , Y l }, it is possible to build the generalized suffix tree GST X,W extending ST X , in time O( l h=1 |Y h |). Moreover, given two strings X and Y of total length q, for each index pair (i, j), lce X,Y (i,j) queries can be computed in constant time per query, after a pre-processing of GST X,Y that takes time and space O(q). We will denote by GST * X,Y such a pre-processed tree for answering lce queries. The time is ripe now to formally introduce the two problems considered here. 3 An Algorithm for k E -EDSM

In [START_REF] Grossi | On-Line Pattern Matching on Similar Texts[END_REF] the exact EDSM problem (that is, for k = 0) was solved in time O(m 2 n+N ).

Allowing up to k substitutions, insertions, and deletions in the occurrences clearly entails a time-cost increase, but the solution proposed here manages to keep the time-cost growth limited, solving the k E -EDSM problem in time O(k 2 mG + kN ), G being the total number of strings in the ED text. At a high level, the k E -EDSM algorithm (pseudocode shown below) works as follows.

Pre-processing phase: the suffix tree for the pattern P is built (line 1 in pseudocode). Searching phase: in an on-line manner, the text T is scanned from left to right and, for each T [i]:

(1) It finds the prefixes of P that have a k E -match ending at T [i]; if there exists an S ∈ T [i] that is long enough, it also searches for k E -occurrences of P that start and end at position i (lines 6 and 16); k E -EDSM(P ,m, T ,n,k)

1 Build ST P ; 2 for j = 0 to m -1 do V c [j] ← ∞; 3 L c ← ∅; 4 Build GST * P, T [0] ; 5 forall S ∈ T [0] do 6 L ← ∅; L ← k E -borders(P, m, S, |S|, GST * P, T [0] , k); 7 forall (j, d) ∈ L do 8 if j = m -1 ∧ d < V c [m -1] then V c [m -1] = d; 9 else insert(L c ,(j, d),V c ); if V c [m -1] = ∞ then report (0, V c [m -1]); for i = 1 to n -1 do L p ← L c ; L c ← ∅; V p ← V c ; for j = 0 to m -1 do V c [j] ← ∞; Build GST * P, T [i] ; forall S ∈ T [i] do L ← ∅; L ← k E -borders(P, m, S, |S|, GST * P, T [i] , k); forall (j, d) ∈ L do if j = m -1 ∧ d < V c [m -1] then V c [m -1] = d; else insert(L c ,(j, d),V c ); if |S| < m then forall p ∈ L p do L ← ∅; L ← k E -extend(p + 1,P ,m,S,|S|,GST * P, T [i] ,k -V p [p]); forall (j, d) ∈ L do 25 if j = m -1 ∧ d + V p [p] < V c [m -1] then V c [m -1] = d + V p [p]; 26 else insert(L c ,(j, d + V p [p]), V c ); if |S| ≥ m then forall p ∈ L p do L ← ∅; L ← k E -extend(p + 1,P ,m,S,|S|,GST * P, T [i] ,k -V p [p]); forall (j, d) ∈ L do 32 if j = m -1 ∧ d + V p [p] < V c [m -1] then V c [m -1] = d + V p [p]; if V c [m -1] = ∞ then report (i, V c [m -1]);
Step (1) of algorithm k E -EDSM is accomplished using algorithm k E -borders described in Section 3.1. Step (2) is implemented by algorithm k E -extend described in Section 3.2.

The following lemma follows directly from Fact 1.

Lemma 5. Given P of length m and T of length n and size N , building GST *

P, T [i]

for all T [i]'s takes total time O(mn + N ).

Besides ST P (built once as a pre-processing step) and GST * P, T [i] (built for all T [i]'s), the algorithm uses the following data structures: is copied. L p thus stores prefixes of P that ended at the previous position (p stands for previous position). V p Similarly, in V p the vector V c of the previous position is copied.

Algorithm k E -EDSM needs to report each position i in T where some k Eoccurrence of P ends with edit distance d, d being the minimal such value for position i. To this aim, the last position of V c can be updated with the following criterion: each time an occurrence of P ending at T

[i], (m -1, d), is found, if V c [m -1] > d then we set V c [m -1] = d. After all S ∈ T [i] have been examined, if V c [m -1] = ∞, the algorithm outputs the pair (i, V c [m -1]).

Algorithm k E -borders

For each i and for each S ∈ T [i],

Step (1) of the algorithm needs to find all prefixes of P that are at distance at most k from a suffix of some S ∈ T [i], as well as k E -occurrences of P that start and end at position i if S is long enough. To this end, we use and modify the Landau-Vishkin algorithm [START_REF] Landau | Introducing efficient parallelism into approximate string matching and a new serial algorithm[END_REF]. We first recall some relevant definitions from [START_REF] Gusfield | Algorithms on strings, trees, and sequences[END_REF] concerning the dynamic programming table.

Given an m by q dynamic programming table (m rows, q columns), the main diagonal consists of cells (h, h) for 0 ≤ h ≤ min {m -1, q -1}. The diagonals above the main diagonal are numbered 1 through (q -1); the diagonal starting in cell (0, h) is diagonal h. The diagonals below the main diagonal are numbered -1 through -(m -1); the diagonal starting in cell (h, 0) is diagonal -h. A d-path in the dynamic programming table is a path that starts in row zero and specifies a total of exactly d errors (insertions, deletions and substitutions). A d-path is farthest reaching in diagonal h if it is a d-path that ends in diagonal h, and the index of its ending column c is ≥ to the ending column of any other d-path ending in diagonal h.

Algorithm k E -borders takes as input a pattern P of length m, a string S ∈ T [i] of length q, the GST * P, T [i] and the upper bound k for edit distance; it outputs pairs (j, d), where j is the rightmost position of the prefix of P that is at distance d from a suffix of S, with the minimal value of d reported for each j. In order to fulfill this task, at a high level, the algorithm executes the following steps on a table having P at the rows and S at the columns:

(1a) For each diagonal 0 ≤ h ≤ q -1 it finds lce P,S (0, h). This specifies the end column of the farthest reaching 0-path on each diagonal from 0 to q -1. (1b) For each 1 ≤ d ≤ k, it finds the farthest reaching d-path on diagonal h, for each -d ≤ h ≤ q -1. This path is found from the farthest reaching (d -1)-paths on diagonals (h -1), h and (h + 1). (1c) If a d-path reaches the last row of the dynamic programming table, then a k E -occurrence of P with edit distance d that starts and ends at position i has been found, and the algorithm reports (m -1, d); if a d-path reaches the end of S in row r, then the prefix of P ending at P [r] is at distance d from a suffix of S, and the algorithm reports (r, d).

In Step (1b), the farthest reaching d-path on diagonal h can be found by computing and comparing the following three particular paths that end on diagonal h: R 1 : Consists of the farthest reaching (d -1)-path on diagonal h + 1, followed by a vertical edge to diagonal h, and then by the maximal extension along diagonal h that corresponds to identical substrings. Function R 1 takes as input the length |X| of a string X, whose letters spell the rows of the dynamic table, the length |Y | of a string Y , whose letters spell the columns, GST * X,Y and the pair row-column (r, c) where the farthest reaching (d -1)-path on diagonal h + 1 ends. It outputs pair (r 1 , c 1 ) where path R 1 ends. This path represents a letter insertion in X. R 2 : Consists of the dual case of R 1 with a horizontal edge representing a letter deletion in X. R 3 : Consists of the farthest reaching (d -1)-path on diagonal h followed by a diagonal edge, and then by the maximal extension along diagonal h that corresponds to identical substrings. Function R 3 takes as input the length |X| of a string X, whose letters spell the rows of the dynamic table, the length |Y | of a string Y , whose letters spell the columns, GST * X,Y and the pair row-column (r, c) where the farthest reaching (d -1)-path on diagonal h ends. It outputs pair (r 3 , c 3 ) where path R 3 ends. This path represents a letter substitution.

Fact 2 ([8])

The farthest reaching path on diagonal h is the path among R 1 , R 2 or R 3 that extends the farthest along diagonal h.

In each one of the iterations in k E -borders, a diagonal is associated with two variables pFRP and cFRP, storing the column reached by the farthest reaching path (FRP) in the previous and in the current iteration, respectively. Lemma 6. Given P of length m, T of length n and size N , the GST * P, T [i] , for all i ∈ [0, n -1], and an integer 0 < k < m, k E -borders finds all prefixes of P that are at edit distance at most k from suffixes of S ∈ T [i] and the k E -occurrences of P that start and end at position i, in time O(k 2 G + kN ), G being the total number of strings in T .

Proof. For a string S ∈ T [i], for each 0 ≤ d ≤ k and each diagonal -k ≤ h ≤ |S| -1, the k E -borders algorithm must retrieve the end of three (d -1)-paths (constant-time operations) and compute the path extension along the diagonal via a constant-time lce query (Fact 1). It thus takes time O(k 2 + k|S|) to find all prefixes of P that are at distance at most k from suffixes of S; the k E -occurrences of P that start and end at position i are computed within the same complexity. The total time is

O(k 2 | T [i]| + k | T [i]|-1 j=0 |S|), for all S ∈ T [i].
Since the size of T is N and the total number of strings in T is G, the result follows.

Algorithm k E -extend

In Step (2), algorithm k E -EDSM needs to extend each partial k E -occurrence that has started earlier in T . That is, at text position T [i], for each p ∈ L p and k E -borders(P, m, S, q, GST * P, T [i] , k)

1 for h = -(k + 1) to -1 do cFRP(h) ← h -1; 2 for h = 0 to q -1 do 3 l ← lceP,S(0, h); 4 cFRP(h) ← l -1 + h; 5 if l + h = q then report (l -1, 0); 6 else 7 if l = m then report (m -1, 0); 8 for d = 1 to k do 9 for h = -d to q -1 do pFRP(h) ← cFRP(h); 10 for h = -d to q -1 do 11 (r1, c1) ← R1(|P |, |S|, GST * P, T [i] , pFRP(h + 1) -(h + 1), pFRP(h + 1)); 12 (r2, c2) ← R2(|P |, |S|, GST * P, T [i] , pFRP(h -1) -(h -1), pFRP(h -1)); 13 (r3, c3) ← R3(|P |, |S|, GST * P, T [i] , pFRP(h) -h, pFRP(h)); 14 cFRP(h) ← max {c1, c2, c3}; 15 if max {r1, r2, r3} = m -1 then report (m -1, d); 16 if max {c1, c2, c3} = q -1 then report (q -1 -h, d);
for each string S ∈ T [i], we try to extend P [p + 1 . . . m -1] with S. Once again, we modify the Landau-Vishkin algorithm [START_REF] Landau | Introducing efficient parallelism into approximate string matching and a new serial algorithm[END_REF] to our purpose: it suffices to look for the FRPs starting at the desired position only. k E -extend takes as input a pattern P of length m, a string S ∈ T [i] of length q, the GST * P, T [i] , the upper bound k for edit distance and the position j in P where the extension should start; it outputs a list of distinct pairs (h, d), where h is the index of P where the extension ends, and d is the minimum additional number of errors introduced by the extension. Algorithm k E -extend somehow performs a task which is the dual of that of k E -borders, as (i) it builds a q × (m -1 -j) DP table (rather than a m × q table) and (ii) instead of searching for occurrences of P starting anywhere within S, k E -extend checks whether the whole S can extend the prefix P [0 . . . j -1] detected at the previous text position, and whether a prefix of S matches the suffix of P starting at P [j] (and hence the whole P has been found). At a high level, the algorithm executes the following steps:

(2a) It finds lce S,P (0, j) specifying the end column of the farthest reaching 0-path on diagonal 0 (as it builds a DP table for S and P

[j . . . m -1]). (2b) For each 1 ≤ d ≤ k, it finds the farthest reaching d-path on diagonal h, for each -d ≤ h ≤ d.
This path is found from the farthest reaching (d -1)-paths on diagonals (h -1), h and (h + 1). (2c) If a d-path reaches the last row of the dynamic programming table in column c, then an occurrence of the whole S with edit distance d has been found, and the algorithm reports (c + j, d), c + j being the position in P where the occurrence ends; if a d-path reaches the end of P , then a prefix of S is at distance d from a suffix of P starting at position j, and the algorithm reports (m -1, d).

k E -extend(j, P, m, S, q, GST * P, T [i] , k)

1 if S = ε then 2 for d = 0 to k do report (j + d, d); 3 else 4 for h = -(k + 1) to k + 1 do cFRP(h) ← h -k -1; 5 l ← lceS,P (0, j); 6 cFRP(0) ← l -1; 7 if l = q then report (l + j -1, 0); 8 for d = 1 to k do 9 for h = -d to d do pFRP(h) ← cFRP(h); 10 for h = -d to d do 11 (r1, c1) ← R1(|S|, m-1-j, GST * P, T [i] , pFRP(h+1)-(h+1), pFRP(h+1)); 12 (r2, c2) ← R2(|S|, m-1-j, GST * P, T [i] , pFRP(h-1)-(h-1), pFRP(h-1)); 13 (r3, c3) ← R3(|S|, m -1 -j, GST * P, T [i] , pFRP(h) -h, pFRP(h)); 14 cFRP(h) ← max {c1, c2, c3}; 15 if max {r1, r2, r3} = q -1 then report (cFRP(h) + j, d); 16 if max {c1, c2, c3} = m -1 -j then report (m -1, d);
Lemma 7. Given a prefix of P , a string S ∈ T [i], the GST * P, T [i] , and an integer 0 < k < m, k E -extend extends the prefix of P with S in time O(k 2 ).

Proof. The k E -extend algorithm does k iterations: at iteration d, for each diagonal -d ≤ h ≤ d, the end of three paths must be retrieved (constant-time operations) and the path extension along diagonal h must be computed via a constant-time lce query (Fact 1). The overall time for the extension is then bounded by O(1

+ 2 + • • • + (2k + 1))=O(k 2 ).
The following lemma summarizes the time complexity of k E -EDSM. Proof. In order to obtain the space bound O(m), it is necessary to modify algorithm k E -EDSM. The proposed method works as follows: each string S ∈ T [i] is (conceptually) divided into windows of size 2m (except for the last one, whose length is ≤ m) overlapping by m. Let W j be the j-th window in S, 1 ≤ j ≤ |S| m . Instead of building GST * P, T [i] for each degenerate letter T [i], the algorithm now builds GST * P,Wj for each 1 ≤ j ≤ |S| m and for each S ∈ T [i]: since the windows are of size 2m, this can be done in both time and space O(m). Both algorithms k Eborders and k E -extend require space linear in the size of the string that spell the columns of the dynamic programming table, that is either P (in extensions) or a window of size 2m (in borders). Each list (L c , L p , L ) and each vector (V c , V p ) requires space O(m), so the overall required space is actually O(m).

The time bound is not affected by these modifications of the algorithm: the maximum number of windows in T Coming to algorithm k E -extend, nothing changes, as prefixes of P can only be extended by prefixes of S, so it suffices to consider one window for each S: it still requires time O(k 2 mG) over the whole ED text. Summing up all these considerations, it is clear that the overall time is

[i], in fact, is max {| T [i]|, Ni m }, where N i = | T [i]|-1 j=0 | T [i][j]|.
O( n-1 i=0 [max {m| T [i]|, N i } + max {km| T [i]|, kN i }] + k 2 mG) = = O( n-1 i=0 [max {km| T [i]|, kN i }] + k 2 mG)
which is clearly bounded by O(k 2 mG + kN ).

An Algorithm for k H -EDSM

The overall structure of algorithm k H -EDSM (pseudocode not shown) is the same as k E -EDSM. The two algorithms differ in the functions used to perform Step (1) (k H -borders rather than k E -borders) and Step (2) (k H -extend rather than k E -extend). The new functions take as input the same parameters as the old ones and, like them, they both return lists of pairs (j, d) (pseudocode shown below). Unlike k E -borders and k E -extend, with k H -borders and k H -extend such pairs now represent (partial) occurrences of P in T with Hamming distance. k H -borders(P ,m,S,q,GST * P, T [i] ,k)

1 for h = 0 to q -1 do 2 count ← 0; 3 j ← 0; 4 h ← h; 5 while count ≤ k do 6 l ← lceP,S(j, h ); 7 if h + l = q then report (q -h -1, count) ; 8 else 9 if h + l + 1 = q ∧ count + 1 ≤ k then report (q -h, count + 1) ; 10 else 11 if j + l = m then report (m -1, count) ; 12 else 13 if j + l + 1 = m ∧ count + 1 ≤ k then report (m -1, count + 1) ; 14 else 15 count ← count + 1; 16 j ← j + l + 1; 17 h ← h + l + 1;
At the i-th iteration, for all S ∈ T [i] and any position h in S, k H -borders determines whether a prefix of P is at distance at most k from the suffix of S starting at position h via executing up to k +1 lce queries in the following manner: computing l = lce P,S (0, h), it finds out that P [0 . . . l -1] and S[h . . . h + l -1] match exactly and P [l] = S[h + l]. It can then skip one position in both strings (the mismatch P [l] = S[h + l]), increasing the error-counter by 1, and compute the lce P,S (l + 1, h + l + 1). This process is performed up to k + 1 times, until either (i) the end of S is reached, and then a prefix of P is at distance at most k from the suffix of S starting at h (lines 7-12 in pseudocode); or (ii) the end of P is reached, then a k H -occurrence of P has been found (lines 13-17 in pseudocode). If the end of S nor the end of P are reached, then more than k mismatches are required, and the algorithm continues with the next position (that is, h + 1) in S.

The following lemma gives the total cost of all the calls of algorithm k Hborders in k H -EDSM.

Lemma 10. Given P of length m, T of length n and size N , the GST * P, T [i] , for all i ∈ [0, n -1], and an integer 0 < k < m, k H -borders finds all prefixes of k H -extend(j,P ,m,S,q,GST * P, T [i] ,k) P that are at Hamming distance at most k from suffixes of S ∈ T [i] and the k H -occurrences of P that start and end at position i, in time O(kN ).

1 if S = ε then report (j, 0); 2 else 3 count ← 0; 4 h ← 0; 5 j ← j; 6 while count ≤ k do 7 l ← lceP,S(i , j); 8 if h + l = q then report (j + l -1, count) ; 9 else 10 if h + l + 1 = q ∧ count + 1 ≤ k then report (j + l, count + 1) ; 11 else 12 if j + l = m then report (m -1, count) ; 13 else 14 if j + l + 1 = m ∧ count + 1 ≤ k then report (m -1, count +
Proof. For any position h in S, the k H -borders algorithm finds the prefix of P that is at distance at most k from the suffix of S starting at position h in time O(k) by performing up to k + 1 lce queries (Fact 1). Over all positions of S, the method therefore requires time O(k|S|). Doing this for all S ∈ T [i] and for all i ∈ [0, n -1] leads to the result.

At the i-th iteration, for each partial k H -occurrence of P started earlier (represented by j ∈ L p similar to algorithm k E -EDSM) k H -extend tries to extend it with a string from the current text position. To this end, for each string S ∈ T [i], it checks whether some partial occurrence can be extended with the whole S starting from position j of P , or whether a full k H -occurrence can be obtained by considering only a prefix of S for the extension. The algorithm therefore executes up to k + 1 lce queries with the same possible outcomes and consequences mentioned for k H -borders.

The following lemma gives the total cost of all the calls of algorithm k Hextend in k H -EDSM.

Lemma 11. Given P of length m, T of length n and size N , the GST * P, T [i] , for all i ∈ [0, n -1], and an integer 0 < k < m, k H -extend finds all the extensions of prefixes of P required by k H -EDSM in time O(kmG), G being the total number of strings in T .

Proof. Algorithm k H -extend determines in time O(k) whether a partial k Hoccurrence of P can be extended by S by performing up to k + 1 constant-time lce queries (Fact 1); checking whether a full k H -occurrence is obtained by considering only a prefix of S for the extension can be performed within the same complexity. Since P has m different prefixes, extending all of them costs O(km) per each string S. Given that there are G such strings, the overall time is O(kmG). The proof of Theorem 9 suggests a way in which algorithm k E -EDSM can be run on-line in space O(m); it should be straightforward to see that a similar modification of algorithm k H -EDSM leads to the following result.

Example 4 .

 4 (Running example) Consider P = GAACAA of length m = 6. The following ED string has n = 7, N = 20, and G = 12. An 1 H -occurrence is underlined, and an 1 E -occurrences is overlined.

  [k E -EDSM] Elastic-Degenerate String Matching with Edit Distance: Input: A deterministic pattern P of length m, an elastic-degenerate text T of length n and size N ≥ m, and an integer 0 < k < m. Output: Pairs (i, d), i being a position in T where at least one k E -occurrence of P ends and d ≤ k being the minimal number of errors (insertions, deletions and substitutions) for occurrence i.

  [k H -EDSM] Elastic-Degenerate String Matching with Hamming Distance: Input: A deterministic pattern P of length m, an elastic-degenerate text T of length n and size N ≥ m, and an integer 0 < k < m. Output: Pairs (i, d), i being a position in T where at least one k H -occurrence of P ends and d ≤ k being the minimal number of mismatches for occurrence i.

( 2 )

 2 It tries to extend at T [i] a partial k E -occurrence of the pattern which has started earlier in the ED text (lines 23 and 30); (3) In both previous cases, if the occurrence of P also ends in T [i], then it outputs position i; otherwise it stores the prefixes of P extended at T [i] (lines 7-9, 17-19, 24-26, 31-32).

L

  A list re-initialized to ∅ for each S ∈ T [i]: contains pairs (j, d) storing the rightmost position j of P such that a k E -match of P [0 . . . j] ends at S with edit distance d. L is filled in by k E -borders and k E -extend. V c A vector of size |P | re-initialized for each T [i] (c stands for current position) to V c [j] = ∞ for all j's: V c [j] contains the lowest number of errors for a partial k E -occurrence of P [0 . . . j]. For each pair (j, d) in L , if V c [j] < d then V c [j] is updated with d by the function insert. V c [j] = ∞ denotes that a partial k E -occurrence of P [0 . . . j] has not yet been found. L c A list re-initialized to ∅ for each T [i]: contains the rightmost positions of all the prefixes of P found ending at T [i]. It is filled in by function insert for each rightmost position j where V c [j] turns into a value = ∞. L p A list where at the beginning of each iteration i for T [i], the L c list for i -1

Lemma 8 .Theorem 9 .

 89 Given P of length m, T of length n and total size N , and an integer 0 < k < m, algorithm k E -EDSM solves the k E -EDSM problem, in an on-line manner, in time O(k 2 mG + kN ), G being the total number of strings in T . Proof. At the i-th iteration, algorithm k E -EDSM tries to extend each j ∈ L p with each string S ∈ T [i]. By Lemma 5, building GST * P, T [i] , for all i ∈ [0, n-1], requires time O(mn+N ). By Lemma 7, extending a single prefix with a string S costs time O(k 2 ); in L p there are at most |P | = m prefixes; then to extend all of them with a single string S requires time O(mk 2 ). In T [i] there are | T [i]| strings, so the time cost rises to O(| T [i]|mk 2 ) for each T [i], leading to an overall time cost of O(k 2 mG)to perform extensions. By Lemma 6, all prefixes of P that are at distance at most k from suffixes of S and the k E -occurrences of P that start and end at position i can be found in time O(k 2 G + kN ); the overall time complexity for the whole k E -EDSM algorithm is then O(mn+ N + k 2 mG + k 2 G + kN ) = O(k 2 mG + kN ).The algorithm is on-line in the sense that any occurrence of the pattern ending at position i is reported before reading T [i + 1]. The k E -EDSM problem can be solved on-line in time O(k 2 mG + kN ) and space O(m).

  This means that it takes time O(m| T [i]|) or O(m Ni m ) = O(N i ) to build and pre-process every suffix tree for T [i]. Algorithm k E -borders requires time O(k 2 + km) = O(km) (because k < m) for each window: again, this must be multiplied by the number of windows in T [i], so the time is max {O(km| T [i]|), O(kN i ))} for T [i].

Lemma 12 .

 12 Given P of length m, T of length n and total size N , and an integer 0 < k < m, algorithm k H -EDSM solves the k H -EDSM problem, in an on-line manner, in time O(kmG + kN ), G being the total number of strings in T . Proof. At the i-th iteration, algorithm k H -EDSM tries to extend each j ∈ L p with each string S ∈ T [i]. By Lemma 5, building GST * P, T [i] , for all i ∈ [0, n -1], requires time O(mn + N ). By Lemma 11, extending prefixes of P stored in L p with each string S ∈ T [i] has an overall time cost of O(kmG). By Lemma 10, finding prefixes of P that are at distance at most k from suffixes of S ∈ T [i] and the k H -occurrences of P that start and end at position i takes time O(kN ) in total. Summing up, the overall time complexity for the whole k H -EDSM algorithm is then O(mn + N + kmG + kN ) = O(kmG + kN ), as G ≥ n. The algorithm is on-line in the sense that any occurrence of the pattern ending at position i is reported before reading T [i + 1].

Theorem 13 .

 13 The k H -EDSM problem can be solved on-line in time O(kmG + kN ) and space O(m).

Acknowledgements

NP and GR are partially supported by the project MIUR-SIR CMACBioSeq ("Combinatorial methods for analysis and compression of biological sequences") grant n. RBSI146R5L. GB, NP, and GR are partially supported by the project UniPi PRA 2017 44 ("Advanced computational methodologies for the analysis of biomedical data"). NP, SPP, and GR are partially supported by the Royal Society project IE 161274 ("Processing uncertain sequences: combinatorics and applications").

INSERT(L,(j, d),V )

In algorithm k E -borders, at most k + q diagonals need to be taken into account: the algorithm first finds the lce's between P [0] and S[j], for all 0 ≤ j ≤ q -1, and hence it initializes q diagonals; after this, for each successive step (there are at most k of them), it widens to the left one diagonal at a time, because an initial deletion can be added; therefore, it will consider at most k + q diagonals.