Trinets encode tree-child and level-2 phylogenetic networks

Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that $\text{ level-1 }$ phylogenetic networks are encoded by their trinets, and also conjectured that all “recoverable” rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level-2 networks and binary tree-child networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets.     

Arthropod-induced neoplastic formations on trees change photosynthetic pigment levels and oxidative enzyme activities

Abstract

In order to test the hypothesis that arthropod-induced neoplastic formations on trees affect biochemical characteristics of both the newly formed galls and host plant tissues, biochemical characteristics with a possible adaptive role were determined in nine gall-former–host tree combinations. Photosynthetic pigments, extractable protein content, and oxidative enzyme activities were determined in gall tissues, leaf tissues of galled leaves, and leaves on ungalled tree branches. Neoplastic tissues were characterized by a low content of photosynthetic pigments, decreased chlorophyll a/b ratio, lower extractable protein content, and decreased activities of peroxidase and polyphenol oxidase as compared with ungalled host leaf tissues. In galled leaves or in leaves adjacent to galls, increased level of peroxidase activity was found. In several gall-inducer–host plant combinations, galled host plant tissues contained increased activity of polyphenol oxidase as well. The presented data reflect long-term systemic effects of neoplastic formation on host tree physiology suggesting that gall inducers affect potential adaptive responses of host plants.     

Tree-Based Unrooted Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that are used to represent non-tree-like evolutionary histories that arise in organisms such as plants and bacteria, or uncertainty in evolutionary histories. An unrooted phylogenetic network on a non-empty, finite set X of taxa, or network, is a connected, simple graph in which every vertex has degree 1 or 3 and whose leaf set is X. It is called a phylogenetic tree if the underlying graph is a tree. In this paper we consider properties of tree-based networks, that is, networks that can be constructed by adding edges into a phylogenetic tree. We show that although they have some properties in common with their rooted analogues which have recently drawn much attention in the literature, they have some striking differences in terms of both their structural and computational properties. We expect that our results could eventually have applications to, for example, detecting horizontal gene transfer or hybridization which are important factors in the evolution of many organisms.     

Tree-based networks: characterisations,metrics, and support trees

Phylogenetic networks generalise phylogenetic trees and allow for the accurate representation of the evolutionary history of a set of present-day species whose past includes reticulate events such as hybridisation and lateral gene transfer. One way to obtain such a network is by starting with a (rooted) phylogenetic tree T, called a base tree, and adding arcs between arcs of T. The class of phylogenetic networks that can be obtained in this way is called tree-based networks and includes the prominent classes of tree-child and reticulation-visible networks. Initially defined for binary phylogenetic networks, tree-based networks naturally extend to arbitrary phylogenetic networks. In this paper, we generalise recent tree-based characterisations and associated proximity measures for binary phylogenetic networks to arbitrary phylogenetic networks. These characterisations are in terms of matchings in bipartite graphs, path partitions, and antichains. Some of the generalisations are straightforward to establish using the original approach, while others require a very different approach. Furthermore, for an arbitrary tree-based network N, we characterise the support trees of N, that is, the tree-based embeddings of N. We use this characterisation to give an explicit formula for the number of support trees of N when N is binary. This formula is written in terms of the components of a bipartite graph.

     

Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.     

Genomic duplication problems for unrooted gene trees

Background

Discovering the location of gene duplications and multiple gene duplication episodes is a fundamental issue in evolutionary molecular biology. The problem introduced by Guigó et al. in 1996 is to map gene duplication events from a collection of rooted, binary gene family trees onto theirs corresponding rooted binary species tree in such a way that the total number of multiple gene duplication episodes is minimized. There are several models in the literature that specify how gene duplications from gene families can be interpreted as one duplication episode. However, in all duplication episode problems gene trees are rooted. This restriction limits the applicability, since unrooted gene family trees are frequently inferred by phylogenetic methods.

Results

In this article we show the first solution to the open problem of episode clustering where the input gene family trees are unrooted. In particular, by using theoretical properties of unrooted reconciliation, we show an efficient algorithm that reduces this problem into the episode clustering problems defined for rooted trees. We show theoretical properties of the reduction algorithm and evaluation of empirical datasets.

Conclusions

We provided algorithms and tools that were successfully applied to several empirical datasets. In particular, our comparative study shows that we can improve known results on genomic duplication inference from real datasets.

     

Reconstructing an ultrametric galled phylogenetic network from a distance matrix

Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n(2) log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M' of M such that there exists an ultrametric galled network that satisfies M' is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it.     

