Secure Surveillance Systems Using Partial-Regeneration-Based Non-Dominated Optimization and 5D-Chaotic Map

: Due to Internet of Things (IoT), it has become easy to surveil the critical regions. Images are important parts of Surveillance Systems, and it is required to protect the images during transmission and storage. These secure surveillance frameworks are required in IoT systems, because any kind of information leakage can thwart the legal system as well as personal privacy. In this paper, a secure surveillance framework for IoT systems is proposed using image encryption. A hyperchaotic map is used to generate the pseudorandom sequences. The initial parameters of the hyperchaotic map are obtained using partial-regeneration-based non-dominated optimization (PRNDO). The permutation and diffusion processes are applied to generate the encrypted images, and the convolution neural network (CNN) can play an essential role in this part. The performance of the proposed framework is assessed by drawing comparisons with competitive techniques based on security parameters. It shows that the proposed framework provides promising results as compared to the existing techniques.

Introduction
Internet of Things (IoT) has changed the way of life by providing connectivity among network-enabled devices. Surveillance is a major advantage of IoT that helps people to keep an eye on the security of homes, business, and critical places. Due to this, a large volume of data is transferred over the network that is further saved on servers. These data can be in the form of images, audio, video, and text, and are further utilized in many applications, such as military communication, healthcare, identification of suspicious activities, remote sensing, etc. As these data contain valuable information, any leakage of the data may create security breaches, which can further hamper the working of government, intelligence agencies, and personal privacy. Therefore, it is necessary to create a secure surveillance framework for IoT systems. In this work, our focus is to secure the images during transmission and storage, because images play an important role in various multimedia applications. The image captured from IoT devices can be sent to a server or directly to concerned personnel for surveillance. If the images are in plain form, then they can reveal all the information to an attacker. Therefore, transmission and storage of the images should be secured. To secure the images, cryptography is the most suitable

•
The secret keys are generated by utilizing a 5D hyperchaotic map. The reason of selection is to generate more complex pseudorandom numbers that cannot be easily estimated.

•
To strengthen the security of the hyperchaotic map, the initial parameters are optimized using partial-regeneration-based non-dominated optimization (PRNDO). A multi-objective fitness function is designed using correlation coefficient and entropy. These two parameters were selected after analyzing their wide acceptability in the literature. Fitness functions based on these parameters provide better optimized solutions. • After the secret key's generation, permutation is performed to change the pixels' position. Thereafter, the diffusion process is performed on scrambled images to produce the encrypted images. • Finally, the performance of the proposed technique is assessed through comparative analyses with competitive techniques based on security parameters.
The rest of the paper is organized as follows: The related work is discussed in Section 2, background is presented in Section 3, and Section 4 elaborates on the image encryption technique for the secure surveillance framework for IoT systems. In Section 5, the simulation results and analyses are discussed, and Section 6 concludes the paper and presents the future research directions.

Literature Review
DNA and hyperchaotic maps (DNA-HC) were used to encrypt the images. In [6], a secure surveillance system was designed using the sine tent cosine approach for the transmission of images, while in [7], a secure communication system was developed using compressive sensing and chaotic map (CSCM) for IoT applications. The authors of [8] encrypted the images using permutation and diffusion operations. The permutation process was carried out using a Henon map, while a chaotic restricted Boltzmann machine was used to perform the diffusion operation on the images [8]. In [9], compressive sensing was used to encrypt the images, where a 3D chaotic map was used to generate the measurement matrix and a 1D chaotic map was utilized to diffuse the pixels of the scrambled image. The authors of [10] proposed an improved fractional 1D chaotic map to perform the image encryption. The permutation and substitution steps were combined to change the position of pixels and the values of an image [10]. The authors of [11] investigated and presented current trends on IP and DS in IOT.
The authors of [12] utilized a differential equation to generate the chaotic oscillator, which is used to scramble the pixels of an image to obtain an encrypted image. In [13], a DP model was proposed for security and privacy. The authors of [14] implemented an image encryption framework: Fresnel transform. In this technique, a lens is not used, and the image is divided into three channels and each is encrypted using a separate key [14]. In [15], a time delay chaotic system was used to encrypt the images. The authors of [16] applied coupled map lattices to generate the keys. In this technique, the random-based diffusion process is implemented to encrypt the images [16]. The authors of [17] developed an image encryption scheme using a 6D chaotic map. The position of pixels of images is permuted at the bit-level to enhance the security, and the pixels are finally diffused using DNA coding. In [18], the authors encrypted the images using tent-dynamics coupled map lattices, and the cyclic shift algorithm was utilized to shift the rows and pseudorandom sequences. The above-discussed techniques involved the use of chaotic maps to generate the secret keys, and although these techniques provide secure image transmission and storage, in most of the techniques, the initial parameters of chaotic maps were not selected optimally. Thus, using parameter estimation techniques, these techniques can be broken [18]. The authors of [19] presented a deep learning model for traffic flow prediction.
Some of the researchers have addressed the above-stated issue by implementing the meta-heuristic techniques in image encryption. The authors of [20] developed an encryption system using DNA and the 1D logistic map for secure transmission of images. Particle swarm optimization (PSO) was utilized to select the best encrypted image based on entropy and the correlation coefficient. The non-dominated sorting genetic algorithm-II (NSGA-II) was used in [21] to optimize the intertwining logistic map, the genetic algorithm (GA) was applied in [22] to optimize the beta-chaotic map, and the Pareto evolutionary algorithm-II was implied in [23] to optimally select the parameters of the 4D chaotic map. Adaptive differential evolution (ADE) was used in [24] for tuning the hyperparameters of the Lorenz chaotic map. Grey hole and black hole attacks were presented in [25], while the 5D chaotic map was tuned in [26] using NSGA. An intertwining logistic map was optimized in [27] using memetic differential evolution, the hyperparameters of the betachaotic map were tuned in [28] using differential evolution, and IoT-based risk assessments were presented in [29].

