<figure><img src="image_1.png" /></figure>

HAL
open science

# An Efficient Cooperative Method to Solve Multiple Sequence Alignment Problem

Lamiche Chaabane

<figure><img src="image_2.png" /></figure>

## To cite this version:

Lamiche Chaabane. An Efficient Cooperative Method to Solve Multiple Sequence Alignment Problem. 6th IFIP International Conference on Computational Intelligence and Its Applications (CIIA), May 2018, Oran, Algeria. pp.185-195, 10.1007/978-3-319-89743-1_17. hal-01913906

HAL Id: hal-01913906

https://inria.hal.science/hal-01913906

Submitted on 7 Nov 2018

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Efficient Cooperative Method to Solve
Multiple Sequence Alignment Problem

Lamiche Chaabane

Computer Science Department, Mohamed Boudiaf University
M'sila, Algeria
Lamiche07@gmail.com

**Abstract.** In this research work, we propose a cooperative approach called simulated particle swarm optimization (SPSO) which is based on metaheuristics to find an approximate solution for the multiple sequence alignment (MSA) problem. The developed approach uses the particle swarm optimization (PSO) algorithm to discover the search space globally and the simulated annealing (SA) technique to improve the population leader « gbest » quality in order to overcome local optimum problem. Simulation results on BaliBASE benchmarks have shown the potent of the proposed method to produce good quality alignments comparing to those given by other existing methods.

**Keywords.** Cooperative approach; multiple sequence alignment; SPSO; PSO; SA; BaliBASE benchmarks.

## 1 Introduction

Multiple sequence alignment (MSA) is a crucial tool in molecular biology and genome analysis. It has been considered as one of the important tasks in bioinformatics [1]. It helps to construct a phylogenetic tree of related DNA sequences, to predict the function and structure of unknown protein sequences, by aligning with other sequences whose function and structure is already known, and to allow comparison of the structural relationships between sequences by simultaneously aligning multiple sequences and constructing connections between the elements in different sequences [2].

Discovering optimal alignment in multiple biological sequence data is known as a NP-complete problem [3]. It has been identified as a combinatorial optimization problem [4], which is solved by using an exact or approximate algorithms. These algorithms lead to exploit various genetic information to determine evolutionary relationships among living beings [3].

Recently, the trend has shifted to the use of iterative algorithms in order to tackle the MSA problem. These approaches are based on the improvement of the given initial alignment through a series of some iterations until a stopping criterion is reached. They include genetic algorithm (GA) [5], simulated annealing algorithm (SA) [6], particle swarm optimization (PSO) [7], GA-ACO algorithm [8], Ant Colony Algorithm [9].
rithm [9] and so on. Generally, these metaheuristics are able to find nearly optimal
solutions for large instances in a reasonable processing time.

In this study, we propose a hybrid approach called SPSO algorithm to solve the MSA problem. The developed model is the cooperation between both PSO algorithm and simulated annealing technique. The remainder of the paper is organized as follows: section 2 presents a brief review of the researches related to the proposed framework. In section 3, both PSO and SA concepts are described. In section 4, our proposed SPSO algorithm is explained in detail. In section 5, the simulation results are provided. Finally, the study is concluded in section 6.

## 2 Background

A brief review of some related works in the multiple sequence alignment field using iterative methods is presented in this section. Rias et al. [10] presented a tabu search algorithm to align multiple sequences. The framework of his work consists to implement the adaptive memory features typical of tabu searches in order to obtain multiple sequences alignment where the quality of an alignment is measured by the COFFEE objective function. In [11], the authors proposed a novel approach to multiple sequence alignment based on Particle Swarm Optimization (PSO) to improve a sequence alignment previously obtained using Clustal X

In Ref. [12], the authors presented an approach to the MSA problem by applying genetic algorithm with a reserve selection mechanism to avoid premature convergence in GA. A better results are obtained compared with those produced by classical GA. The authors in [13] proposed an algorithm based on binary PSO algorithm to address the multiple sequence alignment problem. Simulation results using SP score measure and nine BaliBASE tests case showed that the proposed BPSO algorithm has superior performance when compared to ClustalW and SAGA algorithms.

