TrExML: a maximum-likelihood approach for extensive tree-space exploration

MOTIVATION: Maximum-likelihood analysis of nucleotide and amino acid sequences is a powerful approach for inferring phylogenetic relationships and for comparing evolutionary hypotheses. Because it is a computationally demanding and time-consuming process, most algorithms explore only a minute portion of tree-space, with the emphasis on finding the most likely tree while ignoring the less likely, but not significantly worse, trees. However, when such trees exist, it is equally important to identify them to give due consideration to the phylogenetic uncertainty. Consequently, it is necessary to change the focus of these algorithms such that near optimal trees are also identified. RESULTS: This paper presents the Advanced Stepwise Addition Algorithm for exploring tree-space and two algorithms for generating all binary trees on a set of sequences. The Advanced Stepwise Addition Algorithm has been implemented in TrExML, a phylogenetic program for maximum-likelihood analysis of nucleotide sequences. TrExML is shown to be more effective at finding near optimal trees than a similar program, fastDNAml, implying that TrExML offers a better approach to account for phylogenetic uncertainty than has previously been possible. A program, TreeGen, is also described; it generates binary trees on a set of sequences allowing for extensive exploration of tree-space using other programs. AVAILABILITY: TreeGen, TrExML, and the sequence data used to test the programs are available from the following two WWW sites: http://whitetail.bemidji.msus. edu/trexml/and http://jcsmr.anu.edu.au/dmm/humgen.+ ++html.     

HOMOPLASY AND THE CHOICE AMONG CLADOGRAMS

Abstract Cladistic data are more decisive when the possible trees differ more in tree length. When all the possible dichotomous trees have the same length, no one tree is better supported than the others, and the data are completely undecisive . From a rule for recursively generating undecisive matrices for different numbers of taxa, formulas to calculate consistency, rescaled consistency and retention indices in undecisive matrices are derived. The least decisive matrices are not the matrices with the lowest possible consistency, rescaled consistency or retention indices (on the most parsimonious trees); those statistics do not directly vary with decisiveness. Decisiveness can be measured with a newly proposed statistic, DD = − S )/( − S ) (where S = length of the most parsimonious cladogram, = mean length of all the possible cladograms for the data set and M = observed variation). For any data set, can be calculated exactly with simple formulas; it depends on the types of characters present, and not on their congruence. Despite some recent assertions to the contrary, the consistency index is an appropriate measure of homoplasy (= deviation from hierarchy). The retention index seems more appropriate for comparing the fit of different trees for the same data set.     

PENGUINS,PETRELS, AND PARSIMONY: DOES CLADISTIC ANALYSIS OF BEHAVIOR REFLECT SEABIRD PHYLOGENY?

Whether or not behavior accurately reflects evolutionary relationships (phylogeny) has been hotly debated by ethologists and comparative psychologists. Previous studies attempting to resolve this question have generally lacked a quantitative, phylogenetic approach. In this study we used behavior and life-history (BLH) information (72 characters) to generate phylogenetic trees for 18 seabird species (albatrosses, petrels, and penguins). We compared these trees with trees obtained from isozyme electrophoretic analysis of blood proteins (15 loci and 98 electromorphs) and partial mitochondrial 12S ribosomal DNA sequences (381 base pairs). Cladistic analysis of the BLH data set generated three MP trees (tree length = 243, CI = 0.52, RI = 0.57) with significant cladistic structure. The BLH characters were classified into four types (foraging, agonistic, reproductive, and life history) and levels of homoplasy for each type were measured. No significant differences were found among these categories. The BLH trees were shown to be significantly more congruent with the electrophoretic and 12S sequence trees than expected by chance. This indicates that seabird BLH data contains phylogenetic signal. Areas of incongruence between BLH trees and a phylogeny generated by combining the data sets were predicted to result from ecological constraints that did not covary with phylogeny. These predictions were supported by the results of a concentrated changes test. This study found that this BLH data set was no more homoplasious than molecular data and that BLH trees were significantly congruent with molecular trees.     

CLADISTIC AND BIOGEOGRAPHIC ANALYSES OF HAWAIIAN PIPUNCULIDAE (DIPTERA) REVISITED

Abstract — Pipunculidae (Diptera) of the Hawaiian islands belong to the endemic hawaiiensis subgroup of the subgenus Cephalops ( Semicephalops ). In total 36 species are known from the Hawaiian islands. Cladistic analysis of 31 species, using 21 morphological characters from the male terminalia, resulted in 480 equally parsimonious trees. Three rounds of successive weighting resulted in 610 equally parsimonious trees. A biogeographic analysis was carried out, using the three-area statement technique and based on the strict consensus tree produced from the tree set obtained by successive weighting. The analysis puts the sequence of the island groups in congruence with the geological history of the islands. The results of the cladistic and biogeographic analyses were compared with earlier similar analyses.     