Five-Dimensional Hyperchaotic Map
The five-dimensional (5D) hyperchaotic map (5DHCM) provides significantly complex chaotic behavior [30,31]. The 5DHCM has five attributes, a cubic nonlinear product, and a better Lyapunov exponent (LE). The huge number of attributes improves the key space, the large LE provides a more dynamic 5DHCM, and the cubic nonlinear product achieves good resistance [32]. Thus, 5DHCM can achieve better encryption keys and can be computed as: (1) Here, in Equation (1), d 1, d 2, d 3, d 4, and d 5 are initial attributes required for 5DHCM, and q, r, s, t, u, v, and w define the control attributes of 5DHCM. Chaotic attractors are represented in Figure 1 and Figure 4 for q = 30, r = 10, s = 15.7, t = 5, u = 2.5, v = 4.45, and w = 38.5. Figure 1 demonstrates the chaotic attractor in the d1-d2 plane, whereas Figure 2 shows the chaotic attractor in the d1, d2, and d3 planes. The chaotic attractor in the y1-y2-y3 plane is presented in Figure 2. The time series analysis of the state attribute d1 utilizes Equation (1), as depicted in Figure 3. It is demonstrated that d1 achieves random behavior and is non-periodic in nature. System (1) contains 5 equilibrium points, such as (0, 0, 0, 0, 0), (2.

Partial-Regeneration-Based Non-Dominated Optimization
Partial-regeneration-based non-dominated optimization (PRNDO) [34] provides optimal solutions considering both the best and worst cases. This type of optimization is mainly used to solve the asymmetrical problems. In this study, a bottom-boosting methodology was utilized to reduce the number of function evaluations. It also provides a balance between better solutions and computational speed by developing a novel partialregeneration strategy and mutation operator. Therefore, it can generate efficient solutions with good computational speed. The outline of PRNDO is shown in Figure 4. It contains population initialization, minimum heap (min-heap) construction, bottom-boosting, partial-regeneration strategy, and termination condition. Initially, a population is randomly generated with the pair consisting of solution and scenario. The other parameters are also initialized, such as control attributes, solution and scenario dimensions, and maximum number of generations. Thereafter, by using the given population, a min-heap is built in the beginning of every generation. Every solution is treated as a node of min-heap, and the objective value of it acts as a key of the node. After that, scenarios of min-heap nodes are updated using the bottom-boosting scheme. The fitness function evaluations are also controlled by this scheme. Using fitness values of each individual, a sorted population is generated in increasing order. The trial scenario is produced from mutation and binomial recombination. The fitness value of the trial scenario is then calculated with respect to the original scenario. If the trial provides better fitness, then the original scenario of the individual will be upgraded. Otherwise, the old scenario will be used in the next generation. During the updating of scenarios, min-heap is also updated using the current population. Next, all the individuals are controlled and updated using the partial-regeneration strategy. The mutation and binomial recombination is also utilized. Finally, the termination condition (such as maximum number of generations evaluation) is tested, and optimal solutions are obtained as a result. IoT-based data analytics are presented in [34,35]. In [36] a comparative study is performed based on machine learning techniques.

Proposed Image Encryption Technique for Secure Surveillance Frameworks
An image encryption technique for secure surveillance frameworks for IoT systems is shown in Figure 5. The obtained images from surveillance cameras are initially encrypted by the proposed technique, then transmitted over the network. The obtained image is firstly decomposed into red (R), green (G), and blue (B) channels. The secret keys, such as d 1, d 2, d 3, d 4, and d 5, are obtained from 5DHCM (Algorithm 5). The required initial parameters of 5DHCM are optimized using PRNDO (Algorithm 2). All three channels are permuted using Arnold transform. Then, pixels of permuted channels R, G, and B are diffused utilizing d 1, d 2, and d 3, with the (⊕) operator, respectively. The obtained images are δR, G , and B . G and B are further diffused using ⊕ operation using δR, and produce δG and δB. Two more keys (d 6 and d 7) are generated. d 6 is generated from d 1 and d 2 using ⊕ operation, d 7 is generated from d 3 and d 4 using ⊕ operation, and d 4 is then utilized to update d 5 and d 6. Encrypted color channels, i.e., R, G, and B, are obtained by diffusing δR, δG, and B" with d 5 , d 6 , and d 7, and the η operator, respectively. Finally, the encrypted image (EM) is obtained by concatenating the R, G, and B.
The step-by-step approach is shown in Algorithm 1.

PRNDO-Based Optimal Parameters
The parameters of 5DHCM are d1, d2, d3, d4, d5, q, r, s, t, u, v, and w, and they need to be initialized. Manual selection of the above parameters is a computationally expensive task. For better key generation, these parameters are selected optimally by using PRNDO optimization. The procedure to generate the optimal parameters for 5DHCM using PRNDO is outlined in Algorithm 2.

Algorithm 2 PRNDO-based optimal parameters' generation
Input: Solution dimension Sol o , scenario dimension S o , maximum generation N h , and population size M l Output: Optimized population: Set generation u = 0; //population initialization P a = {(z 1,u , I 1,u ), (z 2,u , I 2,u ), . . . , (z M ,u , I M,u )}, where z k,u = {z 1 , S 2 , . . . , S Sol d } for y = 1 to M s do fitness of individual (z k,u , I k,u ) is evaluated using Algorithm 6; end for u = 1 to N h do Min heap is built for each individual in q u ; Use (Algorithm 3) to implement the bottom-boosting approach on min-heap; for k = 1 to M l do //Individual (z e , I e ) stored as a root node in the min-heap zk,u = ze, Ik,u = Ie; Extract root node from min-heap; end zbest = z1, u; Use partial-regeneration strategy for D u updating (Algorithm 4); D u+1 = D u ; end In Algorithm 2, firstly, the parameters' solution dimension Sol o , scenario dimension S o , maximum generation N h , and population size M l are initialized. Using normal distribution, initial population D u is generated randomly. Each individual (zk,u, Ik,u) represents a set consisting of solution and scenario. Fitness of (zk,u, Ik,u) is evaluated using Algorithm 6. A min-heap is built using D u . The scenarios are updated using Algorithm 3. The current population is updated by extracting the root node of min-heap. Then, the nodes are arranged in increasing order on the basis of fitness. The initial solution of a given population is utilized as a global best solution. Thereafter, a partial-regeneration strategy is utilized to further update the current population (Algorithm 4). The entire steps are iteratively implemented until the stopping criteria are not met.

Secret Keys
The process of secret keys' generation using 5DHCM is elaborated in Algorithm 5. It uses the optimized parameters obtained from Algorithm 2. The keys such as d1, d2, d3, d4, d5, d6, and d7 are generated using Algorithm 5. To diffuse the image, these keys are utilized by Algorithm 1 to obtain the encrypted image.

Fitness Evaluation
To compute the individuals, the following fitness function is utilized Correlation and entropy are widely accepted parameters to obtain the optimal solutions because in image encryption, there is a need to reduce the relationship between the pixels. In the case of maximum entropy, each pixel carries the same amount of information. Both parameters hide the statistical behavior of the images from the attacker. The desired value of correlation and entropy should be near 0 and 8, respectively. The fitness function is described in Algorithm 6.
Apply inverse Arnold transform on R, G, and B; //Concatenate the decrypted channels DI = [R, G, B]; return DI

Image Decryption Algorithm
The encrypted image is decrypted using Algorithm 7 to obtain the original image. The initial values of d1, d2, d3, d4, d5, q, r, s, t, u, v, w, and η attributes are needed to decrypt the image.

Comparative Analysis
Simulations were performed using MATLAB 2020a with the help of the image processing toolbox. The proposed encryption model is compared with five well-known competitive approaches by using various performance metrics. The initial parameters of PRNDO are assigned as F = 0.6, Cr = 0.2, N = 50, KS = 170, and T = 5. Four surveillance camera images were used, with 256 × 256 size.

Visual Analysis
Input and the respective encrypted surveillance images are shown in Figure 6. It clearly indicates that the obtained encrypted surveillance images seem like purely noisy images in nature. Therefore, no attacker can obtain any kind of details of the encrypted images.

Image Decryption Algorithm
The encrypted image is decrypted using Algorithm 7 to obtain the original image. The initial values of d1, d2, d3, d4, d5, q, r, s, t, u, v, w, and η attributes are needed to decrypt the image.

Comparative Analysis
Simulations were performed using MATLAB 2020a with the help of the image processing toolbox. The proposed encryption model is compared with five well-known competitive approaches by using various performance metrics. The initial parameters of PRNDO are assigned as F = 0.6, Cr = 0.2, N = 50, KS = 170, and T = 5. Four surveillance camera images were used, with 256 × 256 size.

Visual Analysis
Input and the respective encrypted surveillance images are shown in Figure 6. It clearly indicates that the obtained encrypted surveillance images seem like purely noisy images in nature. Therefore, no attacker can obtain any kind of details of the encrypted images.

Entropy
Entropy [29] computes the degree of randomness in images. In encrypted images is desirable to have 8 degrees of randomness. An entropy analysis of the proposed secu surveillance system is depicted in Table 1. It shows that the entropy values of all the tec niques on surveillance images (SIk), where k = 1, 2, 3, or 4, were near to 8, but the propos secure surveillance system achieved higher values than the existing techniques.

Entropy
Entropy [29] computes the degree of randomness in images. In encrypted images, it is desirable to have 8 degrees of randomness. An entropy analysis of the proposed secure surveillance system is depicted in Table 1. It shows that the entropy values of all the techniques on surveillance images (SIk), where k = 1, 2, 3, or 4, were near to 8, but the proposed secure surveillance system achieved higher values than the existing techniques.

Mean Absolute Error
Mean absolute error (MAE) analysis is shown in Table 3. It revealed that the proposed model obtained significantly better values than the existing models.

Security Analysis
In this section, we will test the proposed secure surveillance system model against various security attacks. The objective was to evaluate whether or not the proposed secure surveillance system model can resist various security threats.

Histogram Analysis
To evaluate the performance of the proposed secure surveillance system model against an attack, we used histogram analysis. It was found that the histograms of the encrypted images should be uniform. Histogram analysis of the proposed model is shown in Figure 7, and it was found that the histograms of encrypted images obtained from the proposed secure surveillance system model were evenly distributed.

Correlation Analysis
Correlation can also be used to evaluate the statistical information of surveillance images. Thus, it is desirable that the correlation between the adjacent pixels vertically, diagonally, and horizontally should be minimum. The horizontal correlation analysis is depicted in Table 4. It shows that the correlation among horizontal pixels was minimum compared to the existing encryption models. Vertical and diagonal correlation analyses are shown in Tables 5 and 6. The minimum correlation values of the proposed secure surveillance system indicate that the proposed model can resist correlation attacks.  [2] 0.0090 0.0060 0.0040 0.0022 DFRT [3] −0.0050 0.0123 0.0090 0.0040 HDNA-HC [5] 0.0040 0.0070 −0.0090 0.0036 CSCM [7] 0.0072 0.0038 −0.0050 0.0055 Proposed −0.009 0.0016 0.0019 0.0021

Differential Analysis
The differential analysis can be computed using the Number of Pixel Change Rates (NPCR) and Unified Average Change Intensity (UACI). The NPCR and UACI analyses of the proposed secure surveillance system are depicted in Tables 7 and 8. It was found that the proposed model achieved better NPCR and UACI values than the competitive models. Thus, the proposed model is sensitive towards the tiny modification in input surveillance images. Robustness of the proposed secure surveillance system was evaluated against salt and pepper and Gaussian noise attacks with various densities of noise.

Key Analysis
To evaluate the performance of the proposed secure surveillance system against brute-force attack, key sensitivity and key space analysis were considered.

•
Secret key space The proposed secure surveillance system computes the secret keys by 5DHCM. It requires 7 state attributes (i.e., d1, d2, d3, d4, d5, d6, and d7) and 7 control attributes (i.e., q, r, s, t, u, v, and w). Assume that the precision of attributes is 10−16. Thus, each attribute has 1016 possible values. Thus, the proposed secure surveillance system has key space: Since the key space > 1030 (≈ 2100), therefore, the proposed encryption model can resist a brute-force attack.

•
Secret key sensitivity analysis It is desirable for the secret keys to be more sensitive towards tiny changes. Seven keys were evaluated to implement the proposed encryption. These 7 keys were computed by Equation (1) with the help of initial state (i.e., u1, u2, u3, u4, u5, u6, and u7) and control (i.e., s, r, t, i, q1, p, n, e, g, and q2) attributes. Assume that a tiny change is made in the bits of u1. To verify the key sensitivity, we will encrypt the surveillance images using an actual key and with a tiny change in the same key. The encrypted surveillance images with actual and modified keys are shown in Figure 11b,c. Figure 11d shows the error between Figure 11b and c. The computed error seems to be a completely random image. We have also decrypted Figure 11b by utilizing both keys. The evaluated results are depicted in Figure 11e,f. If the identical key is used for decryption, then the obtained image is similar to the actual image. The decrypted image obtained using a tiny change in the actual key seems to be a completely noisy image. Thus, the proposed model is very sensitive towards the encryption key.  Table 9 shows the error between a modified and an actual key-based encrypted image. It demonstrates that the proposed secure surveillance system is sensitive towards initial key values.  Tables 10 and 11. These tables reveal that the proposed model can encrypt and decrypt images at a higher speed, as it requires less time than the existing models.

Conclusions
An image encryption technique for secure surveillance for IoT systems has been proposed in this paper. The image was made secure before the transmission from the surveillance system. A hyperchaotic map was utilized to obtain the pseudorandom sequences. The initial parameters of the hyperchaotic map were produced using PRNDO. The permutation was carried out through Arnold transform. Thereafter, a diffusion process was implemented to generate the encrypted images. The performance of the proposed framework was assessed by drawing the comparisons with competitive techniques based on security parameters. It was found that the proposed framework provides promising results as compared to the existing techniques. The proposed technique is able to resist against different attacks, such as noise and enhancement attacks. Experimental analyses showed that the proposed technique outperformed the competitive techniques in terms of visual analysis, quantitative analysis, security analysis, and execution time. As the proposed technique can encrypt and decrypt images at higher speeds, therefore, the proposed technique can be used for real-time secure surveillance systems.


Text Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Radiography image analysis using cat swarm optimized deep belief networks

: Radiography images are widely utilized in the health sector to recognize the patient health condition. The noise and irrelevant region information minimize the entire disease detection accuracy and computation complexity. Therefore, in this study, statistical Kolmogorov – Smirnov test has been inte grated with wavelet transform to overcome the de - noising issues. Then the cat swarm - optimized deep belief network is applied to extract the features from the a ﬀ ected region. The optimized deep learning model reduces the feature training cost and time and improves the overall disease detection accuracy. The network learning process is enhanced according to the AdaDelta learning process, which replaces the learning parameter with a delta value. This process minimizes the error rate while recognizing the disease. The e ﬃ ciency of the system evaluated using image retrieval in medical application dataset. This process helps to determine the various diseases such as breast, lung, and pediatric studies.

The manuscript is arranged as follows: Section 2 discusses the different research works and analyses the medical radiographic images; Section 3 explains the working process of the optimized DL model for retrieving the clinical patterns; Section 4 evaluates the excellence of the introduced system; and Section 5 defines the conclusion.

Related works
Pandya et al. [23] applied DL techniques for analyzing medical images and detecting diseases. This process uses the medical images (computerized tomography (CT), magnetic resonance imaging (MRI), etc.), biomedical signaling (electrocardiogram, electroencephalogram, and omics (DNA, RNA, etc.) to examine the clinical diseases. The captured medical images are processed by different DL models such as deep belief networks (DBNs), long short-term memory, stacked autoencoder, convolution networks, and recurrent networks. In addition to this, deep hybridized approaches such as multidimensional recurrent networks, deep spatiotemporal networks, and recurrent bidirectional networks classify the diseases from the medical images. Thus, the different DL model ensures promising results while analyzing the medical images with a minimum error rate and human efforts.
Debelee et al. [24] created the breast cancer medical images analyzing system using a deep learning approach (DLA). This process obtains the breast images via the magnetic resonance imaging, digital mammography, ultrasound, and breast tomosynthesis. The gathered medical images are processed using the DL model that predicts the breast cancer patterns with minimum involvement of domain experts.
Wuestemann et al. [25] examined the bone scans to diagnose the tumor entities by applying the DLbased neural network algorithm. This study uses the bone scan imaging (BSI) index values to examine the bone radiographic images. The prostate, lung, breast, and hepatocellular carcinoma cancer entities are examined using DL model from the BSI values. This process helps to minimize the working load also to improve the workflow process in the medical department.
Rehman et al. [26] implemented the brain tumor detection system using the transfer learning with deep learning framework (TLDLF), which uses three convolution networks such as VGGNet, GooglLeNet, and AlexNet for analyzing the various brain tumors such as pituitary, glioma, and meningioma. During the analysis, MRI images are examined with the help of freeze and fine-tune transfer learning process. Data augmentation techniques are applied to generalize the MRI slice image, which helps minimize data overfitting and enhance overall brain tumor recognition accuracy.
Sharma et al. [27] segmented brain tumor-affected region from MRI images using the different evaluations with the OTSU method and neural networks. Initially, in the MRI image, global threshold values are estimated to recognize the tumor-affected region. The optimal threshold value is selected according to the introduced algorithm. This process is continuously trained using neural networks, which effectively minimizes the error rate.
Abid et al. [28] identified lung cancer nodules from CT images using multiview convolution recurrent neural networks (MCRNN). This system is used to resolve the cost-intensive and inconsistent results while recognizing lung cancer nodules. The introduced method utilizes the effective learning process, which examines the image size, shape, and cross-slice variations that improve the accuracy of lung cancer identification. The system's performance was evaluated using Lung Image Database Consortium and Image database resource initiative database with the respective performance metrics.
Azizi et al. [29] examined temporal-enhanced ultrasound images for detecting prostate cancer using deep recurrent neural networks (DRNN). The introduced DRNN approach is analyzing the temporal details from ultrasound images. The extracted information is further investigated with long-term neural networks recognizing the benign and malignant with higher accuracy.
Masud et al. [30] diagnosed breast cancer from ultrasound images using convolution neural networks (CNN). Initially, the ultrasound images are trained by eight different fine-tune models that help to identify the test images related to clinical results. This process utilizes the 10-fold cross-validation process to evaluate the excellence of the system. In addition to this, various research studies are summarized in Table 1. According to the above research studies, DL techniques are widely utilized in the medical field to recognize various clinical diseases. The DL models with effective learning techniques and activation functions to identify the disease-affected region. The DL model requires the optimization process to improve the overall clinical analysis process by reducing the cost, labor intensive, and computation complexity. Moreover, the captured radiographic images are having several noises while gathering the images. Then, the de-noising process also played a crucial role while investing the medical images. So, in this article, we applied the optimized techniques to examine the different radiographic images. The detailed working process of cat swarm-optimized DBNs-based radiography image analysis is discussed in the following section.

Radiography image analysis using optimized DBNs
The detailed working process of optimized DBN-based radiography image analysis is explained in this section. The system aims to increase the radiography image analysis accuracy by reducing the time, error rate, and computation complexity. This process uses different steps such as image noise removal, segmentation, feature extraction, and classification process. According to the discussion, the working process is shown in Figure 2.
Radiography image analysis structure is demonstrated in Figure 2. This system uses the two phases: training and testing; each stage has image preprocessing, segmentation, feature extraction, and classification processes. The training phases use effective learning functions while deriving the medical features and classification process. During the training process, labels are provided and stored in the database. With the help of training images, testing has to be performed to identify the new image patterns. The detailed working process of radiography image analysis is discussed in the following section.

Medical image preprocessing
Preprocessing is nothing but improving the image's quality by applying statistical analysis in a comparable and repeatable manner [1,2]. In medical image processing, the noise removal process consists of resampling, intensity normalization, and co-registration methods. These processes are more helpful to improve further radiographic image analysis. The co-registration is the way of mapping the images with respective reference coordinate system; resampling is performing the voxel size of images with the unique voxel resolution. Therefore, the collected radiographic images are resized into 160 × 160 dimension, and the one-row matrix need to be reshaped.
Further, the complexity of the original images has to be reduced by applying the single-level discrete twodimensional wavelet transform approach, which examines the highly discriminative coefficient values from the medical images; the best coefficient values are selected according to the statistical KSt. Initially, the wavelet transform is applied to the image for reducing the dimensionality of the images by examining the image pixel density value. The density values are derived by using high and low pass filters. Here, Haar wavelet function is applied to the image because of the orthogonality property, which effectively examines the image wavelet coefficients. Considering the mother Haar wavelet function is ( ) φ x that is defined by equation (1).
In equation (1) . Then, the elements presented in the orthogonal basis values are computed using equation (2).
Based on equations (1 and 2), image intensity corresponding coefficient values are computed, and coefficient values are estimated. Then best coefficient values are selected according to the statistical KSt. It is one of the nonparametric tests comparing the two coefficients values from the extracted image coefficient values. This section process is performed according to the location and shape of pixels and cumulative distribution value. Then the empirical distribution function ( ) F n is computed from the distributed observations X i , which is computed using equation (3).
In equation (3), n is independent; the indicator function is denoted as I. From the computed ( ) F x n value, KSt is examined using equation (4).
In equation (4), the supremum of set distance is denoted as sup x . From the computed distance D n value, the KSt samples are analyzed using equation (5).
According to the KSt test similarity values, each pixel was examined with the alternative and null hypothesis. If the pixel has an H0 (null) hypothesis, then both pixels have the same distribution, and there is no need to replace or remove the pixel. If the pixel belongs to the alternative (H1) hypothesis, then pixel has a different population that needs to be removed from the image and replaced by using a median value. After removing the medical image's noise, the disease-affected region must be extracted according to the Prewitt kernel operator.

Region of interest (ROI) region segmentation
The next step is to extract the disease-affected region by applying the Prewitt kernel operator. This process examines the medical image regions by investigating the image edge-related features. The medical image edge features are placed a crucial role while predicting the disease-affected region. This process works similar to the Sobel operator, which means it uses the 3 × 3 kernel. With the kernel details, image left-right adjustment points and upper-lower limit pixels are estimated to identify the edge relevant information. This process eliminates the edge information and smoothens the edge information, which causes to improve the overall ROI segmentation process. Here, the edges are investigated according to the horizontal and vertical direction. Therefore, the horizontal  (6).
From the computed magnitude orientation, the edge gradient direction value should be estimated according to equations (7 and 8).
The computed edge gradient direction value, derivatives of gradient, and vector gradient values are estimated as δ . This has been written as Finally, the computed values are examined to predict the gradient direction ( ) According to the Prewitt kernel values, image edge-relevant details are extracted. Similar edge information is grouped. This Prewitt kernel extracted process is applied continuously to the images for extracting the affected regions.

DBN-based feature derivation
The third important step is feature extraction, which is done by applying the cat swarm optimization algorithm-based deep belief network (CSA-DBN). The extracted edge regions are fed as the input to this process, and the meaningful features are derived. The DBN approach works according to the multilayer restricted Boltzmann machine (RBN) approach that extracts the in-depth image features. During this process, the input data and first hidden layers related to the probability distribution value are estimated in the visible layer computed via equation (10).
The joint probability distribution ( ) − h h , n n 1 between visible and hidden layer values is computed from the RBN model's topmost layer. The RBN has two layers: a visible or input layer and a hidden layer, as shown in Figure 3. The RBN has the connection between the entire visible layer and hidden layer but having no connection within the layer and no connection between the invisible and visible layers. Then the probability distribution of hidden and visible layers is defined as ( ) p v h , here; input image features are obtained from the output layer h. According to the discussion, ( ) p v h , is estimated using equation (11a) and (11b).
The ( ) p v h , value is estimated from the network energy function ( ) E v h , and the normalization factor ( ) Z θ , which are derived from equation (11c) and (11d).
Here, h and v denoted as hidden and visible layer units, visible and hidden layer connections are having W weight, ′ c is the hidden layer bias value, and ′ b is the visible layer bias value. After computing the ( ) p v h , value, the network needs to be trained according to the learning parameters such as weight (W) and a bias value. Initially, the RBM network first layer was trained by fixed training parameters, and the output is passed to the next layer (hidden layer) to predict the image features. The last layer of the network utilizes the SoftMax regression function with supervised gradient descent algorithm. According to RBM algorithm, the training process is performed that helps to investigate the new medical images. In the training process, input samples are analyzed by computing the ( ) p v h , value and contrast divergence value of learning parameter that is calculated as follows: Here, W is weight value, the learning rate of contrast divergence process is denoted as ε, and x x , 1 2 is denoted as the input vectors in the training process. The computed values belong to 1. The samples are trained effectively; the learning parameters should be converged. It has to be updated to improve the overall image training process. In the testing process, the last layer's output is fed into the SoftMax regression function to estimate the image's features. During the input vector training process, AdaDelta learning process is utilized to minimize the convergence value. It is worked according to the squared delta's exponential moving average value. The new weight value is estimated by taking the difference between the newly updated weight value and current value. Therefore, the learning parameter values are replaced by the computed delta value. Then the new weight value is estimated using equation (15).
. After computing the AdaDelta value, the RBM network trained again to improve the system's overall performance. Further, the current weight value detection process should be enhanced by applying the cat swarm optimization algorithm (CSA). The CSA algorithm works better than other optimization algorithms and can resolve the optimization problem during input training and classification. This algorithm works according to food searching behavior of cat, such as seeking and tracing mode. Initially, the cat investigates the surroundings and passes to the next position in the seeking mode. In the tracing process mode, the cat chases a specific target by identifying the location. The cat identifies the global solution in the seeking mode and the local solution in the tracking mode from the searching process. The cat has the seeking memory pool, mixed ratio, and dimension change count parameters during the searching process.
In this process, the fitness value is computed for entire candidate points, and the most relevant probability values are chosen as the fitness value. Else, the seeking and tracking probability value is calculated to select the candidate value, which is done by equation (16).
The seeking mode probability value P k is computed from the fitness value, and the velocity of the cat chasing process is estimated in tracking mode using equation (17).
Here, d is the dimension, and position of the prey or weight value is estimated as , . Inertia weight values are denoted as β, the constant acceleration value is c, and r 1 represented as the random value from 0 to 1. The present and global positions are indicated, respectively, as x k d , and x d best, . This process is repeated every time during the image analysis because the right selection and updating of weight value minimize the deviations while extracting features from the image. Then the overall working process of CSA-DBN-based image feature extraction process is illustrated in Figure 4. Figure 4 shows that the region segmented image pixels are transmitted as the input represented as T1, T2, T3 … Tn. The network processes the input pixels, and the output is obtained as The computed output features are compared with the desired characteristics for investigating the error value done according to equation (19).
If the network produces the error value, then the optimized weight values are selected according to the CSA optimization algorithm process. The algorithm fitness value is estimated using equation (20).
The new velocity is computed using equation (17), and the latest weight value is calculated based on the fitness function. The identified weight values are compared with the current weight value defined in equation (15), and the delta value is used to update the process. This process is repeated until the optimized features from the medical images are extracted. The extracted features are further examined by optimized classifiers such as DL techniques or other classifiers to recognize the affected region's condition. This process effectively identifies the radiographic image's deviation due to the effective examination of each image pixel.

Results and discussion
This section examines the effectiveness of the CSA-DBN-based radiographic image analysis process. The discussed system uses the Medical Segmentation Decathlon dataset for evaluating the proficiency of a defined system. The dataset consists of several radiographic images like hepatic vessel, prostate, liver, heart, brain tumor, spleen, pancreas, and colon. For every medical image, the massive number of radiographic details is illustrated in Table 2. These medical images' segmented regions are investigated pixel by pixel in CSA-DBN algorithm for extracting the optimized features. The derived features are utilized to further image analysis by various  postimage processing techniques. The efficiency of the created system is determined using the following performance metrics: Accuracy rate: Precision rate: F-score: In equations (21), (22), and (23), TrNe represents the true-negative rate, TrPo represents the true-positive rate, FaPo indicates a false-positive rate, and the FaNe indicates a false-negative rate.
The medical image's features are examined effectively from the computation of accuracy in equation (21). The CSA-DBN technique obtained results are compared with the existing research studies such as a DLA [24], TLDLF [26], MCRNN [28], and DRNN [30]. The obtained feature extraction accuracy (Acc) value is shown in Figure 5.  introduced CSA-DBN approach derives the disease-related features from the Prewitt kernel-based segmented region. In addition to these metrics, the presented method's precision value should be examined on the different number of images and another type of medical images. The obtained results are illustrated in Figure 6.    Here, the recall values are investigated in terms of the different number of images and the various medical images. The diseaserelated optimized features are selected from the extracted features according to the CSA seeking and tracking mode. The algorithm determines the best features by computing the fitness value-related weight-updating process. Hence, the introduced CSA-DBN approach ensures the high recall (99.41%) value collated with existing methods such as DLA (95.93%), TLDLF (96.23%), MCRNN (97.01%), and DRNN (98.25%). Due to the effective retrieval and selection of features, improves the overall image feature extraction process. Then the obtained F1-score values are illustrated in Table 3. Table 3 clearly shows that the CSA-DBN obtained high feature extraction accuracy (99.32%) compared to existing researchers works DLA (96.48%), TLDLF (97%), MCRNN (97.65%), and DRNN (98.20%). Although these methods attain high accuracy values, the introduced CSA-DBN approach has a minimum deviation value, which means the extracted features are almost the same as the desired image features. This effectiveness is evaluated using the error rate value. The obtained result is illustrated in Figure 8. , which causes to minimize the deviation between predicted and desired image features. Among the several approaches, CSA-DBN attains the minimum error value (0.11) compared to other methods. Thus, the introduced system successfully recognizes the disease-affected region-related features using optimized learning and training parameters.

Conclusion
Thus, the study analyzes the CSA-DBN-based radiographic image analysis process. In this study, the Medical Segmentation Decathlon dataset was utilized for gathering the medical images. The images are decomposed into approximation and detailed coefficient, which helps remove the noise from the image. Then the KSt test has been conducted to determine the similarity between the pixels. According to the value, the deviated pixels are computed and removed from the image. Then the Prewitt kernel operators are applied to identify the disease-affected region fed into the DBN. The DBN approach recognizes image features by utilizing the AdaDelta learning process. Further, the network process improved by updating the new weight value computed according to the cat swarm optimization technique's seeking and tracking mode. This effective process minimizes the deviation and enhances the feature detection accuracy up to 99.32%. In the future, the excellence of the system is enhanced by using meta-heuristic optimization algorithm based postradiographic image analysis.