An artificial bee colony algorithm for solving MSA problem is introduced in [14]. In Ref. [15], V. Cutello et al. presented an immune inspired algorithm (IMSA) to tackle the multiple sequence alignment problem using ad-hoc mutation operators. Experimental results on BALIBASE v.1.0 show that IMSA is superior to PRRP, CLUSTALX, SAGA, DIALIGN, PIMA, MULTIALIGN and PILEUP8. In [16], simulated annealing technique was applied to solve MSA problem using a set of DNA benchmarks of HIV virus genes of human and simian.

In Ref. [17], the authors proposed a hybrid algorithm using a GA and cuckoo search algorithm to improve multiple sequence alignment. The obtained results are compared with ClustalW by using five different datasets. Recently, an efficient method by using multi-objective genetic algorithm (MSAGMOGA) to discover optimal alignments is proposed in [18]. Experiments on the BALiBASE 2.0 database confirmed that MSAGMOGA obtained better results than MUSCLE, SAGA and MSA-GA methods.
# 3 Preliminaries

## 1.1 Outline of the Particle Swarm Optimization (PSO)

Particle swarm optimization (PSO) is an adapted algorithm developed the first time by Kennedy and Eberhart [19], inspired by bird flocking and fish schooling. PSO used a population of individuals called particles and two primary operators: velocity update and position update. During each generation, each particle moves toward the particles according to its best position and the global best position. In addition, a new velocity value for each particle is calculated based on its current velocity, the distance from its previous best position and the distance from the global best position. The evolution of the swarm is governed by the following equations:

$$V^{(k+1)} = w \cdot V^{(k)} + c_1 \cdot rand_1 \cdot (pbest^{(k)} - X^{(k)}) + c_2 \cdot rand_2 \cdot (gbest^{(k)} - X^{(k)}). \quad (1)$$

$$X^{(k+1)} = X^{(k)} + V^{(k+1)}. \quad (2)$$

where:

* X is the position of the particle,

* V is the velocity of the particle,

* w is the inertia weight,

* pbest is the best position of the particle,

* gbest is the global best position of the swarm,

* rand1, rand2 are random values between 0 and 1,

* c1, c2 are positive constants which determine the impact of the personal best solution and the global best solution on the search process, respectively, k is the iteration number.

Concerning the stopping condition, generally PSO algorithm terminates when a set number of times or until a minimum error is achieved. All parameters of PSO algorithm are fixed experimentally in order to have a good compromise between the convergence time of the algorithm and the final solution quality.

## 1.2 Outline of the Simulated Annealing (SA)

Simulated annealing (SA) is a general probabilistic local search algorithm proposed by Kirkpatrick et al. [20] to solve difficult optimization problems. It is inspired by the annealing of solids in physics. SA models the slow cooling process of solids to achieve the minimum energy as an analogy, reaching the minimum function value. As a result, it attains an optimal/near-optimal solution by implementing an iterative cooling process from a high temperature, at which solid particles are in the liquid phase. Simulated annealing utilizes a control parameter, temperature T, for the cooling process. The solid is allowed to attain the thermal equilibrium for every T degree that has its energy E probabilistically distributed, as given in equation (3), where k_b is the Boltzmann constant.
$$P(E) = e^{\frac{-E}{k_{b}T}}. \qquad (3)$$

In the combinatorial optimization context, if we aim to find a good solution then we move from a solution to one of its neighbors in the search space according to a probabilistic criterion. If the cost decreases then the solution is retained and the move is accepted. Otherwise, the move is accepted only with a probability depending on the cost increase and the temperature parameter T [20].

# 4 Proposed Method

PSO performs excellently in the case of global search but it is not efficient in local search. It suffers from its weak local search ability and the local minima limit. On the other hand, SA is good in local search while less good in global search. However, it takes advantage of the acceptance of candidate solutions by the use of metropolis criteria and must escape from local optimum to search in other solution space.

In order to construct an intelligent algorithm which can be effectively avoid weaknesses and fully use the advantages of both PSO and SA algorithms, we propose a hybrid approach which combines the PSO with simulated annealing, so the new hybrid algorithm called Simulated Particle Swarm optimization (SPSO) conducts both global search and local search in every iteration. According to this hybridization manner, the probability to obtain better solutions significantly increases. At each iteration, the proposed hybrid SPSO algorithm consists of applying PSO algorithm in order to guide global search, and use SA to improve the gbest which helps PSO to escape from local optimum and increase the convergence speed of SPSO algorithm. The flowchart of the proposed SPSO is presented in Fig.1.

