News

• Finally, also packages with executables for different operating systems for pre-release TREE-PUZZLE 5.3.rc16 have been added.

• A pre-release version TREE-PUZZLE 5.3.rc16 has been made available.

• A book chapter about ML-based testing of tree topologies using TREE-PUZZLE and Consel has been published (April 2009):
  H.A. Schmidt (2009) Testing Tree Topologies. In P. Lemey, M. Salemi, A.M. Vandamme (eds.)The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing., 2nd Edition, 381-404, Cambridge University Press, Cambridge. (ISBN: paperback: 9780521730716, hardcover: 9780521877107, datasets at www.thephylogenetichandbook.org)

• A book chapter about ML-based tree reconstruction using TREE-PUZZLE, IQPNNI and other methods has been published (April 2009):
  H.A. Schmidt and A. von Haeseler (2009) Phylogenetic Inference Using Maximum Likelihood Methods. In P. Lemey, M. Salemi, A.M. Vandamme (eds.)The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing., 2nd Edition, 181-209, Cambridge University Press, Cambridge. (ISBN: paperback: 9780521730716, hardcover: 9780521877107, datasets at www.thephylogenetichandbook.org)

• An updated CPBI unit about TREE-PUZZLE has been published (March 2007):
  Schmidt, H.A. and A. von Haeseler (2007) Maximum-Likelihood Analysis Using TREE-PUZZLE. In A.D. Baxevanis, D.B. Davison, R.D.M. Page, G. Stormo, and L. Stein (eds.) Current Protocols in Bioinformatics (Supplement 17), Unit 6.6, Wiley and Sons, New York. (DOI: 10.1002/0471250953.bi0606s17, PMID: 18428792, ISBN 0-471-25093-7, CP online)

• A book chapter on the application of parallel parameter estimation on heterogeneous workstation clusters (May 2006):
  E. Petzold, D. Merkle, M. Middendorf, A. von Haeseler, and H.A. Schmidt (2006) Phylogenetic Parameter Estimation on COWs. In A.Y. Zomaya (ed.) Parallel Computing for Bioinformatics and Computational Biology, 347-368, Wiley and Sons, New York. (ISBN 0-471-71848-3)

• An article about the parallel performance parallel TREE-PUZZLE (October 2003):
  Schmidt, H.A., E. Petzold, M. Vingron, and A. von Haeseler (2003) Molecular Phylogenetics: Parallelized Parameter Estimation and Quartet Puzzling. J. Parallel Distrib. Comput., 63, 719-727. (DOI: 10.1016/S0743-7315(03)00129-1)

Description

TREE-PUZZLE is a computer program to reconstruct phylogenetic trees from molecular sequence data by maximum likelihood. It implements a fast tree search algorithm, quartet puzzling, that allows analysis of large data sets and automatically assigns estimations of support to each internal branch. TREEPUZZLE also computes pairwise maximum likelihood distances as well as branch lengths for user specified trees. Branch lengths can be calculated with and without the molecular-clock assumption. In addition, TREE-PUZZLE o ers likelihood mapping, a method to investigate the support of a hypothesized internal branch without computing an overall tree and to visualize the phylogenetic content of a sequence alignment. TREE-PUZZLE also conducts a number of statistical tests on the data set (chi-square test for homogeneity of base composition, likelihood ratio to test the clock hypothesis, one and two-sided Kishino-Hasegawa test, Shimodaira-Hasegawa test, Expected Likelihood Weights). The models of substitution provided by TREE-PUZZLE are GTR, TN, HKY, F84, SH for nucleotides, Dayhoff, JTT, mtREV24, BLOSUM 62, VT, WAG for amino acids, and F81 for two-state data. Rate heterogeneity is modeled by a discrete Gamma distribution and by allowing invariable sites. The corresponding parameters (except for GTR) can be inferred from the data set.

Also available from this site: PUZZLEBOOT by Mike Holder and Andrew Roger (PUZZLEBOOT main site).

Download current version

An updated version of TREE-PUZZLE (5.3.rc) is available as a pre-release to the upcomming version 5.3.