Uprooted Phylogenetic Networks

The need for structures capable of accommodating complex evolutionary signals such as those found in, for example, wheat has fueled research into phylogenetic networks. Such structures generalize the standard model of a phylogenetic tree by also allowing for cycles and have been introduced in rooted and unrooted form. In contrast to phylogenetic trees or their unrooted versions, rooted phylogenetic networks are notoriously difficult to understand. To help alleviate this, recent work on them has also centered on their “uprooted” versions. By focusing on such graphs and the combinatorial concept of a split system which underpins an unrooted phylogenetic network, we show that not only can a so-called (uprooted) 1-nested network N be obtained from the Buneman graph (sometimes also called a median network) associated with the split system \(\Sigma (N)\) induced on the set of leaves of N but also that that graph is, in a well-defined sense, optimal. Along the way, we establish the 1-nested analogue of the fundamental “splits equivalence theorem” for phylogenetic trees and characterize maximal circular split systems.     

Coalescent histories for discordant gene trees and species trees

Given a gene tree and a species tree, a coalescent history is a list of the branches of the species tree on which coalescences in the gene tree take place. Each pair consisting of a gene tree topology and a species tree topology has some number of possible coalescent histories. Here we show that, for each n≥7, there exist a species tree topology S and a gene tree topology G≠S, both with n leaves, for which the number of coalescent histories exceeds the corresponding number of coalescent histories when the species tree topology is S and the gene tree topology is also S. This result has the interpretation that the gene tree topology G discordant with the species tree topology S can be produced by the evolutionary process in more ways than can the gene tree topology that matches the species tree topology, providing further insight into the surprising combinatorial properties of gene trees that arise from their joint consideration with species trees.     

Presidential Address—Some Reflections On The Nature Of Species

Background: Variation in the distribution and abundance of woody plants as consequence of disturbances such as fire may be explained by lineage age.

Aims: We tested whether lowland tropical tree lineages that colonise secondary forests are more late-diverging than clades from old-growth forests, and whether tree phylogenetic beta diversity from old-growth to secondary forests is higher in burned than non-burned secondary forests.

Methods: We sampled tree communities in old-growth forests and in secondary forests with distinct disturbance histories (burned and unburned). We calculated mean family age in each plot, and tested for differences among forest types using ANOVA. A phylogenetic fuzzy-weighting procedure was employed to generate a matrix describing the abundance of tree clades per plot, which was then analysed using a principal coordinate analysis.

Results: Most clades found in old-growth forests were underrepresented in secondary forests, which have been heavily colonised by a single species from a young lineage that is not found in old-growth forests. Phylogenetic beta diversity was higher between unburned secondary forests and old-growth forests than between burned secondary forests and old-growth forests.

Conclusions: The capacity of Neotropical trees to colonise secondary forests and persist after fire disturbance may be related to the age of distinct lineages.     

THE RELATIONSHIP BETWEEN A FLOWER GALL MIDGE PSEUDAS-PHONDYLIA SP. (DIPTERA: CECIDOMYIIDAE) AND ITS HOST PLANT ACTINIDIA VALVATA*

Abstract Kiwifruit plants, Actinidia sp., are native to subtropical China. The flower-bud gall of A. valvata, which is induced by an undescribed gall midge in the genus Pseud as phond ylia, is valued by the pharmaceutical industry. When studying the biology of the Actinid ia/Pseud as phond ylia interaction in Central-south China we found evidence suggesting that under certain circumstances the gall insect modifies the reproductive mode of the dioecious host plant. Surveys and field experiments in the National Hupingshan Natural Reserve showed a high frequency of galled trees. The density of galled trees varied among valleys and among trees within the valleys. In two valleys, 92% and 75%, respectively, of all trees were attacked, while in a third valley no trees were attacked. When infested, staminate tree only produced galls, whereas pistillate plants produced normal fruits as well as galls. Gall shape differed between male and female trees. Trees with galls tended to produce more fruits than treea without galls. We speculate that this is one of a few documented examples of an insect that induces androdioecy in an otherwise functionally dioecious plant.     

Qualitative and Quantitative Evaluation of Gall Induced by <Emphasis Type="Italic">Pseudophacopteron alstonium</Emphasis> Yang et Li 1983 (Hemiptera: Psyllidae: Phacopteronidae) as Plant Parasite,in <Emphasis Type="Italic">Alstonia scholaris</Emphasis> Leaves