## 1.3 PSO components of MSA problem

**Particle Representation.** Each particle represents a potential solution to the MSA problem, effectively it corresponds to a sequence alignment. A particle is then represented as a set of vectors, where each vector specifies the positions of the gaps in each one of the sequences to be aligned [21].

**Swarm Initialization.** The size of the whole swarm is determined by the user. The initial set of particles is generated by adding gaps into each sequence at random position, thus, all the sequences have the same length L in which its value is 1.2 times of the longest sequences [21].
<figure><img src="image_4.png" /><figcaption>Fig. 1. SPSO algorithm flowchart.</figcaption></figure>

**Fitness Evaluation.** A parameter to determine which alignment will survive in the next generation is its fitness value. A formal definition of the sum-of-pairs (SPS) of multiple sequence alignment is introduced which is used as a tool to compute fitness. The score assigned to each alignment is the sum of the scores (SP) of the alignment of each pair of sequences. The score of each pair of sequences is the sum of the score assigned to the match of each pair of symbols, which is given by the substitution matrix. The score of a multiple alignment is given as follows:

$$ \text{Score } (A) = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} S(A_i, A_j). \qquad (4) $$

where the S(Aᵢ, Aⱼ) is the alignment score between two given sequences Aᵢ and Aⱼ.

**Particle Move:** In the PSO algorithm, each particle moves towards the leader at a speed proportional to the distance between the particle and the leader. In this paper,
this distance will be measured as the proportion of gaps that do not match in the sequences, according to the formula :

$$Distance = \frac{no matching gaps}{total gaps}. \qquad (5)$$

To move particles towards the leader, an operator similar to the crossover operator from genetic algorithms is used [21]. It consists to select a crossover point which divides the alignment into two segments, and then a segment of the particle is replaced with a segment from the leader. This replacement is achieved removing from the particle the gaps that are in the segment, and then adding the gaps from the leader's segment.

## 1.4 SA components of MSA problem

According to the basic elements of simulated annealing cited above, components of our proposed algorithm for MSA problem are as follows :

**Cost Function.** The cost function is used to evaluate the quality of each alignment in the swarm. In order to retain the same paradigm to measure the quality of the solution, we decide in this study to use the sum-of-pairs (SPS) as a cost function which is the same one of that used in the PSO algorithm.

**Initial Solution.** The generation of an initial solution is an important step towards getting a final improved alignment. In our developed method, the initial solution is constructed by insertion of gaps randomly in each sequence of the alignment.

**Generation of Neighbors.** In the multiple sequence alignment context, neighbors of a current solution are obtained by employing some perturbations to the gaps positions into the different sequences. In this work, we choose to apply a simple efficient strategy to change positions of these gaps, this mechanism is called LocalShuffle operator, its main idea is as follows : firstly, picks a random amino acid from a randomly chosen sequence in the alignment and checks whether one of its neighbors is a gap. If this is the case, the algorithm swaps the selected amino acid with a gap neighbor. If both neighbors are gaps then one of them is picked randomly [22].

**Choice of Cooling Schedule.** An effective cooling schedule is essential to reducing the amount of time required by the algorithm to find an optimal solution. Several temperature decreasing schemes have been proposed in the literature, they include static schedules and adaptive schedules [16]. Here, we propose to use the most common cooling function which is defined by $T_{k+1} = \alpha.T_k$. This function decreases the temperature value by a $\alpha$ factor, where $\alpha \in [0.70, 1.0]$. The pseudo-code of our SA is given below.
Pseudo-code of SA algorithm

Fix $T_{initial}$, $T_{final}$, $\alpha$

Set $T \leftarrow T_{initial}$, $S_{current} \leftarrow S_{initial}$, score($S_{current}$) $\leftarrow$ score($S_{initial}$)

While ($T > T_{final}$) do

$S_{new} \leftarrow LocalShuffle(S_{current})$

Compute the calculate score of $S_{new}$

$d$:=score($S_{new}$)- score($S_{current}$)

If ($d \ge 0$) then