• tree-puzzle-5.3.rc16.tar.gz (Source distribution, gzipped TAR format), tree-puzzle-5.3.rc16-linux.tar.gz (with Linux executable), tree-puzzle-5.3.rc16-macosx.zip (with MacOSX executable), tree-puzzle-5.3.rc16-windows.zip
  (with Windows executable)

• Currently only a source version is available which lacks an updates manual. Please refer, to the help output with puzzle -h.
• Installation instructions are given and (incomplete) list of features are given in the manual of version 5.2 (tree-puzzle.pdf).

New features in version 5.3 include

• Likelihood mapping output in SVG format
• An interface to enter commandline parameters if started by double-click (the executable has to be renamed to contain 'clicky', e.g. puzzle-clicky.exe)
• Evaluation of parsimony-informative sites for the alignment using an extended definition of parsimony-informativeness.
• Evaluation of parsimony-informative sites per sequence.
• Stop after alignment evaluation with the flag -statsonly.
• LG model of protein evolution added.
• Perform a relative majority consensus with -consmrel.
• Write pairwise edit distances to PREFIX.editdist with -weditdist.
• Write pairwise substitutions counts to PREFIX.tstv with -wtstv.
• Write splits file PREFIX.splits with -wsf.
• Write splits in nexus format with -wsnex.
• Write site rates to PREFIX.siterate with -wsr.
• Write site log-likelihoods to PREFIX.sitelh (PHILIP-like format) with -wsl.
• Write intermediate trees in nexus format with -witnex.
• Furthermore, a few issues with larger datasets have been fixed.
• Consensus tree construction for user given sets of trees (providing 50% majority and relative majority consensus, cf. manual for details. Was already in 5.2)

References and Publications

If you intend to use TREE-PUZZLE in a publication please cite the program as

Schmidt, H.A., K. Strimmer, M. Vingron, and A. von Haeseler (2002) TREE-PUZZLE: maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics. 18:502-504.
(DOI: 10.1093/bioinformatics/18.3.502, PMID: 11934758)

For the quartet puzzling algorithm please use:

Strimmer, K., and A. von Haeseler (1996) Quartet puzzling: A quartet maximum likelihood method for reconstructing tree topologies. Mol. Biol. Evol. 13: 964-969. (journal page)

For likelihood mapping please use:

Strimmer, K., and A. von Haeseler (1997) Likelihood-mapping: A simple method to visualize phylogenetic content of a sequence alignment. Proc. Natl. Acad. Sci. USA. 94:6815-6819. (PMID: 9192648)

For the quartet selection taking into account 2nd and 3rd best quartets:

Strimmer, K., N. Goldman and A. von Haeseler (1997) Bayesian Probabilities and Quartet Puzzling. Mol. Biol. Evol. 14:210-213. (journal page)

For the current parallel version of TREE-PUZZLE please use:

Schmidt, H.A., K. Strimmer, M. Vingron, and A. von Haeseler (2002) TREE-PUZZLE: maximum likelihood phylogenetic analysis using quartets and parallel computing. Bioinformatics. 18:502-504.
(DOI: 10.1093/bioinformatics/18.3.502, PMID: 11934758)

Hands-on excercises and explainations of features and usage of TREE-PUZZLE can be found in:

Schmidt, H.A. and A. von Haeseler (2007) Maximum-Likelihood Analysis Using TREE-PUZZLE. In A.D. Baxevanis, D.B. Davison, R.D.M. Page, G. Stormo, and L. Stein (eds.) Current Protocols in Bioinformatics (Supplement 17), Unit 6.6, Wiley and Sons, New York. (DOI: 10.1002/0471250953.bi0606s17, PMID: 18428792, ISBN 0-471-25093-7, CP online)

H.A. Schmidt and A. von Haeseler (2009) Phylogenetic Inference Using Maximum Likelihood Methods. In P. Lemey, M. Salemi, A.M. Vandamme (eds.)The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing., 2nd Edition, 181-209, Cambridge University Press, Cambridge. (ISBN: paperback: 9780521730716, hardcover: 9780521877107)

H.A. Schmidt (2009) Testing Tree Topologies. In P. Lemey, M. Salemi, A.M. Vandamme (eds.)The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing., 2nd Edition, 381-404, Cambridge University Press, Cambridge. (ISBN: paperback: 9780521730716, hardcover: 9780521877107)

