Search

The biogeography of Cretaceous Australian dinosaur fauna has been characterized variously as endemic, cosmopolitan or closely related to other Gondwanan faunas. Over the past decade, a large number of new Australian dinosaur taxa have been described and included in phylogenetic analyses, allowing for new insights into their biogeographical affinities to be obtained. Here, I combine the latest phylogenies of Australian dinosaurs into a supertree that includes as many Australian taxa as possible and apply it to the construction of biogeographical networks of Cretaceous dinosaurs. The results show that the Cretaceous dinosaurs of Australia have a strong connection with South American dinosaurs and to those of other Gondwanan continents via South America. Community detection algorithms indicate that the Gondwanan continents form a community within Cretaceous dinosaur biogeographical networks. The biogeographical affinities between Australia and Laurasia detected in previous studies were largely due to the scarce dinosaur fossil record of Gondwana at that time and to the unstable phylogenetic position of Australian dinosaurs because of the fragmentary nature of their fossils. Continuing discoveries of new Australian taxa and refinement of resulting phylogenetic analyses can further deepen our understanding of the biogeographical history of Australia.

1. We present Visual TreeCmp—a package of applications for comparing phylogenetic tree sets. 2. Visual TreeCmp includes a graphical web interface allowing the visualization of compared trees and command line application extended by comparison methods recently proposed in the literature. 3. The phylogenetic tree similarity analysis in Visual TreeCmp can be performed using eighteen metrics, of which 11 are dedicated to rooted trees and seven to the un-rooted ones. Additionally, in the case of different sets of labels, the compared trees can be pruned so that the sets are identical. 4. The Visual TreeCmp is dedicated to people who need a universal and easy-to-use tool designed to compare arbitrary (not necessary binary) phylogenetic trees. An example of its use in a supertree accuracy analysis is described in section 3. 5. The Visual TreeCmp package Web application is available at: (https://eti.pg.edu.pl/TreeCmp), and its source codes available under the GNU license can be reached through several repositories located at: (https://github.com/TreeCmp)

Leafhoppers (Cicadellidae) occur in all biogeographical regions and feed on a wide range of host plants. Classic identification of leafhoppers is based only on the morphology of male genitalia, while DNA barcoding is an effective tool to identify different leafhopper species in any stage of their life cycle. Phylogenetic relationships among leafhoppers remain unexplored, but recent phylogenies have begun to interpret the evolutionary relationships of previously recognized tribes and subfamilies. Here we used mitochondrial Cytochrome Oxidase I sequences to barcode and determine the phylogenetic relationship among eight leafhopper genera collected from Egypt. Eight leafhopper samples from eight different genera were collected from various plants using a sweeping net and aspirator. Males of seven species were available while females only were available from the one genus (Austroagallia sp.). Novel leafhopper-specific mtDNA COI degenerate primers were designed. Our results showed that the mean of intraspecific COI sequence divergence in leafhoppers was 0.45%, with a range from 0.15% to 1.23%, and the divergences of most species were over 2%. For the first time, we were exploring the evolutionary relationships among surveyed genera (Austroagallia, Empoasca, Eupteryx, Exitianus, Macrosteles, Nephotettix, and Orosius) using a robust phylogenetic supertree. Our results demonstrate that DNA barcoding is likely to be a powerful tool for identifying and understanding leafhoppers’ evolution.

One of the Grand Challenges in Science is the construction of the Tree of Life , an evolutionary tree containing several million species, spanning all life on earth. However, the construction of the Tree of Life is enormously computationally challenging, as all the current most accurate methods are either heuristics for NP -hard optimization problems or Bayesian MCMC methods that sample from tree space. One of the most promising approaches for improving scalability and accuracy for phylogeny estimation uses divide-and-conquer: a set of species is divided into overlapping subsets, trees are constructed on the subsets, and then merged together using a ``supertree method". Here, we present Exact-RFS-2, the first polynomial-time algorithm to find an optimal supertree of two trees, using the Robinson-Foulds Supertree (RFS) criterion (a major approach in supertree estimation that is related to maximum likelihood supertrees), and we prove that finding the RFS of three input trees is NP -hard. We also present GreedyRFS (a greedy heuristic that operates by repeatedly using Exact-RFS-2 on pairs of trees, until all the trees are merged into a single supertree). We evaluate Exact-RFS-2 and GreedyRFS, and show that they have better accuracy than the current leading heuristic for RFS. Exact-RFS-2 and GreedyRFS are available in open source form on Github at github.com/yuxilin51/GreedyRFS

Based on the classical non-parametric bootstrapping for phylogenetic trees, we propose a novel bootstrap method to define support for gene duplication and speciation events. By comparing bootstrap gene trees to the original gene tree, we calculate support for evolutionary events. While this approach can be used to annotate orthology and paralogy, we show how it can be used to verify the reliability of tree reconciliation. We propose a linear time algorithm for the computation of bootstrap values, and we show the correspondence of our method with the classical non-parametric bootstrapping. Finally, we present two computational experiments. In the first one, based on simulated data and nine yeast genomes, we show a comparative study of several tree rooting methods and evaluation of their performance by using our bootstrapping method. In the second experiment, using data from the TreeFam database, we tested how the reliability of the gene trees influence the inferred supertree. We found out that species trees inferred from gene trees having highly supported events are more biologically consistent.

The babblers are a diverse group of passerine birds comprising 452 species. The group was long regarded as a “scrap basket” in taxonomic classification schemes. Although several studies have assessed the phylogenetic relationships for subsets of babblers during the past two decades, a comprehensive phylogeny of this group has been lacking. In this study, we used five mitochondrial and seven nuclear loci to generate a dated phylogeny for babblers. This phylogeny includes 402 species (ca. 89% of the overall clade) from 75 genera (97%) and all five currently recognized families, providing a robust basis for taxonomic revision. Our phylogeny supports seven major clades and reveals several non-monophyletic genera. Divergence time estimates indicate that the seven major clades diverged around the same time (18–20 million years ago, Ma) in the early Miocene. We use the phylogeny in a consistent way to propose a new taxonomy, with seven families and 64 genera of babblers, and a new linear sequence of names.

The metric space of phylogenetic trees defined by Billera, Holmes, and Vogtmann [Adv. in Appl. Math., 27 (2001), pp. 733--767], which we refer to as BHV space, provides a natural geometric setting ...

The analysis of scaling relationships, allometric scaling, has a long history of importance for modelling and predicting biological phenomena. Individual organisms are not truly independent, and as a result phylogenetic corrections are necessary to increase the accuracy of scaling relationships. The relationships between body mass and gestation length have not been previously reported at the Family level, as it was previously thought species had insufficient time to diverge evolutionarily leaving phylogenetic corrections unnecessary. Using a Carnivora supertree, we perform a phylogenetically generalised least squares (PGLS) analysis using life history information largely from the Pantheria dataset. Our results suggest that allometric relationships are maintained in four families: Canidae, Felidae, Herpestidae and Otariidae. Conversely, several evolutionary mechanisms may contribute to the lack of a significant scaling parameter in other families, such as diverse reproductive strategies or positive selection for genes affecting adiposity. In addition, low sample sizes or the inclusion of paternal body masses could alter the presence of significant scaling. Our results suggests that PGLS analyses are informative at the family level, and the absence of scaling can provide insight to understanding of the evolutionary mechanisms that work on the family taxonomic level or below.CCS CONCEPTS• Applied computing → Molecular evolution; • Computing methodologies → Modeling methodologies.ACM Reference FormatStefanie Navaratnam and Julie Baker Phillips. 2021. Breaking the Scale: Allometric scaling analysis in Carnivoran families. In BCB: ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, August 01–04, 2021, Virtual due to COVID-19. ACM, New York, NY, USA, 7 pages. https://doi.org/10.1145/1122445.1122456

Each gene has its own evolutionary history which can substantially differ from the evolutionary histories of other genes. For example, some individual genes or operons can be affected by specific horizontal gene transfer and recombination events. Thus, the evolutionary history of each gene should be represented by its own phylogenetic tree which may display different evolutionary patterns from the species tree that accounts for the main patterns of vertical descent. The output of traditional consensus tree or supertree inference methods is a unique consensus tree or supertree. Here, we describe a new efficient method for inferring multiple alternative consensus trees and supertrees to best represent the most important evolutionary patterns of a given set of phylogenetic trees (i.e. additive trees or X-trees). We show how a specific version of the popular k-means clustering algorithm, based on some interesting properties of the Robinson and Foulds topological distance, can be used to partition a given set of trees into one (when the data are homogeneous) or multiple (when the data are heterogeneous) cluster(s) of trees. We adapt the popular Caliński-Harabasz, Silhouette, Ball and Hall, and Gap cluster validity indices to tree clustering with k-means. A special attention is paid to the relevant but very challenging problem of inferring alternative supertrees, built from phylogenies constructed for different, but mutually overlapping, sets of taxa. The use of the Euclidean approximation in the objective function of the method makes it faster than the existing tree clustering techniques, and thus perfectly suitable for the analysis of large genomic datasets. In this study, we apply it to discover alternative supertrees characterizing the main patterns of evolution of SARS-CoV-2 and the related betacoronaviruses.

Cystoseira sensu lato (sl) are three genera widely recognized as bioindicators for their restricted habitat in a sub-coastal zone with low tolerance to pollution. Their ecological, morphological and taxonomic features are still little known due to their singular characteristics. We studied seven species of Cystoseira sl spp. in Cabo de las Huertas (Alicante, SE Spain) and analyzed their distribution using Permutational Analysis of Variance (PERMANOVA) and Principal Component Ordination plots (PCO). A morphological cladogram has been constructed using fifteen phenotypic taxonomic relevant characters. We have also developed an optimized Cystoseira sl DNA extraction protocol. We have tested it to obtain amplicons from mt23S, tRNA-Lys and psbA genes. With these sequence data, we have built a phylogenetic supertree avoiding threatened Cystoseira sl species. Cartography and distribution analysis show that the response to hydrodynamism predicts perennial or seasonal behaviors. Morphological cladogram detects inter-specifical variability between our species and reference studies. Our DNA phylogenetic tree supports actual classification, including for the first-time Treptacantha sauvageauana and Treptacantha algeriensis species. These data support a complex distribution and speciation of Cystoseira sl spp. in the Mediterranean, perhaps involving Atlantic clades. The high ecological value of our area of study merits a future protection status as a Special Conservation Area. This research received partial funding from the Botany section (36502G0001) of the Department of Marine Science and Applied Biology, the University of Alicante.

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 400 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, most notably in the relative contributions of extinction and speciation rate shifts in driving rapid radiations. Supertrees are often viewed as poor substitute for phylogenies inferred directly from character data but the metatree pipeline overcomes many of the past criticisms leveled at these approaches. Meta–analytic phylogenies provide the most immediate route for integrating fossils into macroevolutionary analyses, the results of which range from untrustworthy to nonsensical without them.

The three-taxon statement (also called triplet) is the fundamental unit of rooted trees in phylogenetic systematics. Various supertree and phylogenetic methods use three-taxon statements that are minimal rooted statements of degree of kinship relationships. Because of their fundamental role in phylogenetics, three-taxon statements are present in methodological research of various disciplines in evolutionary biology, as in consensus methods, supertree methods, species-tree methods, distance metrics, phylogenetics, and cladistic biogeography. Three-taxon statements are thus widely used. However, their theoretical properties have been poorly investigated. As a result, three-taxon statements methods are subject to important flaws related to information redundancy. Correcting these biases is essential to improve the efficiency of methods using three-taxon statements. Our aim is to study the behavior of three-taxon statements and the interactions among them in order to enhance their performance in phylogenetic studies. We have identified new types of very specific interactions between three-taxon statements responsible of the emergence of redundancy and dependency in trees. We propose for the first time a classification of three-taxon statements interactions and trace the link between those and the emergence of dependency and redundancy. A new fractional weighting procedure for suppressing redundancy of three-taxon statements is proposed. Our method is subsequently empirically tested in the supertree framework using simulations. We show that three-taxon statements using fractional weights perform drastically better than classical supertree methods such as MRP or methods using unweighted three-taxon statements. Our study shows that appropriate fractional weighting of three taxon statements is an efficient measure of phylogenetic information content for rooted trees. Fractional weighting is of critical importance for removing redundancy in any method using three-taxon statements, as in consensus, supertrees, distance metrics, and phylogenetic or biogeographic analyses.

One of the Grand Challenges in Science is the construction of the Tree of Life, an evolutionary tree containing several million species, spanning all life on earth. However, the construction of the Tree of Life is enormously computationally challenging, as all the current most accurate methods are either heuristics for NP-hard optimization problems or Bayesian MCMC methods that sample from tree space. One of the most promising approaches for improving scalability and accuracy for phylogeny estimation uses divide-and-conquer: a set of species is divided into overlapping subsets, trees are constructed on the subsets, and then merged together using a “supertree method”. Here, we present Exact-RFS-2, the first polynomial-time algorithm to find an optimal supertree of two trees, using the Robinson-Foulds Supertree (RFS) criterion (a major approach in supertree estimation that is related to maximum likelihood supertrees), and we prove that finding the RFS of three input trees is NP-hard. We also present GreedyRFS (a greedy heuristic that operates by repeatedly using Exact-RFS-2 on pairs of trees, until all the trees are merged into a single supertree). We evaluate Exact-RFS-2 and GreedyRFS, and show that they have better accuracy than the current leading heuristic for RFS. Exact-RFS-2 and GreedyRFS are available in open source form on Github at github.com/yuxilin51/GreedyRFS.

Corona Virus Disease 2019 (COVID-19) caused by the emerged coronavirus SARS-CoV-2 is spreading globally. The origin of SARS-Cov-2 and its evolutionary relationship is still ambiguous. Several reports attempted to figure out this critical issue by genome-based phylogenetic analysis, yet limited progress was obtained, principally owing to the disability of these methods to reasonably integrate phylogenetic information from all genes of SARS-CoV-2. Supertree method based on multiple trees can produce the overall reasonable phylogenetic tree. However, the supertree method has been barely used for phylogenetic analysis of viruses. Here we applied the matrix representation with parsimony (MRP) pseudo-sequence supertree analysis to study the origin and evolution of SARS-CoV-2. Compared with other phylogenetic analysis methods, the supertree method showed more resolution power for phylogenetic analysis of coronaviruses. In particular, the MRP pseudo-sequence supertree analysis firmly disputes bat coronavirus RaTG13 be the last common ancestor of SARS-CoV-2, which was implied by other phylogenetic tree analysis based on viral genome sequences. Furthermore, the discovery of evolution and mutation in SARS-CoV-2 was achieved by MRP pseudo-sequence supertree analysis. Taken together, the MRP pseudo-sequence supertree provided more information on the SARS-CoV-2 evolution inference relative to the normal phylogenetic tree based on full-length genomic sequences.

International audience; For over a decade now, High Throughput sequencing (HTS) approaches have revolutionized phylogenetics, both in terms of data production and methodology. While transcriptomes and (reduced) genomes are increasingly used, generating and analyzing HTS datasets remain expensive, time consuming and complex for most non-model taxa. Indeed, a literature survey revealed that 74% of the molecular phylogenetics trees published in 2018 are based on data obtained through Sanger sequencing. In this context, our goal was to identify the strategy that would represent the best compromise among costs, time and robustness of the resulting tree. We sequenced and assembled 32 transcriptomes of the marine mollusk family Turridae, considered as a typical non-model animal taxon. From these data, we extracted the loci most commonly used in gastropod phylogenies (cox1, 12S, 16S, 28S, h3 and 18S), full mitogenomes, and a reduced nuclear transcriptome representation. With each dataset, we reconstructed phylogenies and compared their robustness and accuracy. We discuss the impact of missing data and the use of statistical tests, tree metrics, and supertree and supermatrix methods to further improve phylogenetic data acquisition pipelines. We evaluated the overall costs (time and money) in order to identify the best compromise for phylogenetic data sampling in non-model animal taxa. Although sequencing full mitogenomes seems to constitute the best compromise both in terms of costs and node support, they are known to induce biases in phylogenetic reconstructions. Rather, we recommend to systematically include loci commonly used for phylogenetics and taxonomy (i.e. DNA barcodes, rRNA genes, full mitogenomes, etc.) among the other loci when designing baits for capture.Graphical abstract

Big, time-scaled phylogenies are fundamental to connecting evolutionary processes to modern biodiversity patterns. Yet inferring reliable phylogenetic trees for thousands of species involves numerous trade-offs that have limited their utility to comparative biologists. To establish a robust evolutionary timescale for all approximately 6,000 living species of mammals, we developed credible sets of trees that capture root-to-tip uncertainty in topology and divergence times. Our “backbone-and-patch” approach to tree building applies a newly assembled 31-gene supermatrix to two levels of Bayesian inference: (1) backbone relationships and ages among major lineages, using fossil node or tip dating, and (2) species-level “patch” phylogenies with nonoverlapping in-groups that each correspond to one representative lineage in the backbone. Species unsampled for DNA are either excluded (“DNA-only” trees) or imputed within taxonomic constraints using branch lengths drawn from local birth–death models (“completed” trees). Joining time-scaled patches to backbones results in species-level trees of extant Mammalia with all branches estimated under the same modeling framework, thereby facilitating rate comparisons among lineages as disparate as marsupials and placentals. We compare our phylogenetic trees to previous estimates of mammal-wide phylogeny and divergence times, finding that (1) node ages are broadly concordant among studies, and (2) recent (tip-level) rates of speciation are estimated more accurately in our study than in previous “supertree” approaches, in which unresolved nodes led to branch-length artifacts. Credible sets of mammalian phylogenetic history are now available for download at http://vertlife.org/phylosubsets, enabling investigations of long-standing questions in comparative biology., This study presents a newly robust evolutionary timescale for ~6000 extant species of mammals, aimed at understanding their species-specific rates of diversification and distinct phylogenetic history. Ages and relationships in the tree of life are estimated with probabilistic confidence levels to help future tests of eco-evolutionary hypotheses.

Let P = { T 1 , … , T k } be a collection of phylogenetic trees over various subsets of a set of species. For each i ∈ { 1 , … , k } , let L ( T i ) denote the set of species in tree T i . A supertree for P is a phylogenetic tree with species set ⋃ i = 1 k L ( T i ) . The tree compatibility problem asks whether there exists a supertree T for P such that, for each i ∈ { 1 , … , k } , T i can be obtained from T | L ( T i ) — the minimal subtree of T spanning L ( T i ) — by zero or more contractions of internal edges. If the answer is “yes”, then P is said to be compatible; otherwise, P is incompatible. We characterize compatibility via graph triangulations and tree decompositions. We then study how to make an incompatible collection of trees compatible through edge contraction and tree deletion. Finally, we introduce the notion of a phylogenetic minor to study under which conditions edge contraction, tree removal, and species removal/renaming operations preserve compatibility.

Transcriptome-based exon capture methods provide an approach to recover several hundred markers from genomic DNA, allowing for robust phylogenetic estimation at deep timescales. We applied this method to a highly diverse group of venomous marine snails, Conoidea, for which published phylogenetic trees remain mostly unresolved for the deeper nodes. We targeted 850 protein coding genes (678,322 bp) in ca. 120 samples, spanning all (except one) known families of Conoidea and a broad selection of non-Conoidea neogastropods. The capture was successful for most samples, although capture efficiency decreased when DNA libraries were of insufficient quality and/or quantity (dried samples or low starting DNA concentration) and when targeting the most divergent lineages. An average of 75.4% of proteins was recovered, and the resulting tree, reconstructed using both supermatrix (IQ-tree) and supertree (Astral-II, combined with the Weighted Statistical Binning method) approaches, are almost fully supported. A reconstructed fossil-calibrated tree dates the origin of Conoidea to the Lower Cretaceous. We provide descriptions for two new families. The phylogeny revealed in this study provides a robust framework to reinterpret changes in Conoidea anatomy through time. Finally, we used the phylogeny to test the impact of the venom gland and radular type on diversification rates. Our analyses revealed that repeated losses of the venom gland had no effect on diversification rates, while families with a breadth of radula types showed increases in diversification rates, thus suggesting that trophic ecology may have an impact on the evolution of Conoidea.

The problem of constructing a minimally resolved phylogenetic supertree (i.e., a rootedtree having the smallest possible number of internal nodes) that contains all of the rooted triplets froma consistent set R is known to be NP-hard. In this article, we prove that constructing a phylogenetictree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard,and develop exact, exponential-time algorithms for both problems. The new algorithms are applied toconstruct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaflabel set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in alltrees in S, where “minimal” means either having the smallest possible number of internal nodes or thesmallest possible number of rooted triplets. (The second variant generalizes the RV-II tree, introducedby Kannan et al. in 1998.) We also measure the running times and memory usage in practice of thenew algorithms for various inputs. Finally, we use our implementations to experimentally investigatethe non-optimality of Aho et al.’s well-known BUILD algorithm from 1981 when applied to the localconsensus tree problems considered here.

New World bats represent over one third of global bat species and encompass the widest adaptive radiation among bats. Modern bat diversity in the Americas resulted from a mixture of migrations and colonisations of different taxa throughout the Cenozoic. Traditionally, these taxa are conceived as either South or North American, based on the location of their centres of diversification. To better understand the spatial and temporal processes behind modern biogeographic patterns of New World bat fauna, we investigated phylogenetic diversity (PD) and endemism (PE) for 325 American bat species using distribution maps and a species-level phylogenetic supertree of bats. Randomisation tests were used to evaluate the statistical significance of our results, and to derive a categorical analysis of neo- and palaeo-endemism (CANAPE) to deconstruct significant endemism into its different components. PD and PE showed different patterns than those previously reported for New World bats based on traditional measures of diversity. We found multiple centres of significant endemism across the New World for most bat families, extending the hypothesis of dual centres of diversification, previously proposed for Emballonuridae, Phyllostomidae and Mormoopidae, to Molossidae and Vespertilionidae. Our results indicate that Central America and southern North America played important roles in the diversification of New World bats, as did the Andes in the diversification of Vespertilionidae in South America. This article is protected by copyright. All rights reserved.

We present a new graph-based approach to the following basic problem in phylogenetic tree construction. Let $$\mathcal {P}= \{T_1, \ldots , T_k\}$$ be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a phylogenetic tree T with the following property: for each $$i \in \{1, \dots , k\}$$ , $$T_i$$ can be obtained from the restriction of T to the species set of $$T_i$$ by contracting zero or more edges. If such a tree T exists, we say that $$\mathcal {P}$$ is compatible and that T displays $$\mathcal {P}$$ . Our approach leads to a $$O(M_\mathcal {P}\log ^2 M_\mathcal {P})$$ algorithm for the tree compatibility problem, where $$M_\mathcal {P}$$ is the total number of nodes and edges in $$\mathcal {P}$$ . Our algorithm either returns a tree that displays $$\mathcal {P}$$ or reports that $$\mathcal {P}$$ is incompatible. Unlike previous algorithms, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, our algorithm is equally fast on highly resolved and highly unresolved trees.

Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in the literature, the most commonly used seems to be the Robinson–Foulds distance. In this article, we define a new metric for rooted trees—the Matching Pair (MP) distance. The MP metric uses the concept of the minimum-weight perfect matching in a complete bipartite graph constructed from partitions of all pairs of leaves of the compared phylogenetic trees. We analyze the properties of the MP metric and present computational experiments showing its potential applicability in tasks related to finding the HGT events.

Dothideomycetes is the most diverse fungal class in Ascomycota and includes species with a wide range of lifestyles. Previous multilocus studies have investigated the taxonomic and evolutionary relationships of these taxa but often failed to resolve early diverging nodes and frequently generated inconsistent placements of some clades. Here, we use a phylogenomic approach to resolve relationships in Dothideomycetes, focusing on two genera of melanized, extremotolerant rock-inhabiting fungi, Lichenothelia and Saxomyces, that have been suggested to be early diverging lineages. We assembled phylogenomic datasets from newly sequenced (4) and previously available genomes (238) of 242 taxa. We explored the influence of tree inference methods, supermatrix vs. coalescent-based species tree, and the impact of varying amounts of genomic data. Overall, our phylogenetic reconstructions provide consistent and well-supported topologies for Dothideomycetes, recovering Lichenothelia and Saxomyces among the earliest diverging lineages in the class. In addition, many of the major lineages within Dothideomycetes are recovered as monophyletic, and the phylogenomic approach implemented strongly supports their relationships. Ancestral character state reconstruction suggest that the rock-inhabiting lifestyle is ancestral within the class.

Over the last years, the availability of genomic sequence data from thousands of different species has led to hopes that a phylogenetic tree of all life might be achievable. Yet, the most accurate methods for estimating phylogenies are heuristics for NP-hard optimization problems, many of which are too computationally intensive to use on large datasets. Divide-and-conquer approaches have been proposed to address scalability to large datasets that divide the species into subsets, construct trees on subsets, and then merge the trees together. Prior approaches have divided species sets into overlapping subsets and used supertree methods to merge the subset trees, but limitations in supertree methods suggest this kind of divide-and-conquer approach is unlikely to provide scalability to ultra-large datasets. Recently, a new approach has been developed that divides the species dataset into disjoint subsets, computes trees on subsets, and then combines the subset trees using auxiliary information (e.g., a distance matrix). Here, we describe these strategies and their theoretical properties, present open problems, and discuss opportunities for impact in large-scale phylogenetic estimation using these and similar approaches.

A supertree method is a form of meta-analysis. It combines phylogenetic tree estimates, which typically include only a subset of the species of interest, into a single tree that includes every species found in any input tree. These methods are usually applied to phylogenetic estimates that only have taxonomic labels at their leaves. Taxonomies are another source of information about phylogenetic relationships. They usually convey names for groups of species in addition to species names. If a taxonomy places every species, then its phylogenetic information can be fully expressed as a tree. Such a taxonomy could easily serve as one of the inputs to a supertree method. However, most taxonomies contain incertae sedis taxa, which are species or groups of species that have an uncertain placement within the taxonomic hierarchy. Here, we review some principles of building trees from splits and describe a supertree method that is able to handle incertae sedis taxa without losing taxon names.

We combine two fundamental, previously studied optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency (MAXRTC) and minimally resolved supertree (MINRS) into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). The input to our new problem is a set R of resolved triplets (rooted, binary phylogenetic trees with three leaves each) and the objective is to find a phylogenetic tree with exactly q internal nodes that contains the largest possible number of triplets from R. We first prove that q-MAXRTC is NP-hard even to approximate within a constant ratio for every fixed q ≥ 2, and then develop various polynomial-time approximation algorithms for different values of q. Next, we show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much triplet branching information. As an extreme example, we show that allowing only nine internal nodes is still sufficient to capture on average 80% of the rooted triplets from some recently published trees, each having between 760 and 3081 internal nodes. Finally, to demonstrate the algorithmic advantage of using trees with few internal nodes, we propose a new algorithm for computing the rooted triplet distance between two phylogenetic trees over a leaf label set of size n that runs in O(qn) time, where q is the number of internal nodes in the smaller tree, and is therefore faster than the currently best algorithms for the problem (with O(n log n) time complexity [SODA 2013, ESA 2017]) whenever q = o(log n).

