From a phylogenetic tree to a reticulated network.

In many phylogenetic problems, assuming that species have evolved from a common ancestor by a simple branching process is unrealistic. Reticulate phylogenetic models, however, have been largely neglected because the concept of reticulate evolution have not been supported by using appropriate analytical tools and software. The reticulate model can adequately describe such complicated mechanisms as hybridization between species or lateral gene transfer in bacteria. In this paper, we describe a new algorithm for inferring reticulate phylogenies from evolutionary distances among species. The algorithm is capable of detecting contradictory signals encompassed in a phylogenetic tree and identifying possible reticulate events that may have occurred during evolution. The algorithm produces a reticulate phylogeny by gradually improving upon the initial solution provided by a phylogenetic tree model. The new algorithm is compared to the popular SplitsGraph method in a reanalysis of the evolution of photosynthetic organisms. A computer program to construct and visualize reticulate phylogenies, called T-Rex (Tree and Reticulogram Reconstruction), is available to researchers at the following URL: www.fas.umontreal.ca/biol/casgrain/en/labo/t-rex.     

Reconstruction of biogeographic and evolutionary networks using reticulograms

A reticulogram is a general network capable of representing a reticulate evolutionary structure. It is particularly useful for portraying relationships among organisms that may be related in a nonunique way to their common ancestor - relationships that cannot be represented by a dendrogram or a phylogenetic tree. We propose a new method for constructing reticulograms that represent a given distance matrix. Reticulate evolution applies first to phylogenetic problems; it has been found in nature, for example, in the within-species microevolution of eukaryotes and in lateral gene transfer in bacteria. In this paper, we propose a new method for reconstructing reticulation networks and we develop applications of the reticulate evolution model to ecological biogeographic, population microevolutionary, and hybridization problems. The first example considers a spatially constrained reticulogram representing the postglacial dispersal of freshwater fishes in the Québec peninsula; the reticulogram provides a better model of postglacial dispersal than does a tree model. The second example depicts the morphological similarities among local populations of muskrats in a river valley in Belgium; adding supplementary branches to a tree depicting the river network leads to a better representation of the morphological distances among local populations of muskrats than does a tree structure. A third example involves hybrids between plants of the genus Aphelandra.     

Drawing Rooted Phylogenetic Networks

The evolutionary history of a collection of species is usually represented by a phylogenetic tree. Sometimes, phylogenetic networks are used as a means of representing reticulate evolution or of showing uncertainty and incompatibilities in evolutionary datasets. This is often done using unrooted phylogenetic networks such as split networks, due in part, to the availability of software (SplitsTree) for their computation and visualization. In this paper we discuss the problem of drawing rooted phylogenetic networks as cladograms or phylograms in a number of different views that are commonly used for rooted trees. Implementations of the algorithms are available in new releases of the Dendroscope and SplitsTree programs.     

Phylogenetic analysis under reticulate evolution

The usual assumption that species have evolved from a common ancestor by a simple branching process--where each branch is genetically isolated--has been challenged by the observation of frequent hybridization between species in natural populations. In fact, most plant species are thought to have hybrid origins. This reticulate pattern of species evolution has posed problems in the definition of speciation and in phylogenetic reconstruction, especially when molecular data are used. As a result, hybridization has been largely treated as an evolutionary accident or statistical error in phylogenetic analysis. In this paper, I explicitly incorporate hybridization as an evolutionary occurrence and then conduct phylogenetic reconstruction. I first examine the reticulate evolution under a pure drift model, and then extend the theory to fit a mutation model. A least-squares method is developed for reconstructing a reticulate phylogeny using gene frequency data. The efficacy of the method under the pure drift model is verified via Monte Carlo simulations.     

Bayesian Inference of Reticulate Phylogenies under the Multispecies Network Coalescent