Alstonia scholaris (Dr C. Alston, 1685–1760) (Family Apocynaceae) (Chattim tree), commonly known as devil tree, is an evergreen tropical tree. The tree is native to India and also found in Sri Lanka, Southern China, throughout Malaysia to northern Australia. This plant is seriously damaged by formation of tumor like galls across the Kolkata city,West Bengal which affects its ornamental and medicinal value. Gall is formed by ovipositing adults of Pseudophacopteron alstonium Yang et Li 1983 (Hemiptera: Psyllidae: Phacopteronidae) and results in destruction of host plant. The nymphal stage undergoes moulting through first instar to third instar to reach the adult within galls. It is observed that highly infested leaves can bear 60–80 galls. The gallmaker Pseudophacopteron sp. stresses the host organ, and the host counters it with physiological activities supplemented by newly differentiated tissues. In infested leaves, chlorophyll and carbohydrate contents decreased sequentially with the age of the gall. There were no significant changes in protein and total amino acid content in gall tissue. But total lipid content was highest in mature galled leaves. Increased phenolic content after psylloid herbivory, which exerted oxidative stress on the host plants, was observed in gall infested leaves as compared to fresh ungalled leaves of Alstonia scholaris. Moisture content was highest in ungalled healthy leaves than the young galled, mature galled and perforated galled leaves.     

BIMLR: A method for constructing rooted phylogenetic networks from rooted phylogenetic trees

Rooted phylogenetic trees constructed from different datasets (e.g. from different genes) are often conflicting with one another, i.e. they cannot be integrated into a single phylogenetic tree. Phylogenetic networks have become an important tool in molecular evolution, and rooted phylogenetic networks are able to represent conflicting rooted phylogenetic trees. Hence, the development of appropriate methods to compute rooted phylogenetic networks from rooted phylogenetic trees has attracted considerable research interest of late. The C_ASS algorithm proposed by van Iersel et al. is able to construct much simpler networks than other available methods, but it is extremely slow, and the networks it constructs are dependent on the order of the input data. Here, we introduce an improved C_ASS algorithm, BIMLR. We show that BIMLR is faster than C_ASS and less dependent on the input data order. Moreover, BIMLR is able to construct much simpler networks than almost all other methods. BIMLR is available at http://nclab.hit.edu.cn/wangjuan/BIMLR/.     

Quarnet Inference Rules for Level-1 Networks

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 1980s, Colonius and Schulze gave certain inference rules for deciding when a collection of 4-leaved trees, one for each 4-element subset of X, can be simultaneously displayed by a single supertree with leaf-set X. Recently, it has become of interest to extend this and related 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 recently been shown that a certain type of phylogenetic network, called a (unrooted) 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.     

Complexity of the simplest phylogenetic estimation problem

The maximum-likelihood (ML) solution to a simple phylogenetic estimation problem is obtained analytically The problem is estimation of the rooted tree for three species using binary characters with a symmetrical rate of substitution under the molecular clock. ML estimates of branch lengths and log-likelihood scores are obtained analytically for each of the three rooted binary trees. Estimation of the tree topology is equivalent to partitioning the sample space (space of possible data outcomes) into subspaces, within each of which one of the three binary trees is the ML tree. Distance-based least squares and parsimony-like methods produce essentially the same estimate of the tree topology, although differences exist among methods even under this simple model. This seems to be the simplest case, but has many of the conceptual and statistical complexities involved in phylogeny estimation. The solution to this real phylogeny estimation problem will be useful for studying the problem of significance evaluation.     

Effect of gall formation by a cynipid wasp, Andricus symbioticus, on the development of the leaves and shoots of Quercus dentata

The sexual generation of a cynipid wasp, Andricus symbioticus Kovalev, forms its leaf galls most frequently near and on the leaf petiole of Quercus trees. I examined the effect of gall formation by A. symbioticus on the leaf development of a host plant, Quercus dentata Thunberg, by comparing the size and shape of galled and ungalled leaves. I also examined the effect of gall formation on shoot development by comparing the length of shoots with and without galled leaves. Three of seven Q. dentata trees surveyed were heavily infested with A. symbioticus. Leaf size did not differ between galled and ungalled leaves. However, the ratio of leaf width to length was greater in galled leaves, which is regarded to be a result of gall formation by A. symbioticus inhibiting the growth in length of Q. dentata leaves. Shoot length did not differ significantly between shoots with and without galled leaves. These results suggest that galls of A. symbioticus act as a sink that competes with leaves for reserved photoassimilates.     