Consensus trees and supertrees are regularly used in systematic biology in order to obtain a summary for the common agreement of the evolutionary relationships among a collection of phylogenetic trees (hierarchies). When every tree is defined on the same set of taxa then consensus functions are used, while if the trees are defined on different sets then supertree functions are used. For both of these situations we will consider some of the limitations that might arise from the placing of singularly reasonable and apparently innocuous conditions on the functions. Previous work is reviewed together with new material. In particular, we consider the impact of axioms requiring that the removal or addition of a tree that contains no, or no new, branching information should not affect the outcome.

The rapid increase of molecular, as well as other types, of available classification data has created the need to combine this data into a uni-fied hypothesis. Supertree methods are essential when amalgamating phylogenetic information from various, possibly conflicting, sources into a single tree. The goal of a supertree algorithm is to satisfy maximally each such source of information in the output tree. Triplets, rooted trees over three leaves, are the minimal piece of such information when dealing with rooted trees. Due to its fundamental role in phylogenetics,extensive effort have been dedicated to several aspects regarding triplets’ research.We have devised a new tool, Triplet MaxCut (TMC), performing vari-ous operations in rooted supertree, principally amalgamating rooted trees based on amalgamating rooted triplets. The utility and efficiency of the algorithm is demonstrated by both simulation study and four real data supertree inputs. This article is protected by copyright. All rights reserved.

