Text Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations

In this paper we investigate the \emph{approximate string matching problem} when the allowed edit operations are \emph{non-overlapping unbalanced translocations of adjacent factors}. Such kind of edit operations take place when two adjacent sub-strings of the text swap, resulting in a modified string. The two involved substrings are allowed to be of different lengths. Such large-scale modifications on strings have various applications. They are among the most frequent chromosomal alterations, accounted for 30\% of all losses of heterozygosity, a major genetic event causing inactivation of cancer suppressor genes. In addition, among other applications, they are frequent modifications accounted in musical or in natural language information retrieval. However, despite of their central role in so many fields of text processing, little attention has been devoted to the problem of matching strings allowing for this kind of edit operation. In this paper we present three algorithms for solving the problem, all of them with a $\bigO(nm^3)$ worst-case and a $\bigO(m^2)$-space complexity, where $m$ and $n$ are the length of the pattern and of the text, respectively. % In particular, our first algorithm is based on the dynamic-programming approach. Our second solution improves the previous one by making use of the Directed Acyclic Word Graph of the pattern. Finally our third algorithm is based on an alignment procedure. We also show that under the assumptions of equiprobability and independence of characters, our second algorithm has a $\bigO(n\log^2_{\sigma} m)$ average time complexity, for an alphabet of size $\sigma \geq 4$.


Introduction
String alignment and approximate string matching are two fundamental problems in text processing. Given two input sequences x, of length m, and y, of length n, the string alignment problem consists in finding a set of edit operations able to transform x in y, while the approximate string matching problem consists in finding all approximate matches of x in y. The closeness of a match is measured in terms of the sum of the costs of the elementary edit operations necessary to convert the string into an exact match.
Most string matching methods are based on the Levenshtein distance [21], commonly referred to just as edit distance, or on the Damerau distance [16]. The edit operations in the case of the Levenshtein distance are insertions, deletions, and substitutions of characters, whereas, in the case of the Damerau distance, swaps of characters, i.e., transpositions of two adjacent characters, are also allowed (for an in-depth survey on approximate string matching, see [24]). Both distances assume that changes between strings occur locally, i.e., only a small portion of the string is involved in the mutation event. However evidence shows that in many applications there are several circumstances where large scale changes are possible [13,15,27]. For instance, such mutations are crucial in dna since they often cause genetic diseases [22,23]. For example, large pieces of dna can be moved from one location to another (translocations) [13,25,28,29], or replaced by their reversed complements (inversions) [7].
Translocations can be balanced (when equal length pieces are swapped) or unbalanced (when pieces with different lengths are moved). Interestingly, unbalanced translocations are a relatively common type of mutation and a major contributor to neurodevelopmental disorders [29]. In addition, cytogenetic studies have also indicated that unbalanced translocations can be found in human genome with a de novo frequency of 1 in 2000 [28] and that it is a frequent chromosome alteration in a variety of human cancers [25]. Hence the need for practical and efficient methods for detecting and locating such kind of large scale mutations in biological sequences arises.