The multispecies coalescent (MSC) is a statistical framework that models how gene genealogies grow within the branches of a species tree. The field of computational phylogenetics has witnessed an explosion in the development of methods for species tree inference under MSC, owing mainly to the accumulating evidence of incomplete lineage sorting in phylogenomic analyses. However, the evolutionary history of a set of genomes, or species, could be reticulate due to the occurrence of evolutionary processes such as hybridization or horizontal gene transfer. We report on a novel method for Bayesian inference of genome and species phylogenies under the multispecies network coalescent (MSNC). This framework models gene evolution within the branches of a phylogenetic network, thus incorporating reticulate evolutionary processes, such as hybridization, in addition to incomplete lineage sorting. As phylogenetic networks with different numbers of reticulation events correspond to points of different dimensions in the space of models, we devise a reversible-jump Markov chain Monte Carlo (RJMCMC) technique for sampling the posterior distribution of phylogenetic networks under MSNC. We implemented the methods in the publicly available, open-source software package PhyloNet and studied their performance on simulated and biological data. The work extends the reach of Bayesian inference to phylogenetic networks and enables new evolutionary analyses that account for reticulation.     

Molecular evidence of reticulate evolution in the subgenus Plantago (Plantaginaceae)

Polyploidization is a frequent evolutionary event in plants that has a large influence on speciation and evolution of the genome. Molecular phylogenetic analyses of the taxonomically complex subgenus Plantago were conducted to elucidate intrasubgeneric phylogenetic relationships. A nuclear-encoding single-copy gene, SUC1 (1.0-1.8 kb), was sequenced in 24 taxa representing all five sections of the subgenus Plantago and two taxa from subgenus Coronopus as the outgroup. Fifteen known polyploids and one putative polyploid were sampled to examine polyploid origins and occurrence of reticulate evolution by cloning and sequence analysis of SUC1. Phylogenetic relationships were estimated using maximum parsimony, neighbor-joining, and Bayesian analyses. For the first time, our analysis provides a highly resolved phylogenetic tree. Subgenus Plantago formed a well-supported monophyletic clade. In contrast, alleles from polyploid species were scattered across the whole SUC1 phylogenetic tree, and some independent allopolyploids originated from hybridization between distant lineages. One reason for this taxonomic complexity can be attributed to reticulate evolution within the subgenus Plantago. Our results also suggest the possibility of two independent long-distance dispersals between the northern and southern hemispheres.     

Characterization of reticulate networks based on the coalescent with recombination

Phylogenetic networks aim to represent the evolutionary history of taxa. Within these, reticulate networks are explicitly able to accommodate evolutionary events like recombination, hybridization, or lateral gene transfer. Although several metrics exist to compare phylogenetic networks, they make several assumptions regarding the nature of the networks that are not likely to be fulfilled by the evolutionary process. In order to characterize the potential disagreement between the algorithms and the biology, we have used the coalescent with recombination to build the type of networks produced by reticulate evolution and classified them as regular, tree sibling, tree child, or galled trees. We show that, as expected, the complexity of these reticulate networks is a function of the population recombination rate. At small recombination rates, most of the networks produced are already more complex than regular or tree sibling networks, whereas with moderate and large recombination rates, no network fit into any of the standard classes. We conclude that new metrics still need to be devised in order to properly compare two phylogenetic networks that have arisen from reticulating evolutionary process.     

Exploring phylogenetic hypotheses via Gibbs sampling on evolutionary networks

Background

Phylogenetic networks are leaf-labeled graphs used to model and display complex evolutionary relationships that do not fit a single tree. There are two classes of phylogenetic networks: Data-display networks and evolutionary networks. While data-display networks are very commonly used to explore data, they are not amenable to incorporating probabilistic models of gene and genome evolution. Evolutionary networks, on the other hand, can accommodate such probabilistic models, but they are not commonly used for exploration.

Results

In this work, we show how to turn evolutionary networks into a tool for statistical exploration of phylogenetic hypotheses via a novel application of Gibbs sampling. We demonstrate the utility of our work on two recently available genomic data sets, one from a group of mosquitos and the other from a group of modern birds. We demonstrate that our method allows the use of evolutionary networks not only for explicit modeling of reticulate evolutionary histories, but also for exploring conflicting treelike hypotheses. We further demonstrate the performance of the method on simulated data sets, where the true evolutionary histories are known.

Conclusion

We introduce an approach to explore phylogenetic hypotheses over evolutionary phylogenetic networks using Gibbs sampling. The hypotheses could involve reticulate and non-reticulate evolutionary processes simultaneously as we illustrate on mosquito and modern bird genomic data sets.

     

系统发育网络的构建与应用

