Takuya Mieno
email: takuya.mieno@inf.kyushu-u.ac.jp

Solon P Pissis
email: solon.pissis@cwi.nl

Leen Stougie
email: leen.stougie@cwi.nl

Michelle Sweering
email: michelle.sweering@cwi.nl

String Sanitization Under Edit Distance: Improved and Generalized

Let W be a string of length n over an alphabet Σ, k be a positive integer, and S be a set of length-k substrings of W . The ETFS problem asks us to construct a string X ED such that: (i) no string of S occurs in X ED ; (ii) the order of all other length-k substrings over Σ is the same in W and in X ED ; and (iii) X ED has minimal edit distance to W . When W represents an individual's data and S represents a set of confidential patterns, the ETFS problem asks for transforming W to preserve its privacy and its utility [Bernardini et al., ECML PKDD 2019].

ETFS can be solved in O(n 2 k) time [Bernardini et al., CPM 2020]. The same paper shows that ETFS cannot be solved in O(n 2-δ ) time, for any δ > 0, unless the Strong Exponential Time Hypothesis (SETH) is false. Our main results can be summarized as follows:

• An O(n 2 log 2 k)-time algorithm to solve ETFS.

• An O(n 2 log 2 n)-time algorithm to solve AETFS, a generalization of ETFS in which the elements of S can have arbitrary lengths.

Our algorithms are thus optimal up to polylogarithmic factors, unless SETH fails. Let us also stress that our algorithms work under edit distance with arbitrary weights at no extra cost. In order to arrive at these results, we develop new techniques for computing a variant of the standard dynamic programming (DP) table for edit distance. In particular, we simulate the DP table computation using a directed acyclic graph (DAG) in which every node is assigned to a smaller DP table. We then focus on redundancy in these DP tables and exploit a tabulation technique according to dyadic intervals to obtain an optimal alignment in Õ(n 2 ) total time 5 . As a bonus, we show how to modify some known techniques, which speed up the standard edit distance computation, to be applied to our problems. Beyond string sanitization, our techniques may inspire solutions to other problems related to regular expressions or context-free grammars.

Introduction

Let us start with an example to ensure that the reader is familiar with the basic motivation behind the computational problem investigated here. Consider a sequence W of items representing a user's on-line purchasing history. Further consider a fragment (or a subsequence) of W denoting that the user has first purchased unscented lotions and zinc/magnesium supplements and then unscented soaps and cotton balls in extra-large bags. By having access to W and to the respective domain knowledge, one can infer that the user is probably pregnant and close to the delivery date.

Data sanitization, also known as knowledge hiding, is a privacy-preserving data mining process aiming to prevent the mining of confidential knowledge from published datasets; it has been an active area of research for the past 25 years [START_REF] Clifton | Security and privacy implications of data mining[END_REF][START_REF] Stanley | Protecting sensitive knowledge by data sanitization[END_REF][START_REF] Vassilios | Association rule hiding[END_REF][START_REF] Gkoulalas | An integer programming approach for frequent itemset hiding[END_REF][START_REF] Wu | Hiding sensitive association rules with limited side effects[END_REF][START_REF] Gkoulalas | Exact knowledge hiding through database extension[END_REF][START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF][START_REF] Abul | Knowledge hiding from tree and graph databases[END_REF][START_REF] Gkoulalas | Revisiting sequential pattern hiding to enhance utility[END_REF][START_REF] Gwadera | Permutation-based sequential pattern hiding[END_REF][START_REF] Loukides | Optimal event sequence sanitization[END_REF][START_REF] Bonomi | An information-theoretic approach to individual sequential data sanitization[END_REF][START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF]. Informally, it is the process of disguising (hiding) confidential information in a given dataset. This process typically incurs some data utility loss that should be minimized. Thus, naturally, privacy constraints and utility objective functions lead to the formulation of combinatorial optimization problems. From a fundamental perspective, it is thus relevant to be able to establish some formal guarantees.

A string W is a sequence of letters over some alphabet Σ. Individuals' data, in domains ranging from web analytics to transportation and bioinformatics, are typically represented by strings. For example, when Σ is a set of items, W can represent a user's purchasing history [START_REF] Agrawal | Mining sequential patterns[END_REF]; when Σ is a set of locations, W can represent a user's location profile [START_REF] Ying | Semantic trajectory mining for location prediction[END_REF]; and when Σ is the DNA alphabet, W can represent a patient's genome sequence [START_REF] Daniel | The next-generation sequencing revolution and its impact on genomics[END_REF]. Such strings commonly fuel up a gamut of applications; in particular, frequent pattern mining applications [START_REF] Charu | Applications of frequent pattern mining[END_REF]. For example, frequent pattern mining from location history data facilitates route planning [START_REF] Chen | Mining moving patterns for predicting next location[END_REF]; frequent pattern mining from market-basket data facilitates business decision making [START_REF] Agrawal | Mining sequential patterns[END_REF]; frequent pattern mining from genome sequences facilitates clinical diagnostics [START_REF] Daniel | The next-generation sequencing revolution and its impact on genomics[END_REF]. To support these applications in a privacy-preserving manner, individual sequences are often being disseminated after they have been sanitized.

Towards this end, Bernardini et al. have recently formalized the following string sanitization problem under edit distance [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF]. Let W be a string of length n over an alphabet Σ, k be a positive integer, and S be a set of length-k substrings of W . Set S is conceptually seen as an antidictionary: a set of sensitive patterns modelling private or confidential information. The ETFS problem (Edit distance, Total order, Frequency, Sanitization) asks us to construct a string X ED such that: (i) no string of S occurs in X ED ; (ii) the order of all other length-k substrings over Σ is the same in W and in X ED ; and (iii) X ED has minimal edit distance to W . In order to obtain a feasible solution string, we may need to extend Σ to Σ # = Σ {#}, which includes a special letter # / ∈ Σ.

Example 1. Let W = ecabaaaaabbbadf over alphabet Σ = {a, b, c, d, e, f} be the input string. Further let k = 3 and the set of sensitive patterns be S = {aba, baa, aaa, aab, bba}. Consider the following three feasible (sanitized) strings: X TR = ecab#abb#bbb#badf, X MIN = ecabbb#badf and X ED = ecab#aa#abbb#badf. All three strings contain no sensitive pattern and preserve the total order and thus the frequency of all non-sensitive length-3 patterns of W : X TR is the trivial solution of interleaving the non-sensitive length-3 patterns of W with #; X MIN is the shortest possible such string; and X ED is a string closest to W in terms of edit distance.

A simple O(n 2 k|Σ|)-time solution [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF] to ETFS can be obtained via employing approximate regular expression matching. Consider the regular expression R that encodes all feasible solution strings. The size of R is O(nk|Σ|). By aligning W and R using the standard quadratic-time algorithm [START_REF] Myers | Approximate matching of regular expressions[END_REF], we obtain an optimal solution X ED in O(n 2 k|Σ|) time for ETFS. Bernardini et al. showed that this can be improved to O(n 2 k) time [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF]. Let us informally describe their algorithm. (A formal description of their algorithm follows in the preliminaries section.) We use a dynamic programming (DP) table similar to the standard edit distance algorithm. We write the letters of the input string W on the top of the first row. Since we do not know the exact form of the output string X ED , we write the non-sensitive length-k patterns to the left of the first column interleaved by special # letters. We then proceed to fill this table using recursive formulae. The formulae are more involved than the edit distance ones to account for the possibility to merge consecutive non-sensitive patterns (e.g., eca and cab are merged to ecab in Example 1) and to expand the #'s into longer gadgets that may contain up to k -1 letters from Σ (e.g., #aa# in Example 1). Once the DP table is filled, we construct an X ED by tracing back an optimal alignment.

Bernardini et al. also showed, via a reduction from the weighted edit distance problem [START_REF] Bringmann | Quadratic conditional lower bounds for string problems and dynamic time warping[END_REF], that ETFS cannot be solved in O(n 2-δ ) time, for any δ > 0, unless the strong exponential time hypothesis (SETH) [START_REF] Impagliazzo | On the complexity of k-sat[END_REF][START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] is false. We were thus also motivated to match this lower bound.

Our Results and Techniques Our first main result is the following.

Theorem 1. The ETFS problem can be solved in O(n 2 log 2 k) time.
We also consider a generalized version of ETFS, which we denote by AETFS (Arbitrary lengths, Edit distance, Total order, Frequency, Sanitization). The only difference in AETFS with respect to ETFS is that S can contain elements (sensitive patterns) of arbitrary lengths. This generalization is evidently more useful as it drops the restriction of fixed-length sensitive patterns; it also turns out to be algorithmically much more challenging. In both ETFS and AETFS, we make the standard assumption that substrings of W are represented as intervals over [0, n -1], and thus each element in S has an O(1)-sized representation. We further assume that S satisfies the properties of closure and minimality, which in turn ensure that S has an O(n)-sized representation.

Example 2. Consider the same input string W = ecabaaaaabbbadf as in Example 1. Further let k = 3 and the set of sensitive patterns be S = {aba, aa, abbba}. Then, string Y ED = ecab#abb#bbbadf is a feasible string and is a closest to W in terms of edit distance. Notice that, we cannot merge all of the three consecutive non-sensitive patterns abb, bbb, and bba into one since it will result in an occurrence of the sensitive pattern abbba; we thus rather create abb#bbba.

Our second main result is the following.

Theorem 2. The AETFS problem can be solved in O(n 2 log 2 n) time.

Our algorithms are thus optimal up to polylogarithmic factors, unless SETH fails. Let us also stress that our algorithms work under edit distance with arbitrary weights at no extra cost.

Let us describe the main ideas behind the new techniques we develop. As in Example 2, a sensitive pattern of length greater than k might be generated by merging multiple non-sensitive patterns. In AETFS, we have to consider avoiding such invalid merge operations. If we enumerate all valid combinations of merging non-sensitive patterns, and run the DP for ETFS for all the cases, then we can obtain an optimal solution to AETFS. Our main idea for reducing the time complexity is to carefully maintain a directed acyclic graph (DAG) for representing all such valid combinations. We first construct the DAG, and then plug a small DP table into each node of the DAG. This technique gives us an O(n 3 )-time solution to AETFS. To achieve Õ(n 2 ) time, we focus on redundancy in the DP tables. When the size of the DP tables is large, there must be multiple sub-tables corresponding to the same pair of strings. Before propagating, we precompute lookup table structures of size O(n 2 log 2 n) according to dyadic intervals on [0, n -1]. To this end, we modify the data structure proposed in [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF]. Then, we decompose the DP tables into sub-tables according to these dyadic intervals. We compute only boundaries of such sub-tables using the precomputed lookup table structures, and thus, we obtain an optimal alignment for AETFS in O(n 2 log 2 n) total time. By applying the same technique to ETFS, we obtain an O(n 2 log 2 k)-time solution, which improves the state of the art by a factor of k/ log 2 k [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF]. As a bonus, we show how to (non-trivially) modify the Four Russians [START_REF] Arlazarov | On economical construction of the transitive closure of an oriented graph[END_REF] and the LZ78-factorization [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] techniques, which speed up the standard edit distance computation [START_REF] William | A faster algorithm computing string edit distances[END_REF][START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF], to be applied to ETFS and AETFS.