Related Results
In the last three decades much work has been made for the alignment and matching problem allowing for chromosomal alteration, especially for non-overlapping inversions. Table 1 shows the list of all solutions proposed over the years, together with their worst-case, average-case and space complexities.
Concerning the alignment problem with inversions, a first solution based on dynamic programming, was proposed by Schöniger and Waterman [26], which runs in O(n 2 m 2 )-time and O(n 2 m 2 )-space on input sequences of length n and m. Several other papers have been devoted to the alignment problem with inversions. The best solution is due to Vellozo et al. [27], who proposed a O(nm 2 )time and O(nm)-space algorithm, within the more general framework of an edit graph.
Regarding the alignment problem with translocations, Cho et al. [13] pre- -O(m 2 ) Gao et al. [19] (2003) O(n 2 m 2 ) -O(nm) Chen et al. [12] (2004) O(n 2 m 2 ) -O(nm) Alves et al. [5] (2005) O(n 3 log n) -O(n 2 ) Vellozo et al. [27] (2006) O(nm 2 ) -O(nm) Alignment with inversions and balanced translocations on both strings Cho et al. [13] (2015) O(m 3 ) -O(m 2 ) Pattern matching with inversions Cantone et al. [6] (2011) O(nm) -O(m 2 ) Cantone et al. [7] (2013) O(nm) O(n) O(m 2 ) Pattern matching with unbalanced translocations Faro and Pavone [18] (  can occur on both strings and assume that the input sequences have the same length, namely |x| = |y| = n. Regarding the approximate string matching problem, a first solution was presented by Cantone et al. [6], where the authors presented an algorithm running in O(nm) worst-case time and O(m 2 )-space for the approximate string matching problem allowing for non-overlapping inversions. Additionally, they also provided a variant [7] of the algorithm which has the same complexity in the worst case, but achieves O(n)-time complexity on average. Cantone et al. also proposed in [8] an efficient solution running in O(nm 2 )-time and O(m 2 )space for a slightly more general problem, allowing for balanced translocations of adjacent factors besides non-overlapping inversions. The authors improved their previous result in [9] obtaining an algorithm having O(n)-time complexity on average. We mention also the result by Grabowski et al. [20], which solves the same string matching problem in O(nm 2 )-time and O(m)-space, reaching in practical cases O(n)-time complexity.

Our Results
While in the previous results mentioned above it is intended that a translocation may take place only between balanced factors of the pattern, in this paper we investigate the approximate string matching problem under a string distance whose edit operations are non-overlapping unbalanced translocations of adjacent factors. To the best of our knowledge, this slightly more general problem has never been addressed in the context of approximate pattern matching.
Given a bound δ, we consider the following variants of the approximate string matching problem allowing for non-overlapping unbalanced translocations of adjacent factors: (a) find the number of all unbounded approximate occurrences of x in y; (b) find the number of all δ-bounded approximate occurrences of x in y; (c) find all positions s in y such that x has a δ-bounded approximate occurrence in y at position s; (d) for each position s in y, find the number of distinct δ-bounded approximate occurrences of x in y at position s.
Specifically, after introducing some useful notions and basic definitions (Section 2), we will present the following three solutions for solving variants (a), (b) and (c): -First we propose (Section 3) a solution to the problem, based on the general dynamic programming approach, which needs O(nm 3 )-time and O(m 2 )space. -Subsequently we propose (Section 4) a second solution to the problem that makes use of the Directed Acyclic Word Graph of the pattern and achieves a O(n log 2 σ m)-time complexity on average, for an alphabet of size σ ≥ 4, still maintaining the same complexity, in the worst case, as for our first solution.
-Finally we present (Section 5) an alternative searching algorithm for the same problem also working in O(nm 3 ) worst case time and O(m 2 )-space but based on an alignment approach.

Basic notions and definitions
A string x of length m ≥ 0, over an alphabet Σ, is represented as a finite array x[1 .
. m] of elements of Σ. We write |x| = m to indicate its length. In particular, when m = 0 we have the empty string ε. We denote by x[i] the i-th character of x, for 1 ≤ i ≤ m. Likewise, the factor of x, contained between the i-th and the j-th characters of x is indicated with . m], for some 1 ≤ i ≤ m. We denote by Suff (x) the set of the suffixes of x. Similarly, we say that w is a prefix of x if w = x[1 .. i], for some 1 ≤ i ≤ m. Additionally, we use the symbol x i to denote the prefix of x of length i (i.e.,x i = x[1 .. i]), for 1 ≤ i ≤ m, and make the convention that x 0 denotes the empty string ε. In addition, we write xw for the concatenation of the strings x and w.
For w ∈ Fact(p), we denote with end-pos(w) the set of all positions in x at which an occurrence of w ends; formally, we put end-pos(w) := {i | w x i }. For any given pattern x, we define an equivalence relation R x by putting, for all w, z ∈ Σ * , w R x z ⇐⇒ end-pos(w) = end-pos(z).
We also denote with R x (w) the equivalence class of the string w. For each equivalence class q of R x , we put len(q) = |val (q)|, where val (q) is the longest string w in the equivalence class q. The Directed Acyclic Word Graph [14] of a pattern x (Dawg, for short) is the deterministic automaton A(x) = (Q, Σ, δ, root, F ) whose language is Fact(x), where Q = {R x (w) : w ∈ Fact(x)} is the set of states, Σ is the alphabet of the characters in x, root = R x (ε) is the initial state, F = Q is the set of final states, and δ : Q × Σ → Q is the transition function defined by δ(R x (y), c) = R x (yc), for all c ∈ Σ and yc ∈ Fact(x).
The function s enjoys the following property w R x y =⇒ s (w) = s (y).
We extend the functions s and end-pos to Q by putting s (q) := R x (s (val (q))) and end-pos(q) = end-pos(val (q)), for each q ∈ Q. Figure 2 shows the Dawg of the pattern x = aggga, where the edges of the automaton are depicted in black while the suffix links are depicted in red.
A distance d : Σ * × Σ * → R is a function which associates to any pair of strings x and y the minimal cost of any finite sequence of edit operations which transforms x into y, if such a sequence exists, ∞ otherwise.
In this paper we consider the unbalanced translocation distance, utd(x, y), whose unique edit operation is the translocation of two adjacent factors of the string, with possibly different lengths. Specifically, in an unbalanced translocation a factor of the form zw is transformed into wz, provided that both |z|, |w| > 0 (it is not necessary that |z| = |w|). We assign a unit cost to each translocation. When utd(x, y) < ∞, we say that x and y have utd-match. If x has utd-match with a suffix of y, we write x utd y.