系统发育网络目前主要应用于表达种上复杂的网状进化关系、种内个体及群体之间的关系以及相互矛盾数据集的系统发育分析结果3个方面。本文在综述网状进化现象的基础上,介绍了目前用于构建系统发育网络的几种常用方法,包括T-Rex软件包的网状图法,Tcs软件中的统计简约法,Splitstrees4的中间网法、二分裂法和邻接网法。     

Intraspecific gene genealogies: trees grafting into networks

Intraspecific gene evolution cannot always be represented by a bifurcating tree. Rather, population genealogies are often multifurcated, descendant genes coexist with persistent ancestors and recombination events produce reticulate relationships. Whereas traditional phylogenetic methods assume bifurcating trees, several networking approaches have recently been developed to estimate intraspecific genealogies that take into account these population-level phenomena.     

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.     

Application of phylogenetic networks in evolutionary studies

The evolutionary history of a set of taxa is usually represented by a phylogenetic tree, and this model has greatly facilitated the discussion and testing of hypotheses. However, it is well known that more complex evolutionary scenarios are poorly described by such models. Further, even when evolution proceeds in a tree-like manner, analysis of the data may not be best served by using methods that enforce a tree structure but rather by a richer visualization of the data to evaluate its properties, at least as an essential first step. Thus, phylogenetic networks should be employed when reticulate events such as hybridization, horizontal gene transfer, recombination, or gene duplication and loss are believed to be involved, and, even in the absence of such events, phylogenetic networks have a useful role to play. This article reviews the terminology used for phylogenetic networks and covers both split networks and reticulate networks, how they are defined, and how they can be interpreted. Additionally, the article outlines the beginnings of a comprehensive statistical framework for applying split network methods. We show how split networks can represent confidence sets of trees and introduce a conservative statistical test for whether the conflicting signal in a network is treelike. Finally, this article describes a new program, SplitsTree4, an interactive and comprehensive tool for inferring different types of phylogenetic networks from sequences, distances, and trees.     

Phylogenetics of tribe Orchideae (Orchidaceae: Orchidoideae) based on combined DNA matrices: inferences regarding timing of diversification and evolution of pollination syndromes

Background and aims

Tribe Orchideae (Orchidaceae: Orchidoideae) comprises around 62 mostly terrestrial genera, which are well represented in the Northern Temperate Zone and less frequently in tropical areas of both the Old and New Worlds. Phylogenetic relationships within this tribe have been studied previously using only nuclear ribosomal DNA (nuclear ribosomal internal transcribed spacer, nrITS). However, different parts of the phylogenetic tree in these analyses were weakly supported, and integrating information from different plant genomes is clearly necessary in orchids, where reticulate evolution events are putatively common. The aims of this study were to: (1) obtain a well-supported and dated phylogenetic hypothesis for tribe Orchideae, (ii) assess appropriateness of recent nomenclatural changes in this tribe in the last decade, (3) detect possible examples of reticulate evolution and (4) analyse in a temporal context evolutionary trends for subtribe Orchidinae with special emphasis on pollination systems.

Methods

The analyses included 118 samples, belonging to 103 species and 25 genera, for three DNA regions (nrITS, mitochondrial cox1 intron and plastid rpl16 intron). Bayesian and maximum-parsimony methods were used to construct a well-supported and dated tree. Evolutionary trends in the subtribe were analysed using Bayesian and maximum-likelihood methods of character evolution.

Key Results

The dated phylogenetic tree strongly supported the recently recircumscribed generic concepts of Bateman and collaborators. Moreover, it was found that Orchidinae have diversified in the Mediterranean basin during the last 15 million years, and one potential example of reticulate evolution in the subtribe was identified. In Orchidinae, pollination systems have shifted on numerous occasions during the last 23 million years.

Conclusions

The results indicate that ancestral Orchidinae were hymenopteran-pollinated, food-deceptive plants and that these traits have been dominant throughout the evolutionary history of the subtribe in the Mediterranean. Evidence was also obtained that the onset of sexual deception might be linked to an increase in labellum size, and the possibility is discussed that diversification in Orchidinae developed in parallel with diversification of bees and wasps from the Miocene onwards.     

Exine Micromorphology of Orchidinae (Orchidoideae,Orchidaceae): Phylogenetic Constraints or Ecological Influences?

