Jump to: Freely distributable scientific documents and computer programs

Program T-REX (Tree and Reticulogram reconstruction) Vladimir Makarenkov (with contributions from Alix Boc, Philippe Casgrain, Abdoulaye Baniré Diallo, Olivier Gascuel, Alain Guénoche, Pierre-Alexandre Landry, François-Joseph Lapointe, Bruno Leclerc, Pierre Legendre and Abdellah Mazouzi) April 2008 Departement d'Informatique Université du Québec à Montréal Internet version is now available Also available for download Windows 4.0a1 version Windows 9x/ME/NT/2000/XP executable, documentation and sample files. Main features: Six fast and effective methods for reconstruction of phylogenetic trees from sequence or distance data (including NJ, BioNJ and ADDTREE) Computes bootsrap or jackknife scores to assess the reliability of a reconstructed phylogeny ClustalW sequence alignment tool is incorporated Most popular sequence evolution models (including Jukes-Cantor, Kimura 2-parameters, Jin-Nei Gamma, Kimura Protein, LogDet and F84 distances) are available Weighted tree and reticulogram reconstruction methods Four tree reconstruction methods from partial distance matrices Reticulogram reconstruction algorithm for detecting reticulate evolution processes, including hybridization or recombination events Two algorithms for the detection of horizontal gene transfers Graphical tree and reticulogram representations using hierarchical, axial or radial types of drawing Interactive manipulation of tree and reticulogram drawing Allows one to select the root of a tree or reticulogram Allows one to select the color of the drawn reticulation branches, objects and edges Allows one to copy images as Windows Enhanced Metafile (Windows version only) and Bitmap Reads data matrices in various formats Reads, saves and manipulates tree files in the Newick format The complete documentation is included in the T-REX package. Macintosh version 1.2a4 Macintosh executable, documentation and sample files. for PowerPC Macintoshes only New features: Prints results directly from the program Progress bars indicate calculations' progress Graphical tree and reticulogram representations Five fast and effective additive tree reconstruction methods available Weighted tree and reticulogram reconstruction methods available Allows one to select the root of a tree or reticulogram Allows one to select the color of the drawn reticulations Read the documentation (also included with the above package) 32-bit DOS version 32-bit DOS Console application, suitable for DOS sessions under Windows 95/98/NT. Minimal user interface, provides text-based results (fitted distance matrix, tree edge lengths and statistics). So far, does not include the algorithm for detection of Horizontal Gene Transfers. Read the documentation (also included with the above package). A complete graphical application is in preparation. Source code C++ source code of the 32-bit DOS version above, so you can compile it for your favorite operating system. Make sure you also read the documentation. What does T-REX do? This program carries out a number of popular distance methods for the reconstruction of phylogenetix trees and reticulograms. An tree metric distance or a reticulogram distance is fitted to the given dissimilarity matrix including evolutionary distances between species (i.e. taxa, objects) considered. As far as phylogenetic tree reconstruction is concerned, the program carries out six methods of fitting a tree metric (distance representable by a tree with non-negative edge lengths) to a given dissimilarity. The following methods are available: ADDTREE by Sattath and Tversky (1977); Neighbor-joining (NJ) method by Saitou and Nei (1987); BioNeighbor-joining (BioNJ) method by Gascuel (1997); Unweighted neighbor-joining method (UNJ) by Gascuel (1997); Circular order reconstruction method by Makarenkov and Leclerc (1997), and Yushmanov (1984); Weighted least-squares method MW by Makarenkov (1999), and Makarenkov and Leclerc (1999). The first two methods NJ and ADDTREE are the most frequently used methods for inferring phylogenetic trees. The third and forth method, called BioNJ and UNJ, use at each step the same selection criterion, but different estimation and reduction formulae than NJ to infer the tree. The fifth method reconstructs an additive tree using circular orders of elements associated with a given dissimilarity. This fitting method, presented in Makarenkov and Leclerc (1997), was inspired by Yushmanov's (1984) paper which introduced the notion of circular orders of elements corresponding to the circular (say, clockwise) scanning of leaves of a tree drawing on the plane. The six method, denoted MW, looks for the best additive tree with respect to dissimilarity and weight matrices supplied by the user. This method allows for arbitrary weights, which may be chosen according to one of the classical weighting models proposed in the literature. The tree obtained by any of the six methods are polished by means of the procedure of quadratic approximation (see Barthélemy and Guénoche (1991) in the unweighted case or Makarenkov and Leclerc (1999) in the weighted case) of edge lengths in order to improve the value of the least-squares criterion and to avoid negative edge lengths. As far as reticulogram reconstruction is concerned, the program first computes a classical additive tree using one of the five available tree reconstruction algorithms. Following that, at each step of the reticulogram reconstruction procedure, a reticulation (a new edge) is chosen that minimizes the least-squares or the weighted least-squares loss function; it is added to the growing reticulogram. Two statistical criteria (Q1 and Q2) are proposed to measure the gain in fit when reticulations are added. The minimum of each of these criteria may suggest a stopping rule for addition of reticulations. So, the user can either select an appropriate criterion to stop the procedure of adding reticulations or indicate an exact number of reticulations to be placed to the reticulogram. For a detailed description of the reticulogram reconstruction method the user is referred to the papers by Legendre and Makarenkov (2002) and Makarenkov and Legendre (2004). When HGT (horizontal gene transfer) reticulogram reconstruction option the program maps the gene tree into the species tree using the least-squares. Horizontal transfers of the considered gene are then shown in the species tree, see Boc and Makarenkov (2003) and Makarenkov et al. (2005) for more detail. T-REX also allows one to reconstruct an additive tree from a dissimilarity matrix containing missing values. The following four fitting methods are available: Triangle method by Guénoche and Leclerc (2001), Ultrametric procedure for estimation of missing values by De Soete (1984) and Lapointe and Landry (1997) followed by NJ. Additive procedure for estimation of missing values by Lapointe and Landry (1997) followed by NJ. Weighted least-squares method MW* by Makarenkov and Lapointe (2004) giving weights of 1 to the existing entrees and weights of 0.5 (if reestimated) or 0 (if the reestimation is not possible) to the missing ones. As results the program provides: Fitted phylogenetic or reticulogram distance matrix; List of the tree or reticulogram edges with their lengths and bootsrap or jackknife scores; Values of the (weighted) least-squares criterion, the (weighted) average absolute difference, the (weighted) maximum absolute difference and the total lengths of the obtained tree or reticulogram. If reticulogram reconstruction is performed the program also provides the values of the least-squares criterion, as well as the values of the criterion Q1 or Q2 for each reticulation added to the basic additive tree; Tree or reticulogram drawing. The tree edges are depicted by full lines and the supplementary edges (reticulations or HGTs) are depicted by dashed lines. More distance matrix methods can be found on Joe Felsenstein's software page. Windows 9x/ME/NT/2000/XP version of T-Rex (Version 4.01) including a Setup utility and all Windows DLLs used by the program (7.63MB) Windows 9x/ME/NT/2000/XP version of T-Rex (Version 3.01) including a Setup utility (2.11MB) Windows 9x/ME/NT/2000/XP version of T-Rex (Version 3.01) requiring a quick manual installation (478KB) Windows 9x/ME/NT/2000/XP version of T-Rex (Version 2.01) requiring a quick manual installation (476KB) Windows 9x/ME/NT/2000/XP version of T-Rex (Version 2.01) including a Setup utility (1.56MB) 32-bit DOS version and its source code - T-Rex 2.01 (92KB) Macintosh (Power Mac) version of T-Rex (322KB) References: Barthélemy, J.P., Guénoche, A. 1991. Trees and proximity representations. New York, Wiley. Boc, A., Makarenkov, V. 2003. New Efficient Algorithm for Detection of Horizontal Gene Transfer Events, Algorithms in Bioinformatics, Springer, WABI 2003, 190-201. Cavalli-Sforza, L.L., Edwards, A.W.F. 1967. Phylogenetic analysis models and estimation procedures, American Journal of Human Genetics, 19, 233-257. De Soete, G. 1984. Additive-Tree Representations of Incomplete Dissimilarity Data, Quality and Quantity, 18, 387-393. Fitch, W. M., Margoliash, E. 1967. A non-sequential method for constructing trees and hierarchical classifications, Journal of Molecular Evolution, 18, 30-37. Gascuel, O. 1997. Concerning the NJ algorithm and its unweighted version UNJ, in Mathematical hierarchies and Biology (B. Mirkin, F.R. McMorris, F. Roberts, A. Rzhetsky, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., Providence, RI, 1997, 149-171. Gascuel, O. 1997. BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data, Mol. Biol. Evol., 14(7), 685-695. Guénoche, A., Leclerc B. 2001. The triangles method to build X-trees from incomplete distance matrices. RAIRO Operations Research, 35, 283--300. Landry, P. A., Lapointe, F.-J., Kirsch J. A. W. 1996. Estimating phylogenies from distance matrices: additive is superior to ultrametric estimation. Molecular Biology and Evolution 13(6): 818-823. Landry, P.-A., Lapointe, F.-J. 1997. Estimation of Missing Distances in Path-Length Matrices: Problems and Solutions. Pp. 209-224, in Mathematical hierarchies and Biology (B. Mirkin, F.R. McMorris, F. Roberts, A. Rzhetsky, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., Providence, RI, 1997, 209-224. Lapointe, F.J.,. Legendre, P., Rohlf, J., Smouse, P., Sneath, P. 2000. Special Section dedicated to the reticulate evolution, to appear in the Journal of Classification. Legendre, P. 2000. Biological applications of reticulation analysis, Journal of Classification 17, 153-157. Legendre, P. and V. Makarenkov. 2002. Reconstruction of biogeographic and evolutionary networks using reticulograms. Systematic Biology 51(2): 199-216. Levasseur, C., Landry, P. A. and Lapointe, 2000. Estimating Trees from Incomplete Distance Matrices: a Comparison of Two Methods, Data analysis, Classification and Related Methods (H. A.L. Kiers, J.-P. Rasson, P. J.F. Groenen, M. Schader, eds), 149-154. Levasseur, C., Landry, P. A., Makarenkov, V., Kirsch, J. A. W., Lapointe, F.-J. 2003. Incomplete distance matrices, supertrees and bat phylogeny, Molecular Phylogenetics and Evolution, 239-246. Makarenkov, V. 1997. Propriétés combinatoires des distances d'arbres. Algorithmes et applications, Ph.D. Thesis, EHESS, Paris, and Institute of Control Sciences, Moscow. Makarenkov, V., Leclerc, B. 1997. Tree metrics and their circular orders: some uses for the reconstruction and fitting of phylogenetic trees, in Mathematical hierarchies and Biology (B. Mirkin, F.R. McMorris, F. Roberts, A. Rzhetsky, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., Providence, RI, 1997, 183-208. Makarenkov, V., Leclerc, B. 1999. An algorithm for the fitting of a tree metric according to a weighted least-squares criterion, Journal of Classification 16 3-26. Makarenkov, V., Legendre, P. 2000. Improving the additive tree representation of a dissimilarity matrix using reticulations, In Kiers H.A.L., Rasson J.-P., Groenen P.J.F. and Schader M. (Edts), Data Analysis Classification and Related Methods, Springer, 35-40. Makarenkov, V., B. Leclerc. 2000. Comparison of additive trees using circular orders, Journal of Computational Biology 7, 731-744. Makarenkov, V. 2001. T-Rex: reconstructing and visualizing phylogenetic trees and reticulation networks, Bioinformatics 17, 664-668. Makarenkov, V. 2002. Comparison of four methods for inferring phylogenetic trees from incomplete dissimilarity matrices, in Classification, Clustering, and Data Analysis, (K. Jajuga, A. Sokolowski et H.-H. Bock, eds), Springer, Cracow, Poland, 371-378. Makarenkov, V. and Legendre, P. 2004. From a phylogenetic tree to a reticulated network, Journal of Computational Biology, 11 (1), 195-212. Makarenkov, V., Lapointe, F.-J. 2004. A weighted least-squares approach for inferring phylogenies from incomplete distance matrices, Bioinformatics, 20, 2113-2121. Makarenkov, V., Legendre, P. and Desdevises, Y. 2004. Modeling phylogenetic relationships using reticulated networks, Zoologica Scripta, 33 (1), 89-96. Makarenkov, V., Kevorkov, D. and Legendre, P. 2006. Phylogenetic Network Reconstruction Approaches, Applied Mycology and Biotechnology, v. 6, Genes, Genomics and Bioinformatics, Elsevier Science. Saitou, N., Nei, M. 1987. The neighbor-joining method: a new method for reconstructing phylogenetic trees, Molecular Biology Evolution 4: 406-425. Sattath, S., Tversky, A. 1977. Additive similarity trees, Psychometrika 42: 319-345. Sonea, S., Panisset, M. 1976. Pour une nouvelle bacteriologie. Revue Canadienne de Biologie, 35, 103-167. Swofford, D. L., G. L. Olsen. 1996. Phylogeny reconstruction, 407-514. In D. M. Hill eds. Molecular Systematics. Sinauer. Yushmanov, S.V. 1984. Construction of a tree with p leaves from 2p-3 elements of its distance matrix (russian), Matematicheskie Zametki 35: 877-887 6 examples of application of the reticulograms on real datasets Last updated on Monday, November 21st, 2005 by Vladimir Makarenkov Created on Tuesday, May 26, 1998