A Dynamic Programming Solution
In this section we present a general dynamic programming algorithm for the pattern matching problem with adjacent unbalanced translocations. Specifically we first describe an algorithm for solving Variant (c) of the problem. Subsequently we discuss how to slightly modify such algorithm for solving variant (a), (b) and (d).
Let x be a pattern of length m and y a text of length n, with n ≥ m, both over the same alphabet Σ of size σ. In addition let δ be a bound for the number of translocations allowed in any approximate occurrence of x in y, with δ ≤ m/2 .
Our algorithm is designed to iteratively compute, for j = m, m + 1, . . . , n, all the prefixes of x which have a δ-bounded utd-match with the suffix of y j , by exploiting information gathered at previous iterations.
Since the allowed edit operations involve substrings of the pattern x, it is useful to consider the set F k j of all the positions in x at which an occurrence of the suffix of y j of length k ends. More precisely, for 1 ≤ k ≤ m and k −1 ≤ j ≤ n, we put Observe that Example 3. Let x = cattcatgatcat and y = atcatgacttactgactta be a pattern and respectively a text. Then F 3 5 is the set of all positions in x at which an occurrence of the suffix of y 5 of length 3 ends, namely, cat. Thus The sets F k j can be computed according to the following lemma.
Lemma 1. Let y and x be a text of length n and a pattern of length m, respectively. Then i ∈ F k j if and only if one of the following condition holds: Observe that, based on equation (1), we can represent the sets F k j by means of a single matrix F of size m × n. Specifically, for 1 ≤ i ≤ m and 1 ≤ j ≤ n, we set F[i, j] as the length of the longest suffix of x i which is also a suffix of y j . More formally we have: The size of the set Q i j corresponds to the number of possible different alignments of the string x i against the suffix of y j of length i, allowing for unbalanced translocations of adjacent factors. Observe that the size of the set Q[i, j] is always less than δ. The minimum number of translocations for transforming x i in the suffix of y j is then given by where we agree upon the value +∞ in the case of no possible alignment between the two strings. As a consequence, the pattern x has a δ-bounded utd-match ending at position j of the text y if and only if the set Q m j is not empty. The sets Q i j can then be computed by way of the recursive relations contained in the following elementary lemmas.
Lemma 2. Let y and x be a text of length n and a pattern of length m, respectively. Then t ∈ Q i j , for 1 ≤ i ≤ m and i ≤ j ≤ n, if and only if one of the following two facts holds: Notice that condition (ii) in Lemma 2 refers to a translocation of adjacent factors of length k and h, respectively (see Figure 1).
For solving variant (c) of the problem the sets Q i j can be maintained as a matrix Q of integer values of size n × m, where

Algorithm 1: Dymanic programming solution
Input: A pattern x, a text y and a bound δ Output: The number of approximate occurrences of x in y 1. for j ← 1 to n do 2.
Output j − m Based on the recurrence relations in Lemmas 2 and 1, a general dynamic programming algorithm can be readily constructed, characterized by an overall O(nm 3 )-time and O(m 3 )-space complexity.
The overhead due to the computation and the maintenance of the sets F and Q turns out to be quite relevant.
However, since we need only the last m columns of the matrices F and Q for computing the next column, we can maintain them by means of two matrices of size m 2 . The pseudocode of the resulting dynamic programming algorithm is shown in Algorithm 1. Due to the four for-loops at lines 5, 7, 11, and 12, respectively, it can straightforwardly be proved that Algorithm1 has a O(nm 3 )time and O(m 2 )-space complexity. Indeed, the matrices F and Q are filled by columns and therefore we need to store only the last m columns at each iteration of the for-loop at line 5.