$S_{current} \leftarrow S_{new}$

If score($S_{new}$) > score($S_{better}$) then

$S_{better} \leftarrow S_{new}$

end if

else

If $exp(d/T) > random(0,1)$ then

$S_{current} \leftarrow S_{new}$

end if

end if

$T = \alpha \cdot T$

end while

After the description of the key components of both PSO and SA algorithms, the pseudo-code of our SPSO procedure is summarized as follows:

SPSO Pseudo-code

1. Generate randomly a set of particles

2. Fix ITMAX value

3. Set it $\leftarrow 1$

4. While (it $\le$ ITMAX) do

4.1. Determine the leader particle gbest

4.2. For each particle in population do

a) Measure the distance between gbest and the particle

b) Select randomly a crossover point

c) Apply particle move mechanism

End for

// Calculate the new leader particle gbest

4.3 Update gbest

4.4 New_gbest $\leftarrow$ SA(gbest) // Apply SA to improve gbest

4.5 Insert New_gbest into the current population

4.6. it $\leftarrow$ it + 1

5. End while

// Output the result.

6. Return gbest value and its correspondent particle.
## 5 Simulation and Results

The proposed approach is implemented in Java language. All tests have been fulfilled on a PC with a 2.66 GHz Intel Pentium IV processor and 4GB RAM. We conducted some experiments in order to demonstrate the effectiveness of our SPSO algorithm. For that, a set of benchmark sequences with different identities and lengths are chosen from the BAliBase 1.0 library [23]. Characteristics of the used data and all parameters setting of the algorithm SPSO are summarized in Table 1 and 2 respectively.

<table><caption>**Table 1.** Characteristics of benchmark sequences.</caption><thead><tr><th>Types</th><th>Name</th><th>N</th><th>(Min,Max)</th><th>Identity</th></tr></thead><tbody><tr><td rowspan="3">Short</td><td>SH3</td><td>5</td><td>(80,49)</td><td>&lt;25%</td></tr><tr><td>cytochrome c</td><td>5</td><td>(70,87)</td><td>20%-40%</td></tr><tr><td>serine protease</td><td>5</td><td>(66,82)</td><td>&gt;35%</td></tr><tr><td rowspan="4">Medium</td><td>protein kinase</td><td>5</td><td>(263,276)</td><td>&lt;25%</td></tr><tr><td>anthranilate isomerase</td><td>4</td><td>(247,259)</td><td>20%-40%</td></tr><tr><td>serine protease</td><td>5</td><td>(222,245)</td><td>&gt;35%</td></tr><tr><td>aminotransferase</td><td>4</td><td>(358,387)</td><td>&lt;25%</td></tr><tr><td rowspan="2">Long</td><td>glutamyl-trna synthetase</td><td>5</td><td>(438,486)</td><td>20%-40%</td></tr><tr><td>taq DNA polymerase</td><td>5</td><td>(806,928)</td><td>&gt;35%</td></tr></tbody></table>

<table><caption>**Table 2.** Parameter settings for experiments.</caption><thead><tr><th>Parameter</th><th>Value</th></tr></thead><tbody><tr><td>Number of iterations (ITMAX)</td><td>1000</td></tr><tr><td>Swarm size</td><td>50</td></tr><tr><td>Initial temperature (T<sub>initial</sub>), Final temperature (T<sub>final</sub>)</td><td>100, 0.0001</td></tr><tr><td>Score matrix, Gap open</td><td>PAM250, 10</td></tr><tr><td>c<sub>1</sub>, c<sub>2</sub> constants</td><td>1.49618</td></tr></tbody></table>

All obtained results by GA, PSO, ABC and our SPSO algorithm using the best, the worst and the average SPS values of 10 experiments are summarized in table 3, 4 and 5 respectively.

