Measuring support and finding unsupported relationships in supertrees

Extant species fail to estimate ancestral geographical ranges at older nodes in primate phylogeny

A clade's evolutionary history is shaped, in part, by geographical range expansion, sweepstakes dispersal and local extinction. A rigorous understanding of historical biogeography may therefore yield insights into macroevolutionary dynamics such as adaptive radiation. Modern historical biogeographic analyses typically fit statistical models to molecular phylogenies, but it remains unclear whether extant species provide sufficient signal or if well-sampled phylogenies of extinct and extant taxa are necessary to produce meaningful estimates of past ranges. We investigated the historical biogeography of Primates and their euarchontan relatives using a novel meta-analytical phylogeny of over 900 extant (n= 419) and extinct (n = 483) species spanning their entire evolutionary history. Ancestral range estimates for young nodes were largely congruent with those derived from molecular phylogeny. However, node age exerts a significant effect on ancestral range estimate congruence, and the probability of congruent inference dropped below 0.5 for nodes older than the late Eocene, corresponding to the origins of higher-level clades. Discordance was not observed in analyses of extinct taxa alone. Fossils are essential for robust ancestral range inference and biogeographic analyses of extant clades originating in the deep past should be viewed with scepticism without them.

A supertree of Northern European macromoths

Ecological and life-history data on the Northern European macromoth (Lepidoptera: Macroheterocera) fauna is widely available and ideal for use in answering phylogeny-based research questions: for example, in comparative biology. However, phylogenetic information for such studies lags behind. Here, as a synthesis of all currently available phylogenetic information on the group, we produce a supertree of 114 Northern European macromoth genera (in four superfamilies, with Geometroidea considered separately), providing the most complete phylogenetic picture of this fauna available to date. In doing so, we assess those parts of the phylogeny that are well resolved and those that are uncertain. Furthermore, we identify those genera for which phylogenetic information is currently too poor to include in such a supertree, or entirely absent, as targets for future work. As an aid to studies involving these genera, we provide information on their likely positions within the macromoth tree. With phylogenies playing an ever more important role in the field, this supertree should be useful in informing future ecological and evolutionary studies.

A Total-Group Phylogenetic Metatree for Cetacea and the Importance of Fossil Data in Diversification Analyses

Phylogenetic trees provide a powerful framework for testing macroevolutionary hypotheses, but it is becoming increasingly apparent that inferences derived from extant species alone can be highly misleading. Trees incorporating living and extinct taxa are are needed to address fundamental questions about the origins of diversity and disparity but it has proved challenging to generate robust, species-rich phylogenies that include large numbers of fossil taxa. As a result, most studies of diversification dynamics continue to rely on molecular phylogenies. Here, we extend and apply a recently developed meta-analytic approach for synthesizing previously published phylogenetic studies to infer a well-resolved set of species level, time-scaled phylogenetic hypotheses for extinct and extant cetaceans (whales, dolphins and allies). Our trees extend sampling from the ∼ 90 extant species to over 500 living and extinct species, and therefore allow for more robust inference of macroevolutionary dynamics. While the diversification scenarios we recover are broadly concordant with those inferred from molecular phylogenies they differ in critical ways, notably in the relative contributions of extinction and speciation rate shifts in driving rapid radiations. The metatree approach provides the most immediate route for generating higher level phylogenies of extinct taxa, and opens the door to re-evaluation of macroevolutionary hypotheses derived only from extant taxa.

A Phylogenomic Supertree of Birds

It has long been appreciated that analyses of genomic data (e.g., whole genome sequencing or sequence capture) have the potential to reveal the tree of life, but it remains challenging to move from sequence data to a clear understanding of evolutionary history, in part due to the computational challenges of phylogenetic estimation using genome-scale data. Supertree methods solve that challenge because they facilitate a divide-and-conquer approach for large-scale phylogeny inference by integrating smaller subtrees in a computationally efficient manner. Here, we combined information from sequence capture and whole-genome phylogenies using supertree methods. However, the available phylogenomic trees had limited overlap so we used taxon-rich (but not phylogenomic) megaphylogenies to weave them together. This allowed us to construct a phylogenomic supertree, with support values, that included 707 bird species (~7% of avian species diversity). We estimated branch lengths using mitochondrial sequence data and we used these branch lengths to estimate divergence times. Our time-calibrated supertree supports radiation of all three major avian clades (Palaeognathae, Galloanseres, and Neoaves) near the Cretaceous-Paleogene (K-Pg) boundary. The approach we used will permit the continued addition of taxa to this supertree as new phylogenomic data are published, and it could be applied to other taxa as well.

Phylogenetic supertree and functional trait database for all extant parrots