Several attempts have been made to generate complete species-level phylogenies for large clades, enabling comprehensive analyses of ecological or evolutionary hypotheses at the species level. No such phylogeny has, however, been generated for any major plant group yet, but here we generate such a phylogeny for the palm family (Arecaceae). We do this using a novel Bayesian approach, estimating the validity of intra-generic taxonomic groupings as topological constraints to assist in placing species without genetic or morphological data. From these we implement those that are supported by genetic or morphological data for a given genus or for related genera. The intergeneric relationships in our new phylogeny are surprisingly different from earlier phylogenies in the placement of genera within tribes, but largely identical to previous findings in the deeper branches in the phylogeny, pointing to the need for incorporating phylogenetic uncertainty in analyses based on this phylogeny. Initial analyses of the new phylogeny suggest non-constancy in diversification rates over time within genera, with an apparent increase in diversification rate over time, but no evidence for any geographic variation in the magnitude of this increase. We hope that our study will stimulate further evolutionary or ecological studies using palms as study organisms as well as discussions of the optimal way to place the many species without genetic or morphological data., We are grateful to the Danish Council for Independent Research Natural Sciences (grant 12-125079 to JCS and 4090-00227 to SF) and the European Union’s FP7-PEOPLE programme (grant 327259 to WLE) for financial support.