<table><caption>**Table 3.** Comparison results for short sequences.</caption><thead><tr><th>Sequence name</th><th>Algorithm</th><th>Average</th><th>Best</th><th>Worst</th></tr></thead><tbody><tr><td rowspan="4">SH3</td><td>GA[14]</td><td>0.60.90</td><td>0.6829</td><td>0.5463</td></tr><tr><td>PSO [14]</td><td>0.6444</td><td>0.6543</td><td>0.6296</td></tr><tr><td>ABC [14]</td><td>0.6895</td><td>0.7654</td><td>0.6543</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.7698</strong></td><td><strong>0.8712</strong></td><td><strong>0.8197</strong></td></tr><tr><td rowspan="4">cytochrome c</td><td>GA[14]</td><td>0.5141</td><td>0.5398</td><td>0.4891</td></tr><tr><td>PSO [14]</td><td>0.6252</td><td>0.6407</td><td>0.6116</td></tr><tr><td>ABC [14]</td><td>0.6451</td><td>0.6854</td><td>0.5922</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.7206</strong></td><td><strong>0.7417</strong></td><td><strong>0.6806</strong></td></tr><tr><td rowspan="4">serine protease</td><td>GA [14]</td><td>0.7455</td><td>0.8065</td><td>0.6921</td></tr><tr><td>PSO [14]</td><td>0.7120</td><td>0.7331</td><td>0.7008</td></tr><tr><td>ABC [14]</td><td>0.7956</td><td>0.8168</td><td>0.7732</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.8878</strong></td><td><strong>0.8904</strong></td><td><strong>0.8505</strong></td></tr></tbody></table>
<table><caption>**Table 4.** Comparison results for medium sequences.</caption><thead><tr><th>Sequence name</th><th>Algorithm</th><th>Average</th><th>Best</th><th>Worst</th></tr></thead><tbody><tr><td rowspan="4">protein kinase</td><td>GA[14]</td><td>0.3508</td><td>0.3620</td><td>0.3453</td></tr><tr><td>PSO [14]</td><td>0.4848</td><td>0.5065</td><td>0.4765</td></tr><tr><td>ABC [14]</td><td>0.4951</td><td>0.5272</td><td>0.4765</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.5277</strong></td><td><strong>0.5801</strong></td><td><strong>0.5312</strong></td></tr><tr><td rowspan="4">anthranilate isomerase</td><td>GA[14]</td><td>0.3317</td><td>0.3440</td><td>0.3244</td></tr><tr><td>PSO [14]</td><td>0.3813</td><td>0.4117</td><td>0.3529</td></tr><tr><td>ABC [14]</td><td>0.3825</td><td>0.4292</td><td>0.3682</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.4144</strong></td><td><strong>0.4549</strong></td><td><strong>0.4218</strong></td></tr><tr><td rowspan="4">serine protease</td><td>GA[14]</td><td>0.3792</td><td>0.4334</td><td>0.3579</td></tr><tr><td>PSO [14]</td><td>0.2626</td><td>0.2725</td><td>0.2507</td></tr><tr><td>ABC [14]</td><td>0.4178</td><td>0.4480</td><td>0.4036</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.4646</strong></td><td><strong>0.4703</strong></td><td><strong>0.4209</strong></td></tr></tbody></table>

<table><caption>**Table 5.** Comparison results for long sequences.</caption><thead><tr><th>Sequence name</th><th>Algorithm</th><th>Average</th><th>Best</th><th>Worst</th></tr></thead><tbody><tr><td rowspan="4">aminotransferase</td><td>GA[14]</td><td>0.3646</td><td>0.3719</td><td>0.3548</td></tr><tr><td>PSO [14]</td><td>0.5819</td><td>0.5903</td><td>0.5645</td></tr><tr><td>ABC [14]</td><td>0.5819</td><td>0.5936</td><td>0.5741</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.6602</strong></td><td><strong>0.6378</strong></td><td><strong>0.6612</strong></td></tr><tr><td rowspan="4">glutamyl-trna synthetase</td><td>GA[14]</td><td>0.3738</td><td>0.3824</td><td>0.3648</td></tr><tr><td>PSO [14]</td><td>0.3987</td><td>0.4154</td><td>0.3828</td></tr><tr><td>ABC [14]</td><td>0.4040</td><td>0.4254</td><td>0.3857</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.4316</strong></td><td><strong>0.4449</strong></td><td><strong>0.4207</strong></td></tr><tr><td rowspan="4">taq DNA polymerase</td><td>GA[14]</td><td>0.2500</td><td>0.2644</td><td>0.2441</td></tr><tr><td>PSO [14]</td><td>0.2533</td><td>0.2588</td><td>0.2484</td></tr><tr><td>ABC [14]</td><td>0.2569</td><td>0.2615</td><td>0.2520</td></tr><tr><td><strong>Our SPSO</strong></td><td><strong>0.2603</strong></td><td><strong>0.2882</strong></td><td><strong>0.2794</strong></td></tr></tbody></table>

