{'fraction_non_alphanumeric': 0.03957604739133538, 'fraction_numerical': 0.009706659053600743, 'mean_word_length': 4.346880366342301, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving the Minimum Common String Partition Problem with the Help of Ants

In this paper, we consider the problem of finding a minimum common partition of two strings. The problem has its application in genome comparison. As it is an NP-hard, discrete combinatorial optimization problem, we employ a metaheuristic technique, namely, MAX-MIN ant system to solve this problem. To achieve better efficiency we first map the problem instance into a special kind of graph. Subsequently, we employ a MAX-MIN ant system to achieve high quality solutions for the problem. Experimental results show the superiority of our algorithm in comparison with the state of art algorithm in the literature. The improvement achieved is also justified by standard statistical test.


Introduction
String comparison is one of the important problems in Computer Science with diverse applications in different areas including Genome Sequencing, text processing and compressions. In this paper, we address the problem of finding a minimum common partition (MCSP) of two strings. MCSP is closely related to genome arrangement which is an important topic in computational biology. Given two DNA sequences, the MCSP asks for the least-sized set of the common building blocks of the sequences.
In the MCSP problem, we are given two related strings (X, Y ). Two strings are related if every letter appears the same number of times in each of them. Clearly, two strings have a common partition if and only if they are related. So, the length of the two strings are also the same (say, n). Our goal is to partition each string into c segments called blocks, so that the blocks in the partition of X and that of Y constitute the same multiset of substrings. Cardinality of the partition set, i.e., c is to be minimized. A partition of a string X is a sequence P = (B 1 , B 2 , · · ·, B m ) of strings whose concatenation is equal to X, that is B 1 B 2 · · · B m = X. The strings B i are called the blocks of P . Given a partition P of a string X and a partition Q of a string Y , we say that the pair π =< P, Q > is a common partition of X and Y if Q is a permutation of P . The minimum common string partition problem is to find a common partition of X, Y with the minimum number of blocks. For example, if (X, Y ) = {"ababcab","abcabab"}, then one of the minimum common partition sets is π ={"ab","abc","ab"} and the minimum common partition size is 3. The restricted version of MCSP where each letter occurs at most k times in each input string, is denoted by k-MCSP.
MCSP has its vast application rooted in Comparative Genomics. Given two DNA strings, MCSP answers the possibilities of re-arrangement of one DNA string to another [1]. MCSP is also important in ortholog assignment. In [2], the authors present a new approach to ortholog assignment that takes into account both sequence similarity and evolutionary events at a genomic level. In that approach, first, the problem is formulated as that of computing the signed reversal distance with duplicates between the two genomes of interest. Then, the problem is decomposed into two optimization problems, namely minimum common partition and maximum cycle decomposition problem. Thus MCSP plays an integral part in computing ortholog assignment of genes.

Our Contribution
In this paper, we consider metaheuristic approaches to solve the problem. To the best of our knowledge, there exists no attempt to solve the problem with metaheuristic approaches. Only theoretical works are present in literature. Particularly we are interested in nature inspired algorithms. As the problem is discrete combinatorial optimization problem, the natural choice is Ant Colony Optimization (ACO). Before applying ACO, it is necessary to map the problem into a graph. We have developed this mapping. In this paper, we implement a variant of ACO algorithm namely MAX-MIN Ant System (MMAS) to solve the MCSP problem. We conduct experiments on both random and real data to compare our algorithm with the state of the art algorithm in the literature and achieve excellent results. Notably, a preliminary version of the paper appeared at [3].

Literature Review
MCSP is essentially the breakpoint distance problem [4] between two permutations which is to count the number of ordered pairs of symbols that are adjacent in the first string but not in the other; this problem is obviously solvable in polynomial time [5]. The 2-MCSP is proved to be NP-hard and moreover APX-hard in [5]. The authors in [5] also presented several approximation algorithms. Chen et al. [2] studied the problem, Signed Reversal Distance with Duplicates (SRDD), which is a generalization of MCSP. They gave a 1.5-approximation algorithm for 2-MCSP. In [1], the author analyzed the fixed-parameter tractability of MCSP considering different parametrs. In [6], the authors investigated k-MCSP along with two other variants: M CSP c , where the alphabet size is at most c; and x-balanced MCSP, which requires that the length of the blocks must be within the range (n/d − x, n/d + x), where d is the number of blocks in the optimal common partition and x is a constant integer. They showed that M CSP c is NP-hard when c ≥ 2. As for k-MCSP, they presented an FPT algorithm which runs in O * ((d!) 2k ) time.
Chrobak et al. [7] analyzed a natural greedy heuristic for MCSP: iteratively, at each step, it extracts a longest common substring from the input strings. They showed that for 2-MCSP, the approximation ratio (for the greedy heuristic) is exactly 3. They also proved that for 4-MCSP the ratio would be log n and for the general MCSP, between Ω(n 0.43 ) and O(n 0.67 ).
Ant colony optimization (ACO) [8,9,10] was introduced by M. Dorigo and colleagues as a novel nature-inspired metaheuristic for the solution of hard combinatorial optimization (CO) problems. The inspiring source of ACO is the pheromone trail laying and following behavior of real ants which use pheromones as a communication medium. In analogy to the biological example, ACO is based on the indirect communication of a colony of simple agents, called (artificial) ants, mediated by (artificial) pheromone trails. The pheromone trails in ACO serve as a distributed, numerical information which the ants use to probabilistically construct solutions to the problem being solved and which the ants adapt during the algorithm's execution to reflect their search experience. Different ACO algorithms have been proposed in the literature. The original algorithm is known as the Ant System(AS) [11,12,13]. The other variants are, Elitist AS [12,13], ANT-Q [14], Ant Colony System (ACS) [9], MAX-MIN AS [15,16,17] etc.
Recently growing interest has been noticed towards ACO in the scientific community. There are now available several successful implementations of the ACO metaheuristic applied to a number of different discrete combinatorial optimization problems. In [8] the authors distinguished among two classes of applications of ACO: those to static combinatorial optimization problems, and those to the dynamic ones. When the problem is defined and does not change while the problem is being solved is termed as static combinatorial optimization problems. The authors list some static combinatorial optimization problems those are successfully solved by different variants of ACO. Some of the problems are, travelling salesperson, Quadratic Assignment, job-shop scheduling, vehicle routing, sequential ordering, graph coloring etc. Dynamic problems are defined as a function of some quantities whose values are set by the dynamics of an underlying system. The problem changes therefore at run time and the optimization algorithm must be capable of adapting online to the changing environment. The authors listed connection-oriented network routing and connectionless network routing as the examples of dynamic problems those are successfully solved by ACO.
In 2010 a non-exhaustive list of applications of ACO algorithms grouped by problem types is presented in [18]. The authors categorized the problems into different types namely routing, assignment, scheduling, subset machine learning and bioinformatics. In each type they listed the problems those are successfully solved by some variants of ACO.
There are not too many string related problems solved by ACO in the literature. In [19], the authors addressed the reconstruction of DNA sequences from DNA fragments by ACO. Several ACO algorithms have been proposed for the longest common subsequence (LCS) problem in [20,21]. Recently minimum string cover problem is solved by ACO in [22]. Finally, we note that a preliminary version of this work was presented at [23].

Preliminaries
In this section, we present some definitions and notations that are used throughout the paper. Example 1. X = "abacbd" and Y = "acbbad", then they are related. But if X 1 = "aeacbd" and Y = "acbbad", they are not related Definition 2. Block : A block B = ([id, i, j]), 0 ≤ i ≤ j < n, of a string S is a data structure having three fields: id is an identifier of S and the starting and ending positions of the block in S are represented by i and j, respectively. Naturally, the length of a block [id, i, j] is (j − i + 1). We use substring([id, i, j]) to denote the substring of S induced by the block [id, i, j]. Throughout the report we will use 0 and 1 as the identifiers of X(i.e., id(X)) and Y (i.e., id(Y )) respectively. We use [] to denote an empty block. Two blocks can be intersected or unioned. The intersection of two blocks (with same ids) is a block that contains the common portion of the two.   The union rule with an ordered set of blocks, B lst and a block, B can be defined as follows. We have to find the position where B can be placed in B lst , i.e., we have to find B k ∈ B lst after which B can be placed. Then, we have to replace the ordered subset {B k , B k+1 } with B k ∪ B ∪ B k+1 . On the other hand, B lst ∪ B 3 = [0, 5,12], which is basically identical to Two blocks B 1 and B 2 (in the same string or in two different strings) match if substring(B 1 ) = substring(B 2 ). If the two matched blocks are in two different strings then the matched substring is called a common substring of the two strings denoted by cstring(B 1 , B 2 ).
Definition 5. span: Given a list of blocks with same id, the span of a block, B = [id, i, j] in the list denoted by, span(B) is the length of the block (also in the list) that contains B and whose length is maximum over all such blocks in the list. Note that a block is assumed to contain itself. More formally, given a list of blocks, In other words, span of a block is the maximum length of the super string than contains the substring induced by the block. Definition 6. Partition: A partition of a string X is a list of blocks all with id(X) having the following two properties: (a) Non Overlapping: The blocks must be be disjoint, i.e., no block should overlap with another block. So the intersection of any two blocks must be empty. (b) Cover: The blocks must cover the whole string.
In other words, a partition of a string X is a sequence P = (B 1 , B 2 , . . . , B m ) of strings whose concatenation is equal to X, that is

Basics of ACO
In ACO, a combinatorial optimization (CO) problem is solved by iterating the following two steps. At first, solutions are constructed using a parameterized probability distribution over the solution space which is called pheromone model. The second step is to modify the pheromone values using the solutions that were constructed in earlier iterations in a way that is deemed to bias the search towards the high quality solutions.

Ant Based Solutions Construction
The basic ingredient of an ACO algorithm is a constructive heuristic that constructs solutions probabilistically. Sequences of solution components taken from a finite set of solution components C = {c 1 , c 2 , ...c n } is assembled by a constructive heuristic. Starting with an empty partial solution s p = ∅ a solution is constructed. Then at each construction step the current partial solution s p is extended by adding a feasible solution component from the solution space C. The definition of feasible solution component is problem specific. Typically a problem is mapped into a construction Graph G c = (C, E) whose vertices are the solution components C and the set E are the connections (i.e., edges). The process of constructing solutions can be regarded as a walk (or a path) on the construction graph.

Heuristic Information
In most ACO algorithms the transition probabilities, i.e., the probabilities for choosing the next solution component, are defined as follows: Here, c i is a candidate component, s p is the partial solution. The current partial solution s p is extended by adding a feasible solution component from the set of feasible neighbors N (s p ) ⊆ C. η is a weight function that contains heuristic information and α, β are positive parameters whose values determine the relation between the pheromone information and the heuristic information. The pheromones deployed by the ants are denoted by τ .

Pheromone Update
The pheromone update consists of two parts. The first part is pheromone evaporation, which uniformly decreases all the pheromone values . From a practical point of view, pheromone evaporation prevents too rapid convergence of the algorithm toward a sub-optimal region. Thus it helps to avoid the local optimal solutions and favors the exploration of new areas in the search space. Then, one or more solutions from the current or from earlier iterations (the set is denoted by S upd )are used to increase the values of pheromone trail parameters on solution components that are part of these solutions: Let W (.) is the cost function. Here, S upd is the set of local best or global best solution, ε ∈ (0, 1] is a parameter called the evaporation rate, and F : The function F (.) is commonly called the Fitness Function.
In general, different versions of ACO algorithms differ in the way they update the pheromone values. This also holds for the two currently bestperforming ACO variants in practice, namely, the Ant Colony System (ACS) [9] and the MAX-MIN Ant System (MMAS) [17]. Since in our algorithm we hybridize ACS with MMAS, below we give a brief description of MMAS.

MAX-MIN Ant System (MMAS)
MMAS algorithms are characterized as follows. First, the pheromone values are limited to an interval Pheromone trails are initialized to τ max to favor the diversification during the early iterations so that premature convergence is prevented. Explicit limits on the pheromone values ensure that the chance of finding a global optimum never becomes zero. Second, in case the algorithm detects that the search is too much confined to a certain area in the search space, a restart is performed. This is done by initializing all the pheromone values again. Third, the pheromone update is always performed with either the iterationbest solution, the restart-best solution (i.e., the best solution found since the last restart was performed), or the best-so-far solution.

Formulation of Common Substring Graph
We define a common substring graph, G cs (V, E, id(X)) of a string X with respect to Y as follows. Here V is the vertex set of the graph and E is the edge set. Vertices are the positions of string X, i.e., for More formally, we have: In other words, each edge in the edge set corresponds to a block satisfying the above condition. For convenience, we will denote the edges as edge blocks To find a common partition of two strings (X, Y ) we first construct the common substring graph of (X, Y ). Then from a vertex v i on the graph we take an edge block [id(X), v i , v j ]. Suppose M i is the matchList of this block. We take a block B i from M i . Then we advance to the next vertex that is (v j + 1) M OD |X| and choose another corresponding edge block as before. We continue this until we come back to the starting vertex. Let partitionList and mappedList are two lists, each of length c, containing the traversed edge blocks and the corresponding matched blocks. Now we have the following lemma. Lemma 1. partitionList is a common partition of length c iff, and Proof. By construction, partitionList is a partition of X. We need to prove that mappedList is a partition of Y and with the one to one correspondence between partitionList and mappedList it is obvious that partitionList would be the common partition of (X, Y ). Equation 5 asserts the non overlapping property of mappedList and Equation 6 assures the cover property. So, mappedList will be a partition of Y if Equation 5 and 6 are satisfied.
On the other hand let partitionList along with mappedList is a common partition of (X, Y ). According to construction, partitionList satisfies the two properties of a partition. Let, mappedList is a partition of Y . We assume mappedList does not follow the Equation 5 or 6. So, there might be overlapping between the blocks or the blocks do not cover the string Y , a contradiction. This completes the proof.

Heuristics
Heuristics (η) contain the problem specific information. We propose two different (types of) heuristics for MCSP. Firstly, we propose a static heuristic that does not change during the runs of algorithm. The other heuristic we propose is dynamic in the sense that it changes between the runs.

The Static Heuristic for MCSP
We employ an intuitive idea. It is obvious that the larger is the size of the blocks the smaller is the partition set. To capture this phenomenon, we assign on each edge of the common substring graph a numerical value that is proportional to the length of the substring corresponding to the edge block. Formally, the static heuristic (η s ) of an edge block [id, i, j] is defined as follows:

The Dynamic Heuristic for MCSP
We observe that the static heuristic can sometimes lead us to very bad solutions. For example if (X, Y ) = {"bceabcd","abcdbec"} then according to the static heuristic much higher value will be assigned to edge block [0, 0, 1] than to [0, 0, 0]. But if we take [0, 0, 1], we must match it to the block [1, 1, 2] and we further miss the opportunity to take [0, 3,6] later. The resultant partition will be {"bc","e","a","b","c","d"} but if we would take [0, 0, 0] at the first step, then one of the resultant partitions would be {"b","c","e","abcd"}. To overcome this shortcoming of the static heuristic we define a dynamic heuristic as follows. The dynamic heuristic (η d ) of an edge block (B = [id, i, j]) is inversely proportional to the difference between the length of the block and the minimum span of its corresponding blocks in its matchList. More formally, η d (B) is defined as follows: where We define the total heuristic (η) to the linear combination of the static heuristic (η s ) and the dynamic heuristic (η d ). Formally, the total heuristic of an edge block B is,

Initialization and Configuration
Given two strings (X, Y ), we first construct the common substring graph G cs = (V, E, id(X)). We use the following notations. Local best solution (avg−1) n √ p best . Here, avg is the average number of choices an ant has in the construction phase; n is the length of the string; p best is the probability of finding the best solution when the system converges and ε is the evaporation rate. Initially, the pheromone values of all edge blocks (substring) are initialized to initP heromone which is a large value to favor the exploration at the first iteration [17]. The steps of the initialization is shown in Algorithm 4

Construction of a Solution
Let, nAnts denotes the total number of ants in the colony. Each ant is deployed randomly to a vertex v s of G cs . A solution for an ant starting at a vertex v s is constructed by the following steps: step 1 : Let v i = v s . Choose an available edge block starting from v i by the discrete probability distribution defined below. An edge block is available if its M atchList is not empty and inclusion of it to the partitionList and mappedList obeys Equation 11. The probability for choosing edge block is chosen according to Equation 11 above. We choose a match block B m from the matchList of [0, v i , v k ] and delete B m from the matchList. We also delete every block from every matchList of every edge block that overlaps with B m . Formally we delete a block B if We add [0, v i , v k ] to the partitionList and B m to the mappedList. step 3 : If (v k + 1) M OD length(X) = v s and the mappedList obeys Equation 6, then we have found a common partition of X and Y . The size of the partition is the length of the partitionList. Otherwise, we jump to the step 1.
The construction is shown in Algorithm 5.

Intelligent Positioning
For every edge block of G cs in X, we have a matchList that contains the matched block of string Y . In construction (step 1), when an edge block is chosen by the probability distribution, we take a block from the matchList of the chosen edge block. We can choose the matched block randomly. But we observe that random choosing may lead to a very bad partition. For example, if (X, Y ) = {"ababc","abcab"} then the matchList([0, 0, 1]) = {[1, 0, 1], [1,3,4]}. If we choose the first match block then eventually we will get the partition as {"ab","ab","c"} but a smaller partition exists and that is {"ab","abc"}. To overcome this problem, we have imposed a rule for choosing the matched block. We will select a block from the matchList having the lowest possible span. Formally, for the edge block, B i , a block B ∈ matchList(B i ) will be selected such that span(B ) is the minimum.
In our example span([1, 0, 1]) = 3 where as span([1, 3, 4]) = 2. So it is better to select the second block so that we do not miss the opportunity to match a larger block.

Pheromone Update
When each of the ants in the colony construct a solution (i.e., a common partition), an iteration completes. We set the local best solution as the best partition that is the minimum length partition in an iteration. The global best solution for n iterations is defined as the minimum length common partition over all the n iteration. We

The Pseudocode
The pseudocode of our approach for solving MCSP is given in Algorithm 9.

Experiments
We have conducted our experiments in a computer with Intel Core 2 Quad CPU 2.33 GHz. The available RAM was 4.00 GB. The operating system was Windows 7. The programming environment was java. jre version is"1.7.0 15". We have used JCreator as the Integrated Development Environment. The maximum allowed time for test case instance was 120 minutes.

Datasets
We have conducted our experiments on two types of data: randomly generated DNA sequences and real gene sequences.

Random DNA sequences:
We have generated 30 random DNA sequences each of length at most 600 using [24]. The fraction of bases A, T , G and C is assumed to be 0.25 each. For each DNA sequence we shuffle it to create a new DNA sequence. The shuffling is done using the online toolbox [25]. The original random DNA sequence and its shuffled pair constitute a single input (X, Y ) in our

Real Gene Sequences:
We have collected the real gene sequence data from the NCBI GenBank 1 . For simulation, we have chosen Bacterial Sequencing (part 14). We have taken the first 15 gene sequences whose lengths are within [200, 600].

Parameter Tuning
There are several parameters which have to be carefully set to obtain good results. To obtain a good set of parameters we have done a preliminary experiment. In our experiment we have chosen 3 values for each of the parameters. so there are 243 possible permutations of the 5 parameters. The values of the parameters used in our experiment is listed in Table 1. We have chosen 2 input cases from each of the groups (group1, group2, group3 and realgene). The time limits are set to 10, 20, 30 and 20 minutes for the 4  10.0 Maximum Allowed Time 120 min groups, respectively. The algorithm is run for 4 times and the average result is recorded. Let the partition size of each of the case is denoted by A i where i ∈ [1,8]. With these settings, we find rank of a permutation by the following rule: R j = i∈ [1,8] A i j /max(A i ) ∀j ∈ [1,243] After computing the Rank, R, we find the permutation of the parameters for which the rank is minimum. The best found parameters are reported in Table 2.

Results and Analysis
We have compared our approach with the greedy algorithm of [7] because none of the other algorithms in the literature are for general MCSP: each of the other approximation algorithms put some restrictions on the parameters. As it is expected the greedy algorithm runs very fast. All of the result by greedy algorithm presented in this paper outputs within 2 minutes. Table 3, Table 4 and Table 5 present the comparison between our approach and the greedy approach [7] for the random DNA sequences. For a particular DNA sequence, the experiment was run 15 times and the average result is reported. The first column under any group reports the partition size computed by the greedy approach, the second column is the average partition size found by MMAS, the third and fourth column report the worst and best results among 15 runs, the fifth column represents the difference between the two approaches. A positive (negative) difference indicates that the greedy result is better (worse) than the MMAS result by that amount. The sixth column reports the standard deviation of 15 runs of MMAS, the seventh column is the average time in second by which the reported partition size is achieved. The first 3 columns summarize the t-statistic result for greedy vs. MMAS. The first column reports the t-value of two sample ttest. A positive t-value indicate significant improvement. The second column presents the p-value. A lower p-value represent higher significant improvement and the third column reports whether the null hypothesis is rejected or accepted. Here the null hypothesis is that the two random population (partition sizes from greedy and MMAS) have equal means. We have used +, −, ≈ to denote improvement, deteriotion and almost equal respectively. According to t-statistic value with 5% significance value we have found better solution in 28 cases for MMAS. For the other 2 case we got worse result in 5% significance level.

Effects of Dynamic Heuristics:
In Section 4.2.2, we discussed the dynamic heuristic we employ in our algorithm. We conducted experiments to check and verify the effect of this dynamic heuristic. We conducted experiments with two versions of our algorithm-with and without applying the dynamic heuristic. The effect is presented in Table 6, where for each group the average partition size with dynamic heuristic and without dynamic heuristic is reported. The positive difference depicts the improvement using dynamic heuristic. Out of 30 cases we found positive differences on 27 cases. This clearly shows the significant improvement using dynamic heuristics. It can also be observed that with the increase in length, the positive differences are increased. Figures 2, 3, and 4 show the case by case results. The blue bars represent the partition size using dynamic heuristic and the red bars represent the partition size without the dynamic heuristic.   Table 7 shows the minimum common partition size found by our approach and the greedy approach for the real gene sequences. Out of 15 cases positive improvement is found in 10 cases in 5% significance level.

Conclusion
Minimum Common String Partition problem has important applications in computational biology. In this paper, we have described a metaheuristic approach to solve the problem. We have used static and dynamic heuristic information in this approach with intelligent positioning. The simulation is conducted on random DNA sequences and real gene sequences. The results are significantly better than the previous results. The t-test result also shows significant improvement. As a future work different other metaheuristic techniques may be applied to present better solutions to the problem.