Over the last 20 years, TreeBASE has acquired a substantial body of phylogenetic data, including more than 20,000 published phylogenies. Given latency issues and limited options when it comes to querying the database remotely, a simplified and consolidated version of the database, here called TreeBASEdmp, is made available for download, allowing biologists to design custom analyses of the data on their local computers. The database is indexed to support searching for phylogenetic topologies using nested sets and closure tables. Here we propose a new approach to find broadly-defined phylogenetic patterns, a method we call Generic Topological Querying, which allows the user to find hypotheses of relationship without being constrained to use particular sets of specific taxa. Additionally, we normalize as many leaf nodes as possible to an equivalent species rank identifier to assist in supertree synthesis. Our example script rapidly assembles sets of trees and generates a matrix representation of them for subsequent supertree generation.

Science and society would benefit enormously from comprehensive phylogenetic knowledge of the Tree of Life (ToL), a framework that includes above 1.7 million species on Earth. ToL shows how living things have evolved since the origins of life billions of years ago. With existing computational approaches, we cannot produce a global estimate of evolutionary history from molecular data of all these species. Therefore, the development of computer algorithms and methods is critical to the field of phyloinformatics. The goal of this dissertation is to design, analyze, and implement algorithms to solve three specific problems in the the field of phyloinformatics to support ToL studies. The first part of this dissertation is about algorithms for the matrix representation with flipping (MRF) method to construct large subtrees of the ToL. The utility of the MRF supertree method has been limited by the speed of its heuristic algorithms. We describe a new heuristic algorithm for MRF supertree construction that improves upon the speed of the previous heuristic by a factor of n (the number of taxa in the supertree). This new heuristic makes MRF tractable for large-scale supertree analyses and allows the first comparisons of MRF with other supertree methods using large empirical data sets. Analyses of three published supertree data sets indicate that MRF supertrees are equally or more similar to the input trees on average than matrix representation with parsimony (MRP) and modified mincut supertrees. The results also show that large differences may exist between MRF and MRP supertrees, and demonstrate that the MRF supertree method is a practical and potentially more accurate alternative to the nearly ubiquitous MRP supertree method. The second part of this dissertation is dedicated to new algorithms for partitioning phylogenetic data sets. We describe two new methods to partition phylogenetic data sets of discrete characters based on pairwise compatibility. The partitioning methods make no assumptions regarding the phylogeny

