Regular Research PaperNo Access

Optimizing taxon addition order and branch lengths in the construction of phylogenetic trees using maximum likelihood

Yourim Yoon
Yong-Hyuk Kim

Department of Computer Engineering, College of Information Technology, Gachon University, 1342 Seongnamdaero, Sujeong-gu, Seongnam-si, Gyeonggi-do 13120, Republic of Korea

Search for more papers by this author

and

Yong-Hyuk Kim

Corresponding author.

http://orcid.org/0000-0002-0492-0889

School of Software, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul 01897, Republic of Korea

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0219720020500031Cited by:2

Abstract

Taxon addition order and branch lengths are optimized by genetic algorithms (GAS) within the fastDNAml algorithm for constructing phylogenetic trees of high likelihood. Results suggest that optimizing the order in which taxa are added improves the likelihood of the resulting trees.

Keywords:

References

1. Nei M, Kumar S, Molecular Evolution and Phylogenetics, Oxford University Press, 2000. Google Scholar
2. Day WHE, Computational complexity of inferring phylogenies from dissimilarity matrices, Bull Math Biol 49(4) :461–467, 1987. Crossref, Medline, Google Scholar
3. Edwards AWF, The reconstruction of evolution, Heredity 18 :553, 1963. Google Scholar
4. Felsenstein J, Evolutionary trees from DNA sequences: Amaximum likelihood approach, J Mol Evol 17 :368–376, 1981. Crossref, Medline, Google Scholar
5. Chakraborty R, Estimation of time of divergence from phylogenetic studies, Canadian J Gene Cytol 19 :217–223, 1977. Crossref, Medline, Google Scholar
6. Guindon S, Gascuel O, A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood, Syst Biol 52(5) :696–704, 2003. Crossref, Medline, Google Scholar
7. Lord E, Leclercq M, Boc A, Diallo AB, Makarenkov V, Armadillo 1.1: An original workflow platform for designing and conducting phylogenetic analysis and simulations, PLoS One 7(1) :e29903, 2012. Crossref, Medline, Google Scholar
8. Pond SL, Frost SD, MuseV SV, HyPhy: Hypothesis testing using phylogenies, Bioinformatics 21(5) :676–679, 2005. Crossref, Medline, Google Scholar
9. Vinh LS, von Haeseler A, IQPNNI: Moving fast through tree space and stopping in time, Mol Biol Evol 21 :1565–1571, 2004. Crossref, Medline, Google Scholar
10. Darriba D, Taboada GL, Doallo R, Posada D, jModelTest 2: More models, new heuristics and parallel computing, Nat Meth 9 :772, 2012. Crossref, Medline, Google Scholar
11. Helaers R, Milinkovitch MC, MetaPIGA v2.0: Maximum likelihood large phylogeny estimation using the metapopulation genetic algorithm and other stochastic heuristics, BMC Bioinform 11 :379, 2010. Crossref, Medline, Google Scholar
12. Yang Z, PAML 4: Phylogenetic analysis by maximum likelihood, Mol Biol Evol 24 :1586–1591, 2007. Crossref, Medline, Google Scholar
13. Guindon S, Lethiec F, Duroux P, Gascuel O, PHYML Online — a web server for fast maximum likelihood-based phylogenetic inference, Nucleic Acids Res 33(suppl 2) :W557–W559, 2005. Crossref, Medline, Google Scholar
14. Guindon S, Delsuc F, Dufayard J-F, Gascuel O, Estimating maximum likelihood phylogenies with PhyML, Bioinform DNA Seq Analy Meth Mol Biol 537 :113–137, February, 2009. Crossref, Medline, Google Scholar
15. Guindon S, Dufayard J-F, Lefort V, Anisimova M, Hordijk W, Gascuel O, New algorithms and methods to estimate maximum-likelihood phylogenies: Assessing the performance of PhyML 3.0, Syst Biol 59(3) :307–321, 2010. Crossref, Medline, Google Scholar
16. Gil M, Zanetti MS, Zoller S, Anisimova M, CodonPhyML: Fast maximum likelihood phylogeny estimation under codon substitution models, Mol Biol Evol, 2013. https://doi.org/10.1093/molbev/mst034. Crossref, Medline, Google Scholar
17. Stamatakis A, RAxML-VI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models, Bioinform 22(21) :2688–2690, 2006. Crossref, Medline, Google Scholar
18. Liu K, Linder CR, Warnow T, RAxML and FastTree: Comparing two methods for large-scale maximum likelihood phylogeny estimation, PLoS ONE 6(11) :e27731, 2011. Crossref, Medline, Google Scholar
19. Stamatakis A, RAxML version 8: A tool for phylogenetic analysis and post-analysis of large phylogenies, Bioinfor 30(9) :1312–1313, 2014. Crossref, Google Scholar
20. Milne I, Lindner D, Bayer M, Husmeier D, McGuire G, Marshall DF, Wright F, TOPALi v2: A rich graphical interface for evolutionary analyses of multiple alignments on HPC clusters and multi-core desktops, Bioinform 25(1) :126–127, 2009. Crossref, Medline, Google Scholar
21. Jobb G, von Haeseler A, Strimmer K, TREEFINDER: A powerful graphical analysis environment for molecular phylogenetics, BMC Evol Biol 4 :18, 2004. Crossref, Medline, Google Scholar
22. Schmidt HA, Strimmer K, Vingron M, and von Haeseler A, TREE-PUZZLE: Maximum likelihood phylogenetic analysis using quartets and parallel computing, Bioinform 18(3) :502–504, 2002. Crossref, Medline, Google Scholar
23. Boc A, Diallo AB, Makarenkov V, T-REX: A web server for inferring, validating and visualizing phylogenetic trees and networks, Nucleic Acids Res 40 :W573–W579, 2012. Crossref, Medline, Google Scholar
24. Kumar S, Stecher G, Li M, Knyaz C, Tamura K, MEGA X: Molecular evolutionary genetics analysis across computing platforms, Molecular Biology and Evolution 35(6) :1547–1549, 2018. Crossref, Medline, Google Scholar
25. Nguyen L-T, Schmidt HA, von Haeseler A, Minh BQ, IQ-TREE: A fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies, Mol Biol Evol 32(1) :268–274, 2015. Crossref, Medline, Google Scholar
26. Lin Y, Hu F, Tang J, Moret BME, Maximum likelihood phylogenetic reconstruction from high-resolution whole-genome data and a tree of 68 eukaryotes. In Pacific Symp Biocomputing, pp. 285–296, 2013. Google Scholar
27. Felsenstein J, PHYLIP — phylogeny inference package (version 3.2), Cladstics 5 :164–166, 1989. Google Scholar
28. Olsen GJ, Matsuda H, Hagstrom R, Overbeek R, fastDNAml: A tool for construction of phylogenetic trees of DNA sequences using maximum likelihood, Comput Appl Biosci 10(1) :41–48, 1994. Medline, Google Scholar
29. Kim Y-H, Lee S-K, Moon B-R, Optimizing the order of taxon addition in phylogenetic tree construction using genetic algorithm, in Proc Genetic Evol Computation Conf, pp. 2168–2178, 2003. Crossref, Google Scholar
30. Matsuda H, Protein phylogenetic inference using maximum likelihood with a genetic algorithm, in Pacific Symp Biocomputing, pp. 512–523, 1996. Google Scholar
31. Lewis PO, A genetic algorithm for maximum likelihood phylogeny inference using nucleotide sequence data, Mol Biol Evol 15(3) :277–283, 1998. Crossref, Medline, Google Scholar
32. Katoh K, Kuma K, Miyata T, Genetic algorithm-based maximum-likelihood analysis for molecular phylogeny, J Mol Evo 53 :477–484, 2001. Crossref, Medline, Google Scholar
33. Meade A, Corne D, Pagel M, Sibly R, Using evolutionary algorithms to estimate transition rates of discrete characteristics in phylogenetic trees, in Proc Congress on Evolutionary Computation, pp. 1170–1177, 2001. Crossref, Google Scholar
34. Yang Z, Nielsen R, Goldman N, Pedersen AMK, Codon-substitution models for variable selection pressure at amino acid sites, Genetics 155 :431–449, 2000. Medline, Google Scholar
35. Lockhart PJ, Steel MA, Hendy MD, Penny D, Recovering evolutionary trees under a more realistic model of sequence evolution, Mol Biol Evol 11 :605–612, 1994. Medline, Google Scholar
36. Rambaut A, Estimating the rate of molecular evolution: Incorporating non-contemporaneous sequences into maximum likelihood phylogenies, Bioinform 16(4) :395–399, 2000. Crossref, Medline, Google Scholar
37. Yang Z, Kumar S, New parsimony-based methods for estimating the pattern of nucleotide substitution and the variation of substitution rates among sites and comparison with likelihood methods, Mol Biol Evol 13 :650–659, 1996. Crossref, Medline, Google Scholar
38. Messier W, Stewart C-B, Episodic adaptive evolution of primate lysozymes, Nature 385 :151–154, 1997. Crossref, Medline, Google Scholar
39. Yang Z, Likelihood ratio tests for detecting positive selection and application to primate lysozyme evolution, Mol Biol Evol 15 :568–573, 1998. Crossref, Medline, Google Scholar
40. Yoder AD, Yang Z, Estimation of primate speciation dates using local molecular clocks, Mol Biol Evol 17 :1081–1090, 2000. Crossref, Medline, Google Scholar
41. Hayasaka K, Gojobori T, Horai S, Molecular phylogeny and evolution of primate mitochondrial DNA, Mol Biol Evol 5 :626–644, 1988. Medline, Google Scholar
42. Yang Z, Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites: approximate methods, J Mol Evol 39 :306–314, 1994. Crossref, Medline, Google Scholar
43. Yang Z, A space-time process model for the evolution of DNA sequences, Genetics 139 :993–1005, 1995. Medline, Google Scholar
44. Hasegawa M, Kishino H, Yano T, Dating the human-ape splitting by a molecular clock of mitochondrial DNA, J Mol Evol 22 :160–174, 1985. Crossref, Medline, Google Scholar
45. Kim Y-H, Moon B-R, Lock-gain based graph partitioning, J Heuristics 10(1) :37–57, 2004. Crossref, Google Scholar
46. Moraglio A, Kim Y-H, Yoon Y, Moon B-R, Geometric crossover for multiway graph partitioning, Evol Comput 15(4) :445–474, 2007. Crossref, Medline, Google Scholar
47. Yoon Y, Kim Y-H, An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks, IEEE Trans Cybernet 43(5) :1473–1483, 2013. Crossref, Medline, Google Scholar
48. Goldberg D, Lingle R, Alleles, loci and the traveling salesman problem, in Proc Int Conf Genetic Algorithms, pp. 154–159, 1985. Google Scholar
49. Pethica R, Barker G, Kovacs T, Gough J, TreeVector: Scalable, interactive, phylogenetic trees for the web, PLoS ONE 5 :e8934, 2010. Crossref, Medline, Google Scholar
50. Kim Y-H, Yoon Y, Moon B-R. A Lagrangian approach for multiple personalized campaigns, IEEE Trans Knowl Data Eng 20(3) :383–396, 2008. Crossref, Google Scholar
51. Yoon Y, Kim Y-H, Moraglio A, Moon B-R, A theoretical and empirical study on unbiased boundary-extended crossover for real-valued representation, Inf Sci 183(1) :48–65, 2012. Crossref, Google Scholar
52. Yoon Y, Kim Y-H, Geometricity of genetic operators for real-coded representation, Appl Math Comput 219(23) :10915–10927, 2013. Crossref, Google Scholar
53. Syswerda G, Uniform crossover in genetic algorithms, in Proc Third Int Conf Genetic Algorithms, pp. 2–9, 1989. Google Scholar
54. Tan G, Muffato M, Ledergerber C, Herrero J, Goldman N, Gil M, Dessimoz C, Current methods for automated filtering of multiple sequence alignments frequently worsen single-gene phylogenetic inference, Syst Biol 64(5) :778–791, 2015. Crossref, Medline, Google Scholar
55. Tamura K, Peterson D, Peterson N, Stecher G, Nei M, Kumar S, MEGA5: Molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods, Mol Biol Evol 28(10) :2731–2739, 2011. Crossref, Medline, Google Scholar
56. Felsenstein J, Inferring Phylogenies, Sinauer Associates, Inc., 2004. Google Scholar
57. Lefort V, Desper R, Gascuel O, FastME 2.0: A comprehensive, accurate and fast distance-based phylogeny inference program, Mol Biol Evol 32(10) :2798–2800, 2015. Crossref, Medline, Google Scholar

Published: 6 May 2020

Vol. 18, No. 02

Metrics

Downloaded 23 times

History

Received 30 January 2019

Accepted 22 January 2020

Keywords

PDF download

System Upgrade on Mon, Jun 21st, 2021 at 1am (EDT)

Optimizing taxon addition order and branch lengths in the construction of phylogenetic trees using maximum likelihood

Abstract

References

Recommended