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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Thompson, J.D., Thierry, J.E., Poch, O.: Rapid scanning and correction of multiple sequence alignments. Bioinformatics 19, 1155–1161 (2003)
Jiang, T., Wang, L.: On the complexity of multiple sequence alignment. J. Comput. BioI. 1, 337–378 (1994)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New York (1998)
Horng, J.T., Wu, L.C., Lin, C.M., Yang, B.H.: A genetic algorithm for multiple sequence alignment. In: Proceedings of LNCS, pp. 407–420 (2005)
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. Phys. Rev. E 72, 1–7 (2005)
Lei, C.W., Ruan, J.H.: A particle swarm optimization algorithm for finding DNA sequence motifs. In: Proceedings of IEEE, pp. 166–173 (2008)
Lee, Z.J., Su, S.F., Chuang, C.C., Liu, K.H.: Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Appl. Soft Comput. 8, 55–78 (2008)
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 2007), pp. 208–212 (2007)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, Perth, vol. 4, pp. 1942–1948 (1995)
Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 34, 1097–1100 (1997)
Taheri, J., Zomaya, A.Y.: RBT-GA: a novel metaheuristic for solving the multiple sequence alignment problem. BMC Genom. 10, 1–11 (2009)
Yadav, R.K.: GSAMSA: gravitational search algorithm for multiple sequence alignment. Indian J. Nat. Sci. 6(33), 10523–10537 (2015)
Bahr, A., Thompson, J.D., Thierry, J.C., Poch, O.: BALIBASE (Benchmark Alignment dataBASE): enhancements for repeats, transmembrane sequences and circular permutation. Nucleic Acids Res. 29(1), 323–326 (2001)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Chaabane, L. (2019). An Enhanced Hybrid Model for Solving Multiple Sequence Alignment Problem. In: Farhaoui, Y., Moussaid, L. (eds) Big Data and Smart Digital Environment. ICBDSDE 2018. Studies in Big Data, vol 53. Springer, Cham. https://doi.org/10.1007/978-3-030-12048-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-12048-1_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12047-4
Online ISBN: 978-3-030-12048-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)