An important problem in phylogenetics is the construction of phylogenetic trees. One way to approach this problem, known as the supertree method, involves inferring a phylogenetic tree with leaves consisting of a set $X$ of species from a collection of trees, each having leaf-set some subset of $X$. In the 1980's characterizations, certain inference rules were given for when a collection of 4-leaved trees, one for each 4-element subset of $X$, can all be simultaneously displayed by a single supertree with leaf-set $X$. Recently, it has become of interest to extend such results to phylogenetic networks. These are a generalization of phylogenetic trees which can be used to represent reticulate evolution (where species can come together to form a new species). It has been shown that a certain type of phylogenetic network, called a level-1 network, can essentially be constructed from 4-leaved trees. However, the problem of providing appropriate inference rules for such networks remains unresolved. Here we show that by considering 4-leaved networks, called quarnets, as opposed to 4-leaved trees, it is possible to provide such rules. In particular, we show that these rules can be used to characterize when a collection of quarnets, one for each 4-element subset of $X$, can all be simultaneously displayed by a level-1 network with leaf-set $X$. The rules are an intriguing mixture of tree inference rules, and an inference rule for building up a cyclic ordering of $X$ from orderings on subsets of $X$ of size 4. This opens up several new directions of research for inferring phylogenetic networks from smaller ones, which could yield new algorithms for solving the supernetwork problem in phylogenetics., 17 pages

