An Enhanced Hybrid Model for Solving Multiple Sequence Alignment Problem
In this work, we aim to develop a novel hybrid system (VNPSO) for solving multiple sequence alignment (MSA) problem. The presented procedure is a hybridization of particle swam optimization (PSO) algorithm and variable neighborhood descent (VND) method. W
- PDF / 410,643 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 231 Views
Abstract. In this work, we aim to develop a novel hybrid system (VNPSO) for solving multiple sequence alignment (MSA) problem. The presented procedure is a hybridization of particle swam optimization (PSO) algorithm and variable neighborhood descent (VND) method. When the first metaheuristic is used to discover the search space, the VND procedure is exploited to improve the swarm leader (gbest) solution quality and to overcome the local optimum problem. Experimental studies on BaliBASE benchmark have shown the effectiveness of the proposed method and its ability to obtain good quality solutions comparing to those given by some literature published works. Keywords: Hybrid system Multiple sequence alignment Neighbourhood generation BaliBASE benchmark
PSO
VND
1 Introduction In recent years, multiple sequence alignment (MSA) problem is one of the most challenging tasks in bioinformatics [1]. MSA is generally the alignment of three or more biological sequences (protein or nucleic acid) of similar length. From the output, homology can be inferred and the evolutionary relationships between the sequences studied. Finding the optimal alignment of a set of sequences is known as a NPcomplete problem [2]. It classified as a combinatorial optimization problem [3], which is solved by using computer algorithms. Following to their advantages, metaheuristics have been largely used to solve the MSA problem. These approaches are based on the improvement of a starting solution through a series of iterations until the solution doesn’t become better any longer. They include genetic algorithm (GA) [4], simulated annealing algorithm (SA) [5], particle swarm optimization (PSO) [6], GA-ACO algorithm [7], Ant Colony Algorithm [8] and so on. In this research work, we present a hybrid approach based on PSO and VND metaheuristics to solve the MSA problem. The rest of the paper is structured as follows: Sect. 2 presents the proposed methodology. In Sect. 3, the simulation results are provided. Finally, the study is concluded in Sect. 4.
© Springer Nature Switzerland AG 2019 Y. Farhaoui and L. Moussaid (Eds.): ICBDSDE 2018, SBD 53, pp. 86–91, 2019. https://doi.org/10.1007/978-3-030-12048-1_11
An Enhanced Hybrid Model for Solving MSA Problem
87
2 Materials and Methods 2.1
Particle Swarm Optimization (PSO)
Particle swarm optimization (PSO) is a population-based stochastic optimization algorithm proposed for the first time by Kennedy and Eberhart [9]. The problem is tackled by considering a population (particles), where each particle is a potential solution to the problem. Initial positions and velocities of the particles are chosen randomly. In the commonly used standard PSO, each particle’s position is updated at each iteration step according to its own personal best position and the best solution of the swarm. The evolution of the swarm is governed by the following equations: V ðk þ 1Þ ¼ w:V ðkÞ þ c1 :rand1 : pbestðkÞ X ðkÞ þ c2 :rand2 : gbestðkÞ X ðkÞ
ð1Þ
X ðk þ 1Þ ¼ X ðkÞ þ V ðk þ 1Þ
ð2Þ
where: X is the positio
Data Loading...