Solving other variants of the problem
Algorithm 1, as proposed in the previous section, solves variant (c) of the approximate string matching problem allowing for non overlapping unbalanced translocations. In this section we briefly discuss how to slightly modify the algorithm to obtain a solution for variants (a), (b) and (d) respectively.
We first start with Variant (b) which consists in finding the number of all δ-bounded approximate occurrences of x in y. In this case it is enough to modify Algorithm 1 in order to count the matching positions while they are given in line 16. Thus the solution maintains the same time and space complexity.  Observe that, is δ ≤ w, the whole algorithm requires the same time maintains the same time and space complexity of Algorithm 1, where w is the size of a word in the target machine. Otherwise, when δ > w the worst case time complexity of the algorithm if O(nm 3 δ/w) while the space complexity is O(m 2 δ/w).

An Automaton-Based Algorithm
In this section we improve the algorithm described in Section 3 by means of an efficient method for computing the sets F k j , for 1 ≤ j ≤ n and 1 ≤ k < j. Such method makes use of the Dawg of the pattern x and the function end-pos. In addition we introduce an efficient method for maintaining information from the sets Q j i . Let A(x) = (Q, Σ, δ, root, F ) be the Dawg of x. For each position j in y, let w be the longest factor of x which is a suffix of y j too; also, let q j be the state of A(x) such that R x (w) = q j , and let l j be the length of w. We call the pair (q j , l j ) a y-configuration of A(x).
The idea is to compute the y-configuration (q j , l j ) of A(x), for each position j of the text, while scanning the text y. The set F k j computed at previous iterations do not need to be maintained explicitly; rather, it is enough to maintain only y-configurations. These are then used to compute efficiently the set F k j only when needed.
Example 4. Let x = aggga be a pattern and y = aggagcatgggactaga a text respectively. Let A(x) = (Q, Σ, δ, root, F ) be the DAWG of x as depicted in Figure 2, where root = q 0 is the initial state and F = {q 1 , q 2 , q 3 , q 4 , q 5 , q 6 , q 7 } is the set of final states. Edges of the Dawg are depicted in black while suffix links are depicted in red. Observe that, after scanning the suffix y 5 starting from state q 0 of A(x), we reach state q 2 of the automaton. Thus, the corresponding y-configuration is (q 2 , 2). Similarly, after scanning the suffix y 11 , we get the yconfiguration (q 4 , 3).
The longest factor of x ending at position j of y is computed in the same way as in the Forward-Dawg-Matching algorithm for the exact pattern matching problem (the interested readers are referred to [14] for further details). Specifically , if such a node exists; otherwise (q j , l j ) is set to (root, 0). 1 Before explaining how to compute the sets F k j , it is convenient to introduce the partial function φ : Q × N → Q, which, given a node q ∈ Q and a length k ≤ length(q), computes the state φ(q, k) whose corresponding set of factors contains the suffix of val (q) of length k. Roughly speaking, φ(q, k) is the first node p in the suffix path of q such that length(s (p)) < k.
In the preprocessing phase, the Dawg A(x) = (Q, Σ, δ, root, F ), together with the associated end-pos function, is computed. Since for a pattern x of length m we have |Q| ≤ 2m + 1 and |end-pos(q)| ≤ m, for each q ∈ Q, we need only O(m 2 ) extra space (see [14]).
To compute the set F k j , for 1 ≤ k ≤ l j , we take advantage of the relation F k j = end-pos(φ(q j , k)).
Notice that, in particular, we have F lj j = end-pos(q j ). The time complexity of the computation of φ(q, k) can be bounded by the length of the suffix path of node q. Specifically, since the sequence len(s (0) (q)), len(s (1) (q)), . . . , 0 of the lengths of the nodes in the suffix path from q is strictly decreasing, we can do at most len(q) iterations over the suffix link, obtaining a O(m)-time complexity.
According to Lemma 2, a translocation of two adjacent factors of length k and h, respectively, at position j of the text y is possible only if two factors of x of lengths at least k and h, respectively, have been recognized at both positions j and j − h, namely if l j ≥ h and l j−h ≥ k hold (see Figure 1).
Let h 1 , h 2 , . . . , h r be the increasing sequence of all the values h such that 1 ≤ h ≤ min(l j , l j−h ). For each 1 ≤ i ≤ r, condition (ii) of Lemma 2 requires member queries on the sets F hi j . Observe that if we proceed for decreasing values of h, the sets F h j , for 1 ≤ h ≤ l j , can be computed in constant time. Specifically, for h = 1, . . . , l j − 1 F h j can be computed in constant time from F h+1 j with at most one iteration over the suffix link of the state φ(q j , h + 1).
Subsequently, for each member query on the set F hi j , condition (ii) of Lemma 2 requires also member queries on the sets F k j−hi , for 1 ≤ k < h i . Let k 1 , k 2 , . . . , k s be the increasing sequence of all the values k such that 1 ≤ k ≤ min(l j−hi , l j−hi−k ). Also in this case we can proceed for decreasing values of k, in order to compute the sets F k j−hi in constant time, for 1 ≤ k ≤ l j−hi . In order to efficiently maintain the elements in the sets Q j i we introduce the sets P j , for 1 ≤ j ≤ n, as the set of all prefixes of the pattern x which have an approximate occurrences ending at position j of the text. More formally Such sets can be maintained as linked lists in order to be able to scan in linear time, for each position j of the text, the set of all position i for which it holds that Q j i ≤ δ. The resulting algorithm for the approximate string matching problem allowing for unbalanced translocations of adjacent factors is shown in Algorithm 2. In the next sections, we analyze its worst-case and average-case complexity.