We present a complete dataset from the literature on functional traits including morphological measurements, dietary information, foraging strategy, and foraging location for all 398 extant species of parrots. The morphological measurements include: mass, total length, wing chord, culmen length, tarsus length, and tail length. The diet data describe whether each species is known to consume particular food items (e.g. nectar, berries, and carrion), foraging strategy data describes how each species captures or accesses food, and foraging location data describe the habitat from which each species finds food (e.g. ground, canopy, and subcanopy). We also present a time-calibrated phylogenetic supertree that contains all 398 extant species as well as 15 extinct species (413 total species). These data are hosted on the Figshare data depository (https://figshare.com/s/6cdf8cf00793deab7ba6).

Bad Clade Deletion Supertrees: A Fast and Accurate Supertree Algorithm

Supertree methods merge a set of overlapping phylogenetic trees into a supertree containing all taxa of the input trees. The challenge in supertree reconstruction is the way of dealing with conflicting information in the input trees. Many different algorithms for different objective functions have been suggested to resolve these conflicts. In particular, there exist methods based on encoding the source trees in a matrix, where the supertree is constructed applying a local search heuristic to optimize the respective objective function. We present a novel heuristic supertree algorithm called Bad Clade Deletion (BCD) supertrees. It uses minimum cuts to delete a locally minimal number of columns from such a matrix representation so that it is compatible. This is the complement problem to Matrix Representation with Compatibility (Maximum Split Fit). Our algorithm has guaranteed polynomial worst-case running time and performs swiftly in practice. Different from local search heuristics, it guarantees to return the directed perfect phylogeny for the input matrix, corresponding to the parent tree of the input trees, if one exists. Comparing supertrees to model trees for simulated data, BCD shows a better accuracy (F1 score) than the state-of-the-art algorithms SuperFine (up to 3%) and Matrix Representation with Parsimony (up to 7%); at the same time, BCD is up to 7 times faster than SuperFine, and up to 600 times faster than Matrix Representation with Parsimony. Finally, using the BCD supertree as a starting tree for a combined Maximum Likelihood analysis using RAxML, we reach significantly improved accuracy (1% higher F1 score) and running time (1.7-fold speedup).

Horizontal gene flow from Eubacteria to Archaebacteria and what it means for our understanding of eukaryogenesis

The origin of the eukaryotic cell is considered one of the major evolutionary transitions in the history of life. Current evidence strongly supports a scenario of eukaryotic origin in which two prokaryotes, an archaebacterial host and an α-proteobacterium (the free-living ancestor of the mitochondrion), entered a stable symbiotic relationship. The establishment of this relationship was associated with a process of chimerization, whereby a large number of genes from the α-proteobacterial symbiont were transferred to the host nucleus. A general framework allowing the conceptualization of eukaryogenesis from a genomic perspective has long been lacking. Recent studies suggest that the origins of several archaebacterial phyla were coincident with massive imports of eubacterial genes. Although this does not indicate that these phyla originated through the same process that led to the origin of Eukaryota, it suggests that Archaebacteria might have had a general propensity to integrate into their genomes large amounts of eubacterial DNA. We suggest that this propensity provides a framework in which eukaryogenesis can be understood and studied in the light of archaebacterial ecology. We applied a recently developed supertree method to a genomic dataset composed of 392 eubacterial and 51 archaebacterial genera to test whether large numbers of genes flowing from Eubacteria are indeed coincident with the origin of major archaebacterial clades. In addition, we identified two potential large-scale transfers of uncertain directionality at the base of the archaebacterial tree. Our results are consistent with previous findings and seem to indicate that eubacterial gene imports (particularly from δ-Proteobacteria, Clostridia and Actinobacteria) were an important factor in archaebacterial history. Archaebacteria seem to have long relied on Eubacteria as a source of genetic diversity, and while the precise mechanism that allowed these imports is unknown, we suggest that our results support the view that processes comparable to those through which eukaryotes emerged might have been common in archaebacterial history.

Why should we investigate the morphological disparity of plant clades?

BACKGROUND

Disparity refers to the morphological variation in a sample of taxa, and is distinct from diversity or taxonomic richness. Diversity and disparity are fundamentally decoupled; many groups attain high levels of disparity early in their evolution, while diversity is still comparatively low. Diversity may subsequently increase even in the face of static or declining disparity by increasingly fine sub-division of morphological 'design' space (morphospace). Many animal clades reached high levels of disparity early in their evolution, but there have been few comparable studies of plant clades, despite their profound ecological and evolutionary importance. This study offers a prospective and some preliminary macroevolutionary analyses.

METHODS

Classical morphometric methods are most suitable when there is reasonable conservation of form, but lose traction where morphological differences become greater (e.g. in comparisons across higher taxa). Discrete character matrices offer one means to compare a greater diversity of forms. This study explores morphospaces derived from eight discrete data sets for major plant clades, and discusses their macroevolutionary implications.

KEY RESULTS

Most of the plant clades in this study show initial, high levels of disparity that approach or attain the maximum levels reached subsequently. These plant clades are characterized by an initial phase of evolution during which most regions of their empirical morphospaces are colonized. Angiosperms, palms, pines and ferns show remarkably little variation in disparity through time. Conifers furnish the most marked exception, appearing at relatively low disparity in the latest Carboniferous, before expanding incrementally with the radiation of successive, tightly clustered constituent sub-clades.

CONCLUSIONS

Many cladistic data sets can be repurposed for investigating the morphological disparity of plant clades through time, and offer insights that are complementary to more focused morphometric studies. The unique structural and ecological features of plants make them ideally suited to investigating intrinsic and extrinsic constraints on disparity.

Elevated Extinction Rates as a Trigger for Diversification Rate Shifts: Early Amniotes as a Case Study

Tree shape analyses are frequently used to infer the location of shifts in diversification rate within the Tree of Life. Many studies have supported a causal relationship between shifts and temporally coincident events such as the evolution of “key innovations”. However, the evidence for such relationships is circumstantial. We investigated patterns of diversification during the early evolution of Amniota from the Carboniferous to the Triassic, subjecting a new supertree to analyses of tree balance in order to infer the timing and location of diversification shifts. We investigated how uneven origination and extinction rates drive diversification shifts, and use two case studies (herbivory and an aquatic lifestyle) to examine whether shifts tend to be contemporaneous with evolutionary novelties. Shifts within amniotes tend to occur during periods of elevated extinction, with mass extinctions coinciding with numerous and larger shifts. Diversification shifts occurring in clades that possess evolutionary innovations do not coincide temporally with the appearance of those innovations, but are instead deferred to periods of high extinction rate. We suggest such innovations did not cause increases in the rate of cladogenesis, but allowed clades to survive extinction events. We highlight the importance of examining general patterns of diversification before interpreting specific shifts.

Towards a Supertree of Arthropoda: A Species-Level Supertree of the Spiny, Slipper and Coral Lobsters (Decapoda: Achelata)

While supertrees have been built for many vertebrate groups (notably birds, mammals and dinosaurs), invertebrates have attracted relatively little attention. The paucity of supertrees of arthropods is particularly surprising given their economic and ecological importance, as well as their overwhelming contribution to biodiversity. The absence of comprehensive archives of machine-readable source trees, coupled with the need for software implementing repeatable protocols for managing them, has undoubtedly impeded progress. Here we present a supertree of Achelata (spiny, slipper and coral lobsters) as a proof of concept, constructed using new supertree specific software (the Supertree Toolkit; STK) and following a published protocol. We also introduce a new resource for archiving and managing published source trees. Our supertree of Achelata is synthesised from morphological and molecular source trees, and represents the most complete species-level tree of the group to date. Our findings are consistent with recent taxonomic treatments, confirming the validity of just two families: Palinuridae and Scyllaridae; Synaxidae were resolved within Palinuridae. Monophyletic Silentes and Stridentes lineages are recovered within Palinuridae, and all sub-families within Scyllaridae are found to be monophyletic with the exception of Ibacinae. We demonstrate the feasibility of building larger supertrees of arthropods, with the ultimate objective of building a complete species-level phylogeny for the entire phylum using a divide and conquer strategy.

Synthesis of phylogeny and taxonomy into a comprehensive tree of life

Reconstructing the phylogenetic relationships that unite all lineages (the tree of life) is a grand challenge. The paucity of homologous character data across disparately related lineages currently renders direct phylogenetic inference untenable. To reconstruct a comprehensive tree of life, we therefore synthesized published phylogenies, together with taxonomic classifications for taxa never incorporated into a phylogeny. We present a draft tree containing 2.3 million tips-the Open Tree of Life. Realization of this tree required the assembly of two additional community resources: (i) a comprehensive global reference taxonomy and (ii) a database of published phylogenetic trees mapped to this taxonomy. Our open source framework facilitates community comment and contribution, enabling the tree to be continuously updated when new phylogenetic and taxonomic data become digitally available. Although data coverage and phylogenetic conflict across the Open Tree of Life illuminate gaps in both the underlying data available for phylogenetic reconstruction and the publication of trees as digital objects, the tree provides a compelling starting point for community contribution. This comprehensive tree will fuel fundamental research on the nature of biological diversity, ultimately providing up-to-date phylogenies for downstream applications in comparative biology, ecology, conservation biology, climate change, agriculture, and genomics.

Implementing and testing Bayesian and maximum-likelihood supertree methods in phylogenetics

Since their advent, supertrees have been increasingly used in large-scale evolutionary studies requiring a phylogenetic framework and substantial efforts have been devoted to developing a wide variety of supertree methods (SMs). Recent advances in supertree theory have allowed the implementation of maximum likelihood (ML) and Bayesian SMs, based on using an exponential distribution to model incongruence between input trees and the supertree. Such approaches are expected to have advantages over commonly used non-parametric SMs, e.g. matrix representation with parsimony (MRP). We investigated new implementations of ML and Bayesian SMs and compared these with some currently available alternative approaches. Comparisons include hypothetical examples previously used to investigate biases of SMs with respect to input tree shape and size, and empirical studies based either on trees harvested from the literature or on trees inferred from phylogenomic scale data. Our results provide no evidence of size or shape biases and demonstrate that the Bayesian method is a viable alternative to MRP and other non-parametric methods. Computation of input tree likelihoods allows the adoption of standard tests of tree topologies (e.g. the approximately unbiased test). The Bayesian approach is particularly useful in providing support values for supertree clades in the form of posterior probabilities.

Reweaving the tapestry: a supertree of birds

Our knowledge of the avian tree of life remains uncertain, particularly at deeper levels due to the rapid diversification early in their evolutionary history. They are the most abundant land vertebrate on the planet and have been of great historical interest to systematists. Birds are also economically and ecologically important and as a result are intensively studied, yet despite their importance and interest to humans around 13% of taxa currently on the endangered species list perhaps as a result of human activity. Despite all this no comprehensive phylogeny that includes both extinct and extant species currently exists. Here we present a species-level supertree, constructed using the Matrix Representation with Parsimony method, of Aves containing approximately two thirds of all species from nearly 1000 source phylogenies with a broad taxonomic coverage. The source data for the tree were collected and processed according to a strict protocol to ensure robust and accurate data handling. The resulting tree topology is largely consistent with molecular hypotheses of avian phylogeny. We identify areas that are in broad agreement with current views on avian systematics and also those that require further work. We also highlight the need for leaf-based support measures to enable the identification of rogue taxa in supertrees. This is a first attempt at a supertree of both extinct and extant birds, it is not intended to be utilised in an overhaul of avian systematics or as a basis for taxonomic re-classification but provides a strong basis on which to base further studies on macroevolution, conservation, biodiversity, comparative biology and character evolution, in particular the inclusion of fossils will allow the study of bird evolution and diversification throughout deep time.

Analyzing and synthesizing phylogenies using tree alignment graphs

Phylogenetic trees are used to analyze and visualize evolution. However, trees can be imperfect datatypes when summarizing multiple trees. This is especially problematic when accommodating for biological phenomena such as horizontal gene transfer, incomplete lineage sorting, and hybridization, as well as topological conflict between datasets. Additionally, researchers may want to combine information from sets of trees that have partially overlapping taxon sets. To address the problem of analyzing sets of trees with conflicting relationships and partially overlapping taxon sets, we introduce methods for aligning, synthesizing and analyzing rooted phylogenetic trees within a graph, called a tree alignment graph (TAG). The TAG can be queried and analyzed to explore uncertainty and conflict. It can also be synthesized to construct trees, presenting an alternative to supertrees approaches. We demonstrate these methods with two empirical datasets. In order to explore uncertainty, we constructed a TAG of the bootstrap trees from the Angiosperm Tree of Life project. Analysis of the resulting graph demonstrates that areas of the dataset that are unresolved in majority-rule consensus tree analyses can be understood in more detail within the context of a graph structure, using measures incorporating node degree and adjacency support. As an exercise in synthesis (i.e., summarization of a TAG constructed from the alignment trees), we also construct a TAG consisting of the taxonomy and source trees from a recent comprehensive bird study. We synthesized this graph into a tree that can be reconstructed in a repeatable fashion and where the underlying source information can be updated. The methods presented here are tractable for large scale analyses and serve as a basis for an alternative to consensus tree and supertree methods. Furthermore, the exploration of these graphs can expose structures and patterns within the dataset that are otherwise difficult to observe.

Updating the evolutionary history of Carnivora (Mammalia): a new species-level supertree complete with divergence time estimates

BACKGROUND

Although it has proven to be an important foundation for investigations of carnivoran ecology, biology and evolution, the complete species-level supertree for Carnivora of Bininda-Emonds et al. is showing its age. Additional, largely molecular sequence data are now available for many species and the advancement of computer technology means that many of the limitations of the original analysis can now be avoided. We therefore sought to provide an updated estimate of the phylogenetic relationships within all extant Carnivora, again using supertree analysis to be able to analyze as much of the global phylogenetic database for the group as possible.

RESULTS

In total, 188 source trees were combined, representing 114 trees from the literature together with 74 newly constructed gene trees derived from nearly 45,000 bp of sequence data from GenBank. The greater availability of sequence data means that the new supertree is almost completely resolved and also better reflects current phylogenetic opinion (for example, supporting a monophyletic Mephitidae, Eupleridae and Prionodontidae; placing Nandinia binotata as sister to the remaining Feliformia). Following an initial rapid radiation, diversification rate analyses indicate a downturn in the net speciation rate within the past three million years as well as a possible increase some 18.0 million years ago; numerous diversification rate shifts within the order were also identified.

CONCLUSIONS

Together, the two carnivore supertrees remain the only complete phylogenetic estimates for all extant species and the new supertree, like the old one, will form a key tool in helping us to further understand the biology of this charismatic group of carnivores.

Fossil gaps inferred from phylogenies alter the apparent nature of diversification in dragonflies and their relatives

BACKGROUND

The fossil record has suggested that clade growth may differ in marine and terrestrial taxa, supporting equilibrial models in the former and expansionist models in the latter. However, incomplete sampling may bias findings based on fossil data alone. To attempt to correct for such bias, we assemble phylogenetic supertrees on one of the oldest clades of insects, the Odonatoidea (dragonflies, damselflies and their extinct relatives), using MRP and MRC. We use the trees to determine when, and in what clades, changes in taxonomic richness have occurred. We then test whether equilibrial or expansionist models are supported by fossil data alone, and whether findings differ when phylogenetic information is used to infer gaps in the fossil record.

RESULTS

There is broad agreement in family-level relationships between both supertrees, though with some uncertainty along the backbone of the tree regarding dragonflies (Anisoptera). "Anisozygoptera" are shown to be paraphyletic when fossil information is taken into account. In both trees, decreases in net diversification are associated with species-poor extant families (Neopetaliidae, Hemiphlebiidae), and an upshift is associated with Calopterygidae + Polythoridae. When ghost ranges are inferred from the fossil record, many families are shown to have much earlier origination dates. In a phylogenetic context, the number of family-level lineages is shown to be up to twice as high as the fossil record alone suggests through the Cretaceous and Cenozoic, and a logistic increase in richness is detected in contrast to an exponential increase indicated by fossils alone.

CONCLUSIONS

Our analysis supports the notion that taxa, which appear to have diversified exponentially using fossil data, may in fact have diversified more logistically. This in turn suggests that one of the major apparent differences between the marine and terrestrial fossil record may simply be an artifact of incomplete sampling. Our results also support previous notions that adult colouration plays an important role in odonate radiation, and that Anisozygoptera should be grouped in a single inclusive taxon with Anisoptera, separate from Zygoptera.

Split-based computation of majority-rule supertrees

Background

Supertree methods combine overlapping input trees into a larger supertree. Here, I consider split-based supertree methods that first extract the split information of the input trees and subsequently combine this split information into a phylogeny. Well known split-based supertree methods are matrix representation with parsimony and matrix representation with compatibility. Combining input trees on the same taxon set, as in the consensus setting, is a well-studied task and it is thus desirable to generalize consensus methods to supertree methods.

Results

Here, three variants of majority-rule (MR) supertrees that generalize majority-rule consensus trees are investigated. I provide simple formulas for computing the respective score for bifurcating input- and supertrees. These score computations, together with a heuristic tree search minmizing the scores, were implemented in the python program PluMiST (Plus- and Minus SuperTrees) available from http://www.cibiv.at/software/plumist. The different MR methods were tested by simulation and on real data sets. The search heuristic was successful in combining compatible input trees. When combining incompatible input trees, especially one variant, MR(-) supertrees, performed well.

Conclusions

The presented framework allows for an efficient score computation of three majority-rule supertree variants and input trees. I combined the score computation with a heuristic search over the supertree space. The implementation was tested by simulation and on real data sets and showed promising results. Especially the MR(-) variant seems to be a reasonable score for supertree reconstruction. Generalizing these computations to multifurcating trees is an open problem, which may be tackled using this framework.

Accuracy of phylogeny reconstruction methods combining overlapping gene data sets

Background

The availability of many gene alignments with overlapping taxon sets raises the question of which strategy is the best to infer species phylogenies from multiple gene information. Methods and programs abound that use the gene alignment in different ways to reconstruct the species tree. In particular, different methods combine the original data at different points along the way from the underlying sequences to the final tree. Accordingly, they are classified into superalignment, supertree and medium-level approaches. Here, we present a simulation study to compare different methods from each of these three approaches.

Results

We observe that superalignment methods usually outperform the other approaches over a wide range of parameters including sparse data and gene-specific evolutionary parameters. In the presence of high incongruency among gene trees, however, other combination methods show better performance than the superalignment approach. Surprisingly, some supertree and medium-level methods exhibit, on average, worse results than a single gene phylogeny with complete taxon information.

Conclusions

For some methods, using the reconstructed gene tree as an estimation of the species tree is superior to the combination of incomplete information. Superalignment usually performs best since it is less susceptible to stochastic error. Supertree methods can outperform superalignment in the presence of gene-tree conflict.

Comparative performance of supertree algorithms in large data sets using the soapberry family (Sapindaceae) as a case study

For the last 2 decades, supertree reconstruction has been an active field of research and has seen the development of a large number of major algorithms. Because of the growing popularity of the supertree methods, it has become necessary to evaluate the performance of these algorithms to determine which are the best options (especially with regard to the supermatrix approach that is widely used). In this study, seven of the most commonly used supertree methods are investigated by using a large empirical data set (in terms of number of taxa and molecular markers) from the worldwide flowering plant family Sapindaceae. Supertree methods were evaluated using several criteria: similarity of the supertrees with the input trees, similarity between the supertrees and the total evidence tree, level of resolution of the supertree and computational time required by the algorithm. Additional analyses were also conducted on a reduced data set to test if the performance levels were affected by the heuristic searches rather than the algorithms themselves. Based on our results, two main groups of supertree methods were identified: on one hand, the matrix representation with parsimony (MRP), MinFlip, and MinCut methods performed well according to our criteria, whereas the average consensus, split fit, and most similar supertree methods showed a poorer performance or at least did not behave the same way as the total evidence tree. Results for the super distance matrix, that is, the most recent approach tested here, were promising with at least one derived method performing as well as MRP, MinFlip, and MinCut. The output of each method was only slightly improved when applied to the reduced data set, suggesting a correct behavior of the heuristic searches and a relatively low sensitivity of the algorithms to data set sizes and missing data. Results also showed that the MRP analyses could reach a high level of quality even when using a simple heuristic search strategy, with the exception of MRP with Purvis coding scheme and reversible parsimony. The future of supertrees lies in the implementation of a standardized heuristic search for all methods and the increase in computing power to handle large data sets. The latter would prove to be particularly useful for promising approaches such as the maximum quartet fit method that yet requires substantial computing power.

SuperTriplets: a triplet-based supertree approach to phylogenomics

MOTIVATION

Phylogenetic tree-building methods use molecular data to represent the evolutionary history of genes and taxa. A recurrent problem is to reconcile the various phylogenies built from different genomic sequences into a single one. This task is generally conducted by a two-step approach whereby a binary representation of the initial trees is first inferred and then a maximum parsimony (MP) analysis is performed on it. This binary representation uses a decomposition of all source trees that is usually based on clades, but that can also be based on triplets or quartets. The relative performances of these representations have been discussed but are difficult to assess since both are limited to relatively small datasets.

RESULTS

This article focuses on the triplet-based representation of source trees. We first recall how, using this representation, the parsimony analysis is related to the median tree notion. We then introduce SuperTriplets, a new algorithm that is specially designed to optimize this alternative formulation of the MP criterion. The method avoids several practical limitations of the triplet-based binary matrix representation, making it useful to deal with large datasets. When the correct resolution of every triplet appears more often than the incorrect ones in source trees, SuperTriplets warrants to reconstruct the correct phylogeny. Both simulations and a case study on mammalian phylogenomics confirm the advantages of this approach. In both cases, SuperTriplets tends to propose less resolved but more reliable supertrees than those inferred using M(atrix) Representation with Parsimony.

AVAILABILITY

Online and JAVA standalone versions of SuperTriplets are available at http://www.supertriplets.univ-montp2.fr/.

Many hexapod groups originated earlier and withstood extinction events better than previously realized: inferences from supertrees

Comprising over half of all described species, the hexapods are central to understanding the evolution of global biodiversity. Direct fossil evidence suggests that new hexapod orders continued to originate from the Jurassic onwards, and diversity is presently higher than ever. Previous studies also suggest that several shifts in net diversification rate have occurred at higher taxonomic levels. However, their inferred timing is phylogeny dependent. We re-examine these issues using the supertree approach to provide, to our knowledge, the first composite estimates of hexapod order-level phylogeny. The Purvis matrix representation with parsimony method provides the most optimal supertree, but alternative methods are considered. Inferring ghost ranges shows richness of terminal lineages in the order-level phylogeny to peak just before the end-Permian extinction, rather than the present day, indicating that at least 11 more lineages survived this extinction than implied by fossils alone. The major upshift in diversification is associated with the origin of wings/wing folding and for the first time, to our knowledge, significant downshifts are shown associated with the origin of species-poor taxa (e.g. Neuropterida, Zoraptera). Polyneopteran phylogeny, especially the position of Zoraptera, remains important resolve because this influences findings regarding shifts in diversification. Our study shows how combining fossil with phylogenetic information can improve macroevolutionary inferences.

The origins of species richness in the Hymenoptera: insights from a family-level supertree

BACKGROUND

The order Hymenoptera (bees, ants, wasps, sawflies) contains about eight percent of all described species, but no analytical studies have addressed the origins of this richness at family-level or above. To investigate which major subtaxa experienced significant shifts in diversification, we assembled a family-level phylogeny of the Hymenoptera using supertree methods. We used sister-group species-richness comparisons to infer the phylogenetic position of shifts in diversification.

RESULTS

The supertrees most supported by the underlying input trees are produced using matrix representation with compatibility (MRC) (from an all-in and a compartmentalised analysis). Whilst relationships at the tips of the tree tend to be well supported, those along the backbone of the tree (e.g. between Parasitica superfamilies) are generally not. Ten significant shifts in diversification (six positive and four negative) are found common to both MRC supertrees. The Apocrita (wasps, ants, bees) experienced a positive shift at their origin accounting for approximately 4,000 species. Within Apocrita other positive shifts include the Vespoidea (vespoid wasps/ants containing 24,000 spp.), Anthophila + Sphecidae (bees/thread-waisted wasps; 22,000 spp.), Bethylidae + Chrysididae (bethylid/cuckoo wasps; 5,200 spp.), Dryinidae (dryinid wasps; 1,100 spp.), and Proctotrupidae (proctotrupid wasps; 310 spp.). Four relatively species-poor families (Stenotritidae, Anaxyelidae, Blasticotomidae, Xyelidae) have undergone negative shifts. There are some two-way shifts in diversification where sister taxa have undergone shifts in opposite directions.

CONCLUSIONS

Our results suggest that numerous phylogenetically distinctive radiations contribute to the richness of large clades. They also suggest that evolutionary events restricting the subsequent richness of large clades are common. Problematic phylogenetic issues in the Hymenoptera are identified, relating especially to superfamily validity (e.g. "Proctotrupoidea", "Mymarommatoidea"), and deeper apocritan relationships. Our results should stimulate new functional studies on the causes of the diversification shifts we have identified. Possible drivers highlighted for specific adaptive radiations include key anatomical innovations, the exploitation of rich host groups, and associations with angiosperms. Low richness may have evolved as a result of geographical isolation, specialised ecological niches, and habitat loss or competition.

Robinson-Foulds supertrees

BACKGROUND

Supertree methods synthesize collections of small phylogenetic trees with incomplete taxon overlap into comprehensive trees, or supertrees, that include all taxa found in the input trees. Supertree methods based on the well established Robinson-Foulds (RF) distance have the potential to build supertrees that retain much information from the input trees. Specifically, the RF supertree problem seeks a binary supertree that minimizes the sum of the RF distances from the supertree to the input trees. Thus, an RF supertree is a supertree that is consistent with the largest number of clusters (or clades) from the input trees.

RESULTS

We introduce efficient, local search based, hill-climbing heuristics for the intrinsically hard RF supertree problem on rooted trees. These heuristics use novel non-trivial algorithms for the SPR and TBR local search problems which improve on the time complexity of the best known (naïve) solutions by a factor of Theta(n) and Theta(n2) respectively (where n is the number of taxa, or leaves, in the supertree). We use an implementation of our new algorithms to examine the performance of the RF supertree method and compare it to matrix representation with parsimony (MRP) and the triplet supertree method using four supertree data sets. Not only did our RF heuristic provide fast estimates of RF supertrees in all data sets, but the RF supertrees also retained more of the information from the input trees (based on the RF distance) than the other supertree methods.

CONCLUSIONS

Our heuristics for the RF supertree problem, based on our new local search algorithms, make it possible for the first time to estimate large supertrees by directly optimizing the RF distance from rooted input trees to the supertrees. This provides a new and fast method to build accurate supertrees. RF supertrees may also be useful for estimating majority-rule(-) supertrees, which are a generalization of majority-rule consensus trees.

Constructing majority-rule supertrees

BACKGROUND

Supertree methods combine the phylogenetic information from multiple partially-overlapping trees into a larger phylogenetic tree called a supertree. Several supertree construction methods have been proposed to date, but most of these are not designed with any specific properties in mind. Recently, Cotton and Wilkinson proposed extensions of the majority-rule consensus tree method to the supertree setting that inherit many of the appealing properties of the former.

RESULTS

We study a variant of one of Cotton and Wilkinson's methods, called majority-rule (+) supertrees. After proving that a key underlying problem for constructing majority-rule (+) supertrees is NP-hard, we develop a polynomial-size exact integer linear programming formulation of the problem. We then present a data reduction heuristic that identifies smaller subproblems that can be solved independently. While this technique is not guaranteed to produce optimal solutions, it can achieve substantial problem-size reduction. Finally, we report on a computational study of our approach on various real data sets, including the 121-taxon, 7-tree Seabirds data set of Kennedy and Page.

CONCLUSIONS

The results indicate that our exact method is computationally feasible for moderately large inputs. For larger inputs, our data reduction heuristic makes it feasible to tackle problems that are well beyond the range of the basic integer programming approach. Comparisons between the results obtained by our heuristic and exact solutions indicate that the heuristic produces good answers. Our results also suggest that the majority-rule (+) approach, in both its basic form and with data reduction, yields biologically meaningful phylogenies.

Prokaryotic evolution and the tree of life are two different things

BACKGROUND

The concept of a tree of life is prevalent in the evolutionary literature. It stems from attempting to obtain a grand unified natural system that reflects a recurrent process of species and lineage splittings for all forms of life. Traditionally, the discipline of systematics operates in a similar hierarchy of bifurcating (sometimes multifurcating) categories. The assumption of a universal tree of life hinges upon the process of evolution being tree-like throughout all forms of life and all of biological time. In multicellular eukaryotes, the molecular mechanisms and species-level population genetics of variation do indeed mainly cause a tree-like structure over time. In prokaryotes, they do not. Prokaryotic evolution and the tree of life are two different things, and we need to treat them as such, rather than extrapolating from macroscopic life to prokaryotes. In the following we will consider this circumstance from philosophical, scientific, and epistemological perspectives, surmising that phylogeny opted for a single model as a holdover from the Modern Synthesis of evolution.

RESULTS

It was far easier to envision and defend the concept of a universal tree of life before we had data from genomes. But the belief that prokaryotes are related by such a tree has now become stronger than the data to support it. The monistic concept of a single universal tree of life appears, in the face of genome data, increasingly obsolete. This traditional model to describe evolution is no longer the most scientifically productive position to hold, because of the plurality of evolutionary patterns and mechanisms involved. Forcing a single bifurcating scheme onto prokaryotic evolution disregards the non-tree-like nature of natural variation among prokaryotes and accounts for only a minority of observations from genomes.

CONCLUSION

Prokaryotic evolution and the tree of life are two different things. Hence we will briefly set out alternative models to the tree of life to study their evolution. Ultimately, the plurality of evolutionary patterns and mechanisms involved, such as the discontinuity of the process of evolution across the prokaryote-eukaryote divide, summons forth a pluralistic approach to studying evolution.

REVIEWERS

This article was reviewed by Ford Doolittle, John Logsdon and Nicolas Galtier.

Eusociality and the success of the termites: insights from a supertree of dictyopteran families

Sociality in insects may negatively impact on species richness. We tested whether termites have experienced shifts in diversification rates through time. Supertree methods were used to synthesize family-level relationships within termites, cockroaches and mantids. A deep positive shift in diversification rate is found within termites, but not in the cockroaches from which they evolved. The shift is responsible for most of their extant species richness suggesting that eusociality is not necessarily detrimental to species richness, and may sometimes have a positive effect. Mechanistic studies of speciation and extinction in eusocial insects are advocated.

Phylogenetic analysis of sexual systems in Inuleae (Asteraceae)

From an ancestor with bisexual flowers, plants with unisexual flowers, or even unisexual individuals have evolved in different lineages of angiosperms. The Asteraceae tribe Inuleae includes hermaphroditic, monoecious, dioecious, and gynomonoecious species. Gynomonoecy, the sexual system in which female and bisexual flowers occur on the same plant, is prevalent in the Asteraceae. We inferred one large gene phylogeny (ndhF) and two supertrees to investigate whether gynomonoecy was a stage in the evolution from hermaphroditism to monoecy. We identified transitions in sexual system evolution using the stochastic character mapping method. From gynomonoecious ancestors, both hermaphroditic and monoecious descendants have evolved. Gynomonoecy was not restricted to a stage in the evolution toward monoecy because the number of transitions and the rate of change from monoecy to gynomonoecy were much higher than the opposite. We also investigated one hypothesized association among female flowers and the development of a petaloid ray as an explanation of gynomonoecy maintenance in Asteraceae. We found that peripheral female flowers and petaloid rays were phylogenetically correlated. However, empirical evidence shows that a causal relationship between these traits is not clear.

Dinosaurs and the Cretaceous Terrestrial Revolution

The observed diversity of dinosaurs reached its highest peak during the mid- and Late Cretaceous, the 50 Myr that preceded their extinction, and yet this explosion of dinosaur diversity may be explained largely by sampling bias. It has long been debated whether dinosaurs were part of the Cretaceous Terrestrial Revolution (KTR), from 125-80 Myr ago, when flowering plants, herbivorous and social insects, squamates, birds and mammals all underwent a rapid expansion. Although an apparent explosion of dinosaur diversity occurred in the mid-Cretaceous, coinciding with the emergence of new groups (e.g. neoceratopsians, ankylosaurid ankylosaurs, hadrosaurids and pachycephalosaurs), results from the first quantitative study of diversification applied to a new supertree of dinosaurs show that this apparent burst in dinosaurian diversity in the last 18 Myr of the Cretaceous is a sampling artefact. Indeed, major diversification shifts occurred largely in the first one-third of the group's history. Despite the appearance of new clades of medium to large herbivores and carnivores later in dinosaur history, these new originations do not correspond to significant diversification shifts. Instead, the overall geometry of the Cretaceous part of the dinosaur tree does not depart from the null hypothesis of an equal rates model of lineage branching. Furthermore, we conclude that dinosaurs did not experience a progressive decline at the end of the Cretaceous, nor was their evolution driven directly by the KTR.

A supertree of temnospondyli: cladogenetic patterns in the most species-rich group of early tetrapods

As the most diverse group of early tetrapods, temnospondyls provide a unique opportunity to investigate cladogenetic patterns among basal limbed vertebrates. We present five species-level supertrees for temnospondyls, built using a variety of methods. The standard MRP majority rule consensus including minority components shows slightly greater resolution than other supertrees, and its shape matches well several currently accepted hypotheses of higher-level phylogeny for temnospondyls as a whole. Also, its node support is higher than those of other supertrees (except the combined standard plus Purvis MRP supertree). We explore the distribution of significant as well as informative changes (shifts) in branch splitting employing the standard MRP supertree as a reference, and discuss the temporal distribution of changes in time-sliced, pruned trees derived from this supertree. Also, we analyse those shifts that are most relevant to the end-Permian mass extinction. For the Palaeozoic, shifts occur almost invariably along branches that connect major Palaeozoic groups. By contrast, shifts in the Mesozoic occur predominantly within major groups. Numerous shifts bracket narrowly the end-Permian extinction, indicating not only rapid recovery and extensive diversification of temnospondyls over a short time period after the extinction event (possibly less than half a million years), but also the role of intense cladogenesis in the late part of the Permian (although this was counteracted by numerous 'background' extinctions).

Majority-rule supertrees

Most supertree methods proposed to date are essentially ad hoc, rather than designed with particular properties in mind. Although the supertree problem remains difficult, one promising avenue is to develop from better understood consensus methods to the more general supertree setting. Here, we generalize the widely used majority-rule consensus method to the supertree setting. The majority-rule consensus tree is the strict consensus of the median trees under the symmetric-difference metric, so we can generalize the consensus method by generalizing this metric to trees with differing leaf sets. There are two different natural generalizations, based on pruning or grafting leaves to produce comparable trees, and these two generalizations produce two different, but related, majority-rule supertree methods.

Supertrees Disentangle the Chimerical Origin of Eukaryotic Genomes

Eukaryotes are traditionally considered to be one of the three natural divisions of the tree of life and the sister group of the Archaebacteria. However, eukaryotic genomes are replete with genes of eubacterial ancestry, and more than 20 mutually incompatible hypotheses have been proposed to account for eukaryote origins. Here we test the predictions of these hypotheses using a novel supertree-based phylogenetic signal-stripping method, and recover supertrees of life based on phylogenies for up to 5,741 single gene families distributed across 185 genomes. Using our signal-stripping method, we show that there are three distinct phylogenetic signals in eukaryotic genomes. In order of strength, these link eukaryotes with the Cyanobacteria, the Proteobacteria, and the Thermoplasmatales, an archaebacterial (euryarchaeotes) group. These signals correspond to distinct symbiotic partners involved in eukaryote evolution: plastids, mitochondria, and the elusive host lineage. According to our whole-genome data, eukaryotes are hardly the sister group of the Archaebacteria, because up to 83% of eukaryotic genes with a prokaryotic homolog have eubacterial, not archaebacterial, origins. The results reject all but two of the current hypotheses for the origin of eukaryotes: those assuming a sulfur-dependent or hydrogen-dependent syntrophy for the origin of mitochondria.

Imputing supertrees and supernetworks from quartets

Inferring species phylogenies is an important part of understanding molecular evolution. Even so, it is well known that an accurate phylogenetic tree reconstruction for a single gene does not always necessarily correspond to the species phylogeny. One commonly accepted strategy to cope with this problem is to sequence many genes; the way in which to analyze the resulting collection of genes is somewhat more contentious. Supermatrix and supertree methods can be used, although these can suppress conflicts arising from true differences in the gene trees caused by processes such as lineage sorting, horizontal gene transfer, or gene duplication and loss. In 2004, Huson et al. (IEEE/ACM Trans. Comput. Biol. Bioinformatics 1:151-158) presented the Z-closure method that can circumvent this problem by generating a supernetwork as opposed to a supertree. Here we present an alternative way for generating supernetworks called Q-imputation. In particular, we describe a method that uses quartet information to add missing taxa into gene trees. The resulting trees are subsequently used to generate consensus networks, networks that generalize strict and majority-rule consensus trees. Through simulations and application to real data sets, we compare Q-imputation to the matrix representation with parsimony (MRP) supertree method and Z-closure, and demonstrate that it provides a useful complementary tool.

Increasing data transparency and estimating phylogenetic uncertainty in supertrees: Approaches using nonparametric bootstrapping

The estimation of ever larger phylogenies requires consideration of alternative inference strategies, including divide-and-conquer approaches that decompose the global inference problem to a set of smaller, more manageable component problems. A prominent locus of research in this area is the development of supertree methods, which estimate a composite tree by combining a set of partially overlapping component topologies. Although promising, the use of component tree topologies as the primary data dissociates supertrees from complexities within the underling character data and complicates the evaluation of phylogenetic uncertainty. We address these issues by exploring three approaches that variously incorporate nonparametric bootstrapping into a common supertree estimation algorithm (matrix representation with parsimony, although any algorithm might be used), including bootstrap-weighting, source-tree bootstrapping, and hierarchical bootstrapping. We illustrate these procedures by means of hypothetical and empirical examples. Our preliminary experiments suggest that these methods have the potential to improve the correspondence of supertree estimates to those derived from simultaneous analysis of the combined data and to allow uncertainty in supertree topologies to be quantified. The ability to increase the transparency of supertrees to the underlying character data has several practical implications and sheds new light on an old debate. These methods have been implemented in the freely available program, tREeBOOT.

A higher-level MRP supertree of placental mammals

BACKGROUND

The higher-level phylogeny of placental mammals has long been a phylogenetic Gordian knot, with disagreement about both the precise contents of, and relationships between, the extant orders. A recent MRP supertree that favoured 'outdated' hypotheses (notably, monophyly of both Artiodactyla and Lipotyphla) has been heavily criticised for including low-quality and redundant data. We apply a stringent data selection protocol designed to minimise these problems to a much-expanded data set of morphological, molecular and combined source trees, to produce a supertree that includes every family of extant placental mammals.

RESULTS

The supertree is well-resolved and supports both polyphyly of Lipotyphla and paraphyly of Artiodactyla with respect to Cetacea. The existence of four 'superorders'--Afrotheria, Xenarthra, Laurasiatheria and Euarchontoglires--is also supported. The topology is highly congruent with recent (molecular) phylogenetic analyses of placental mammals, but is considerably more comprehensive, being the first phylogeny to include all 113 extant families without making a priori assumptions of suprafamilial monophyly. Subsidiary analyses reveal that the data selection protocol played a key role in the major changes relative to a previously published higher-level supertree of placentals.

CONCLUSION

The supertree should provide a useful framework for hypothesis testing in phylogenetic comparative biology, and supports the idea that biogeography has played a crucial role in the evolution of placental mammals. Our results demonstrate the importance of minimising poor and redundant data when constructing supertrees.