In a nutshell, our main technical contribution is that we manage to align a string of length n and a specific regular expression of size Ω(nk|Σ|) in Õ(n 2 ) time. We can also view the solution spaces of ETFS and AETFS as context-free languages. The main idea of our AETFS algorithm is to first preprocess a set of non-terminals N , such that we can later use them in O(n) time each. We then write the context-free language as a new language, which is accepted by a Deterministic Acyclic Finite State Automaton (DASFA), taking the set N as its terminals. In this paper, we develop several techniques to reduce the size of the DAFSA (cf. DAG) to Õ(n) and efficiently precompute the set N (cf. lookup tables) in Õ(n 2 ) time. Thus, beyond string sanitization, our techniques may inspire solutions to other problems related to regular expressions or context-free grammars.

Paper Organization Section 2 introduces the basic definitions and notation used throughout, and also provides a summary of the currently fastest algorithm for ETFS [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF]. In Section 3, we describe our lookup table structures. In Section 4, we present the O(n 3 )-time algorithm for solving AETFS. This algorithm is refined to an Õ(n 2 )-time algorithm, which is described in Section 5. Along the way, in Section 5, we also describe an Õ(n 2 )-time algorithm for ETFS. In Section 6 we show how to utilize the Four Russians and the LZ78-factorization techniques for our problems.

Preliminaries

Strings An alphabet Σ is a finite set of elements called letters. Let S = S[0]S [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF] . . . S[n -1] be a string of length |S| = n over an alphabet Σ of size σ = |Σ|. Let Γ = { , ⊕, ⊗} be a set of special letters with Γ ∩ Σ = ∅. By Σ * we denote the set of all strings over Σ, and by Σ k the set of all length-k strings over Σ. For two indices 0 ≤ i ≤ j ≤ n -1, S[i . . j] = S[i] . . . S[j] is the substring of S that starts at position i and ends at position j of S. By ε we denote the empty string of length 0. A prefix of S is a substring of the form S[0 . . j], and a suffix of S is a substring of the form S[i . . n -1]. Given two strings U and V we say that U has a suffix-prefix overlap of length > 0 with V if and only if the length-suffix of U is equal to the length-prefix of V , i.e.,

U [|U | -. . |U | -1] = V [0 . . -1].
We fix a string W of length n over an alphabet Σ. We assume that Σ = {1, . . . , n O(1) }. If this is not the case, we use perfect hashing [START_REF] Michael | Storing a sparse table with 0(1) worst case access time[END_REF] to hash W [i], for all i ∈ [1, n], and obtain another string over Σ = {1, . . . , n} in O(n) time with high probability or in O(n log n) time deterministically via sorting. We consider the obtained string to be W . We also fix an integer 0 < k < n. Unless specified otherwise, we refer to a length-k string or a pattern interchangeably. An occurrence of a pattern is uniquely defined by its starting position. Let S k be the set representing the sensitive patterns as starting positions over {0, . . . , n -k} with the following closure property: for every i ∈ S k , any j for which W [j . . j + k -1] = W [i . . i + k -1], must also belong to S k . That is, if an occurrence of a pattern is in S k , then all its occurrences are in S k . A substring W [i . . i + k -1] of W is called sensitive if and only if i ∈ S k ; S k is thus the complete set of occurrences of sensitive patterns. The difference set I = {0, . . . , n -k} \ S k is the set of occurrences of non-sensitive patterns.

For any substring U , we denote by I U the set of occurrences in U of non-sensitive length-k strings over Σ. (We have that I W = I.) We call an occurrence i the t-predecessor of another occurrence j in I U if and only if i is the largest element in I U that is less than j. This relation induces a strict total order on the occurrences in I U . We call a subset J of I U a t-chain if for all elements in J except the minimum one, their t-predecessor is also in J . For two strings U and V , chains J U and J V are equivalent, denoted by J U ≡ J V , if and only if

|J U | = |J V | and U [u . . u + k -1] = V [v . . v + k -1],
where u is the j-th smallest element of J U and v is the j-th smallest of J V , for all j ≤ |J U |.

Given two strings U and V the edit distance d E (U, V ) is defined as the minimum number of elementary edit operations (letter insertion, deletion, or substitution) that transform one string into the other. Each edit operation can also be associated with a cost: a fixed positive value. Given two strings U and V the weighted edit distance d WE (U, V ) is defined as the minimal total cost of a sequence of edit operations to transform one string into the other. We assume throughout that the three edit operations all have unit weight. However, our algorithms also work for arbitrary weights at no extra cost. The standard algorithm to compute the edit distance between two strings U and V [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] works by creating a The ETFS Problem We formally define ETFS, one of the problems considered in this paper.

(|U |+1)×(|V |+1) DP table D with D[i][j] = d E (U [0 . . i-1], V [0 . . j-1]). The sought edit distance is thus d E (U, V ) = D[|U |][|V |].
Problem 1 (ETFS). Given a string W of length n, an integer k > 1, and a set S k (and thus set I), construct a string X ED which is at minimal (weighted) edit distance from W and satisfies: C1 X ED does not contain any sensitive pattern. P1 I W ≡ I X ED , i.e., the t-chains I W and I X ED are equivalent.

The AETFS Problem The length of sensitive patterns in the ETFS setting is fixed. In what follows, we define a generalization of the ETFS problem which allows for arbitrary length sensitive patterns. Let S be a set of intervals with the two following properties (closure property and minimality property): (i) For every [i, j] ∈ S, any [i , j ] for which W [i . . j ] = W [i . . j], must also belong to S; and (ii) any proper sub-interval of [i, j] is not in S. It is easy to see that |S| ≤ n from its minimality. Now, we redefine notions of sensitive and non-sensitive patterns as follows: A sensitive pattern is an arbitrary length substring W [i . . j] of W for each [i, j] ∈ S. For a fixed k, a non-sensitive pattern is a length-k substring of W containing no sensitive pattern as a substring.

Problem 2 (AETFS). Given a string W of length n, an integer k > 1, and a set S (and thus set I), construct a string Y ED which is at minimal (weighted) edit distance from W and satisfies: C1 Y ED does not contain any sensitive pattern. P1 I W ≡ I Y ED , i.e., the t-chains I W and I Y ED are equivalent.

