A novel approach based on multiobjective variable mesh optimization to Phylogenetics
Abstract
One of the most relevant problems in Bioinformaticsand Computational Biology is the search and reconstruction ofthe most accurate phylogenetic tree that explains, as exactly aspossible, the evolutionary relationships among species from agiven dataset. Different criteria have been employed to evaluatethe accuracy of evolutionary hypothesis in order to guide a searchalgorithm towards the best tree. However, these criteria may leadto distinct phylogenies, which are often conflicting among them.Therefore, a multi-objective approach can be useful. In this work,we present a phylogenetic adaptation of a multiobjective variablemesh optimization algorithm for inferring phylogenies, to tacklethe phylogenetic inference problem according to two optimalitycriteria: maximum parsimony and maximum likelihood. Theaim of this approach is to propose a complementary view ofphylogenetics in order to generate a set of trade-off phylogenetictopologies that represent a consensus between both criteria.Experiments on four real nucleotide datasets show that ourproposal can achieve promising results, under both multiobjectiveand biological approaches, with regard to other classical andrecent multiobjective metaheuristics from the state-of-the-art.
Downloads
References
A. Stamatakis, “Distributed and Parallel Algorithms and Systems for Inference of Huge Phylogenetic Trees based on the Distributed and Parallel Algorithms and Systems for Inference of Huge Phylogenetic Trees based on the Maximum Likelihood Method,” Ph.D. dissertation, Technische Universit ̈at M ̈unchen, Germany, 10 2004.
C. Zambrano-Vega, A. J. Nebro, J. J. Durillo, J. García-Nieto, andJ. Aldana-Montes, “Multiple sequence alignment with multiobjective metaheuristics. a comparative study, ”International Journal of Intelligent Systems, vol. 32, no. 8, pp. 843–861, 2017. [Online]. Available: http://dx.doi.org/10.1002/int.21892
C. Zambrano-Vega, A. J. Nebro, J. Garc ́ıa-Nieto, and J. Aldana-Montes, “Comparing multi-objective metaheuristics for solving a three-objective formulation of multiple sequence alignment, ”Progressin Artificial Intelligence, pp. 1–16, 2017. [Online]. Available: http://dx.doi.org/10.1007/s13748-017-0116-6
S. Santander-Jiménez and M. A. Vega-Rodríguez, “Applying a multiob-jective metaheuristic inspired by honey bees to phylogenetic inference,”Biosystems, vol. 114, no. 1, pp. 39–55, 2013. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0303264713001615
J.Handl,D.B.Kell,andJ.Knowles,“Multiobjective optimization in bioinformatics and computational biology. ”IEEE/ACM transactions on computational biology and bioinformatics / IEEE,ACM, vol. 4, no. 2, pp. 279–92, 2007. [Online]. Available:http://www.ncbi.nlm.nih.gov/pubmed/17473320
S. Santander-Jim ́enez and M. A. Vega-Rodr ́ıguez, “A multiobjectiveproposal based on the firefly algorithm for inferring phylogenies,” inEuropean Conference on Evolutionary Computation, Machine Learningand Data Mining in Bioinformatics. Springer, 2013, pp. 141–152.
W. Cancino and A. C. Delbem, “A Multi-objective EvolutionaryApproach for Phylogenetic Inference,” inEvolutionary Multi-CriterionOptimization, ser. Lecture Notes in Computer Science, S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, and T. Murata, Eds.SpringerBerlin Heidelberg, 2007, vol. 4403, pp. 428–442. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-70928-234
S. Santander-Jim ́enez and M. A. Vega-Rodríguez, “A hybrid approachto parallelize a fast non-dominated sorting genetic algorithm for phylogenetic inference, ”Concurrency and Computation: Practice and Experience, vol. 27, no. 3, pp. 702–734, 2014. [Online]. Available: http://doi.wiley.com/10.1002/cpe.3269
Y. Salgueiro, J. L. Toro, R. Bello, and R. Falcon, “Multiobjective variable mesh optimization,”Annals of Operations Research, pp. 1–25,2016. [Online]. Available: http://dx.doi.org/10.1007/s10479-016-2221-5
C. Zambrano-Vega, A. J. Nebro, and J. Aldana-Montes, “Mophylogenetics: a phylogenetic inference software tool with multiobjective evolutionary metaheuristics, ”Methods in Ecology and Evolution, vol. 7, no. 7, pp. 800–805, 2016. [Online]. Available: http://dx.doi.org/10.1111/2041210X.12529
A. Edwards, L. Cavalli-Sforza, V. Heywoodet al., “Phenetic and phylogenetic classification, ”Systematic Association Publication No. 6,pp. 67–76, 1964.
W. H. Day, D. S. Johnson, and D. Sankoff, “The computational complexity of inferring rooted phylogenies by parsimony,”Mathematical biosciences, vol. 81, no. 1, pp. 33–42, 1986.[13] B. Chor and T. Tuller, “Maximum likelihood of evolutionary trees: hardness and approximation,”Bioinformatics, vol. 21, no. suppl 1, pp.i97–i106, 2005.[14] J. Felsenstein, Inferring Phylogenies. Palgrave Macmillan, 2004. [Online]. Available: http://books.google.fr/books?id=GI6PQgAACAAJ
D. Swofford, G. Olsen, P. Waddell, and D. Hillis, “Phylogeny reconstruction,” in Molecular Systematics, 3rd ed. Sinauer, 1996, ch. 11, pp.407–514.
W.M.Fitch,“Toward defining the course of evolution: Minimum change for a specific tree topology, ”Systematic Biology, vol. 20, no. 4, pp. 406–416, 1971. [Online]. Available: http://sysbio.oxfordjournals.org/content/20/4/406.abstract
D. Darriba, G. L. Taboada, R. Doallo, and D. Posada, “jmodeltest 2:more models, new heuristics and parallel computing, ”Nature methods,vol. 9, no. 8, pp. 772–772, 2012.
C. Cotta and P. Moscato, “Inferring phylogenetic trees using evolutionary algorithms,” in International Conference on Parallel Problem Solving from Nature. Springer, 2002, pp. 720–729.
T. Flouri, F. Izquierdo-Carrasco, D. Darriba, A. Aberer, L.-T. Nguyen, B. Minh, A. Von Haeseler, and A. Stamatakis, “The Phylogenetic Likelihood Library,”Systematic Biology, vol. 64, no. 2, pp. 356–362,2015.
A. Go ̈effon, J.-M. Richer, and J.-K. Hao, “Progressive tree neighborhood applied to the maximum parsimony problem.”IEEE/ACM transactions on computational biology and bioinformatics / IEEE,ACM, vol. 5, no. 1, pp. 136–45, 2008. [Online]. Available: http://www.ncbi.nlm.nih.gov/pubmed/18245882
H. Matsuda, “Construction of Phylogenetic Trees from Amino Acid Sequences using a Genetic Algorithm,”Sciences, Computer, p. 560,1995.
C. B. Congdon, “Gaphyl: An Evolutionary Algorithms Approach ForThe Study Of Natural Evolution,” inGECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, 2002, pp. 1057–1064.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,”IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,”IEEE Trans. Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.
N. Beume, B. Naujoks, and M. Emmerich, “Sms-emoa: Multiobjective selection based on dominated hypervolume,”European Journal of Operational Research, vol. 181, no. 3, pp. 1653–1669, 2007.
W. Cancino and A. Delbem, “A multicriterion evolutionary approachapplied to phylogenetic reconstruction,” in New Achievements in Evolutionary Computation, P. Korosec, Ed.Rijeka: InTech, 2010,ch. 06. [Online]. Available: http://dx.doi.org/10.5772/8051
C. Lanave, G. Preparata, C. Sacone, and G. Serio, “A new method for calculating evolutionary substitution rates,”Journal of molecular evolution, vol. 20, no. 1, pp. 86–93, 1984.
Copyright Notice
Authors who publish this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-Non-Commercial-Share-Alike 4.0 International 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
Disclaimer
LAJC in no event shall be liable for any direct, indirect, incidental, punitive, or consequential copyright infringement claims related to articles that have been submitted for evaluation, or published in any issue of this journal. Find out more in our Disclaimer Notice.