BACKGROUND AND AIMS: Pollen characters have been widely used in defining evolutionary trends in orchids. In recent years, information on pollination biology and phylogenetic patterns within Orchidinae has become available. Hence, the aim of the presented work is to re-evaluate exine micromorphology of Orchidinae in light of recent phylogenetic studies and to test whether pollen micromorphology strictly depends on phylogenetic relationships among species or whether it is influenced by the marked differences in pollination ecology also reported among closely related species. METHODS: Pollen sculpturing of 45 species of Orchidinae and related taxa was investigated using scanning electron microscopy. To cover potential intraspecific variation, several accessions of the same species were examined. KEY RESULTS: Orchidinae show remarkable variation in exine sculpturing, with a different level of variation within species groups. In some genera, such as Serapias (rugulate) and Ophrys (psilate to verrucate), intrageneric uniformity corresponds well to a common pollination strategy and close relationships among species. However, little exine variability (psilate-scabrate and scabrate-rugulate) was also found in the genus Anacamptis in spite of striking differences in floral architecture and pollination strategies. A larger variety of exine conditions was found in genera Dactylorhiza (psilate, psilate-scabrate and reticulate) and Orchis s.s. (psilate, reticulate, perforate-rugulate and baculate) where no unequivocal correspondence can be found to either phylogenetic patterns or pollination strategies. CONCLUSIONS: Changes in pollen characteristics do not consistently reflect shifts in pollination strategy. A unique trend of exine evolution within Orchidinae is difficult to trace. However, the clades comprising Anacamptis, Neotinea, Ophrys and Serapias show psilate to rugulate or scabrate pollen, while that of the clade comprising Chamorchis, Dactylorhiza, Gymnadenia, Orchis s.s., Platanthera, Pseudorchis and Traunsteinera ranges from psilate to reticulate. Comparison of the data with exine micromorphology from members of the tribe Orchidieae and related tribes suggests a possible general trend from reticulate to psilate.     

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.

     

Distinguishing terminal monophyletic groups from reticulate taxa: performance of phenetic, tree-based, and network procedures

Hybridization is a well-documented, natural phenomenon that is common at low taxonomic levels in the higher plants and other groups. In spite of the obvious potential for gene flow via hybridization to cause reticulation in an evolutionary tree, analytical methods based on a strictly bifurcating model of evolution have frequently been applied to data sets containing taxa known to hybridize in nature. Using simulated data, we evaluated the relative performance of phenetic, tree-based, and network approaches for distinguishing between taxa with known reticulate history and taxa that were true terminal monophyletic groups. In all methods examined, type I error (the erroneous rejection of the null hypothesis that a taxon of interest is not monophyletic) was likely during the early stages of introgressive hybridization. We used the gradual erosion of type I error with continued gene flow as a metric for assessing relative performance. Bifurcating tree-based methods performed poorly, with highly supported, incorrect topologies appearing during some phases of the simulation. Based on our model, we estimate that many thousands of gene flow events may be required in natural systems before reticulate taxa will be reliably detected using tree-based methods of phylogeny reconstruction. We conclude that the use of standard bifurcating tree-based methods to identify terminal monophyletic groups for the purposes of defining or delimiting phylogenetic species, or for prioritizing populations for conservation purposes, is difficult to justify when gene flow between sampled taxa is possible. As an alternative, we explored the use of two network methods. Minimum spanning networks performed worse than most tree-based methods and did not yield topologies that were easily interpretable as phylogenies. The performance of NeighborNet was comparable to parsimony bootstrap analysis. NeighborNet and reverse successive weighting were capable of identifying an ephemeral signature of reticulate evolution during the early stages of introgression by revealing conflicting phylogenetic signal. However, when gene flow was topologically complex, the conflicting phylogenetic signal revealed by these methods resulted in a high probability of type II error (inferring that a monophyletic taxon has a reticulate history). Lastly, we present a novel application of an existing nonparametric clustering procedure that, when used against a density landscape derived from principal coordinate data, showed superior performance to the tree-based and network procedures tested.     

The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection

Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa.     

Hybrids in real time

We describe some new and recent results that allow for the analysis and representation of reticulate evolution by non-tree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. [Directed acyclic graph; reticulate evolution; hybrid species; sub-tree prune and re-graft.].     

Maximum Parsimony on Phylogenetic networks

Background

Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a character-based approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past.

Results

In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain well-known algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores.

Conclusion

The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an in-built cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network.