Please wait a minute...
ZOOLOGICAL RESEARCH    2013, Vol. 34 Issue (6) : 640-650     DOI: 10.11813/j.issn.0254-5853.2013.6.0640
Review |
A bird’s eye view of the algorithms and software packages for reconstructing phylogenetic trees
Li-Na ZHANG1, Chang-He RONG2, Yuan HE1, Qiong GUAN4, Bin HE4, Xing-Wen ZHU1, Jia-Ni LIU4, Hong-Ju CHEN3,4
1. Mathematics and Computer Science College, Dali University, Dali Yunnan 671003, China;
2. Yunnan Forestry Technological College, Kunming Yunnan 650224, China;
3. College of Mathematics, Honghe University, Mengzi Yunnan 661100, China;
4. Computational Biology and Medical Ecology Lab, State Key Laboratory of Genetic Resources and Evolution, Kunming Institute of Zoology, Chinese Academy of Sciences, Kunming Yunnan 650223, China
Download: PDF(487 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks    

The prototype phylogenetic tree, i.e., evolutionary "tree" or "tree of life", was first conceived by Charles Darwin in his seminal book "The Origin of Species", and its reconstructions have been approached by generations of biologists ever since. In this article, we briefly reviewed the major algorithms and software packages for reconstructing phylogenetic trees. Specifically we discuss four categories of phylogeny algorithms including distance-matrix, maximum parsimony, maximum likelihood, and Bayesian framework, as well as software packages (PHYLIP, MEGA, MrBayes) based on them.

Keywords Phylogenetic tree      Distance matrix      Maximum parsimony      Maximum likelihood      Bayesian framework      Phylogenetic analysis software     
PACS:  Q332  
Issue Date: 08 December 2013
E-mail this article
E-mail Alert
Articles by authors
Chang-He RONG
Yuan HE
Qiong GUAN
Bin HE
Xing-Wen ZHU
Jia-Ni LIU
Hong-Ju CHEN
Cite this article:   
Li-Na ZHANG,Chang-He RONG,Yuan HE, et al. A bird’s eye view of the algorithms and software packages for reconstructing phylogenetic trees[J]. ZOOLOGICAL RESEARCH, 2013, 34(6): 640-650.
URL:     OR

Altschul SF, GISH W, Miller W, Myers EW, Ipman DJ. 1990. Basic local alignment search Tool. Journal of Molecular Biology, 215(3): 402-410.
Avise J. 2006. Evolutionary Pathways in Nature: A Phylogenetic Approach. New York: Cambridge University Press.
Bruno W J, Socd N D, Halpern AL. 2000. Weighted neighbor joining: a likelihood-based approach to distance-based phylogeny reconstruction. Molecular Biology and Evolution, 17(1): 189-197.
Bryant D, Galtier N, Poursat MA. 2005. Mathematics of Evolution and Phylogeny: Likelihood Calculation in Molecular Phylogeny. Oxford: Oxford University Press USA.
Camin J H, Sokal R R. 1965. A method for deducing branching sequences in phylogeny. Evolution, 19(3): 311-326.
Chen NT, Wang NC, Shi BC. 2006. Fast algorithm for constructing neighbor-joining phylogenetie trees. Journal of Southeast University, 22(2): 176-179.
Criscuolo A, Gascuel Q. 2008. Fast NJ-like algorithms to deal with incomplete distance matrices. BMC Bioinformatics, 9(1): 166-18.
Desper R, Gascuel Q. 2002. Fast and accurate phylogeny reconstruction algorithms based on the Minimum-Evolution principle. Journal of Computational Biology, 9(5): 687-705.
Dobzhansky T. 1973. Nothing in biology makes sense except in the light of evolution. The American Biology Teacher, 35: 125-129.
Edgar RC. 2004. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, 32(5): 1792-1797.
Even S, Even G. 2011. Graph Algorithms. New York: Cambridge University Press, 46-48.
Felsenstein J. 1978. Cases in which parsimony or compatibility methods will be positively misleading. Systematic Zoology, 27(4):401-410.
Felsenstein J. 1979. Alternative methods of phylogenetic inference and their interrelationship. Systematic Zoology, 28(1): 49-62.
Felsenstein J. 1981a. A likelihood approach to character weighting and what it tells us about parsimony and compatibility. Biological Journal of the Linnean Society, 16(3): 183-196.
Felsenstein J. 1981b. Evolutionary trees from DNA sequences: a maximum likelihood approach. Journal of Molecular Evolution, 17(6): 368-376.
Felsenstein J. 1985. Confidence limits on phylogenies: an approach using the bootstrap. Evolution, 39(4): 783-791.
Fitch W. 1971. Toward defining the course of evolution: Minimum change for a specified tree topology. Systematic Zoology, 20: 406-416.
Foulds LR, Graham RL. 1982. The steiner tree problem in phylogeny is NP-complete. Advances in Applied Mathematics, 3: 4-49.
Gascuel Q. 1997. BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data. Molecular Biology and Evolution, 14(7): 685-695.
Gregory TR. 2008. Understanding evolutionary trees. Evolution: Education and Outreach, 1(2): 121-137.
Hein J. 1990. Reconstructing evolution of sequences subject to recombination using parsimony. Mathematical Biosciences, 98(2): 185-200.
Hein J. 1993. A heuristic method to reconstruct the history of sequences subject to recombination. Journal of Molecular Evolution, 36(4): 396-405.
Holder M, Lewis PO. 2003. Phylogeny estimation: traditional and bayesian approaches. Nature, 4(4): 275-284.
Huelsenbeck JP, Ronquist F. 2001. MRBAYES: bayesian inference of phylogenetic trees. Bioinfrmatics, 17 (8):754-755.
Jukes TH, Cantor CR. 1969. Evolution of protein molecules. In: Mammalian Protein Metabolism. New York: Academic Press.
Kidd KK, Sgaramelh-Zonta LA. 1971. Phylogenetic Analysis: concepts and methods. The American Journal of Human Genetics, 23(3): 235-252.
Kimura M. 1980. A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. Journal of Molecular Evolution, 16(2): 111-120.
Land AH, Doig AG. 1960. An automatic method of solving discrete programming problems. Econometrica, 28(3): 497-520.
Larkin MA, Blackshields G, Brown NP, Chenna R, McGettigan PA, McWilliam H, Valentin F, Wallace IM, Wilm A,Lopez R, Thompson JD, Gibson TJ, Higgins DG. 2007. Clustal W and Clustal X version 2.0. Bioinformatics, 23(21): 2947-2948.
Lipman DJ, Pearson WR. 1985. Rapid and sensitive protein similarity searches. Science, 227(4693): 1435-1441.
Mount DW. 2008. Maximum parsimony method for phylogenetic prediction. Cold Spring Harbor Protocols, doi: 10.1101/pdb.top32.
Mucherino A, Seref O. 2009. Modeling and solving real-life global optimization problems with meta-heuristic methods. Advances in Modeling Agricultural Systems, 25: 403-419.
Myung IJ. 2003. Tutorial on maximum likelihood estimation. Journal of Mathematical Psychology, 47(1): 90-100.
Penny D. 1982. Towards a basis for classification: the incompleteness of distance measures, incompatibility analysis and phenetic classification. Journal of Theoretical Biology, 96(2): 129-142.
Penny D, Hendy MD. 1985. The use of tree comparison metrics. Systematic Zoology, 34(1): 75-82.
Saitou N, Nei M. 1986. The number of nucleotides required to determine the branching order of three species, with special reference to the human-chimpanzee-gorilla divergence. Journal of Molecular Evolution, 24(1-2): 189-204.
Saitou N, Imanishi T. 1989. Relative efficiencies of the fitch-margoliash, maximum-parsimony, maximum-likelihood, minimum-evolution, and neighbor-joining methods of phylogenetic tree construction in obtaining the corrent tree. Molecular Biology and Evolution, 6(5): 514-525.
Sanmartín I, van der Mark P, Ronquist F. 2008. Inferring dispersal: a Bayesian approach to phylogeny-based island biogeography, with special reference to the Canary Islands. Journal of Biogeography, 35(3): 428-449.
Shao J, Tu DS. 1996. The Jackknife and Bootstrap. New York: Springer.
Studier JA, Keppler KJ. 1988. A note on the neighbor-joining algorithm of Saitou and Nei. Molecular Biology and Evolution, 5(6): 729-731.
Sober E. 1988. Reconstructing the Past: Parsimony Evolution and Inference. London: Cambridge MIT Press.
Takezaki N. 1998. Tie trees generated by distance methods of phylogenetic reconstruction. Molecular Biology and Evolution, 15(6): 727-737.
Taylor MP, Wedel MJ, Cifelli RL. 2011. A new sauropod dinosaur from the Lower Cretaceous Cedar Mountain Formation, Utah, USA. Acta Palaeontologica Polonica, 56(1): 75-98.
Wu CFJ. 1986. Jackknife, bootstrap and other resampling methods in regression analysis. The Annals of Statistics, 14(4): 1261-1295.
Yang ZH, Rannala B. 2012. Molecular phylogenetics: principles and practice. Nature Reviews Genetics, 13(5): 303-314.
Zhang SB, Lai JH. 2010. Bioinformatics approach for molecular evolution research. Computer Science, 37(8): 47-51. [张树波, 赖剑煌. 2010. 分子系统发育分析的生物信息学方法. 计算机科学, 37(8): 47-51.]
Zhong Y, Zhao L, Zhao Q. 2001. An Introduction to Bioinformatics. Beijing: Higher Education Press. [钟扬, 赵亮, 赵琼. 2001. 简明生物信息学. 北京: 高等教育出版社.]

[1] Ian S. LOGAN. ZIKA-How fast does this virus mutate?[J]. ZOOLOGICAL RESEARCH, 2016, 37(2): 110-115.
[2] YU Li,ZHANG Ya-ping ,*. Summary of Phylogeny in Mammalian Order Carnivora[J]. ZOOLOGICAL RESEARCH, 2006, 27(6): 657-665.
[3] HUANG Jing-fei,LIU Ci-quan. The Relationship Between Cytochrome Hydrophobicity and Molecular Evolution[J]. ZOOLOGICAL RESEARCH, 1996, 17(2): 179-185.
[4] ZHANG Ya-ping,CHEN Xing,SHI Li-ming. Polymorphism in The mtDNA of Three Species of Pheasants[J]. ZOOLOGICAL RESEARCH, 1991, 12(4): 387-392.
Full text