The evolutionary emergence of land plant body plans transformed the planet. However, our understanding of this formative episode is mired in the uncertainty associated with the phylogenetic relationships among bryophytes (hornworts, liverworts, and mosses) and tracheophytes (vascular plants). Here we attempt to clarify this problem by analyzing a large transcriptomic dataset with models that allow for compositional heterogeneity between sites. Zygnematophyceae is resolved as sister to land plants, but we obtain several distinct relationships between bryophytes and tracheophytes. Concatenated sequence analyses that can explicitly accommodate site-specific compositional heterogeneity give more support for a mosses-liverworts clade, “Setaphyta,” as the sister to all other land plants, and weak support for hornworts as the sister to all other land plants. Bryophyte monophyly is supported by gene concatenation analyses using models explicitly accommodating lineage-specific compositional heterogeneity and analyses of gene trees. Both maximum-likelihood analyses that compare the fit of each gene tree to proposed species trees and Bayesian supertree estimation based on gene trees support bryophyte monophyly. Of the 15 distinct rooted relationships for embryophytes, we reject all but three hypotheses, which differ only in the position of hornworts. Our results imply that the ancestral embryophyte was more complex than has been envisaged based on topologies recognizing liverworts as the sister lineage to all other embryophytes. This requires many phenotypic character losses and transformations in the liverwort lineage, diminishes inconsistency between phylogeny and the fossil record, and prompts re-evaluation of the phylogenetic affinity of early land plant fossils, the majority of which are considered stem tracheophytes. Puttick et al. resolve a “Setaphyta” clade uniting liverworts and mosses and support for bryophyte monophyly. Their results indicate that the ancestral land plant was more complex than has been envisaged based on phylogenies recognizing liverworts as the sister lineage to all other embryophytes.