Further details about TREE-PUZZLE can be found in:

H.A. Schmidt (2003) Phylogenetic Trees from Large Datasets. PhD Thesis, Düsseldorf University, Germany. (available from Düsseldorf University E-Diss server or as local copy)

Korbinian Strimmer (1997) Maximum likelihood methods in molecular phylogenetics. PhD Thesis, Munich University, Germany. (manuscript available from Korbinian Strimmer's Lab)

E. Petzold, D. Merkle, M. Middendorf, A. von Haeseler, and H.A. Schmidt (2006) Phylogenetic Parameter Estimation on COWs. In A.Y. Zomaya (ed.) Parallel Computing for Bioinformatics and Computational Biology, 347-368, Wiley and Sons, New York. (ISBN 0-471-71848-3)

Distribution site

The most up-to-date version of the TREE-PUZZLE program is distributed at

• TREE-PUZZLE Home Page (www.tree-puzzle.de)

In addition, binary distributions can be found at (these are possibly older versions)

• Debian Linux Packages (http://packages.debian.org/tree-puzzle)
  [different Debian versions available - some versions are outdated]
• Ubuntu Linux Packages (packages.ubuntu.com/tree-puzzle)
• FreeBSD Port (cvsweb.freebsd.org/ports/biology/treepuzzle)
• NetBSD Package (pkgsrc.se/biology/puzzle)
  [using the old name PUZZLE]

Previous Versions

For "historical" reasons (e.g., to allow cross-checks of older results) we keep previous versions of PUZZLE available. As the sources and documentation are identical across different platforms only gzipped tar archives are provided.

• version 5.2: tree-puzzle-5.2.tar.gz (Source), tree-puzzle-5.2-linux.tar.gz (with Linux executable), tree-puzzle-5.2-macosx.tar.gz (with MacOSX executable), tree-puzzle-5.2-windows.zip
  (with Windows executable)

• version 5.1: tree-puzzle-5.1.tar.gz
• version 5.0: tree-puzzle-5.0.tar.gz (Source, Unix), tree-puzzle-5.0.hqx (MacOS PPC), tree-puzzle-5.0.zip(Windows)
• version 4.0.2
• version 4.0.1
• version 4.0
• version 3.1
• version 3.0
• version 2.5.1
• version 2.5
• version 2.4
• version 2.3
• version 2.2
• version 2.1
• version 2.0

Related Software (in alphabetical order)

consel

consel (by Hidetoshi Shimodaira & Masami Hasegawa) for assessing the confidence of phylogenetic tree selection based on partial likelihoods, e.g., output by tree-puzzle using the '-wsl' option.

covARES

covARES (by Christian Blouin) allows to map site rates extracted from a tree-puzzle output file into a PDB protein structure. The resulting PDB files have their beta and occupancy fields mapped with the specified values.

PUZZLEBOOT

Michael E. Holder (holder(AT)uh.edu) from the High Performance Computing Center of the University of Houston and Andrew J. Roger (aroger(AT)is.dal.ca) from the Department of Biochemistry and Molecular Biology of Dalhousie University are distributing a shell-script program called "puzzleboot" that allows the analysis of multiple data sets with PUZZLE even though PUZZLE lacks the "M" option of many PHYLIP programs. It is designed for use with the distance matrix option of PUZZLE. PUZZLEBOOT is available from the PUZZLEBOOT main site or from this site (download the README file and the puzzleboot v1.03 script).

Acknowledgment: PUZZLEBOOT was originally conceived and developed while both authors were in the employ of Mitch Sogin at the Marine Biological Laboratory, Woods Hole, MA 02543 USA.

Contact

Heiko A. Schmidt

email: heiko.schmidt(AT)univie.ac.at,
Center for Integrative Bioinformatics Vienna (CIBIV),
Max F. Perutz Laboratories (MFPL),
A-1030 Vienna, Austria.

Arndt von Haeseler

email: arndt.von.haeseler(AT)univie.ac.at,
Center for Integrative Bioinformatics Vienna (CIBIV),
Max F. Perutz Laboratories (MFPL),
A-1030 Vienna, Austria.