Source: https://www.labunix.uqam.ca/~makarenkov_v/trex.html
Timestamp: 2019-04-26 02:08:33+00:00

Document:
Boc, A., Diallo, Alpha B. and Makarenkov, V. (2012), T-REX: a web server for inferring, validating and visualizing phylogenetic trees and networks, Nucleic Acids Research, 40 (W1), W573-579.
Makarenkov, V. 2001.T-Rex: Reconstructing and visualizing phylogenetic trees and reticulation networks, Bioinformatics 17, 664-668.
What does the T-REX web server do?
1) Methods for the visualization, drawing and interactive manipulation of phylogenetic trees (using Hierarchical, Radial and Axial types of drawing). For instance, the Newick Viewer application allows users to visualize a phylogenetic tree coded by its Newick string and the Newick Builder application allows users to draw a phylogenetic tree and then save it as a Newick string.
2) Inference of phylogenetic trees using distances (NJ, NINJA, BioNJ, UNJ, ADDTREE, MW, FITCH, Circular order reconstruction), maximum likelihood (PHYML, RAxML and ML methods from PHYLIP) and maximum parsimony (MP methods from PHYLIP). T-Rex also carries out bootstrap and jackknife resampling to assess strength of support of the tree or network branches.
· Weighted least-squares method MW by Makarenkov (1999), and Makarenkov and Leclerc (1999).
The first three methods, NJ (including NINJA) and ADDTREE, are among the most frequently used methods for inferring phylogenetic trees. The third and forth method, called BioNJ and UNJ, use the same that NJ selection criterion, but different estimation and reduction formulae to infer the tree. The fifth method reconstructs a 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 concept of circular orders of elements corresponding to the circular (say, clockwise) scanning of leaves of a tree drawing on the plane. The sixth method, called MW, looks for the best additive tree with respect to the given dissimilarity and weight matrices. 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 above-mentioned methods is then 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 branch lengths in order to improve the value of the least-squares criterion and to avoid negative branch lengths.
Ultrametric procedure for the estimation of missing values by De Soete (1984) and Lapointe and Landry (1997) followed by NJ.
Additive procedure for the 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 impossible) to the missing ones.
4) As far as reticulogram inferring (i.e. reticulated cladogram or network) is concerned, the program first builds a supporting phylogenetic tree using one of the available tree inferring methods. Following that step, a reticulation (a new branch) that minimizes the least-squares or weighted least-squares loss function is added to the network at each step of the inferring procedure. Two statistical criteria (Q1 and Q2) have been proposed in order to measure the gain in fit when reticulations are added. The minimum of each of these criteria may suggest a stopping rule for the addition of reticulations. Thus, the user can either select an appropriate criterion to stop the procedure of adding reticulations or indicate an exact number of reticulations to be added 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).
5) When HGT (horizontal gene transfer) detection option is selected, the program infers an optimal (i.e. minimum-cost) scenario of horizontal (i.e. lateral) gene transfers reconciling a given pair of species and gene trees (for more detail, see Boc, Philippe and Makarenkov, 2010). Statistical validation of the obtained gene transfers by bootstrapping can be also performed. HGT Consensus, Parallel and Interactive versions of the HGT-Detection algorithm are also available. A consol version of the HGT-Detection program allowing for detecting partial horizontal gene transfer events (when only a part of the gene is transferred and acquired by the host allele through intragenic recombination) is also provided.
6) MAFFT and MUSCLE algorithm, which is one of the most widely used multiple sequence alignment tools, is available.
Uncorrected, Jukes-Cantor, Tajima-Nei, Kimura 2-parameters, Tamura, Jin-Nei gamma, Kimura protein, LogDet, F84, WAG, JTT and LG.
8) Computation of the Robison and Foulds topological distance between two (or more) phylogenetic trees can be carried out.
9) Tree format conversion - from Newick to Distance matrix format and vice versa - is provided.
10) Generation of a specified number of random phylogenetic trees with a specified number of leaves (i.e., species, taxa) and a predefined average branch length according the procedure described by Kuhner and Felsenstein (1994).
For the tree reconstruction – the values of the (weighted) least-squares coefficient, (weighted) average absolute difference, (weighted) maximum absolute difference and total lengths of the obtained tree. If the reticulogram reconstruction is performed, the program also provides the values of the least-squares criterion, as well as the values of the selected stopping criterion Q1 or Q2 for the supporting tree topology as well as for each reticulation added to such a supporting tree. If HGT-Detection is performed, the values of the bipartition dissimilarity (see Boc, Philippe and Makarenkov 2010), Robinson and Foulds distance and least-squares coefficient are provided at each step of the HGT inferring algorithm.
Tree, reticulogram or HGT network drawing: The tree branches are depicted by full lines and reticulations or gene transfer branches are depicted by dashed lines.
Windows 9x/ME/NT/2000/XP executable, documentation and sample files.
The complete documentation is included in the T-REX package.
Macintosh executable, documentation and sample files.
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.
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.
Barthélemy, J.P., Guénoche, A. 1991. Trees and proximity representations. New York, Wiley.
Beiko, R. G., and Hamilton, N. 2006. Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol., 6, 15.
Boc, A., Makarenkov, V. 2003. New Efficient Algorithm for Detection of Horizontal Gene Transfer Events, Algorithms in Bioinformatics, Springer, WABI 2003, 190-201.
Boc, A., Philippe, H. and Makarenkov, V. 2010. Inferring and validating horizontal gene transfer events using bipartition dissimilarity, Systematic Biology, 59, 195-211.
Boc, A., Diallo, Alpha. B. and Makarenkov, V. 2011. Un nouvel algorithme pour la détection des transferts horizontaux de gènes partiels entre les espèces et pour la classification des transferts inférés, Proceedings of the 18-èmes Rencontres de la SFC, SFC-2011, Orleans, France, 25-28.
Boc, A. and Makarenkov, V. 2011. Towards an accurate identification of mosaic genes and partial horizontal gene transfers, Nucleic Acids Research, 39, e144.
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.
Edgar, R. C. 2004. MUSCLE: multiple sequence alignment with high accuracy and high throughput, Nucl. Acids Res., 32, 1792-1797.
Felsenstein, J. 1981 Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol., 17, 368–376.
Felsenstein, J. 1989. PHYLIP - Phylogeny Inference Package (Version 3.2). Cladistics 5, 164-166.
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.
Guindon, S. and Gascuel, O. 2002. Efficient biased estimation of evolutionary distances when substitution rates vary across sites. Mol. Biol. Evol., 19, 534-543.
Guindon, S., Dufayard, J. F., Lefort, V., Anisimova, M., Hordijk, W. and Gascuel, O. 2010. New algorithms and methods to estimate maximum-likelihood phylogenies: Assessing the performance of PhyML 3.0. Syst. Biol., 59, 307-321.
Gogarten, J. P., W. F. Doolittle, and J. G. Lawrence. 2002. Prokaryotic Evolution in Light of Gene Transfer. Mol. Biol. Evol. 19:2226-2238.
Guénoche, A., Leclerc B. 2001. The triangles method to build X-trees from incomplete distance matrices. RAIRO Operations Research, 35, 283--300.
Hallett, M. and Lagergren, J. 2001. Efficient algorithms for lateral gene transfer problems. In El-Mabrouk,N., Lengauer,T. and Sankoff,D. (eds.), Proceedings of the fifth annual international conference on research in computational biology. ACM Press, New-York, pp. 149-156.
Hollingshead, S.K., Becker, R. and Briles, D.E. 2000. Diversity of PspA: mosaic genes and evidence for past recombination in Streptococcus pneumoniae. Infect. Immun., 68, 5889-5900.
Jin, L. and Nei, M. 1990. Limitations of the evolutionary parsimony method of phylogenetic analysis. Mol. Biol. Evol., 7, 82-102.
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 Munro,H.N. (ed.), Mammalian protein metabolism. New York: Academic Press. pp. 21–123.
Katoh, K., Kuma, K., Toh, H. and Miyata,T. (2005) MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Res., 33, 511-518.
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.
Kimura, M. 1983. The neutral theory of molecular evolution. Cambridge University Press, Camb.
Kuhner, M. and Felsenstein, J. 1994. A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol. Biol. Evol., 11, 459-468.
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.
Le, S. Q. and Gascuel, O. 2008. LG: an improved, general amino-acid replacement matrix. Mol. Biol. Evol., 25, 1307-1320.
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.
Lockhart, P. J, Steel, M. A., Hendy, M. D. and Penny, D. 1994. Recovering evolutionary trees under a more realistic model of sequence evolution. Mol. Biol. Evol., 11, 605-612.
Maddison, W. P. 1997. Gene trees in species trees. Systematic Biology 46:523-536.
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.
Makarenkov, V., Boc, A. and Diallo, Alpha. B. 2007. La dissimilarité de bipartition et son utilisation pour détecter les transferts horizontaux de gènes, Proceedings of the 14-èmes Rencontres de la SFC 2007, ENST de Paris, France, 90-93.
Page, R. D. M., and M. A. Charleston. 1998. Trees within trees: phylogeny and historical associations. Trends in Ecol. and Evol. 13:356-359.
Robinson, D. R. and Foulds, L. R. 1981. Comparison of phylogenetic trees. Math. Biosciences, 53, 131-147.
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.
Stamatakis, A., Hoover, P. and Rougemont, J. 2008. A rapid bootstrap algorithm for the RAxML web-servers, Syst. Biol., 75, 758-771.
Swofford, D. L., G. L. Olsen. 1996. Phylogeny reconstruction, 407-514. In D. M. Hill eds. Molecular Systematics. Sinauer.
Tajima, F. and Nei, M. 1984. Estimation of evolutionary distance between nucleotide sequences. Mol. Biol. Evol., 1, 269-285.
Tamura, K. 1992. Estimation of the number of nucleotide substitutions when there are strong transition-transversion and G+C content biases. Mol. Biol. Evol., 9, 678–687.
Than, C., Ruths, D. and Nakhleh, L. 2008. PhyloNet: A software package for analyzing and reconstructing reticulate evolutionary relationships. BMC Bioinf., 9, 322.
Thompson, J. D., Higgins, D. G. and Gibson, T. J. 1994. CLUSTAL W: Improving the sensitivity of multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucl. Acids Res., 22, 4673-4680.
Wheeler, T. J. (2009) Large-scale neighbor-joining with NINJA. In Salzberg,S. and Warnow,T (eds.), Proceedings of the 9th Workshop on Algorithms in Bioinformatics, Springer Verlag, Berlin, pp. 375-389.
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.
Woese, C. R., G. Olsen, M. Ibba, and D. Söll. 2000. Aminoacyl-tRNA synthetases, the genetic code, and the evolutionary process. Microbiol. Mol. Biol. Rev. 64:202-236.
Yushmanov, S.V. 1984. Construction of a tree with p leaves from 2p-3 elements of its distance matrix (in Russian), Matematicheskie Zametki 35: 877-887.
Zhaxybayeva, O., P. Lapierre, and J. P. Gogarten. 2004. Genome mosaicism and organismal lineages. Trends Genet. 20:254-260.

References: V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 v.