Molecular phylogeny of staphylinid beetles as published in 36 papers is reviewed. For every paper, the markers used, the size of the analyzed dataset, and the taxonomic focus are listed. Availability of sequence and genomic data for the entire family and all subfamilies is summarized. The current knowledge of staphylinid phylogeny is presented in a supertree. Phylogenetic relationships between the Staphylinidae and other staphylinoid families, among and within staphylinid subfamilies, are discussed.

Many cases of rapid evolutionary radiations in plant and animal lineages are known; however phylogenetic relationships among these lineages have been difficult to resolve by systematists. Increasing amounts of genomic data have been sequentially applied in an attempt to resolve these radiations, dissecting their evolutionary patterns into a series of bifurcating events. Here we explore one such rapid radiation in the tropical plant order Zingiberales (the bananas and relatives) which includes eight families, approximately 110 genera, and more than 2600 species. One clade, the “Ginger families”, including (Costaceae + Zingiberaceae) (Marantaceae + Cannaceae), has been well-resolved and well-supported in all previous studies. However, well-supported reconstructions among the “Banana families” (Musaceae, Heliconiaceae, Lowiaceae, Strelitziaceae), which most likely diverged about 90 Mya, have been difficult to confirm. Supported with anatomical, morphological, single locus, and genome-wide data, nearly every possible phylogenetic placement has been proposed for these families. In an attempt to resolve this complex evolutionary event, hybridization-based target enrichment was used to obtain sequences from up to 378 putatively orthologous low-copy nuclear genes (all ≥ 960 bp). Individual gene trees recovered multiple topologies among the early divergent lineages, with varying levels of support for these relationships. One topology of the “Banana families” (Musaceae (Heliconiaceae (Lowiaceae + Strelitziaceae))), which has not been suggested until now, was almost consistently recovered in all multilocus analyses of the nuclear dataset (concatenated – ExaML, coalescent – ASTRAL and ASTRID, supertree – MRL, and Bayesian concordance – BUCKy). Nevertheless, the multiple topologies recovered among these lineages suggest that even large amounts of genomic data might not be able to fully resolve relationships at this phylogenetic depth. This lack of well-supported resolution could suggest methodological problems (i.e., violation of model assumptions in both concatenated and coalescent analyses) or more likely reflect an evolutionary history shaped by an explosive, rapid, and nearly simultaneous polychotomous radiation in this group of plants towards the end of the Cretaceous, perhaps driven by vertebrate pollinator selection.