The results plotted in table 3-5 show clearly the considerable improvement of scores by the proposed SPSO approach. Indeed, it produces alignments of much better quality than that of the other cited methods in both specified categories.

In order to further assess the potent of our SPSO algorithm, a second experiment using another datasets is performed, where the goal is to compare our SPSO approach with TLPSO-MSA[24] technique. In this experiment, three different sets of protein coming from the BaliBASE 3.0 database [25] are selected. The average SP and TC scores [26] are portrayed in table 6.

<table><caption>**Table 6.** Comparison results on the selected test cases.</caption><thead><tr><th rowspan="2">Sequence set</th><th rowspan="2">N</th><th colspan="2">TLPSO-MSA[24]</th><th colspan="2">Our SPSO</th></tr><tr><th>SP</th><th>TC</th><th>SP</th><th>TC</th></tr></thead><tbody><tr><td>RV11</td><td>38</td><td>0.80</td><td>0.71</td><td><strong>0.84</strong></td><td><strong>0.74</strong></td></tr><tr><td>RV12</td><td>44</td><td><strong>0.92</strong></td><td>0.80</td><td>0.86</td><td><strong>0.81</strong></td></tr><tr><td>RV20</td><td>41</td><td>0.91</td><td>0.64</td><td><strong>0.92</strong></td><td><strong>0.68</strong></td></tr><tr><td>Overall average</td><td></td><td>0.87</td><td>0.72</td><td><strong>0.87</strong></td><td><strong>0.74</strong></td></tr></tbody></table>

From table 6, it can be seen that our SPSO outperforms clearly TLPSO-MSA method in terms of TC score for all cases. In terms of SP score, it finds results better
than TSPSO-MSA for RV11 and RV20 protein families and produces a competitive
results on RV12 dataset.

6 Conclusion

In this work, we contributed to the ongoing research by proposing a hybrid model for
finding optimized alignments to the MSA problem. The developed approach uses the
characteristics of the random search, global convergence of the PSO and the potent of
the simulated annealing to update the global optimal solution. The performance of the
proposed SPSO algorithm is judged on a set of BaliBase benchmark problems and is
favorably compared with other algorithms in the literature. The results demonstrate
that the proposed approach is overall more effective to find better alignments in a
reasonable processing time.

In the future, we will revise our score function to make this score more realistic,
also, we can use another intelligent heuristic to generate the initial whole swarm in
order to increase the convergence speed of the algorithm. In addition, we can incorpo-
rate other efficient mechanisms for the neighborhood structure to improve the global
solution quality. A comparison of the proposed method with some other aligners such
as Clustal W, SAGA or MULTALIGN is possible to verify its effectiveness.

References

1. Thompson, J.D., Thierry, J.E., O. Poch, O.: Rapid Scanning and Correction of Multiple Sequence Alignments. Bioinformatics 19 (2003)

2. Jiang, T., Wang L.: On the Complexity of Multiple Sequence Alignment. J. Comput. BioI. 1, 337–378 (1994)

3. Bonizzoni, L.P., Gianluca, P.: The Complexity of Multiple Sequence Alignment with SP-score that is a Metric. Theoretical Computer Science 259: 63–79, 2001.

4. Papadimitriou, C.H, Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New York (1998)

5. Horng, J.T., Wu, L.C., Lin, C.M., Yang, B.H.: A Genetic Algorithm for Multiple Sequence Alignment. In . Proc. LNCS, pp. 407–420 (2005)

6. Hernández-Guía, M., Mulet, R., Rodríguez-Pérez, S.: A new Simulated Annealing Algorithm for the Multiple Sequence Alignment Problem. The approach of polymers in a random media. Physical Review E 72, 1–7 (2005)

7. Lei, C.W., Ruan, J.H.: A Particle Swarm Optimization Algorithm for Finding DNA Sequence Motifs. In: Proc. IEEE, pp.166–173 (2008)

