Abstract
Evolutionary relationships among species are usually (1) illustrated by means of a phylogenetic tree and (2) inferred by optimising some measure of fitness, such as the total evolutionary distance between species or the likelihood of the tree (given a model of the evolutionary process and a data set). The combinatorial complexity of inferring the topology of the best tree makes phylogenetic inference an ideal candidate for evolutionary algorithms. However, difficulties arise when different data sets provide conflicting information about the inferred `best' tree(s). We apply the techniques of multi-objective optimisation to phylogenetic inference for the first time. We use the simplest model of evolution and a four species problem to illustrate the method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Brooks DR, McLennan DA (2002) The nature of diversity: an evolutionary voyage of discovery. University of Chicago Press, Chicago
Chor B, Hendy MD, Holland BR, Penny D (2000) Multiple maxima of likelihood in phylogenetic trees: an analytic approach. Mol Biol Evol 17:1529–1541
Coello Coello CA, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, New York
Congdon CB (2001) Gaphyl: a genetic algorithms approach to cladistics. In: DeRaedt L, Siebes A (eds) Principles of data mining and knowledge discovery. Lecture Notes in Computer Science, vol 2168. Springer, Berlin, pp 67–68
Congdon CB (2002) Gaphyl: an evolutionary algorithms approach for the study of natural evolution. In: Genetic and evolutionary computation conference. San Francisco, California, pp 1057–1064
Congdon CB, Septor KJ (2003) Phylogenetic trees using evolutionary search: initial progress in extending gaphyl to work with genetic data. In: Congress on evolutionary computation, CEC 2003 Canberra, Australia
Day WHE (1987) Computational complexity of inferring phylogenies from dissimilarity matrices. Bull Math Biol 49:461–467
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester
Deb K, Goel T (2001) Controlled elitist non-dominated sorting genetic algorithm for better convergence. Lectures Notes in Computer Science, vol 1993, pp. 67–81
Edwards AWF, Cavalli-Sforza LL (1964) Reconstruction of evolutionary trees. In: Heywood VH, McNeill J (eds) Phenetic and phylogenetic classification. Systematics Association, London
Farris JS (1969) A succesive approximations approach to character weighting. Syst Zool 18:374–385
Felsenstein J (1981) Evolutionary trees from DNA sequences: A maximum-likelihood approach. J Mol Evol 17:368–376
Felsenstein J (1993) PHYLIP (Phylogeny Inference Package) version 3.5c. Distributed by the author. Department of Genetics, University of Washington, Seattle. http://evolution.genetics.washington.edu/phylip.html
Felsenstein J (2004) Inferring phylogenies. Sinauer Associates, Sunderland, Massachusetts
Hennig W (1950) Grundzüge einer Theory der phylogenetischen Systematik. Deutscher Zentralverlag, Berlin
Hennig W (1966) Phylogenetic systematics. University of Illinois Press, Urbana
Jermiin LS, Olsen GJ, Mengersen KL, Easteal S (1997) Majority-rule consensus of phylogenetic trees obtained by maximum-likelihood analysis. Mol Bio Evol 14:1296–1302
Jermiin LS, Ho SYH, Ababneh F, Robinson J, Larkum AWD (2004) The biasing effect of compositional heterogeneity on phylogenetic estimates may be underestimated. Syst Biol 53:638–643
Jukes T, Cantor CR (1969) Evolution of protein molecules. In: Munro HN (ed) Mammalian protein metabolism. Academic, New York, pp 21–132
Kluge AG (1997) Testability and the refutation and corroboration of cladistic hypotheses. Clad 13:81–96
Lewis PO (1998) A genetic algorithm for maximum likelihood phylogeny inference using nucletide sequence data. Mol Biol Evol 15:277–283
Matsuda H (1996) Protein phylogenetic inference using maximum likelihood with a genetic algorithm. In: Hunter L, Klein TE (eds) Pacific symposium on biocomputing '96. World scientific, London pp 512–523
Meade A, Corne D, Pagel M, Sibly RM (2001) Using evolutionary algorithms to estimate transition rates of discrete characteristics in phylogenetic trees. In: Proceedings of the IEEE Congress on Evolutionary Compuattion, COEX, Seoul pp 1170–1177
Moilanen A (1999) Searching for most parsimonious tree with simulated evolutionary optimisation. Clad 15:39–50
http://evolution.genetics.washington.edu/phylip/ newicktree.html
de Queiroz A, Donoghue MJ, Kim J (1995) Separate versus combined analysis of phylogenetic evidence: Ann Rev Eco Syst 26:657–681
Salemi M, VanDamme A-M (2003) Handbook of phylogenetic methods. Cambridge University Press, Cambridge
Strimmer K, von Haesler A (1996) Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies. Mol Biol Evol 13:964–969
Swofford DL, Olsen GJ, Waddell PJ, Hillis DM (1996) Phylogenetic Inference In: Hillis DM, Moritz C, Mable BK (eds) Molecular systematics, 2nd edn Sunderland, Massachusetts pp 407–514
Wolf MJ, Easteal S, Kahn M, McKay BD, Jermiin LS (2000) TrExML: a maximum likelihood approach for extensive tree-space exploration. Bioinformatics 16:383–394
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Poladian, L., Jermiin, L. Multi-objective evolutionary algorithms and phylogenetic inference with multiple data sets. Soft Comput 10, 359–368 (2006). https://doi.org/10.1007/s00500-005-0495-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-005-0495-7