The ETFS-DP Algorithm. For independent reading we describe here ETFS-DP, the algorithm from [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF] that solves the ETFS problem in O(n 2 k) time. The output string X ED is a string that contains all non-sensitive patterns in the same order as in W . For each pair of consecutive non-sensitive patterns, their occurrences in X ED are either (i) overlapping by k -1 letters (e.g., eca and cab in Example 1) or (ii) delimited by a string over Σ ∪ {#} which contains no length-k string over Σ (e.g., #aa# in Example 1). We call such strings gadgets. For case (ii), we use the following regular expressions:

Σ <k = (a 1 |a 2 | . . . |a |Σ| |ε) k-1 ,
where Σ = {a 1 , a 2 , . . . , a |Σ| }. Also, the special letters , ⊕, ⊗ ∈ Γ correspond to regular expressions (Σ <k #) * , #(Σ <k #) * , and (#Σ <k ) * , respectively. Let N 0 , N 1 , . . . , N |I|-1 be the sequence of nonsensitive patterns sorted in the order in which they occur in W . In what follows, we fix string

T = N 0 ⊕ N 1 ⊕ • • • ⊕ N |I|-1 ⊗ of length (k + 1)|I| + 1.
String T corresponds to the regular expression R that represents the set of all feasible solutions (feasible strings) in which all nonsensitive patterns in the string are delimited by stings over Σ ∪ {#}. Moreover, we need to consider feasible strings in which a non-sensitive pattern overlaps the next one. Let M be a binary array of length |I| such that for each 0

≤ i ≤ |I| -1, M [i] = 1 if i > 0 and N i-1 has a suffix-prefix overlap of length k -1 with N i , and M [i] = 0 otherwise. Namely, M [i] = 1 implies that N i-1 and N i can be merged for 0 < i ≤ |I| -1. Let E be a table of size ((k + 1)|I| + 1) × (n + 1
). The rows of E correspond to string T defined above and the columns to string W . Note that the leftmost column corresponds to the empty string ε as in the standard edit distance DP table. Each cell E[i][j] contains the edit distance between the regular expression corresponding to T [0 . . i] and W [0 . . j -1]. We classify the rows of E into three categories: gadget rows; possibly mergeable rows; and ordinary rows. We call every row corresponding to a special letter in Γ a gadget row. Namely, rows with index i ≡ 0 mod (k + 1) are gadget rows. Also, we call every row corresponding to the last letter of a non-sensitive pattern a possibly mergeable row. Namely, rows with index i ≡ -1 mod (k + 1) are possibly mergeable rows. All the other rows are called ordinary rows. The recursive formula of ordinary rows is the same as in the standard edit distance solution:

E[i][j] = min      E[i -1][j] + 1, (insert) E[i][j -1] + 1, (delete) E[i -1][j -1] + I[T [i] = W [j -1]], (match or substitute),
where I is an indicator function:

I[T [i] = W [j -1]] = 1 if T [i] = W [j -1]
, and 0 otherwise. Next, consider a possibly mergeable row E[i][•] which is the last row of the non-sensitive pattern N h . If M [h] = 0, then the recursive formula is the same as that of ordinary rows. Otherwise (M [h] = 1), N h-1 and N h can be merged. Merging them means that the values in the previous mergeable row

E[i -k -1][•] will be propagated to E[i][•]
directly without considering the k rows below. Thus, the recursive formula is:

E[i][j] = min                E[i -1][j] + 1, (insert) E[i][j -1] + 1, (delete) E[i -1][j -1] + I[T [i] = W [j -1]],
(match or substitute)

E[i -k -1][j] + 1, if M [h] = 1 (insert and merge) E[i -k -1][j -1] + I[T [i] = W [j -1]], if M [h] = 1 (match or sub.

and merge).

Next, consider a gadget row E[i][•] which corresponds to a special letter in Γ. Because of the form of regular expressions corresponding to special letters, a # can either be inserted or substituted directly after a non-sensitive pattern, or be preceded by another # no more than k positions earlier. This results in the following recursive formula:

E[i][j] = min      E[i -1][j] + 1, (insert) E[i -1][j -1] + 1, (substitute) E[i][j -1] + 1, . . . , E[i][max{0, j -k}] + 1, (delete or extend gadget).
For completeness, we write down the recursive formula for initializing the leftmost column:

E[i][0] = E[i -k -1][0] + 1, if i ≡ -1 mod (k + 1) ∧ M [h] = 1 (merge) E[i -1][0] + 1, otherwise (no merge).
Unlike in the standard setting [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF], the edit distance between W and any string matching the regular expression R is not necessarily found in its bottom-right entry

E[|I|(k +1)][|W |].
Instead, it is found among the rightmost k entries of the last row (in case X ED ends with a string in ⊗), and the rightmost entry of the second-last row (when X ED ends with the last letter of the last non-sensitive pattern). After computing the edit distance value, we construct an X ED . To do so, when computing each entry E[i][j], we memorize a backward-pointer to an entry from which the minimum value for E[i][j] was obtained. We then construct X ED from right to left with respect to the sequence of edit operations corresponding to an optimal alignment obtained by the backward-pointers.

Compact Lookup Table Structure for Squared Blocks

In this section we consider the standard edit distance table, and propose a data structure which can answer some queries on a b × b sub-table of the DP table, which we call a block, corresponding to two strings of the same length. Our data structure is similar to the one proposed in [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF], tailored, however, to our needs. We next provide some further definitions about blocks. Let B be a b × b block to be processed. The top (resp. bottom) row of B is called the input (resp. output) row of B. Similarly, the leftmost (resp. rightmost) column of B is called the input (resp. output) column of B. A cell in the input (resp. output) row or column is called an input (resp. output) cell.

In the following, we propose a lookup table for b × b blocks that compute all output cell values of a block in O(b) time for any given block and input cell values of the block. We modify the following known result to enhance it with a trace-back functionality. In [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF], the authors did not refer to tracing back, i.e., it is not clear how to obtain an optimal alignment using Theorem 3. We prove that we can trace back a shortest path to an output cell in a b × b block in O(b) time using O(b 2 log b) additional space. This yields an optimal alignment. We next briefly describe the data structure of Theorem 3, and explain how we modify it.

Constructing a Data Structure for a Pair of Strings

For constructing the data structure of Theorem 3, Brubach and Ghurye [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF] utilize the result of [START_REF] Schmidt | All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings[END_REF]. Instead, we use the following result by Klein [START_REF] Philip N Klein | Multiple-source shortest paths in planar graphs[END_REF], which is more general.

Theorem 4 ([25]

). Given an N -node planar graph with non-negative edge labels, we can construct a data structure of size O(N log N ) in O(N log N ) time such that given a node s in the graph and another node t on the boundary of the infinite face, the data structure can compute the maximum (or minimum) distance from s to t in O(log N ) time. Also, if the graph has constant degree, then we can compute the shortest s-t path in time linear in the length of the path.

The lookup table structure for a block is constructed as follows (see [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF] for details). Let B be a b × b block to be preprocessed. First, we regard B as a grid-graph of size b × b. Namely, each node corresponds to a cell in the block, and each edge corresponds to an edit operation. Also, each edge is labeled by the weight of its corresponding edit operation. Then, we construct the data structure of Theorem 4 for the grid-graph. We denote this data structure by D B . Next, for each input cell u and each output cell v, we compute the weight of the shortest path from u to v, and store them to table M B of size (2b -1) × (2b -1). Each row (resp. column) of M B corresponds to each output (resp. input) cell of B. A table is called monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum. It is totally monotone if the same property is true for every sub-table defined by an arbitrary subset of the rows and columns of the given table . It is known that we can construct M B so that it is totally monotone [START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF]. We thus construct D B and M B in O(b 2 log b) time and space.

By Theorem 3, the size of the final data structure (that depends on the size of M B ) is O(b 2 ). However, O(b 2 log b) working space is used for constructing D B . In our algorithm, we also use table M B and keep the temporary data structure D B to support tracing back operations efficiently.

Answering Queries and Tracing Back

Given a query input row and column, we can compute the output row and column in O(b) time using the SMAWK algorithm [START_REF] Aggarwal | Geometric applications of a matrix-searching algorithm[END_REF] for finding the minimum value in each row of an implicitly-defined totally monotone table, since M B is totally monotone [START_REF] Brubach | A succinct four Russians speedup for edit distance computation and one-against-many banded alignment[END_REF]. Note that, for each output cell v of B, we can also obtain an input cell s v which is the starting cell of a shortest path ending at v from the result of SMAWK algorithm. Thus, by using data structure D B , we can obtain a shortest s v -v path in time linear in the length of the path. To summarize, we obtain the following lemma. Note that this data structure works under edit distance with arbitrary weights at no extra cost.

Sensitive Patterns of Arbitrary Lengths

In this section we propose a data structure with which we can solve the AETFS problem in time O(n 3 ). First, let us consider whether ETFS-DP can be applied directly to the AETFS problem. The AETFS problem is a generalization of the ETFS problem, and there are some differences between them: if there exists a long sensitive pattern of length longer than k, then we cannot apply the same logic for the possibly mergeable rows to the AETFS problem. This is because merging multiple non-sensitive patterns of length k may create a long sensitive pattern, while this sensitive pattern must be hidden. In contrast, if there exists a short sensitive pattern of length less than k, then we cannot apply the same logic for the gadget rows to the AETFS problem, since this may introduce a short sensitive pattern in a gadget. Thus AETFS is much more challenging.

Let L = O(n 2 ) denote the total length of long sensitive patterns. As a first step towards our main result, we prove the following lemma. Note that Lemma 2 yields O(n 2 k) time for ETFS because in this case L = 0. Lemma 2 thus generalizes Theorem 2 in [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF]. In what follows, we propose a new data structure for solving the AETFS problem and prove Lemma 2. The main idea is to use multiple DP tables and link them under specific rules. Interestingly, our data structure is shaped as a DAG consisting of DP tables.

Long Sensitive Patterns

If there is a long sensitive pattern, we need to consider the case where multiple non-sensitive patterns are contained in a single sensitive pattern. (Recall that all non-sensitive patterns have fixed length k.) In this case, we cannot apply the ETFS-DP algorithm from [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF] directly.

Let us consider the situation in which we have just finished computing a possibly mergeable row. We may be able to choose the next move from two candidates: either go down to the next (gadget) row or jump to the next possibly mergeable row if possible. We consider a decision tree T that represents all combinations of such choices at all possibly mergeable rows (inspect Figure 1). We regard T as a tree of tables, i.e., each node of T represents a small DP table. Let E[0 . . (k + 1)|I|][0 . . n] be the DP table of the ETFS-DP algorithm described in Section 2. There are three types of nodes in T : root, #-node, and m-node. The root represents sub-table

E[0 . . k][0 . . n]. For each depth b with 1 ≤ b ≤ |I| -1, the #-node at depth b represents sub- table E[b(k + 1) . . (b + 1)(k + 1) -1][0 . . n],
and each m-node at depth b represents a copy of possibly mergeable row E[(b + 1)(k + 1) -1][0 . . n]. Each edge (u, v) of T means that the bottom row values of u will be propagated to the top row of v. If there are multiple incoming edges (u 1 , v), (u 2 , v), . . . , (u p , v) of a single node v, then we virtually consider a row r[0 . . n] as the previous possibly mergeable row of v such that r[j] is the minimum value between all j-th values in the last rows of u 1 , u 2 , . . . , u p for each 0 ≤ j ≤ n. We call a path that consists of only m-nodes an m-path.

We can solve the AETFS problem if we can simulate all valid combinations of merge operations represented by T . However, we do not have to check all combinations explicitly. This is due to the [START_REF] Aggarwal | Geometric applications of a matrix-searching algorithm[END_REF][START_REF] Bonomi | An information-theoretic approach to individual sequential data sanitization[END_REF], [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Bringmann | Quadratic conditional lower bounds for string problems and dynamic time warping[END_REF]}. fact that we can prune branches and merge nodes in the decision tree T as follows 6 .

For incremental b = 1, 2, . . . , |I| -1, we edit T according to the following four rules: Finally, we add the sink node under the decision tree such that the sink node corresponds to the bottom row E[|I|(k + 1)][0 .

. n], and each node at depth |I| -1 has only one outgoing edge to the sink node. We also rename the root to the source node.

After executing all pruning and merging operations, the decision tree becomes a DAG whose all source-to-sink paths represent all valid choices (inspect Figure 2). We call such DAG the decision DAG, and we denote it by G. Although the size of T can be exponentially large, we can directly construct G in a top-down fashion from an instance of AETFS in O(|G|) time.

Correctness We show that no valid path is eliminated and all invalid paths are eliminated while constructing G from T . Clearly, crossing #-nodes creates no invalid path. In what follows, we mainly focus on m-nodes that can create invalid paths.

It is easy to see that a path (v 1 , v 2 , . . . , v p ) is invalid if and only if (i) there is a sub-path (v s , . . . , v t ) where v s and v t respectively correspond to the length-k prefix and suffix of the same sensitive pattern, and v s+1 , • • • , v t are all m-nodes or (ii) there is an edge (v i-1 , v i ) such that M [d i ] = 0 where d i is the depth of v i . By Rule 1, we delete all invalid paths which satisfy condition (ii), and do not delete any valid path. By Rule 2, we delete an invalid path which satisfies condition (i), and do not delete any valid path. By Rule 3, we merge #-nodes, however, it does not matter since this operation does not cause deleting or creating any path. By Rule 4, we may merge mnodes, however, the m-nodes to be merged are carefully chosen to not interfere with Rule 2. Thus, this also does not cause deleting or creating any path. Therefore, G is constructed correctly.

The Size of the DAG We next analyze the size of G. Clearly, the total number of #-nodes is equal to |I| -1. Also, the source node and the sink node are unique. The number of m-nodes, each of which is a child of some #-node, is equal to the number of #-nodes, i.e., |I| -1. The number of the rest of m-nodes is at most L. Also, each node has at most two outgoing edges.

Each #-node and the source node represent a sub-table of size (k + 1) × (n + 1). Each m-node represents a possibly mergeable row, and the sink node represents the last gadget row. Therefore, the total size of G is O(|I|kn + |I|n + Ln) = O(k|I|n + Ln).

Time Complexity

The decision DAG G is computed in O(k|I| + L) time without creating the original decision tree T by applying the above four rules for incremental b = 1, 2, . . . , |I| -1. Also, we can compute each cell in G in amortized constant time [START_REF] Bernardini | String Sanitization Under Edit Distance[END_REF]. Thus, the total time is O(k|I|n+Ln).

Short Sensitive Patterns

Running the ETFS-DP algorithm may introduce short sensitive patterns in its gadgets. We explain how to modify the recursive formulae of the gadget row to account for short sensitive patterns. We first prove that w.l.o.g. all gadgets are either a single # or can be optimally aligned such that:

1. All #'s in gadgets are substituted by letters in W ; 2. All letters in gadgets are matched with letters in W ; and

No further letters are inserted between letters of the same gadget.

If some extra inserted letters of W are aligned with a gadget, we can add some extra #'s to change them into substitutions without increasing the cost, changing the number of non-sensitive patterns or increasing the number of sensitive patterns. Similarly, if some letters of the gadget are not matched with the same letters in W , these gadget letters can be replaced by #. Finally, if some #'s in the gadget are not aligned with any letter in W , we can either remove them or move them to the place of an adjacent gadget letter while deleting that letter. Inspect the following example. (2) all letters are matched with letters in W ; and (3) no further letters are inserted between the gadget's letters. Note that the rightmost gadget is a single # and so the modified alignment satisfies all conditions above.

A single # cannot introduce any sensitive pattern, so just as in the ETFS-DP algorithm we can get a cost of

E[i -1][j] + 1 corresponding to the case that a single # is inserted after W [j -1] or a cost of E[i -1][j -1] + 1 corresponding to the case that a single # is aligned with W [j -1].
For longer gadgets the possibilities are a bit more restricted than in the ETFS-DP algorithm. Assuming the gadget to have the structure described above, it follows that the previous # cannot be aligned before W [F [j-1]], where F [j] is defined to be the largest integer such that W [F [j] . . j-1] contains a sensitive or non-sensitive pattern (if it exists). More formally:

F [j] = max({i < j | W [i . . j -1] contains a sensitive pattern} ∪ {j -k} ∪ {0}).
F can be computed in O(kn) time. We denote the point-wise minimum of the copies of the preceding merge row with r; in the case of ETFS this is just the previous merge row. This gives us the following formula for the gadget rows. For all 0 ≤ i ≤ (k + 1)|I| with i ≡ 0 mod k + 1,

E[i][j] = min      r[j] + 1 r[j -1] + 1 E[i][j -1] + 1, E[i][j -2] + 1, . . . , E[i][F [j -1] + 1] + 1.
(Notice that a string position and its corresponding table index differ by one.)

To conclude, we also need to consider the range in which the edit distance value lies. Since the last row corresponds to ⊗, the value stored in E[|I|(k + 1)][j], for all 0 ≤ j ≤ n, is the cost of an optimal alignment between W [0 . . j + e j -1] and a string in the regular expression whose length-(e j + 1) suffix is #W [j . . j + e j -1], where e j = min(max{e | W [j . . j + e -1] does not contain any sensitive or non-sensitive pattern} ∪ {n -j}). The edit distance between W and any string matching the regular expression is found among the rightmost n -F [n] entries of the last row or the rightmost entry of the second-last row. Thus, we obtain:

d E (Y ED , W ) = min E[|I|(k + 1) -1][n], E[|I|(k + 1)][n], E[|I|(k + 1)][n -1], . . . , E[|I|(k + 1)][F [n] + 1].
For each E[i][j] and r[j] we store a pointer to an entry which leaded to this minimum value. We can then trace back as in ETFS-DP, taking the minimizing entry of the above equation as a starting point, and obtain Y ED in an additional O(kn) time. Therefore the total time complexity of AETFS is O(k|I|n + Ln) and we arrive at Lemma 2.

Õ(n 2 )-Time Algorithms using Dyadic Intervals

In this section we improve ETFS-DP and the algorithm of Lemma 2. We first show an algorithm to compute gadget rows in amortized constant time per cell in the rows. Secondly, we focus on the Time Complexity Precomputing a lookup table for two strings of length up to 2 i takes O(2 2i i) time. In total this gives a precomputation time of

O   log k i=0 n 2 i • n 2 i • 2 2i i   = O(n 2 log 2 k).
Each possibly mergeable row can now be computed in O(n log k) time from the previous merge and gadget row, since each non-sensitive length-k pattern can be partitioned into at most 2 log k + 2 precomputed strings. Gadget rows can be computed in O(n) time each from the preceding possibly mergeable rows using the technique described by Lemma 3.

For the traceback, note that |X ED | = O(kn), i.e., the length of an optimal alignment path over E is O(kn). We do not know how the path behaves inside each block. However we can compute the sub-path inside a block in time linear in the path's length by using Lemma 1. The gadget rows can be traced back in a further O(n) time. Thus, we can trace back in a total time of O(kn). Therefore the total time complexity is O(n 2 log 2 k). We arrive at the following result.

Theorem 1. The ETFS problem can be solved in O(n 2 log 2 k) time.

AETFS in O(n 2 log 2 n) Time

In this section we describe how to further reduce the decision DAG G from Section 4 by precomputing parallel m-paths. First, we give some observations for m-paths. An m-path is said to be maximal if the m-path cannot be extended either forward or backward. Any two maximal m-paths do not share any nodes, since every m-node in G has at most one outgoing edge to m-nodes and at most one incoming edge from m-nodes. Also, the number of maximal m-paths is at most |I| since the parent of the first m-node of each maximal m-path is a different #-node or the source node. In what follows, suppose G contains a total of p maximal m-paths of length 1 , . . . , p with p i=1 i ≤ n + n, where is the length of the longest sensitive pattern. Recall that an m-node represents a possibly mergeable row of size 1 × (n + 1), and thus, we will identify an m-path of length x with a DP table of size x × (n + 1).

Let us now describe our DAG reduction. An example of the DAG reduction is demonstrated in Figure 3. In the prepocessing phase, we first construct a lookup table structure for all possible mpaths corresponding to dyadic intervals of lengths at most over the range [1, |I| -1] of the depths of m-paths, in a similar way as in Section 5.2. Next, for each maximal m-path in G, we decompose it into shorter m-paths according to dyadic intervals. We then contract each such m-path into a single node named j-node consisting of a single row, which jumps from the beginning of the m-path to the end and represent consecutive merges. Also, we have to take into account edges leaving the m-path. Note that paths that leave the m-path early always leave to a #-node, so we do not have to worry about introducing any sensitive patterns. We therefore create a new copy of the m-path preceded by an additional node named c-node consisting of a single row, which takes the point-wise minimum of the parent nodes of the m-paths.

After finishing the DAG reduction, we fill the DP tables from top to bottom: all j-nodes are computed by using the lookup table; all new m-paths are computed in the original fashion, including all outgoing edges; and all the other nodes are computed as in Section 5.2. Also, we can trace back and find the solution to AETFS by storing appropriate backward-pointers and the data structures of Lemma 1 just as in Section 5.2. We contract each m-path to a j-node corresponding to the case in which four consecutive non-sensitive patterns are merged. Also, we create an m-path of length 3 preceded by a c-node corresponding to the case in which at least one gadget is inserted.

Time Complexity

(n/2 i ) 2 blocks of size 2 i × 2 i each in O(2 2i i) time. We can also easily contract G in O(n 2 ) time by traversing the DAG. Note that the number of nodes in the original DAG is O(n 2 ) (Section 4.1). We partition each path of length i into at most 2(log + i / ) precomputed paths: at most i /2 log paths of length 2 log and at most 2 of each shorter length. Therefore the j-nodes can be computed in O(n • p i=1 2(log + i / )) = O(n 2 log ) time. The c-nodes and the following m-nodes can be computed in O(n 2 log ) time, because there is at most one c-or m-node per depth and per precomputed path length. The #-nodes can each be computed in O(n log 2 k) time using the method described in Section 5.2. Finally, tracing back takes only O(kn) time by using the backward-pointers and the data structures of Lemma 1.

Summarizing this section, we have shown that the AETFS problem can be solved in time O(n 2 log 2 k + min{n 2 log 2 , Ln}). We arrive at the following result.

Theorem 2. The AETFS problem can be solved in O(n 2 log 2 n) time.

Applying Four Russians and LZ78-Factorization

In this section we show how to apply the Four Russians [START_REF] Arlazarov | On economical construction of the transitive closure of an oriented graph[END_REF] and the LZ78-factorization [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] techniques, which speed up the standard edit distance computation [START_REF] William | A faster algorithm computing string edit distances[END_REF][START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF], to the ETFS and AETFS problems. The recursive formula of the ordinary rows is the same as that of edit distance. Thus, it is easy to see that we can partially apply the Four Russians technique to our problems. On the contrary, applying LZ78-factorization to our problems is nontrivial, since LZ78-factorization does not take into account gadget rows or possibly mergeable rows. We define a new factorization, which is an extension of LZ78, and show that we can modify the technique of [START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF] to ETFS and AETFS.

Applying the Four-Russians Method

We apply the Four Russians method to the ETFS problem. Let b ≤ k be the length of one side of a squared block. First, we create a lookup table for all possible σ 2b pairs of length-b strings over Σ. Each lookup entry is a data structure of Lemma 1 whose size is O(b 2 log b), and it can be constructed in O(b 2 log b) time. The total time to create the lookup table is O(σ 2b b 2 log b). Next, we decompose the DP table into b × b-sized blocks except for possibly mergeable rows and gadget rows. Since the number of blocks is O(k|I|n/b 2 ) and the computation time for propagation is O(b) per block, the total time for computing all boundaries of all blocks is O(k|I|n/b). Unlike the original Four Russians method [START_REF] William | A faster algorithm computing string edit distances[END_REF], we compute all possibly mergeable rows and gadget rows consisting of O(|I|n) cells. We can compute these rows in a total of O(|I|n) time by Lemma 3. For the AETFS setting, we can apply the Four Russians method above to each #-node and the source node in the decision DAG. Thus, we obtain the following corollary.

Corollary 1. The AETFS problem can be solved in O(n 2 + min{n 2 log 2 k, n 2 k log σ n } + min{n 2 log 2 , nL}) time.

Further Speedup for Highly Repetitive Strings

For highly repetitive strings, we can obtain a faster algorithm than Theorem 5 by modifying the method of [START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF]. We define the two following factorizations for a given string. A sequence of strings (s 0 , . . . , s t-1 ) is called a factorization of string S if and only if

s 0 • • • s t-1 = S. LZ78-factorization ([39]) A factorization LZ (W ) = (f 0 = ε, f 1 , . . . , f z ) of string W is called the LZ78-factorization of W if and only if each f i with 1 ≤ i ≤ z is the longest prefix of W [|f 0 . . . f i-1 | . . |W | -1] such that f i = f j c
for some j < i and letter c. The LZ78-trie of W is a rooted tree such that each node represents a factor f i , and there is an edge (f j , f i ) with label c if f i = f j c. Given a string W of length n, LZ (W ) and the LZ78-trie of S can be computed in O(n) time [START_REF] Nakashima | Constructing LZ78 tries and position heaps in linear time for large alphabets[END_REF]. See Figure 4 for examples of LZ78-factorization and LZ78-trie.

G-factorization

We define a new factorization based on the LZ78-factorization and the special letters Γ as follows. Let LZ (S) = (f 0 , . . . , f z ) be the LZ78-factorization of string S ∈ (Σ ∪ Γ) * . For every factor f i we check if f i = xcy for x ∈ Σ * , c ∈ Γ, and y ∈ (Σ ∪ Γ) * . If so, we further factorize it into three factors (x, c, y), and continue checking y recursively. After that, we rename the factors by (g 0 , . . . , g ). We call such a factorization the G-factorization of S, and we denote it by G(S). We define the G-trie, which is a variant of LZ78-trie, w.r.t. G-factorization. The G-trie of S is a rooted tree such that (1) each node u represents a multiset of factors {{g u 1 , . . . , g ut }} with g u 1 = • • • = g ut , (2) g u 1 = g v 1 if u = v, and (3) there is an edge (v, u) with label c ∈ Σ ∪ Γ if g u 1 = g v 1 c. Notice that, if S ∈ Σ * , then LZ (S) = G(S) and its G-trie is the same as its LZ78-trie. It should also be clear that |G(S)| ≤ |LZ (S)| + 2 c∈Γ |occ S (c)|, where occ S (c) denotes the total number of occurrences of letter c in S. See Figure 4 for examples of G-factorization and G-trie. Also, given LZ (S), we can compute G(S) in O(|S|) time. Finally, we show that we can construct the G-trie of S over Σ ∪ Γ from G(S) in O(|S|) time. We first construct the suffix tree of S in O(|S|) time [START_REF] Farach-Colton | On the sorting-complexity of suffix tree construction[END_REF]. Next, we compute the loci of all G-factors in G(S) in the suffix tree, and make them explicit in O(|S| + |G(S)|) time [START_REF] Kociumaka | A linear-time algorithm for seeds computation[END_REF], and then, we remove all the other nodes except for the loci from the suffix tree. Thus, we can construct G-trie of S in O(|S|) time. Utilizing G-factorization In the rest of this section, we prove the following theorem. First, we provide an overview of the algorithm of [START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF] for the standard edit distance problem. Let A and B be the input strings both of length n, and let z a and z b be respectively the size of the LZ78factorization of A and B. They first partition the DP table into z a × z b blocks each corresponding to a comparison of an LZ78 factor of A with an LZ78 factor of B. Each block implicitly holds the DIST table, which stores the minimal weights from all input cells of the block to all output cells of the block. It is known that DIST is totally monotone [START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF], and thus, given values of input cells we can compute all row and column maxima of DIST in time linear in the length of the boundary of the block by using the SMAWK algorithm [START_REF] Aggarwal | Geometric applications of a matrix-searching algorithm[END_REF]. The total size of DIST tables for all blocks is O(n 2 ); however, each block actually stores only one column of DIST and O(bnd ) pointers to previous blocks which store all the other columns, where bnd is the length of the boundary of the block. The total time and space complexity is O((z a + z b )n) ⊆ O( n 2 log σ n ). The correctness of their algorithm can be proved by using the following property of the LZ78-factorization. Property 1. Let LZ (S) = (f 0 , f 1 , . . . , f z ) be the LZ78-factorization of string S. For each LZ78factor f i with 0 < i ≤ z, there exists a factor f j such that j < i and f i = f j c for a letter c. Also, when f i is given, we can obtain such f j and c in constant time by using the LZ78-trie of S.

Since the G-factorization holds the same properties as the above, we can apply their method even if we use G-factorization instead. We consider the LZ78-factorization of W and the G-factorization of T , and then, apply their method to ETFS. Therefore, we obtain Theorem 6.

Note that Theorem 6 is at least as good as Theorem 5; and Corollary 2 is at least as good as Corollary 1. Actually, the size of the LZ78-factorization of a string of length n is in O(hn/ log σ n) for most strings (i.e. strings that are compressible), where 0 < h ≤ 1 is the entropy of the string [START_REF] Lempel | On the complexity of finite sequences[END_REF][START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF][START_REF] Jacquet | Asymptotic behavior of the lempel-ziv parsing scheme and digital search trees[END_REF][START_REF] Crochemore | A subquadratic sequence alignment algorithm for unrestricted scoring matrices[END_REF]. As a consequence, the ETFS problem can be solved in O(n 2 + (h W +h T )n 2 k log σ n

) time for such strings, where h W and h T are, respectively, the entropy of W and the entropy of T .

  Since we compute each table entry from the entries to the left, top and top-left in O(1) time, the algorithm runs in O(|U | • |V |) time. Moreover, we can find an optimal (minimum cost) alignment by tracing back through the table.

Theorem 3 (

 3 Theorem 1 in [12]). Given two strings both of length b corresponding to a b × b block, we can construct a data structure of size O(b 2 ) in O(b 2 log b) time such that given any values for the input row and column of the block, the data structure can compute the output row and column of the block in O(b) time.

Lemma 1 .

 1 Given two strings both of length b corresponding to a b × b block, we can construct a data structure of size O(b 2 log b) in O(b 2 log b) time such that given any values for the input row and column of the block, the data structure can compute the output row and column of the block in O(b) time. Furthermore, given an output cell v and any other cell u in the block, we can compute a shortest u-v path in time linear in the length of the path.

Lemma 2 .

 2 The AETFS problem can be solved in O(k|I|n + Ln) time.

Figure 1 :

 1 Figure 1: An example for pruning and merging a decision tree. The red arrow represents a long sensitive pattern, and blue arrows represent non-sensitive patterns. The tree on the top-left represents the decision tree after pruning or merging operations for depths b = 0, 1, 2. For b = 3, we merge two #-nodes by Rule 3. For b = 4, we prune an m-node by Rule 2, merge three #-nodes by Rule 3, and merge two m-nodes by Rule 4. Finally, we add the sink node at the bottom.

Figure 2 :

 2 Figure 2: The decision DAG for W = abaabbaababb, k = 4, and S = {[2, 7], [3, 10], [5, 11]}.

Rule 1 .Rule 2 .Rule 3 .Rule 4 .

 1234 If M [b] = 0, then prune all edges to m-nodes at depth b. If there is a path (v 1 , v 2 , . . . , v p ) such that the depth of v p is b, (v 2 , . . . , v p ) is an m-path, and v 1 and v p respectively corresponds to the length-k prefix and the length-k suffix of the same sensitive pattern, then prune the edge (v p-1 , v p ). If there are multiple #-nodes at depth b, then merge all of them into a single #-node. If there are multiple m-nodes {v 1 , v 2 , . . .} at depth b such that each u i does not correspond to the length-k prefix of any sensitive pattern, where u i is the parent of the starting node of the longest m-path ending at v i , then merge such m-nodes into a single m-node.

Example 3 .

 3 Let the following optimal alignment from Example 1 with cost 4. Gadgets are in red. e c a b -a a a a a b b -b a d f e c a b # a a # a b b b # b a d f We transform it to another optimal alignment of the same cost that respects the above conditions: e c a b a a a a a b b -b a d f e c a b # a # a b b b # b a d f Let us first consider the leftmost gadget: (1) #'s are substituted by letters in W ;

Figure 3 :

 3 Figure 3: An example of contracting a part of the decision DAG. Before contracting, there are three parallel m-paths each of length 2 2 = 4.We contract each m-path to a j-node corresponding to the case in which four consecutive non-sensitive patterns are merged. Also, we create an m-path of length 3 preceded by a c-node corresponding to the case in which at least one gadget is inserted.

Theorem 5 .

 5 The ETFS problem can be solved in O(n 2 + n 2 k log σ n ) time. Proof. From the above discussion, we can solve the ETFS problem in O(kn|I|/b+σ 2b b 2 log b+|I|n) time for b ≤ k. Then σ 2b b 2 log b ∈ O(n 2 ) for b = (log σ n)/2 yields the statement.

Figure 4 :

 4 Figure 4: Examples for LZ78-factorization, LZ78-trie, G-factorization, and G-trie of string T = aba ⊕ baa ⊕ baa ⊕ bbb⊗. Factorizations (f 0 = ε, f 1 , . . . , f 10 ) and (g 0 = ε, g 1 , . . . , g 14 ) of T are respectively the LZ78-factorization and the G-factorization of T . The tree on the left is the LZ78trie of T and the tree in the right is the G-trie of T .

Theorem 6 .

 6 The ETFS problem can be solved in timeO(n 2 + |LZ (W )|kn + |LZ (T )|n) ⊆ O(n 2 + n 2 k log σ n ).The following corollary immediately holds.Corollary 2. The AETFS problem can be solved in time O(n 2 + min{n 2 log 2 k, |LZ (W )|kn + |LZ (T )|n} + min{n 2 log 2 , nL}) ⊆ O(n 2 + min{n 2 log 2 k, n 2 k log σ n } + min{n 2 log 2 , nL}).

Once the merge operation is applied to the decision tree, it is no longer a tree. However, we continue calling it the decision "tree" for convenience.

Acknowledgments We wish to thank Grigorios Loukides (King's College London) for useful discussions about improving the presentation of this manuscript.

* Supported by the JSPS KAKENHI Grant Number JP20J11983. † Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

‡ Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. 5 The notation Õ(f ) denotes O(f • polylog(f )).

redundancy in the computation of ordinary rows, and propose an algorithm to compute them by using the lookup table structure of Section 3 according to dyadic intervals. These two improvements yield an Õ(n 2 )-time algorithm for ETFS. Finally, we employ a similar lookup table technique to contract m-paths in the decision DAG, which yields an Õ(n 2 )-time algorithm for AETFS as well.

Speeding Up Gadget Rows Computation

First, we show how to speedup the gadget rows computation. For each #-node u in the decision DAG G, we denote by d u the in-degree of u. Let G u [0 . . n] be the gadget row in u. For each

. n] be a possibly mergeable row of a node which has an edge pointing to u. The recursive formula for G u [i] is as follows:

Proof. Let us fix an arbitrary #-node u and omit subscripts related to u. Let r j be the index such that G[r j ] is the rightmost minimum value in the range G[F [j -1] + 1 . . j], and let m j = G[r j ] be that minimum value. Then, it can be seen that G[p] = m j + 1, for any r j < p ≤ j, since G[p] > G[r j ] and G[p] ≤ G[r j ] + 1 by the recursive formula. Clearly, r 0 = 0. We assume that r j-1 is known before computing G

, and r j = arg min{G[r j-1 ], G[j]}. Note that F is a non-decreasing array, i.e., F [j] ≥ F [j -1]. Thus, we can compute G[j] and r j in O(d) time.

By Lemma 3, we can compute all gadget rows in a total of O(n u∈G d u ) = O(n|I| + nL) time.

ETFS in O(n 2 log 2 k) Time

In this section we describe an algorithm which solves ETFS in O(n 2 log 2 k) time. The key to losing the factor k is the fact that the string T on the left is highly repetitive and only consists of substrings of the length-n string W (interleaved by some letters in Γ). Therefore we can compute the DP table efficiently using only few precomputed sub-tables as in the Four Russians method [START_REF] Arlazarov | On economical construction of the transitive closure of an oriented graph[END_REF].

First, we partition W into substrings of length 2 i (or shorter if 2 i |W |) for each i ∈ {0, 1, 2, . . . , log k }. This gives a set A of at most 2n different strings. Moreover, note that each length-k pattern in W can be written as the concatenation of at most 2 log k + 2 such strings.

For every pair of strings in (w 1 , w 2 ) ∈ A 2 with |w 1 | = |w 2 |, we precompute the lookup table for the strings w 1 and w 2 according to Lemma 1. Now we can compute the non-merge case of each possibly mergeable row using at most 2 • n/2 i precomputed lookup tables of size 2 i × 2 i (or smaller) for each i ∈ {0, 1, 2, . . . , log k }.


Huma Hameed

Ph.D Khurram Rehman
email: rehman_khurram@ymail.com

Anam Hameed

Abdul Qayuum

Preparation and characterization of pH responsive ionic cross-linked microparticles of mercaptupurine to target ulcerative colitis

Keywords: 6-Mercaptopurine, chitosan, casein, carrageenan, Ionic cross-linking

The objective of this study was the preparation of ionically-crosslinked 6-Mercaptopurine (6-MP) monohydrate microparticles through preparing polyelectrolyte complexes of drug and polymers. Polymers such as Chitosan, Casein and Carrageenan were used to prepare cross-linked microparticles, and sodium tripolyphosphate was used as cross-linker.Microparticles were characterized for their flow behavior, compressibility, percentage yield, micromeritic and entrapment efficiency. Scanning electron microscopy was conducted to understand the surface morphology of the microparticles and the result was correlated with the swelling index and percentage drug release. Mathematical modeling of drug release in order to determine the drug release kinetics was also determined to understand the mechanism involving the release of 6-Mercaptopurine from the microparticles. The ionic cross-linked microparticles were in the range of 664µm to 798µm particle size having good flow and compressibility properties with percentage yield were found to be from 77.5% to 87.5% in range. The entrapment efficiency for the formulations were found to be from 63.5% to 83.5%, with MCP-5 gavemaximum entrapment efficiency of 83.5%. In vitro swelling and drug releasestudies were in accordance with the polymer properties followingzero order model with super-case transport II.

Introduction

Colorectal cancer is the one of the most common cancer accounting for 10-11% of cancer cases in both males and females. Generally, it is third leading cause of death in cancer patients, predominantly a malignant disease of elderly people [START_REF] Korelitz | Histological healing favors lower risk of colon carcinoma in extensive ulcerative colitis[END_REF][START_REF] Siegel | CA: a cancer journal for clinicians[END_REF] .Patients suffering from ulcerative colitis and Crohn's disease have high risk of colon cancer [START_REF] Freeman | Colorectal cancer risk in Crohn's disease[END_REF] . Targeted drug delivery to colon should ideally be capable of protecting the drug delivered to the colon i.e. drug release and absorption should not occur in the stomach as well as the small intestine and neither the bioactive agent should be degraded in either of the dissolution sites but only released and absorbed once the system reaches the colon. Colon targeted drug delivery systems have gained a great deal of attention as potential carriers for the local treatment of colonic diseases with reduced systemic side effects and also for the enhanced oral delivery of various therapeutics vulnerable to acidic and enzymatic degradation in the upper gastrointestinal tract [START_REF] Lee | Strategic Approaches for Colon Targeted Drug Delivery: An Overview of Recent Advancements[END_REF] . Colon-targeted drug delivery systems for macromolecules can provide therapeutic benefits including better patient and lower costs. To achieve more efficient colonic drug delivery for local or systemic drug effects, various strategies have been explored including pH-dependent systems [START_REF] Maroni | Enteric coatings for colonic drug delivery: state of the art[END_REF][START_REF] Krishnamachari | Development of pH-and time-dependent oral microparticles to optimize budesonide delivery to ileum and colon[END_REF] , enzyme-triggered systems [START_REF] Kotla | Bioresponsive drug delivery systems in intestinal inflammation: State-of-the-art and future perspectives[END_REF] , and polymeric nano/microparticles [START_REF] Lee | Strategic Approaches for Colon Targeted Drug Delivery: An Overview of Recent Advancements[END_REF][START_REF] Zeeshan | Advances in orally-delivered pH-sensitive nanocarrier systems; an optimistic approach for the treatment of inflammatory bowel disease[END_REF] . Previously polymeric microparticles for the purpose of controlled drug delivery were produced by chemically crosslinking with glutaraldehyde [START_REF] Shu | Chitosan/gelatin microspheres prepared by modified emulsification and ionotropic gelation[END_REF] , sodium hydroxide and ethylene glycoldiglycidyl ether [START_REF] Ko | Preparation and characterization of chitosan microparticles intended for controlled drug delivery[END_REF] . However, these chemical crosslinking agents have possibility of inducing undesirable effects [START_REF] Shu | Chitosan/gelatin microspheres prepared by modified emulsification and ionotropic gelation[END_REF] . To overcome this disadvantage of chemical cross-linking, ionic crosslinking interaction has been favored [START_REF] Elzoghby | Novel ionically crosslinked casein nanoparticles for flutamide delivery: formulation, characterization, and in vivo pharmacokinetics[END_REF][START_REF] Bhumkar | Studies on effect of pH on cross-linking of chitosan with sodium tripolyphosphate: a technical note[END_REF] . The ionic crosslinking of polymers with sodium tripolyphosphate (TPP), leads to formation of biocompatible cross-linked nano or microparticles, which can be efficiently employed in drug delivery and even delivery of vaccines and proteins [START_REF] Bhumkar | Studies on effect of pH on cross-linking of chitosan with sodium tripolyphosphate: a technical note[END_REF][START_REF] Sedyakina | Modulation of Entrapment Efficiency and In Vitro Release Properties of BSA-Loaded Chitosan Microparticles Cross-Linked with Citric Acid as a Potential Protein-Drug Delivery System[END_REF] . The cross-linking of polymers can allow modulation of drug release and extend its range of potential applications in drug delivery.

The aim of this study was to develop pH responsive, ionically-crosslinked drug-polymeric microparticles, colon targeted drug delivery system. For this purpose, ionically-crosslinked 6-Mercaptopurine monohydrate microparticles were prepared. 6-Mercaptopurine monohydrate belongs to antimetabolites that can prevent the biosynthesis of normal cellular metabolites [START_REF] Desai | Preparation of cross-linked chitosan microspheres by spray drying: Effect of cross-linking agent on the properties of spray dried microspheres[END_REF] . It has been used with other chemotherapy drugs for the treatment of different types of acute leukemias [START_REF] Karim | Differential role of thiopurine methyltransferase in the cytotoxic effects of 6-mercaptopurine and 6-thioguanine on human leukemia cells[END_REF] . It is also effective in the treatment of inflammatory bowel disease (IBD) including Crohn's disease and ulcerative colitis, and arthritis [START_REF] Kevadiya | Evaluation of clay/poly (l-lactide) microcomposites as anticancer drug, 6-mercaptopurine reservoir through in vitro cytotoxicity, oxidative stress markers and in vivo pharmacokinetics[END_REF][START_REF] Korelitz | Expert opinion: experience with 6-mercaptopurine in the treatment of inflammatory bowel disease[END_REF][START_REF] Pb | Anti-cancerous efficacy and pharmacokinetics of 6-mercaptopurine loaded chitosan nanoparticles[END_REF] . 6-Mercaptopurine also helps to decrease the dose of steroids in patients with IBD, and also reduce their dependence on steroids [START_REF] Korelitz | Expert opinion: experience with 6-mercaptopurine in the treatment of inflammatory bowel disease[END_REF][START_REF] Nagy | Efficacy of 6-mercaptopurine treatment after azathioprine hypersensitivity in inflammatory bowel disease[END_REF] .Although 6-mercaptopurine is known for its toxicity [START_REF] Govindappa | Toxicity evaluation of 6mercaptopurine-Chitosan nanoparticles in rats[END_REF] but attempts have been made to control the toxicity via polymeric controlled drug delivery systems [START_REF] Kevadiya | Evaluation of clay/poly (l-lactide) microcomposites as anticancer drug, 6-mercaptopurine reservoir through in vitro cytotoxicity, oxidative stress markers and in vivo pharmacokinetics[END_REF][START_REF] Pb | Anti-cancerous efficacy and pharmacokinetics of 6-mercaptopurine loaded chitosan nanoparticles[END_REF] . Microparticles of 6-Mercaptopurine were prepared by ionic gelation and emulsification techniques using natural polymers due to their biocompatible nature. In this study, Chitosan (CS), Casein (CAS), and carrageenan (CRG) polymers were used along with sodium tripolyphosphate (TPP) as a crosslinker.The microparticles were evaluated for surface morphology and shape by scanning electron microscopy (SEM), percentage yield, micromeritic properties, encapsulation efficiency, in-vitro swelling index and in-vitro drug release studies by applying kinetic models.

Materials and methods

Materials

6-Mercaptopurine monohydrate (Pharmedic Laboratories (Pvt.) Ltd. Pakistan), Chitosan, Sodium caseinate, sodium tripolyphosphate, ethanol, glacial acetic acid, dichloromethane,tween 80 were commercially obtained from Sigma-Aldrich (United States). Sodium hydroxide, lactic acid, monobasic potassium phosphate andhydrochloric acid were commercially obtained from Merck (Pakistan) and Carrageenan from Flukachemika(Malaysia).All the purchased chemicals were of analytical grade.

Methods

Preparation of ionically-crosslinkedparticles

6-Mercaptopurine monohydrate ionically-crosslinkedparticles were prepared by Polyelectrolyte complexation (PEC) technique. Several ratios of drug, CS, CASand CRG polymerswere used and formulations were named as MCP-1, MCP-2, MCP-3, MCP-4, MCP-5 and MCP-6as described in Table 1. 6-Mercaptopurine monohydrate (0.1%w/v ethanol solution) was added to all formulations. Preparation phase of each formulation is described as follows.

Preparation of MCP-1 & MCP-2ionically-crosslinkedparticles

Solution of chitosan (2-3%w/v) was prepared by addition of CS to glacial acetic acid solution (1%w/w). Above prepared drug solution was added to CS solution and after that flask was tightly closed. Both solutions were mixed for 15 minutes by magnetic stirrer. Aqueous casein solution (0.5-1% w/v) was adjusted to pH 2.0 with 1 N hydrochloric acid. Tween 80 (2% v/v) was added as a surfactant to CAS solution under magnetic stirring and added to previously prepared CS solution. Solution of CRG (0.5-1%) prepared in distilled water was added in previously prepared CS-CAS solution. TTP Solution (5-7%w/v) was prepared in distilled water [START_REF] Elzoghby | Novel ionically crosslinked casein nanoparticles for flutamide delivery: formulation, characterization, and in vivo pharmacokinetics[END_REF][START_REF] Rodrigues | Chitosan/carrageenan nanoparticles: Effect of cross-linking with tripolyphosphate and charge ratios[END_REF] and then CS solution was added drop wise by hypodermic syringe having needle size of 20G into solution of TPP. Theionically-crosslinkedparticles were prepared and named as MCP-1 and MCP-2 respectively. The crosslinking time was 30 minutes and ionic cross-linked particles were filtered, washed with distilled water and dried at room temperature.

Preparation of MCP-3 & MCP-4ionically-crosslinkedparticles

MCP-3 and MCP-4 were prepared by emulsification followed by polyelectrolyte complexation method [START_REF] Wang | Microencapsulation of Ginger Volatile Oil Based on Gelatin/Sodium Alginate Polyelectrolyte Complex[END_REF] . Aqueous CAS solution (0.5-1% w/v) was adjusted to pH 2.0 with 1 N hydrochloric acid. Tween 80 (2% v/v) was added as a surfactant to CAS solution under magnetic stirring.

Methylene chloride solution of 6-Mercaptopurine as the oil phase was mixed with aqueous CAS solution phase by homogenization at a speed of 1000 rpm for 1 hr to obtain an oil-in-water emulsion. The ratio of oil and aqueous phase was 1:10 v/v and prepared emulsion was after sonication mixed with (2-3%) CS solution. CS-CAS solution was added with the help of syringe in (5-7%) TPP solution under gentle magnetic stirring. The prepared crosslinked particles were named as MCP-3 and MCP-4 respectively, and after 2 hours of crosslinking, nanoparticles were isolated and subsequently washed several times with Tween 80 solution (0.1% v/v) and water and then dried at room temperature.

Preparation of MCP-5 & MCP-6ionically-crosslinkedparticles

CS (2-3%w/v in 1% glacial acetic acid) solution and drug solution (as prepared above) was mixed for 15 minutes by magnetic stirrer. Solution of CRG (0.5-1%) prepared in distilled water was added in previously prepared chitosan solution and solution was homogenized for 2 hr [START_REF] Rodrigues | Chitosan/carrageenan nanoparticles: Effect of cross-linking with tripolyphosphate and charge ratios[END_REF] .

Then CS-CRGsolution was added drop wise by hypodermic syringe having needle size of 20G into solution of (5-7%) TPP solution. The preparedionic cross-linked particles were named as MCP-5 and MCP-6 respectively. The crosslinking time was 30 minutes and ionically-crosslinked particles were filtered, washed with distilled water, and dried at room temperature.

Micromeritics

Micromeritic properties of the formulations were determined to analyze the particle size, flowability and compressibility characteristics of the microparticles. Sieve analysis was used to obtain the particle size. Sieves having mesh size: 10, 12, 14, 16, 18, 20 and 25 were used as mentioned in Table 2, which were shaken mechanically using Ro-Tap sieve shaker (Gilson, SS8R, USA).The samples were agitated for 150 taps per minute for 20 minutes [START_REF] Bartley | Effect of particle length to width ratio on sieving accuracy and precision[END_REF] .Percentage of particles retained on each sieve was calculated and average size was found out using following formula.

𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝑆𝑆𝑆𝑆𝑆𝑆𝐴𝐴 =

𝑃𝑃𝐴𝐴𝐴𝐴𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝑃𝑃𝐴𝐴𝑆𝑆𝑃𝑃𝐴𝐴𝑟𝑟 × 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝑠𝑠𝑆𝑆𝑆𝑆𝐴𝐴 𝑜𝑜𝑜𝑜 𝑚𝑚𝐴𝐴𝑠𝑠ℎ 𝑜𝑜𝑜𝑜𝐴𝐴𝑃𝑃𝑆𝑆𝑃𝑃𝐴𝐴 100

Each formulation was tested for their flow properties via angle of repose. The angle of repose was measured using a fixed funnel method [START_REF] Khan | Paclitaxel-loaded micro or nano transfersome formulation into novel tablets for pulmonary drug delivery via nebulization[END_REF][START_REF] Piriyaprasarth | Effect of source variation on drug release from HPMC tablets: Linear regression modeling for prediction of drug release[END_REF] . The funnel was clamped with a standand the lower end of the funnel adjusted at 2 -4 cm distance from the table surface. The weight of the powder was recorded and poured into a funnel, where a uniform cone was formed. The heightof the powder cone (from base to the tip of the cone formed) and diameter of the powder base was measured. The angle of repose was then determined with the help of following equation.

𝐴𝐴𝑃𝑃𝐴𝐴𝐴𝐴𝐴𝐴 𝑜𝑜𝑜𝑜 𝑅𝑅𝐴𝐴𝑜𝑜𝑜𝑜𝑠𝑠𝐴𝐴 = tan -1 height of pile radius of particle ′ s cone base

The bulk and tapped densities of formulations were determined as the volume before and after 100 taps in a graduated cylinder of 25 mL.Hausner's ratio was determined as the ratio of bulk density to the tapped density and was calculated using following equation.

𝐻𝐻𝐴𝐴𝐻𝐻𝑠𝑠𝑃𝑃𝐴𝐴𝐴𝐴 ′ 𝑠𝑠 𝐴𝐴𝐴𝐴𝑃𝑃𝑆𝑆𝑜𝑜 = Tapped density

Bulk density

Carr's index or percentage compressibility was determined as the percentage ratio at which the formulations were packed down to the tapped density. Carr's/ compressibility index was found out by using following formula:

𝑃𝑃𝐴𝐴𝐴𝐴𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃𝐴𝐴𝐴𝐴𝐴𝐴 𝑃𝑃𝑜𝑜𝑚𝑚𝑜𝑜𝐴𝐴𝐴𝐴𝑠𝑠𝑠𝑠𝑆𝑆𝑖𝑖𝑆𝑆𝐴𝐴𝑆𝑆𝑃𝑃𝑖𝑖 𝑆𝑆𝑃𝑃𝑟𝑟𝐴𝐴𝑖𝑖 = Tapped density -Bulk density
Tapped density × 100

Percentage yield

Percentage yield was calculated as the weight of final product with respect to the total weight of starting materials. The total amount of drug and polymer used was noted or wet microspheres were weighed then microspheres were dried and weighed again, percentage(w/w) was determined by using the given formula.

𝑃𝑃𝐴𝐴𝐴𝐴𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃𝐴𝐴𝐴𝐴𝐴𝐴 𝑖𝑖𝑆𝑆𝐴𝐴𝐴𝐴𝑟𝑟 =

Weight of final product Initial weight of drug and polymer used × 100

Determination of percentage entrapment efficiency

Percentage entrapment efficiency is percentage of drug entrapped in the microparticles regarding to original quantity used. Measured amount of microparticles MCP-1 to MCP-6 i.e. 10 mg were taken one by one, after crushing they were added to 100 ml of phosphate buffer pH 7.2, by using an ultrasonic bath for complete removal of 6-Mercaptopurine monohydrate from microparticles respectively. Then solution was filtered with the help of 0.45 um filter paper. 0.5 ml of filtered solution was taken with pipette and diluted to 5 ml with phosphate buffer solution of pH 7.2.

After dilution, absorbance of 6-Mercaptopurine was measured at 316 nm by using a UV-VIS spectrophotometer. And that absorbance was then converted to the quantity of 6-Mercaptopurine monohydrate by applying data in standard calibration curve. Entrapment efficiency was measured by using following formula.

𝐸𝐸𝑃𝑃𝑃𝑃𝐴𝐴𝐴𝐴𝑜𝑜𝑚𝑚𝐴𝐴𝑃𝑃𝑃𝑃 𝐴𝐴𝑜𝑜𝑜𝑜𝑆𝑆𝑃𝑃𝑆𝑆𝐴𝐴𝑃𝑃𝑃𝑃𝑖𝑖 = Entrapped quanity of drug per gram microparticles

Theoretical quantity of drug per gram microparticles × 100

Scanning Electron Microscopy

The surface morphology of formulated ionic crosslinked particles was evaluated by scanning electron microscope (SEM). For SEM samples were arranged by sprinkling microspheres powder on an aluminum stub with the help of double adhesive tape. The stubs were coated with gold-palladium alloy to a thickness of (150-200 Å) using coat sputter JFC 1100 (JEOL-Japan).

The microparticles were observed and examined under scanning electron microscope (JEOL, JSM-6100 SEM, and JAPAN) and photograph was taken.

In-vitro swelling studies

Swelling studies were performed with the help of empty tea bags that contained 50 mg of each formulation; the empty bag was placed in a closed flat bottom tube with 100 ml of a buffer solution that was maintained at hours at 37˚C ± 0.5˚ C at 100 rpm [START_REF] Rehman | Influence of Beta-cyclodextrin and Chitosan in the Formulation of a Colon-Specific Drug Delivery System[END_REF] . The three different pH levels were selected in order to determine the drug release under different gastrointestinal region such as stomach, small intestine, large intestine and colon. 5ml of sample was withdrawn at definite interval from dissolution medium and 6-Mercaptopurine monohydrate contents were analyzed by UV-Visible spectrophotometer at λ max 316 nm, same amount of fresh dissolution medium was added after each withdrawal.

Drug Release Kinetic Analysis

Drug release kinetic analysis regarding all formulations MCP-1 to MCP-6 was applied in excel by using add-in DDSolver software to find out the highest values of regression coefficient that tells us about best fit model either Zero order, First order, Highuchi, Hixon-Crowell, Korsmeyer-Peppas and also value of n was seen by applying Korsmeyer-Peppas model to check out the pattern of drug release.

The ideal kinetic models for drug release and permeation were estimated using the different log time (Korsmeyer-Peppas model) [START_REF] Rehman | Probing the effects of fish oil on the delivery and inflammation-inducing potential of imiquimod[END_REF] .

Following equations were used for the calculation of each kinetic model.

Zero order equation: Qt = Q0 + K0t

First order equation:

𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 = -𝐾𝐾 Higuchi equation: Q = K3√ t
Hixon -Crowell equation: Q0

Results and discussion

Micromertics

Micromertic properties of microparticles were evaluated in terms of particle size, flowability and compressibility. Particle size is a simple concept, but it is a most critical process parameter in preformulationand manufacturing. It is also true that the reduction of particle size impacts directlyon the bioavailability of drug. Particle size of the formulations ranged from 664-798 µm.

The ionic cross-linked particles prepared from emulsification method produced microparticles of larger size as compared to other two methods. MCP-6 formulation exhibited smallest particle size of 664±0.57µm whereas MCP-4 formulation displayed the largest particle size of 798±0.66 µm. The concentration of casein polymer could also be contributing factor in larger particle size.

All the formulations displayed excellent flowability with angle of repose values between 23-28 o

angles. The Hausner ratio may be related to the compressibility of powderand values of <1.25 is indicative of good compressibility. TheCarr's index may also be indicative of flowability and degree of packing of thematerial, which are relevant properties when filling the matricesof the tablet press. CI of <15% indicates an adequate flow of powdersand stable packing, while values of >25% are characteristic ofpoor flow properties. All the microparticles showed excellent compressibility and flow properties [START_REF] El-Bary | Influence of some formulation variables on the optimization of pH-dependent, colon-targeted, sustained-release mesalamine microspheres[END_REF][START_REF] Kajjari | Novel Interpenetrating Polymer Network Hydrogel Microspheres of Chitosan and Poly(acrylamide)-grafted-Guar Gum for Controlled Release of Ciprofloxacin[END_REF] and the results of hausner's ratio, carr's index and angle of repose for each formulation is given in Table 2.

Percentage yield

The percentage yield varies from 77.5-87.5 % in different formulations. Formulations that were prepared from emulsification process (MCP-3 and MCP-4) showed lower percentage yield as compared to other formulations. The factors that could have been contributed in low yield are the drying of ionic crossed linked particles would be less efficient through emulsions as compared to the aqueous solutions of other formulations and emulsification process required more crosslinking time as compared to other method. The results for percentage yield of each formulation are given Table 2.

Percentage Entrapment Efficiency of ionic cross-linked particles

Percentage entrapment efficiencies of ionic cross-linked microparticles were in the range of 57.4% to 83%, whereas the highest percentage entrapment was 83% of formulation MCP-5. The entrapment efficiency was increased with the increase in polymeric concentration except in case of MCP-4 as shown in Table 2. The ionic cross-linked particles prepared from emulsification method produced showed lowest entrapment efficiency thus proving that emulsification might not be a suitable method for 6-Mercaptopurine entrapment. It was also observed that lower concentration of casein or complete absence of casein resulted into better entrapment efficiency.

Scanning Electron Microscopy (SEM)

To determine the surface morphology of the formulations, microparticles were evaluated by scanning electron microscope (SEM). The Microparticles prepared with chitosan and TPP were smooth and spherical in shape as shown in the Figure 1. Microparticles prepared with chitosan, casein and TPP were appeared to be porous and these pores could affect the release rate of drug from polymer [START_REF] Jeyanthi | Effect of solvent removal technique on the matrix characteristics of polylactide/glycolide microspheres for peptide delivery[END_REF] . Microparticles prepared with chitosan, carrageenan and TPP were also smooth and spherical. The spherical particles with smooth even surface indicated the absence of any drug crystal on the surface and confirmed the even distribution of drug in the polymeric matrix.The spherical microparticles that were smooth in nature resulted into better entrapment of the drug that could also influence release of drug in a control manner [START_REF] Mahboubian | Preparation and In-vitro Evaluation of Controlled Release PLGA Microparticles Containing Triptoreline[END_REF][START_REF] El-Say | Maximizing the encapsulation efficiency and the bioavailability of controlledrelease cetirizine microspheres using Draper-Lin small composite design[END_REF] . Surface morphology also indicated that the emulsification method for preparing the microparticles lacked proper drying that resulted into porus morphology of the microparticles prepared by emulsification.

In-vitro Swelling Ratio

The In-vitro swelling studies of microparticles were performed at different pH values. The swelling behavior was in accordance with the increasing affinity of polymers for the buffer as the pH increased. Thus, the systems MCP-1 to MCP-6 were swelled highly at pH 7.2, while in acidic environment pH 2, the swelling was considerably smaller. The formulation in pH 2 never surpassed the 8%. MCP-1 to MCP-6 micro-particles swelling increased as the pH increased.At pH 2.0 and 5.5, the swelling index never reached the 10%. At pH 7.4 swelling was constantly increased reaching more than 22% after 24 h and showing a tendency to still increase as shown in the Figure 2. This could be a useful property as it might result into a controlled manner of drug release in large intestine, thus achieving a pH responsive micro-particulate drug delivery system. The swelling and pH responsiveness are important for the targeted intestinal drug delivery systems. The principle sites of drug absorption are stomach and proximal part of small intestine, but for the purpose of drug to be delivered into colon region, drug delivery systems should offer restraint towards releasing the drug in lower pH or stomach and small intestine environment. Our results indicated the control of swelling at lower pH which could also result into controlled drug release. Furthermore, there was a relationship observed between the concentration of the TPP crosslinker, pH and the swelling properties [START_REF] Vityazev | Pectin-glycerol gel beads: Preparation, characterization and swelling behaviour[END_REF][START_REF] Karimi | Chitosan hydrogels cross-linked with tris(2-(2-formylphenoxy)ethyl)amine: Swelling and drug delivery[END_REF] . Formulations containing lower concentrations of TPP showed lower swelling index at pH 2 and PH 5.5 but higher swelling index at colonic environment of pH 7.2. The influence of TPP crosslinker on the swelling properties have been previously reported and in accordance with our findings. Thus, it could be suggested that the concentration of TPP crosslinker could influence the controlled drug delivery and targeted drug release in the colon region.

In-vitro drug release studies

The mechanism of drug release from the prepared ionically-crosslinked microparticles depends on various factors such as composition of polymers, crosslinker, geometry (size and shape), were prepared by emulsification process, had lower drug entrapment efficiency that was evident through their SEM images. Therefore, these formulations resulted into lower percentage drug release (Figure 3). All the other formulations had smooth and spherical morphology and had very good drug entrapment efficiency resulted into controlled drug release in an effective manner and at colonic region. Thus, proving them to be an excellent colon specific, pH responsive, drug delivery vehicle systems (Figure 3). The maximum drug release was offered by MCP-5 and MCP-6 combination formulations releasing 99.3 % and 99.6% of drug respectively (as shown in Figure 3). The results clearly displayed the pH dependent drug delivery mechanism from all the formulations. Less than 10% drug was released at pH 1.2 which highlighted a successful control and delay of release of active ingredient from the microparticles. Around 20-40% drug was released at pH 5.5 whereas maximum drug was released at pH 7.2 which represents the colon pH. The drug entrapped in the microparticles released gradually over the period of 12 h. There was almost no initial drug release from the microparticles in an acidic environment but as formulations came into contact with increased pH simulating the small intestine and colon environment (pH 5.5 and pH 7.2 respectively) the microparticles gradually started to release the drug in response to the changes in the dissolution medium's pH.Thus, making these formulations an ideal candidate for inflammatory bowel diseases and colon cancer.

Drug Release Kinetics

Mathematical models are an important tool to design pharmaceutical formulations, evaluate drug release processes in vitro and in vivo and, in general, come up with the optimal design for new systems [START_REF] Peppas | Mathematical models in drug delivery: How modeling has shaped the way we design new drug delivery systems[END_REF] . They allow the analysis of some important physical parameters (e.g., drug diffusion coefficient) and resort to model fitting on experimental release data. The amount and type of active agent, polymer and adjuvants as well as the size and shape of the system designed to achieve a certain drug release profile can be predicted theoretically [START_REF] Siepmann | Modeling of drug release from delivery systems based on hydroxypropyl methylcellulose (HPMC)[END_REF] .Data collected by in-vitro release studies of all formulations was fitted in Zero order release model, first order release model, Higuchi model, Korsmeyer-Peppas model and Hixon -Crowell Model by using DDSolver software. The values of correlation coefficient were found for each kinetic equation is mentioned in Table 3. The results indicated that drug followed the Zero order release pattern due to higher regression coefficient values in zero order model and super case II transport as n > 0.89 that was found out by applying korsmeyer-Peppas model [START_REF] Siepmann | A New Model Describing the Swelling and Drug Release Kinetics from Hydroxypropyl Methylcellulose Tablets[END_REF][START_REF] Mhlanga | Kinetic models for the release of the anticancer drug doxorubicin from biodegradable polylactide/metal oxide-based hybrids[END_REF] .For zero-order kinetics, the results indicate that the release of an active agent is only a function of time and the process takes place at a constant rate independent of active agent concentration.Moreover, zero-order release indicates that the microparticles were permeable to both active agent and water and as they become hydrated the drug is dissolved until it reached its saturated concentration.

Conclusion

Controlled release pH responsive microparticles of 6-Mercaptopurine monohydrate were successfully prepared by polyelectrolyte complexation and emulsification method that will improve patient compliance by decreasing side effects regarding to anti-cancer drugs due to controlled effect. Ionic cross-linked microparticles were prepared by polyelectrolyte complexation and emulsification method produced microspheres of regular and spherical shape except foremulsification method as found in SEM analysis. The porous morphology of microparticles prepared from emulsification method (MCP-3 and MCP-4) were resulted into low entrapment efficient and least percentage drug release. The analytical determinations of entrapment efficiency, percentage yield and mean particle size and drug release behavior have seen among all formulations due to different polymer combinations and ratio. In vitro swelling and drug release studies were in accordance with the polymer properties, showing the highest swelling ratio and drug release at pH7.2 where microparticles were able to deliver more than 85% of 6-MP monohydrate during 12 hours of experiments.A significant relationship was observed between TPP crosslinker concentration, polymer and the pH responsiveness. The MCP-5 was considered the good encapsulating option amongst the six formulations to make sustained release formulation. In-vitro release studies pointed out that there was pH responsive controlled drug release from MCP-1 to MCP-6 and considered to be the best in order to achieve the objective of the study regarding to side effects of drug for patient suffering from ulcerative colitis.Drug release was super transport case II which followed zero order release model that indicates patient compliance because of decrease in dosing frequency by decreasing side effects regarding to anti-cancer drugs due to controlled, sustained, and targeted effect.

  37 •C up to 24 h. It was carried out for MCP-1 to MCP-6 formulation in two different solutions with different pH values, i.e. of pH 2.0 in first beaker for first 2 hours, then tea bags were shifted beakers for conforming small intestine condition (pH = 5.5) upto 6 hours and finally to confirm large intestine conditions all previously used tea bags at pH 5.5 were shifted to beakers having phosphate buffer (pH = 7.4) and studied upto 24 hours. It was done to analyze swelling in stomach, intestinal and colon region. At specific time intervals, sample bags were removed from the swelling medium, blotted with a piece of paper for 5s to absorb excess water on surface and then change in the weight was determined to calculate the swelling index using following equation[START_REF] Vityazev | Pectin-glycerol gel beads: Preparation, characterization and swelling behaviour[END_REF][START_REF] Karimi | Chitosan hydrogels cross-linked with tris(2-(2-formylphenoxy)ethyl)amine: Swelling and drug delivery[END_REF] .𝑆𝑆𝑆𝑆𝐴𝐴𝐴𝐴𝐴𝐴𝑆𝑆𝑃𝑃𝐴𝐴 𝑆𝑆𝑃𝑃𝑟𝑟𝐴𝐴𝑖𝑖 =Weight of microspheres at specific time (Wt) -Weight of dry microspheres(Wo) Weight of dry microspheres (Wo) × 100In-vitro drug release studiesIn-vitro drug release or dissolution profiles of microparticles of 6-Mercaptopurine monohydrate were found out by enclosing micro-beads in hard gelatin capsule in a quantity equivalent to 50 mg dose of drug. (Pharma max. TEST) dissolution apparatus was used to carry out the study to check the release behavior of microparticles. The dissolution was carried out for 2 hours in 900ml of 0.1 N HCl solution and then in phosphate buffer having pH 5.5, 7.2 and 7.4 for 12

  mathematical equation plots: cumulative amount of drug permeated vs. time (zero-order model), log cumulative percentage of drug remaining vs. time (first-order model), cumulative percentage drug permeated vs. square root of time (Higuchi model), cube root of drug percentage remaining in matrix vs. time (Hixson-Crowell model) and log cumulative percentage drug permeated vs.

Figure 3 .

 3 preparation technique and environmental conditions during drug release. The amount of drug release was measured by UV-Vis spectroscopy and is plotted as a cumulative release with time in All the formulations were analyzed in acidic and basic medium to determine their drug release in gastrointestinal environment. All formulations were subjected to in-vitro dug release studies; the in-vitro drug release of MCP-1 to MCP-6 was carried out for first 2 hours in 0.1 N HCl at 37± 0.5 °C at 100 rpm to mimic conditions of stomach, then each formulation was shifted and analyzed under small intestinal environment for next 2 hours(phosphate buffer of 5.5 pH)and then that same formulations were shifted to phosphate buffer of 7.2 pH to analyze its release in large intestinal and colon environment. The formulations MCP-3 and MCP-4, which

Conflict of interest

Authors have no conflict of interest to report.