Worst-case time and space analysis
In this section we determine the worst-case time and space analysis of the algorithm presented in the previous section. In particular, we will refer to the solution reported in Algorithm 2.
First of all, observe that the main for-loop at line 7 is always executed n times.  if q = nil then 6.

10.
q ← δA(q, c); 11. else 12. l ← l + 1; In order to evaluate the space complexity of Algorithm 2, we observe that in the worst case, during the j-th iteration of its main for-loop, the sets F k j−k and P j−k , for 1 ≤ k ≤ m, must be kept in memory to handle translocations. However, as explained before, we do not keep the values of F k j−k explicitly but rather we maintain only their corresponding y-configurations of the automaton A(x). Thus, we need O(m)-space for the last m configurations of the automaton and O(m 2 )space to keep the last m+1 values of the sets P j−k , since the maximum cardinality of each such set is m + 1. Observe also that, although the size of the Dawg is linear in m, the end-pos(·) function can require O(m 2 )-space. Therefore, the total space complexity of Algorithm 2 is O(m 2 ).

Average-case time analysis
In this section we evaluate the average time complexity of our new automatonbased algorithm, assuming the uniform distribution and independence of characters in an alphabet Σ with σ ≥ 4 characters.
In our analysis we do not include the time required for the computation of the DAWG and the end-pos(·) function, since they require O(m) and O(m 2 ) worst-case time, respectively, which turn out to be negligible if we assume that m is much smaller than n. Hence we evaluate only the searching phase of the algorithm.
Given an alphabet Σ of size σ ≥ 4, for j = 1, . . . , n, we consider the following nonnegative random variables over the sample space of the pairs of strings x, y ∈ Σ * of length m and n, respectively: -X(j) = the length l j ≤ m of the longest factor of x which is a suffix of y j ; Then the run-time of a call to Algorithm 2 with parameters (x, y) is proportional to where the external summation refers to the main for-loop (at line 7), the second summation within it takes care of the internal for-loop at line 15, and the third summation refers to the inner for-loop at line 19.
Hence the average-case complexity of Algorithm 2 is the expectation of (3), which, by linearity, is equal to where E(·) be the expectation function. Since E(X(j)) ≤ E(X(n − 1)) and E(Z(j)) ≤ E(Z(n − 1)), for 1 ≤ j ≤ n, 2 by putting X = X(n − 1) and Z = Z(n − 1), the expression (4) gets bounded from above by Let Z i and X h be the indicator variables defined for i = 1, . . . , m and h = 1, . . . , m, respectively as

So that we have
which yields the following upper bound for (5): To estimate each of the terms E(X h X k ) in (6), we use the well-known Cauchy-Schwarz inequality which in the context of expectations assumes the form |E(U V )| ≤ E(U 2 )E(V 2 ) , for any two random variables U and V such that E(U 2 ), E(V 2 ) and E(U V ) are all finite.
Then, for 1 ≤ h ≤ m and 1 ≤ k ≤ m, we have From (7), it then follows that (6) is bounded from above by To better understand (8), we evaluate the expectations E(X) and E(Z) and the sum m h=1 E(X h ). To this purpose, it will be useful to estimate also the In view of (9), we have: Let h be the smallest integer 1 ≤ h < m such that m−h+1 σ h < 1. Then, from (10), we have Since m−(h+1)+1 σ h+1 ≥ 1, then σ h+1 ≤ m−(h+1)+1 ≤ m−1, so that h+1 < log σ m. Hence from (11) and h + 1 < log σ m, we obtain Likewise, from (9) and h + 1 < log σ m, we have where h is defined as above.
Next we estimate E(Z i ) = Pr {x i utd y}, for 1 ≤ i ≤ m. Let us denote by µ(i) the number of distinct strings which have a utd-match with a given string of length i and whose characters are pairwise distinct. Then it is not hard to see that µ(i + 1) ≤ 3 i , for i = 1, 2, . . . , m, so that we have Then, concerning E(Z), from (14) we have (15) (we recall that we have assumed σ ≥ 4). From (15), (12), and (13), it then follows that (4) is bounded from above by n · (1 + log σ m + 3 log 2 σ m), yielding a O(n log 2 σ m) average-time complexity for our automaton based algorithm.

