Maximum‐Likelihood Analysis Using TREE‐PUZZLE

Heiko A. Schmidt1, Arndt von Haeseler1

1 Center for Integrative Bioinformatics Vienna (CIBIV), Max F. Perutz Laboratories (MFPL), Vienna, Austria; University of Vienna, Austria; Medical University Vienna, Austria; University of Veterinary Medicine, Vienna, Austria
Publication Name:  Current Protocols in Bioinformatics
Unit Number:  Unit 6.6
DOI:  10.1002/0471250953.bi0606s17
Online Posting Date:  March, 2007
GO TO THE FULL TEXT: PDF or HTML at Wiley Online Library


TREE‐PUZZLE provides a means to analyze and reconstruct evolutionary relationships and trees based on quartets, i.e., groups of four sequences. Basic Protocol 1 explains how to reconstruct trees based on the maximum‐likelihood principle and quartet puzzling. Basic Protocol 2 discusses likelihood mapping, a method to visualize phylogenetic content in a multiple sequence alignment. Basic Protocol 3 explains how to compare tree topologies using different tests.

Keywords: evolutionary tree; phylogeny reconstruction; tree‐puzzle; visualizing phylogenetic content; comparing trees

PDF or HTML at Wiley Online Library

Table of Contents

  • Basic Protocol 1: Reconstruct a Phylogenetic Tree
  • Basic Protocol 2: Analyze the Content of Phylogenetic Information and the Quartet Support for the Relationship of Groups of Sequences
  • Basic Protocol 3: Compare Tree Topologies
  • Support Protocol 1: Obtain and Install TREE‐PUZZLE for Unix/Linux and Mac OS X
  • Support Protocol 2: Obtain and Install Tree‐Puzzle for Mac OS X
  • Support Protocol 3: Obtain and Install Tree‐Puzzle for MS Windows
  • Guidelines for Understanding Results
  • Commentary
  • Literature Cited
  • Figures
  • Tables
PDF or HTML at Wiley Online Library


PDF or HTML at Wiley Online Library