真正柑桔果树群植物的分支学研究

本文用相容性分析方法(Compatability snalysis)分析了真正柑桔果树群(芸香科Rutaceae-柑桔亚科Aurantioideae-柑桔族(Citreae)-柑桔亚族(Citrinae)植物内各属间的分支学关系。给出了建立在7个相容性性状组成的最大族所决定的分支图。性状极性的确定使用了外群法。结果表明,柑桔属(Citrus L.)和多蕊桔属(Clymenia Swing)构成一个单系类群,他们的姐妹群是金柑属(Fortunella Swing.)。被认为起源于中国的3个属,柑桔属(Citrus)、金柑属(Fortunella)和积属(Poncirus Raf.)并未构成一个单系类群。本文还利用分支关系分析和讨论了真正柑桔果树群的种系发生关系。     

A cladistic analysis of Geranium subgen. Erodioidea (Picard) Yeo (Geraniaceae)

Subgenus Erodioidea , comprising 19 species, is diagnosed exclusively by the type of fruit discharge and associated morphological characters, all of which are of widespread occurrence within the Geraniaceae. We have no evidence to suggest that the three included sections ( Erodioidea, Aculeolata and Subacaulia) form a monophyletic group. Cladistic analysis of a data set containing 30 morphological characters has confirmed our doubts of monophyly of the subgenus by placing part of the outgroup within the ingroup. Subsequent analyses of the two included non-monotypic sections, Erodioidea and Subacaulia , give different results. For both sections, the monophyly assumption is reasonably well-supported by characters. However, while analysis of sect. Erodioidea results in an explicit hypothesis of relationships and a fully resolved cladogram, resolution within sect. Subacaulia is low. For analysis of the latter, seven different outgroups were used and, in each one, the successive approximations weighting procedure (available in the program Hennig 86) was followed to improve resolution. Despite this, lower nodes in the cladogram remained unresolved, and strict consensus trees of all the analyses resulted in only a few replicated subterminal clades. These results are discussed in connection with biogeographical data and with the hypothesis that representatives of sect. Subacaulia are schizoendemics.     

Cladistic analysis of the Lythraceae sensu lato based on morphological characters

GRAHAM, S. A., CRISCI, J. V. & HOCH, P. C, 1993. Cladistic analysis of the Lythraceae sensu lato based on morphological characters. The Lythraceae s. I. comprise 31 mostly highly distinctive genera distributed worldwide. Cladistic analyses of the family were undertaken using 26 characters from anatomy, floral morphology, pollen, and seed morphology. Of four outgroup hypotheses, the Onagraceae offered the best heuristic assessment, generating 3746 trees with a tree length of 83 and consistency index and (C.I.) of 0.41. A strict consensus tree from the 3746 trees produced a basal monophyletic group of five genera (Sonneratia, Duabanga, Punka, Lagerstroemia, Lawsonia) characterized by anthotelic (determinate) inflorescences and wet stigmas, and a second clade with blastotelic (indeterminate) inflorescences, dry stigmas, and reduced carpel number. Successive weighting with Onagraceae as outgroup generated five most parsimonious trees with a tree length of 164 and C.I. of 0.75. Internal branches are weakly supported by only seven non-homoplasious characters. Significant results of the analysis include: (1) recognition of the two major clades and a total of seven monophyletic groups within the family; (2) the paraphyly of subfamily Lythroideae (Lythraceae s. s .); and (3) indication that genera endemic to the New World have been derived from more than one ancient Old World evolutionary line. The current taxonomic classification of the family is not closely correlated with results of the cladistic analysis.     

QDist--quartet distance between evolutionary trees

SUMMARY: QDist is a program for computing the quartet distance between two unrooted trees, i.e. the number of quartet topology differences between the trees, where a quartet topology is the topological subtree induced by four species. The program is based on an algorithm with running time O(n log2 n), which makes it practical to compare large trees. Available under GNU license. AVAILABILITY: http://www.birc.dk/Software/QDist     

A fast algorithm to build a supertree with a set of gene trees

Important desired properties of an algorithm to construct a supertree (species tree) by reconciling input trees are its low complexity and applicability to large biological data. In its common statement the problem is proved to be NP-hard, i.e. to have an exponential complexity in practice. We propose a reformulation of the supertree building problem that allows a computationally effective solution. We introduce a biologically natural requirement that the supertree is sought for such that it does not contain clades incompatible with those existing in the input trees. The algorithm was tested with simulated and biological trees and was shown to possess an almost square complexity even if horizontal transfers are allowed. If HGTs are not assumed, the algorithm is mathematically correct and possesses the longest running time of n3 x[V0]3, where n is the number of input trees and [V0] is the total number of species. The authors are unaware of analogous solutions in published evidence. The corresponding inferring program, its usage examples and manual are freely available at http://lab6.iitp.ru/en/super3gl. The available program does not implement HGTs. The generalized case is described in the publication "A tree nearest in average to a set of trees" (Information Transmission Problems, 2011).     

A phylogenetic analysis of the Schisandraceae based on morphology and nuclear ribosomal ITS sequences

Cladistic analyses were conducted using morphological and ITS sequence data to examine phylogenetic relationships within the Schisandraceae. The most parsimonious trees obtained from the morphological data consistently show a dichotomy, with clades corresponding with the two currently accepted genera, Kadsura and Schisandra . In the ITS trees S. propinqua consistently groups with the Kadsura clade, and the position of S. glabra is uncertain. The trees resulting from the analysis of combined data are polytomous, due to the variable positions of K. scandens, K. coccinea and S. propinqua . The monophyletic status of Kadsura subgen. Kadsura sect. Kadsura and Schisandra subgen. Pleiostema are strongly supported, although the monophyly of other supraspecific taxa is unclear. Further studies are required before an unambiguous phylogeny is achieved for the family.     

The utility of NBS profiling for plant systematics: a first study in tuber-bearing Solanum species

Systematic relationships are important criteria for researchers and breeders to select materials. We evaluated a novel molecular technique, nucleotide binding site (NBS) profiling, for its potential in phylogeny reconstruction. NBS profiling produces multiple markers in resistance genes and their analogs (RGAs). Potato (Solanum tuberosum L.) is a crop with a large secondary genepool, which contains many important traits that can be exploited in breeding programs. In this study we used a set of over 100 genebank accessions, representing 49 tuber-bearing wild and cultivated Solanum species. NBS profiling was compared to amplified fragment length polymorphism (AFLP). Cladistic and phenetic analyses showed that the two techniques had similar resolving power and delivered trees with a similar topology. However, the different statistical tests used to demonstrate congruency of the trees were inconclusive. Visual inspection of the trees showed that, especially at the lower level, many accessions grouped together in the same way in both trees; at the higher level, when looking at the more basal nodes, only a few groups were well supported. Again this was similar for both techniques. The observation that higher level groups were poorly supported might be due to the nature of the material and the way the species evolved. The similarity of the NBS and AFLP results indicate that the role of disease resistance in speciation is limited.     

DupTree: a program for large-scale phylogenetic analyses using gene tree parsimony

DupTree is a new software program for inferring rooted species trees from collections of gene trees using the gene tree parsimony approach. The program implements a novel algorithm that significantly improves upon the run time of standard search heuristics for gene tree parsimony, and enables the first truly genome-scale phylogenetic analyses. In addition, DupTree allows users to examine alternate rootings and to weight the reconciliation costs for gene trees. DupTree is an open source project written in C++. Availability: DupTree for Mac OS X, Windows, and Linux along with a sample dataset and an on-line manual are available at http://genome.cs.iastate.edu/CBL/DupTree     

Molecular phylogenetics of the genus Ceratitis (Diptera: Tephritidae)

The Afrotropical fruit fly genus Ceratitis MacLeay is an economically important group that comprises over 89 species, subdivided into six subgenera. Cladistic analyses of morphological and host use characters have produced several phylogenetic hypotheses for the genus. Only monophyly of the subgenera Pardalaspis and Ceratitis (sensu stricto) and polyphyly of the subgenus Ceratalaspis are common to all of these phylogenies. In this study, the hypotheses developed from morphological and host use characters are tested using gene trees produced from DNA sequence data of two mitochondrial genes (cytochrome oxidase I and NADH-dehydrogenase subunit 6) and a nuclear gene (period). Comparison of gene trees indicates the following relationships: the subgenus Pardalaspis is monophyletic, subsection A of the subgenus Pterandrus is monophyletic, the subgenus Pterandrus may be either paraphyletic or polyphyletic, the subgenus Ceratalaspis is polyphyletic, and the subgenus Ceratitis s. s. might not be monophyletic. In addition, the genera Ceratitis and Trirhithrum do not form reciprocally monophyletic clades in the gene trees. Although the data statistically reject monophyly for Trirhithrum under the Shimodaira-Hasegawa test, they do not reject monophyly of Ceratitis.     

The evolution of growth-forms in the Macaronesian genus Aeonium (Crassulaceae) inferred from chloroplast DNA RFLPs and morphology

Phylogenetic relationships among species of Aeonium were studied using morphological characters and chloroplast DNA RFLPs. Cladistic analysis of weighted morphological data indicates that the small, herbaceous and least woody species are basal in the genus. Chloroplast DNA data gave similar results, supporting the separation of the herbaceous or small, woody species from the large, hapaxanth rosettes, rosette trees, and branched subshrubs with yellow, white or red flowers as well as the only (herbaceous) species with axillary inflorescences. The relationships among the species descending from a polytomy that comprises all species of the genus as well as a polytomy which comprises 18 of the 26 species studied, are only very incompletely resolved, except for two monophyletic clades that contain the branched subshrubs with yellow flowers ( A . sect. Aeonium ) and the branched subshrubs and rosette trees with white or red flowers ( A . sect. Leuconium ), respectively. Cladistic analysis of the combined morphological and chloroplast DNA data improved resolution considerably. Four monophyletic clades are distinguished, each of which, except for three species, comprises only one of the five main growth-form types. Although Aeonium is generally regarded as an outstanding example of adaptive radiation, this mode of speciation seems to have been of minor significance in the evolution of the genus, because each growth-form apparently evolved only once. Instead, island speciation in the absence of major ecological shifts, is probably more important in the evolution of the genus.     

URec: a system for unrooted reconciliation

URec is a software based on a concept of unrooted reconciliation. It can be used to reconcile a set of unrooted gene trees with a rooted species tree or a set of rooted species trees. Moreover, it computes detailed distribution of gene duplications and gene losses in a species tree. It can be used to infer optimal species phylogenies for a given set of gene trees. URec is implemented in C++ and can be easily compiled under Unix and Windows systems. Availability: Software is freely available for download from our website at http://bioputer.mimuw.edu.pl/~gorecki/urec. This webpage also contains Windows executables and a number of advanced examples with explanations.     

芍药属牡丹组基于形态学证据的系统发育关系分析

对芍药属牡丹组Paeonia L.sect.Moutan DC.（全部野生种）40个居群进行了基于形态学证据的系统学分析,试图建立组内种间的系统发育关系。利用PAUP （4.0）计算机程序分别构建了建立在25个形态学性状基础上的所有研究类群的距离树（UPGMA、NJ）和最大简约树（MP）。所得树的拓扑结构基本一致,差异只发生在距离树和简约树之间,在由形态和细胞学关系都很近的5个种（牡丹P.suffruticosa、矮牡丹P.jishanensis、卵叶牡丹P.qiui、紫斑牡丹P.rockii和凤丹P.o     

TOPD/FMTS: a new software to compare phylogenetic trees

SUMMARY: TOPD/FMTS has been developed to evaluate similarities and differences between phylogenetic trees. The software implements several new algorithms (including the Disagree method that returns the taxa, that disagree between two trees and the Nodal method that compares two trees using nodal information) and several previously described methods (such as the Partition method, Triplets or Quartets) to compare phylogenetic trees. One of the novelties of this software is that the FMTS (From Multiple to Single) program allows the comparison of trees that contain both orthologs and paralogs. Each option is also complemented with a randomization analysis to test the null hypothesis that the similarity between two trees is not better than chance expectation. AVAILABILITY: The Perl source code of TOPD/FMTS is available at http://genomes.urv.es/topd.     

RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models

RAxML-VI-HPC (randomized axelerated maximum likelihood for high performance computing) is a sequential and parallel program for inference of large phylogenies with maximum likelihood (ML). Low-level technical optimizations, a modification of the search algorithm, and the use of the GTR+CAT approximation as replacement for GTR+Gamma yield a program that is between 2.7 and 52 times faster than the previous version of RAxML. A large-scale performance comparison with GARLI, PHYML, IQPNNI and MrBayes on real data containing 1000 up to 6722 taxa shows that RAxML requires at least 5.6 times less main memory and yields better trees in similar times than the best competing program (GARLI) on datasets up to 2500 taxa. On datasets > or =4000 taxa it also runs 2-3 times faster than GARLI. RAxML has been parallelized with MPI to conduct parallel multiple bootstraps and inferences on distinct starting trees. The program has been used to compute ML trees on two of the largest alignments to date containing 25,057 (1463 bp) and 2182 (51,089 bp) taxa, respectively. AVAILABILITY: icwww.epfl.ch/~stamatak     

A novel algorithm and web-based tool for comparing two alternative phylogenetic trees

SUMMARY: We describe an algorithm and software tool for comparing alternative phylogenetic trees. The main application of the software is to compare phylogenies obtained using different phylogenetic methods for some fixed set of species or obtained using different gene sequences from those species. The algorithm pairs up each branch in one phylogeny with a matching branch in the second phylogeny and finds the optimum 1-to-1 map between branches in the two trees in terms of a topological score. The software enables the user to explore the corresponding mapping between the phylogenies interactively, and clearly highlights those parts of the trees that differ, both in terms of topology and branch length. AVAILABILITY: The software is implemented as a Java applet at http://www.mrc-bsu.cam.ac.uk/personal/thomas/phylo_comparison/comparison_page.html. It is also available on request from the authors.