An Alignment Based Solution
In this section we present a third solution for the approximate string alignment problem allowing for unbalanced translocations of adjacent factors. This solution is based on a procedure used for checking whenever an approximate match exists between two equal length strings x and z.
The corresponding approximate string matching algorithm allowing for unbalanced translocations of adjacent factors can be trivially obtained by iterating the given procedure for all possible subsequences of the text of length m.
The algorithm is composed by a preprocessing and searching phase, which we describe in Section 5.1 and in Section 5.2, respectively. Then, in Section 5.3, we prove the correctness of the algorithm and discuss its worst case time complexity.

The Preprocessing Phase
During the preprocessing phase of the algorithm three functions are computed, in the form of tables, which are then used during the alignment process.
We also define the border set function ψ x of a given string x as the set of the lengths of all borders of x. Specifically we define ψ x (i, j), for each 1 ≤ i < j ≤ m, For each i, j with 1 ≤ i ≤ j ≤ m, we can represent the set ψ x (i, j) by using a vector of (j − i + 1) boolean values such that its k-th entry is set iff k ∈ ψ x (i, j). More formally the function ψ x can be maintained using a tridimensional bit-table Ψ x , which we call border set table of x, defined as The border set table Ψ x can be computed in O(m 3 )-time and space by using Procedure Compute-Border-Set, where Compute-Border- Table is the O(m) function used in the Knuth-Morris-Pratt algorithm [2].
Observe that using Ψ x we can answer in constant-time to queries of the the type "is k the length of a border of the substring x[i..j]? ", which translates to evaluate if Ψ [i, j, k] is set.
In addition we define the shortest border function of a string x, as the function ρ x : {1, . . . , m} × {1, . . . , m} → {1, . . . , m} which associates any nonempty substring of x to the length of its shortest border. Specifically we set ρ x (i, j) to be the length of the shortest border of the string x[i . . . j], for 1 ≤ i < j ≤ m. More formally we have It is trivial to observe that, if we already computed the border set function ψ x , for the pattern x, the shortest border function ρ x of x can be computed in O(m 3 )-time using O(m 2 ) space.
In what follows we will use the symbols µ, ψ and ρ, in place of µ x , ψ x and ρ x , respectively, when the reference to x is clear from the context.

The Searching Phase
The searching phase of the algorithm is based on an alignment procedure 3 specifically designed to check, given two input strings x and y of the same length, if a set of translocations exists allowing to transform x in y. The searching phase of our Algorithm 3 simply consists in applying the alignment procedure between the pattern and any possible substring of the text of length m.
The alignment procedure finds a possible utd-match between two equal length strings. The pseudocode of Algorithm 3 is tuned to process two strings x and y, of length m, where translocations can take place only in x.
while r ≤ m do 10.