8. Lee, Z.J., Su, S.F., Chuang, C.C., Liu, K.H., Genetic Algorithm with Ant Colony Optimization (GA-ACO) for Multiple Sequence Alignment. Applied Soft Computing 8, 55–78 (2008)

9. Chen, L., Zou, L., Chen, j., An Efficient ant Colony Algorithm for Multiple Sequences Alignment. In Proceedings of the 3rd International Conference on Natural Computation (ICNC '07), pp. 208–212 (2007)
10. Riaz, T., Wang, Y., Li, K.B.: Multiple Sequence Alignment Using Tabu Search. In Proceedings of 2nd Asia-Pacific Bioinformatics Conference (APBC), pp. 223–232, Dunedin, New Zealand (2004)

11. Xu1, F., Chen, Y.: A Method for Multiple Sequence Alignment Based on Particle Swarm Optimization. In: ICIC 2009, LNAI 5755, pp. 965–973 (2009)

12. Chen, Y., Hu, J., Hirasawa, K., Yu, S.: Multiple Sequence Alignment Based on Genetic Algorithm with Reserve Selection. In: Proc. of Int. conf. on Networking, Sensing and Control (ICNSC), pp. 1511–1516 (2008)

13. Long, H.X., Xu, W.B., Sun, J., Ji, W.J.: Multiple Sequence Alignment Based on a Binary Particle Swarm Optimization Algorithm. In: Proceedings of Fifth International Conference on Natural Computation, pp. 265–269 (2009)

14. Lei, X., Sun, J., Xu, X., Guo, L.: Artificial Bee Colony Algorithm for Solving Multiple Sequence Alignment. In: Proc. of 2010 IEEE Fifth International Conference on BIC-TA, pp. 337–342 (2010)

15. Cutello, V., Nicosia, G., Pavone, M., Prizzi, I.: Protein Multiple Sequence Alignment by Hybrid Bio-inspired Algorithms. Nucleic Acids Research 39(6), 1980–1992 (2011)

16. Ernesto, L.G., Lorena, M.G.: Simulated Annealing with Previous Solutions Applied to DNA Sequence Alignment. ISRN Artificial intelligence 2012, 1–6 (2012)

17. Abu-Srhan, A., Al Daoud, E.: A Hybrid Algorithm Using a Genetic Algorithm and Cuckoo Search Algorithm to Solve the Traveling Salesman Problem and its Application to Multiple Sequence Alignment. International Journal of Advanced Science and Technology 61, 29–38 (2013)

18. Kayaa, M., Sarhanb, A., Alhajjb, R.: Multiple Sequence Alignment with Affine Gap by using Multi-objective Genetic Algorithm. Computer Methods and Programs in Biomedicine 114, 38–49 (2014)

19. Kennedy, J., Eberhart, R.: Particle Swarm Optimization. In: Proceedings of IEEE International Conference on Neural Networks. 4, pp.1942–1948, Perth (1995)

20. Ben-Ameur, W.: Computing the Initial Temperature of Simulated Annealing. Computational Optimization and Applications 29, 369–385 (2004)

21. Rodriguez P.F., Nino, L.F., Alonso, O.M.: Multiple Sequence Alignment Using Swarm Intelligence. International Journal of Computational Intelligence Research 3(2), 123–130 (2007).

22. Lamiche, C.: An Effective Alignment Technique to Solve MSA Problem. Asian Journal of Mathematics and Computer 17(2), 2395–4213 (2017)

23. Thompson J.D., Plewniak, F., Poch, O.: BAliBASE: A Benchmark Alignment Database for the Evaluation of Multiple Alignment Programs. Bioinformatics 15, 87–88 (1999)

24. Lalwani, S., Kumar, R., Gupta, N.: A Novel Two-level Particle Swarm Optimization Approach for Efficient Multiple Sequence Alignment. Memetic Computing 7(2), 119–133 (2015)

25. Thompson, J.D., Koehl, P., Ripp, R., Poch, O.: BAliBASE 3.0: Latest Developments of the Multiple Sequence Alignment Benchmark. Proteins 61(1), 127–136 (2005)

26. Thompson, J. D., Plewniak, F., Poch, O.: A Comprehensive Comparison of Multiple Sequence Alignment Programs. Nucleic Acids Research 27(13), 2682–2690 (1999)