Literature Cited

   Adachi, J. and Hasegawa, M. 1996. Model of amino acid substitution in proteins encoded by mitochondrial DNA. J. Mol. Evol. 42:459‐468.
   Dayhoff, M.O., Schwartz, R.M., and Orcutt, B.C. 1978. A model of evolutionary change in proteins. In Atlas of Protein Sequence Structure, Vol. 5 (M.O. Dayhoff, ed.) pp. 345‐352. National Biomedical Research Foundation, Washington, D.C.
   Edwards, A.W.F. and Cavalli‐Sforza, L.L. 1964. Reconstruction of evolutionary trees. In Phenetic and Phylogenetic Classification (V.H. Heywood and J. McNeill, eds.) pp. 67‐76. Systematics Association, London.
   Felsenstein, J. 1978. The number of evolutionary trees. Syst. Zool. 27:27‐33.
   Felsenstein, J. 1981. Evolutionary trees from DNA sequences: A maximum likelihood approach. J. Mol. Evol. 17:368‐376.
   Felsenstein, J. 1984. Distance methods for inferring phylogenies: A justification. Evolution 38:16‐24.
   Felsenstein, J. 2004. Inferring Phylogenies. Sinauer Associates, Sunderland, Mass.
   Goldman, N. 1993a. Statistical tests of models of DNA substitution. J. Mol. Evol. 36:182‐198.
   Goldman, N. 1993b. Simple diagnostic statistical tests of models for DNA substitution. J. Mol. Evol. 37:650‐661.
   Goldman, N., Anderson, J.P., and Rodrigo, A.G. 2000. Likelihood‐based tests of topologies in phylogenetics. Syst. Biol. 49:652‐670.
   Gu, X., Fu, Y.‐X., and Li, W.‐H. 1995. Maximum likelihood estimation of the heterogeneity of substitution rate among nucleotide sites. Mol. Biol. Evol. 12:546‐557.
   Hasegawa, M., Kishino, H., and Yano, T. 1985. Dating the human‐ape split by a molecular clock of mitochondrial DNA. J. Mol. Evol. 22:160‐174.
   Henikoff, S. and Henikoff, J.G. 1992. Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. U.S.A. 89:10915‐10919.
   Hillis, D.M. 1996. Inferring complex phylogenies. Nature 383:130‐131.
   Iwabe, N., Kuma, K.‐I., Hasegawa, M., Osawa, S., and Miyata, T. 1989. Evolutionary relationship of Archaebacteria, Eubacteria, and Eukaryotes inferred from phylogenetic trees of duplicated genes. Proc. Natl. Acad. Sci. U.S.A. 86:9355‐9359.
   Jones, D.T., Taylor, W.R., and Thornton, J.M. 1992. The rapid generation of mutation data matrices from protein sequences. Comput. Appl. Biosci. 8:275‐282.
   Jukes, T.H. and Cantor, C.R. 1969. Evolution of protein molecules. In Mammalian Protein Metabolism (H.N. Munro, ed.). Academic Press, New York.
   Kimura, M. 1980. A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. J. Mol. Evol. 16:111‐120.
   Kishino, H. and Hasegawa, M. 1989. Evolution of the maximum likelihood estimate of the evolutionary tree topologies from DNA sequence data, and the branching order in Hominoidea. J. Mol. Evol. 29:170‐179.
   Lanave, C., Preparata, G., Saccone, C., and Serio, G. 1984. A new method for calculating evolutionary substitution rates. J. Mol. Evol. 20:86‐93.
   McMorris, F.R. and Neumann, D.A. 1983. Consensus functions defined on trees. Math. Soc. Sci. 4:131‐136.
   Müller, T. and Vingron, M. 2000. Modeling amino acid replacement. J. Comput. Biol. 7:761‐776.
   Page, R.D. and Holmes, E.C. 1998. Molecular Evolution: A Phylogenetic Approach. Blackwell Science, Oxford.
   Posada, D. and Crandall, K.A. 1998. MODELTEST: Testing the model of DNA substitution. Bioinformatics 14:817‐818.
   Posada, D. and Buckley, T. 2004. Model selection and model averaging in phylogenetics: Advantages of akaike information criterion and Bayesian approaches over likelihood ratio tests. Syst. Biol. 53:793‐808.
   Sanderson, M.J. and Shaffer, H.B. 2002. Troubleshooting molecular phylogenetic analyses. Annu. Rev. Ecol. Syst. 33:49‐72.
   Schmidt, H.A., Strimmer, K., Vingron, M., and von Haeseler, A. 2002. TREE‐PUZZLE: Maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics 18:502‐504.
   Schöniger, M. and von Haeseler, A. 1994. A stochastic model for the evolution of autocorrelated DNA sequences. Mol. Phyl. Evol. 3:240‐247.
   Shimodaira, H. and Hasegawa, M. 1999. Multiple comparisons of log‐likelihoods with applications to phylogenetic inference. Mol. Biol. Evol. 16:1114‐1116.
   Strimmer, K. and von Haeseler, A. 1996. Quartet puzzling: A quartet maximum likelihood method for reconstructing tree topologies. Mol. Biol. Evol. 13:964‐969.
   Strimmer, K. and von Haeseler, A. 1997. Likelihood mapping: A simple method to visualize phylogenetic content of a sequence alignment. Proc. Natl. Acad. Sci. U.S.A. 94:6815‐6819.
   Strimmer, K. and Rambaut, A. 2002. Inferring confidence sets of possibly misspecified gene trees. Proc. R. Soc. Lond. B 269:137‐142.
   Strimmer, K., Goldman, N., and von Haeseler, A. 1997. Bayesian probabilities and quartet puzzling. Mol. Biol. Evol. 14:210‐213.
   Swofford, D.L., Olsen, G.J., Waddell, P.J., and Hillis, D.M. 1996. Phylogeny reconstruction. In Molecular Systematics, 2nd ed. (D.M. Hillis, C. Moritz, and B.K. Mable, eds.) pp. 407‐514. Sinauer Associates, Sunderland, Mass.
   Tamura, K. and Nei, M. 1993. Estimation of the number of nucleotide substitutions in the control region of mitochondrial DNA in humans and chimpanzees. Mol. Biol. Evol. 10:512‐526.
   Tavare, S. 1986. Some probabilistic and statistical problems on the analysis of DNA sequences. Lec. Math. Life Sci. 17:57‐86.
   Whelan, S. and Goldman, N. 2001. A general empirical model of protein evolution derived from multiple protein families using a maximum likelihood approach. Mol. Biol. Evol. 18:691‐699.
Key References
   Felsenstein, 2004. See above.
  A comprehensive textbook covering almost all areas of phylogenetic inference.
   Goldman et al., 2000. See above.
  A comprehensive review discussing tests for tree topologies and their applicability.
   Page and Holmes, 1998. See above.
  A well written textbook about phylogenetics and its applications.
   Sanderson and Shaffer, 2002. See above.
  A good review on problems in phylogeny reconstruction.
   Strimmer and von Haeseler, 1996. See above.
  An original publication of the Quartet Puzzling method.
   Strimmer and von Haeseler, 1997. See above.
  A more detailed description of Likelihood Mapping.
   Swofford et al., 1996. See above.
  An excellent introduction to the rich collection of phylogenetic methods.
Internet Resources
  TREE‐PUZZLE Web site.
  TreeTool Web site (tree‐drawing program).
  TreeView Web site (tree‐drawing program, see UNIT ).
  Joe Felsenstein's list of tree‐reconstruction and ‐drawing programs.
  GhostScript Web page (PostScript viewer and converter).
PDF or HTML at Wiley Online Library