Output j;
In order to probe the details of the alignment procedure, let x and y be two strings of length m over the same alphabet Σ. The procedure sequentially reads all characters of the string y, proceeding from left to right. While scanning it tries to evaluate all possible unbalanced translocations in x which may be involved in the alignment between the two strings.
We define a translocation attempt at position i of y, for 1 ≤ i ≤ m, as a quintuple of indexes, (s 1 , k 1 , s 2 , k 2 , t), with all elements in {0, 1, 2, . . . , m}∪{null} and where, referring to the string x, s 1 and k 1 pinpoints the leftmost position and the length of the first factor (the factor moved on the left), while s 2 and k 2 pinpoints the leftmost position and the length of the second factor (the factor moved on the right). In this context we refer to s 1 and s 2 as the key positions of the translocation attempt. The last value t of the quintuple identify the cost of the attempt in terms of number of translocations.
In the special case where no translocation takes place in the attempt we assume by convention that s 1 = i and s 2 = k 1 = k 2 = null. 4 During the execution of the algorithm for each translocation attempt, (s 1 , k 1 , s 2 , k 2 , t), at position i, the invariant given by the following lemma 5 holds.
Lemma 3. Let y and x be two strings of length m over the same alphabet Σ. Let Γ (i) be the set of all translocation attempts computed by Algorithm 3 during the i-th iteration. If (s 1 , k 1 , s 2 , k 2 , t) ∈ Γ (i) then it holds that: Proof. We prove the statement by induction on the value of i. For the base case observe that when i = 0 we have Γ (0) = {0, null, null, null, 0} and the statements trivially hold.
Suppose now that the statements hold for i − 1 ≥ 0 and prove that they hold also for i. Let (s 1 , k 1 , s 2 , k 2 , t) ∈ Γ (i−1) be a translocation attempt computed at iteration i − 1. By induction we have s 1 + k 1 + k 2 = i − 1. We can distinguish the following three different cases.
If we are in Case 1 and x[i] = y[i] then (i, null, null, null, t) is added to Γ (i) which trivially satisfies all the statements (a-d ). Moreover, for each j > i such that x[j] = y[i] the new translocation attempt (i − 1, null, j − 1, 1, t + 1) is added to Γ (i) . In this last case we have that the statement (b) still holds and we have also that s 1 + k 1 + k 2 = s 1 + 1 = i − 1 + 1 = i, so the statement (a) holds too.
If we are in Case 2 the right factor can be extended by a single character to the right adding (s 1 , k 1 , s 2 , k 2 +1, t) to Γ (i) . Also in this case we have s 1 +k 1 +k 2 +1 = i − 1 + 1 = i and the property is satisfied.
Finally, if we are in Case 3 the left factor can be extended by a single character to the right adding (s 1 , k 1 + 1, s 2 , k 2 , t) to Γ (i) getting again s 1 + k 1 + 1 + k 2 = i − 1 + 1 = i. Observe also that if we close a translocation attempt (when k 1 + 1 = s 2 ) the attempt (i, null, null, null, t) is added to Γ (i) , which trivially satisfies the property.
However we can prove that it is not necessary to process all possible translocation attempts. Some of them, indeed, leads to detect the same utd-matches so that they can be skipped. Specifically it can be proved that the following Lemma holds. Proof. We will consider the following three cases, which depend on the length of w in relation with the length of w.z. The three cases discussed below are depicted in Figure 4, cases (a), (b) and (c), respectively.
-Case (a): suppose first |w | ≥ |w| + |z|. Refering to y, we have that w.z is a prefix of w and we can write w = w.z.a for some a ∈ Σ * , with |a| ≥ 0.
In the specific case where |w | = |w| + |z| we have w = w.z and a = ε.  The procedure iterates on the values of i, for 1 ≤ i ≤ m, while scanning the characters of y, and during the i-th iteration it computes the set Γ (i) from Γ (i−1) . For each translocation attempt (s 1 , k 1 , s 2 , k 2 , t) ∈ Γ (i−1) we distinguish the following three cases (depicted in Fig. 3): Case (3.a) i.e. if s 1 + k 1 = s 2 , Γ i is extended by adding the attempt (s 1 + k 1 + k 2 , null, null, null), t (lines 29-30) which indicates that x i utd = y i . Otherwise Γ (i) is extended by adding the attempt (s 1 , k 1 + 1, s 2 , k 2 , t) (line 32).
In this case the right factor u cannot be extended. Before quitting the translocation attempt we try to find some new factors rearrangements on the same key positions, s 1 and s 2 , but with different lengths, k 1 and k 2 . Specifically we try to transfer a suffix w of u r to the prefix position of u , reducing the length k 2 and extending the length k 1 accordingly. This can be done only if we find a suffix w of u r which is also a prefix of x[s 1 + 1..s 2 ] and, in addition, we can move u to the right of |w| position along the left factor. More formally, if we assume that |w| = b we must have: 1. |w| < |u r |, or rather b < k 2 (indicating that w is a proper suffix of u r ); 2. b ∈ φ(s 1 +1, s 2 +k 2 ) (indicating that w is a border of x[s 1 +1..s 2 +k 2 ]); 3. (k 1 − s 1 + 1) ∈ φ(s 1 + 1, k 1 + b) (indicating that u is a border of x[s 1 + 1..s 1 + k 1 + |w|]); 4. s 1 + k 1 + |w| < s 2 (indicating that the updated u does not overflow onto u r ); 5. x[s 1 + k 1 + |w| + 1] = y[i] (indicating that the updated u can be extended by y[i])

