Abstract
The alignment of more than two biological sequences is a widely used technique in a number of areas of computational biology. However, finding an optimal alignment has been shown to be an NP-complete optimization problem. Furthermore, Multiple Sequence Alignment (MSA) can be formulated according to more than one score function, leading to multi-objective formulations of this problem. Due to these reasons, metaheuristics have been proposed to deal with MSA problems. In this paper, we present jMetalMSA, an Open Source software tool for solving MSA problems with multi-objective metaheuristics. Our motivation here is to offer to the scientific community in computational biology, a platform including state-of-the-art optimization algorithms aimed at solving different formulations of the MSA. We describe the main features of jMetalMSA, including the metaheuristics and scores that are currently available. In addition, we show a working example for illustration purposes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
jMetalMSA project in GitHub: http://github.com/jmetal/jmetalmsa.
References
Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol. 1, 337–348 (1994)
Seeluangsawat, P., Chongstitvatana, P.: A multiple objective evolutionary algorithm for multiple sequence alignment. In: Proceedings of the 7th Conference, GECCO 2005, pp. 477–478. ACM, New York (2005)
Ortuño, F., Valenzuela, O., Rojas, F., Pomares, H., Florido, J., Urquiza, J., Rojas, I.: Optimizing multiple sequence alignments using a genetic algorithm based on three objectives: structural information, non-gaps percentage and totally conserved columns. Bioinformatics 29(17), 2112–2121 (2013). Oxford, New York
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)
Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms. Wiley, New York (2001)
Coello, C., Lamont, G., van Veldhuizen, D.: Multi-objective Optimization Using Evolutionary Algorithms, 2nd edn. Wiley, New York (2007)
Soto, W., Becerra, D.: A multi-objective evolutionary algorithm for improving multiple sequence alignments. In: Campos, S. (ed.) BSB 2014. LNCS, vol. 8826, pp. 73–82. Springer, Cham (2014). doi:10.1007/978-3-319-12418-6_10
Kaya, M., Sarhan, A., Abdullah, R.: Multiple sequence alignment with affine gap by using multi-objective genetic algorithm. Comput. Methods Programs Biomed. 114(1), 38–49 (2014)
Zhu, H., He, Z., Jia, Y.: A novel approach to multiple sequence alignment using multiobjective evolutionary algorithm based on decomposition. IEEE J. Biomed. Health Inform. 20(2), 717–727 (2016)
Rubio-Largo, A., Vega-Rodríguez, M., González-Álvarez, D.: Hybrid multiobjective artificial bee colony for multiple sequence alignment. Appl. Soft Comput. 41, 157–168 (2016)
Rani, R.R., Ramyachitra, D.: Multiple sequence alignment using multi-objective based bacterial foraging optimization algorithm. Biosystems 150, 177–189 (2016)
Durillo, J., Nebro, A.: jMetal: a Java framework for multi-objective optimization. Adv. Eng. Softw. 42(10), 760–771 (2011)
Nebro, A., Durillo, J.J., Vergne, M.: Redesigning the jMetal multi-objective optimization framework. In: Proceedings of the GECCO Companion 2015, pp. 1093–1100. ACM, New York (2015)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577–601 (2014)
Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)
Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the Pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)
Nebro, A., Durillo, J., Luna, F., Dorronsoro, B., Alba, E.: MOCell: a cellular genetic algorithm for multiobjective optimization. Int. J. Intell. Syst. 24(7), 723–725 (2009)
R. Saborido, A.R., Luque., M.: Global WASF-GA: an evolutionary algorithm in multiobjective optimization to approximate the whole Pareto optimal front. Evol. Comput. (2016, in Press)
Henikoff, S., Henikoff, J.: Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. 89(22), 10915–10919 (1992)
Dayho, M., Schwartz, R., Orcutt, B.C.: A model of evolutionary change in proteins. Atlas Protein Sequences Struct. 5, 345–352 (1978)
Kemena, C., Taly, J., Kleinjung, J., Notredame, C.: Strike: evaluation of protein MSAS using a single 3D structure. Bioinformatics 27(24), 3385–3391 (2011)
Berman, H., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., Bourne, P.: The protein data bank. Nucleic Acids Res. 28(1), 235–242 (2000)
Thompson, J., Koehl, P., Poch, O.: Balibase 3.0: latest developments of the multiple sequence alignment benchmark. Proteins 61, 127–136 (2005)
Zambrano-Vega, C., Nebro, A.J., Garca-Nieto, J., Aldana-Montes, J.F.: Comparing multi-objective metaheuristics for solving a three-objective formulation of multiple sequence alignment. Prog. Artif. Intell. 1–16 (2017). Springer
Zambrano-Vega, C., Nebro, A.J., Durillo, J.J., Garca-Nieto, J., Aldana-Montes, J.F.: Multiple sequence alignment with multi-objective metaheuristics. A comparative study. Int. J. Intell. Syst. Periodicals (2017, in press). Wiley
Acknowledgements
This work has been partially supported by the Secretaría Nacional de Educación Superior Ciencia y Tecnología SENESCYT from Ecuador, and Spanish Grants TIN2014-58304-R (Ministerio de Economía y Competitividad), P11-TIC-7529 and P12-TIC-1519 (Plan Andaluz I+D+I - Junta de Andalucía). José García-Nieto is recipient of a Post-Doctoral fellowship of “Captación de Talento para la Investigación” at Universidad de Málaga.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zambrano-Vega, C., Nebro, A.J., García-Nieto, J., Aldana-Montes, J.F. (2017). A Multi-objective Optimization Framework for Multiple Sequence Alignment with Metaheuristics. In: Rojas, I., Ortuño, F. (eds) Bioinformatics and Biomedical Engineering. IWBBIO 2017. Lecture Notes in Computer Science(), vol 10209. Springer, Cham. https://doi.org/10.1007/978-3-319-56154-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-56154-7_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-56153-0
Online ISBN: 978-3-319-56154-7
eBook Packages: Computer ScienceComputer Science (R0)