Tree-average distances on certain phylogenetic networks have their weights uniquely determined

ABSTRACT: A phylogenetic network N has vertices corresponding to species and arcs corresponding to direct genetic inheritance from the species at the tail to the species at the head. Measurements of DNA are often made on species in the leaf set, and one seeks to infer properties of the network, possibly including the graph itself. In the case of phylogenetic trees, distances between extant species are frequently used to infer the phylogenetic trees by methods such as neighbor-joining. This paper proposes a "tree-average" distance for networks more general than trees. The notion requires a "weight" on each arc measuring the genetic change along the arc. For each displayed tree the distance between two leaves is the sum of the weights along the path joining them. At a hybrid vertex, each character is inherited from one of its parents. We will assume that for each hybrid there is a probability that the inheritance of a character is from a specified parent. Assume that the inheritance events at different hybrids are independent. Then for each displayed tree there will be a probability that the inheritance of a given character follows the tree; this probability may be interpreted as the probability of the tree. The "tree-average" distance between the leaves is defined to be the expected value of their distance in the displayed trees. For a class of rooted networks that includes rooted trees, it is shown that the weights and the probabilities at each hybrid vertex can be calculated given the network and the tree-average distances between the leaves. Hence these weights and probabilities are uniquely determined. The hypotheses on the networks include that hybrid vertices have indegree exactly 2 and that vertices that are not leaves have a tree-child.     

Weak phylogenetic signal for specialisation in antagonistic liana–tree networks

Background: Antagonistic interactions, such as parasitism and herbivory, are generally specialised and have a strong phylogenetic signal for specialisation. As lianas and trees interact antagonistically, we expect to find phylogenetic signal for specialisation.

Aims: We aimed to answer the following questions: (1) Is the liana–tree network specialised? (2) Is the specialisation of liana–tree network related to the abundance of both the life forms? (3) Is liana and tree specialisation related to species phylogeny? (4) Do phylogenetically related liana species occupy phylogenetically related tree species, and vice versa?

Methods: For three areas in southern Brazil, we calculated the specialisation value of each liana and tree species (d') and of the entire network (H₂′). Binomial regression and null models were used to test the role of abundance on d' and H₂′, respectively. We searched for the presence of phylogenetic signal with phylogenetic independent contrasts for d'. We also compared the similarity of species sets and their interaction with phylogenetic distance between them using Mantel test.

Results: All three networks had significant values of H₂′, but the values of d' did not have significant phylogenetic signals. Closely related lianas did not share similar host-tree assemblages and vice versa. Rare species were more specialised than abundant species, and abundance did not influence H₂′.

Conclusions: Our study indicates that the significant H₂′ may be due to co-evolution in some lineages of lianas and trees. Nevertheless, the abundance of species may also play an important role in species interaction, mainly rare species.     

Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent

Gene trees are evolutionary trees representing the ancestry of genes sampled from multiple populations. Species trees represent populations of individuals—each with many genes—splitting into new populations or species. The coalescent process, which models ancestry of gene copies within populations, is often used to model the probability distribution of gene trees given a fixed species tree. This multispecies coalescent model provides a framework for phylogeneticists to infer species trees from gene trees using maximum likelihood or Bayesian approaches. Because the coalescent models a branching process over time, all trees are typically assumed to be rooted in this setting. Often, however, gene trees inferred by traditional phylogenetic methods are unrooted. We investigate probabilities of unrooted gene trees under the multispecies coalescent model. We show that when there are four species with one gene sampled per species, the distribution of unrooted gene tree topologies identifies the unrooted species tree topology and some, but not all, information in the species tree edges (branch lengths). The location of the root on the species tree is not identifiable in this situation. However, for 5 or more species with one gene sampled per species, we show that the distribution of unrooted gene tree topologies identifies the rooted species tree topology and all its internal branch lengths. The length of any pendant branch leading to a leaf of the species tree is also identifiable for any species from which more than one gene is sampled.     

When is a Phylogenetic Network Simply an Amalgamation of Two Trees?

Phylogenetic networks generalise phylogenetic (evolutionary) trees by allowing for the representation of reticulation (non-treelike) events. The structure of such networks is often viewed by the phylogenetic trees they embed. In this paper, we determine when a phylogenetic network \({\mathcal {N}}\) has two phylogenetic tree embeddings which collectively contain all of the edges of \({\mathcal {N}}\). This determination leads to a polynomial-time algorithm for recognising such networks and an unexpected characterisation of the class of reticulation-visible networks.