Worst-case time and space analysis
In this section we discuss the worst-case time and space analysis of Algorithm 3 presented in the previous section. Let x be a pattern of length m and y be a text of length n over the same alphabet Σ and assume to run Algorithm 3 for searching all δ-bounded approximate occurrences of x in y.
Regarding the space analysis, as stated in Section 5. Regarding the time analysis, we first consider the time complexity required by a single iteration of the main loop of line 1 of the algorithm. Specifically let Γ (i) be the the set of all translocation attempts computed at iteration i, for First of all we observe that each Γ (i) contains at most one translocation attempt with k 2 = null (i.e. of the form (s 1 , null, null, null), t). We put Γ (0) = {(0, null, null, null, 0)} (line 2), thus the statement holds for i = 0. Observe that, if i > 0 a translocation attempt of the form (s 1 , null, null, null, t) can be added to Γ (i) only in line 7 or in line 30. However by condition at line 29, if it is added to Γ (i) in line 7, it cannot be added again in line 30.
We now prove that the total number of translocation attempts processed during a sngle execution of the main loop of the algorithm is bounded by m 3 . More formally we have To prove that equation (16) holds observe that new translocation attempts are added to Γ (i) only when we are in Case 1. When we are in Case 2 or in Case 3 a translocation attempt is simply rearranged by extending the right factor (Case 2) or the left factor (Case 3). As observed above only one translocation attempt in Γ (i) is in Case 1 and the while cycle of line 9 can add at most m − i new translocation attempts to Γ (i+1) . In the worst case each translocation attempt added to Γ (i+1) will be closed only at iteration m, thus it will be extended along the sets Γ (j) , for j > i. Thus the overall contribute of each translocation attempt added to Γ i+1 is m − i.
Thus the total number of translocation attempts processed during a single iteration of the main loop of the algorithm is bounded by Finally we observe that each translocation attempt in Case 2 and Case 3.a is processed in constant time, during the execution of Algorithm 3. A translocation attempt in Case 1 my be processed in O(m − i) worst case time. However the overall contribution of the while cycle at line 9 is at most O(m 2 ) since, as observer above, there is a single translocation attempt in Case 1 for each Γ (i) .
For a translocation attempt in Case 3, observe that at each execution of line 22 the value of b is increased of at most 1. Then in line 23 we decrease k 2 by b. Since the value of k 2 is increased only in line 15, this implies that overall number of times the while cycle of line 21 is executed is bounded by k 2 , which is at most m. Thus the overall contribution given by the while cycle of line 19 is O(m 3 ).
We can conclude that the overall time complexity of a single iteration of Algorithm 3 is O(m 3 ) and that the overall complexity of the algorithm is therefore O(nm 3 ).

Solving other variants of the problem
Algorithm 3, as proposed in the previous section, solves variant (c) of the approximate string matching problem allowing for non overlapping unbalanced translocations. Thus it finds all positions s in y such that x has a δ-bounded approximate occurrence in y at position s. In this section we briefly discuss how to slightly modify the algorithm to obtain a solution for variants (a), (b) and (d) respectively.
For solving Variant (a) of the problem a translocation attempt at a given position of y can be simply represented as a quadruple of indexes (s 1 , k 1 , s 2 , k 2 ). Thus we don't need to maintain the cost t of the attempt in terms of number of translocations. The resulting algorithm could be simplified accordingly, although this simplification doesn't lead to a reduction in terms of time or space complexity.
Variant (b) of the problem asks to find the number of all δ-bounded approximate occurrences of x in y. In this case it is enough to modify Algorithm 3 in order to count the matching positions while they are given in line 34. Thus the solution maintains the same time and space complexity.
Finally, Variant (d) of the problem asks to find, for each position s in y, the number of distinct δ-bounded approximate occurrences of x in y at position s. As i the previous case it is enough to maintain a counter which must be increased, in line 34, by the size of the set Γ m . Also in this case the solution maintains the same time and space complexity as Algorithms 3.

Conclusions and Future Works
We presented a three solutions for the approximate string matching problem allowing for unbalanced translocations of adjacent factors working in O(nm 3 ) worst case time using O(m 2 )-space. To the best of our knowledge this is the first paper addressing this kind of problem.
Although our three solutions have the same time and space complexity Algorithm 2 and Algorithm 3 have some special features. Specifically we prove that Algorithm 2 has a O(n log 2 σ m) average case time complexity, for alphabets of size σ ≥ 4. In addition Algorithm 3 uses a constructive approach which could be more efficient in practice and which can be easily optimized. It turns out, indeed, by our preliminary experimental results that our solution has a sub-quadratic behaviour in practical cases. This suggests us to focus our future works on an accurate analysis of the algorithm's complexity in the average case.