Reconstructing the evolutionary history of polyploids from multilabeled trees

In recent studies, phylogenetic networks have been derived from so-called multilabeled trees in order to understand the origins of certain polyploids. Although the trees used in these studies were constructed using sophisticated techniques in phylogenetic analysis, the presented networks were inferred using ad hoc arguments that cannot be easily extended to larger, more complicated examples. In this paper, we present a general method for constructing such networks, which takes as input a multilabeled phylogenetic tree and outputs a phylogenetic network with certain desirable properties. To illustrate the applicability of our method, we discuss its use in reconstructing the evolutionary history of plant allopolyploids. We conclude with a discussion concerning possible future directions. The network construction method has been implemented and is freely available for use from http://www.uea.ac.uk/ approximately a043878/padre.html.     

Inferring species networks from gene trees in high-polyploid North American and Hawaiian violets (Viola, Violaceae)

The phylogenies of allopolyploids take the shape of networks and cannot be adequately represented as bifurcating trees. Especially for high polyploids (i.e., organisms with more than six sets of nuclear chromosomes), the signatures of gene homoeolog loss, deep coalescence, and polyploidy may become confounded, with the result that gene trees may be congruent with more than one species network. Herein, we obtained the most parsimonious species network by objective comparison of competing scenarios involving polyploidization and homoeolog loss in a high-polyploid lineage of violets (Viola, Violaceae) mostly or entirely restricted to North America, Central America, or Hawaii. We amplified homoeologs of the low-copy nuclear gene, glucose-6-phosphate isomerase (GPI), by single-molecule polymerase chain reaction (PCR) and the chloroplast trnL-F region by conventional PCR for 51 species and subspecies. Topological incongruence among GPI homoeolog subclades, owing to deep coalescence and two instances of putative loss (or lack of detection) of homoeologs, were reconciled by applying the maximum tree topology for each subclade. The most parsimonious species network and the fossil-based calibration of the homoeolog tree favored monophyly of the high polyploids, which has resulted from allodecaploidization 9-14 Ma, involving sympatric ancestors from the extant Viola sections Chamaemelanium (diploid), Plagiostigma (paleotetraploid), and Viola (paleotetraploid). Although two of the high-polyploid lineages (Boreali-Americanae, Pedatae) remained decaploid, recurrent polyploidization with tetraploids of section Plagiostigma within the last 5 Ma has resulted in two 14-ploid lineages (Mexicanae, Nosphinium) and one 18-ploid lineage (Langsdorffianae). This implies a more complex phylogenetic and biogeographic origin of the Hawaiian violets (Nosphinium) than that previously inferred from rDNA data and illustrates the necessity of considering polyploidy in phylogenetic and biogeographic reconstruction.     

Do Triplets Have Enough Information to Construct the Multi-Labeled Phylogenetic Tree?

The evolutionary history of certain species such as polyploids are modeled by a generalization of phylogenetic trees called multi-labeled phylogenetic trees, or MUL trees for short. One problem that relates to inferring a MUL tree is how to construct the smallest possible MUL tree that is consistent with a given set of rooted triplets, or SMRT problem for short. This problem is NP-hard. There is one algorithm for the SMRT problem which is exact and runs in time, where is the number of taxa. In this paper, we show that the SMRT does not seem to be an appropriate solution from the biological point of view. Indeed, we present a heuristic algorithm named MTRT for this problem and execute it on some real and simulated datasets. The results of MTRT show that triplets alone cannot provide enough information to infer the true MUL tree. So, it is inappropriate to infer a MUL tree using triplet information alone and considering the minimum number of duplications. Finally, we introduce some new problems which are more suitable from the biological point of view.     

Computing phylogenetic diversity for split systems

In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size n. We show that for general split systems this problem is NP-hard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal O(n) time algorithm for phylogenetic trees and an O(n log n + nk) time algorithm for choosing an optimal subset of size k relative to a circular split system.     

Inferring phylogenetic relationships avoiding forbidden rooted triplets

To construct a phylogenetic tree or phylogenetic network for describing the evolutionary history of a set of species is a well-studied problem in computational biology. One previously proposed method to infer a phylogenetic tree/network for a large set of species is by merging a collection of known smaller phylogenetic trees on overlapping sets of species so that no (or as little as possible) branching information is lost. However, little work has been done so far on inferring a phylogenetic tree/network from a specified set of trees when in addition, certain evolutionary relationships among the species are known to be highly unlikely. In this paper, we consider the problem of constructing a phylogenetic tree/network which is consistent with all of the rooted triplets in a given set C and none of the rooted triplets in another given set F. Although NP-hard in the general case, we provide some efficient exact and approximation algorithms for a number of biologically meaningful variants of the problem.     

Phylogenetic Networks that Display a Tree Twice

In the last decade, the use of phylogenetic networks to analyze the evolution of species whose past is likely to include reticulation events, such as horizontal gene transfer or hybridization, has gained popularity among evolutionary biologists. Nevertheless, the evolution of a particular gene can generally be described without reticulation events and therefore be represented by a phylogenetic tree. While this is not in contrast to each other, it places emphasis on the necessity of algorithms that analyze and summarize the tree-like information that is contained in a phylogenetic network. We contribute to the toolbox of such algorithms by investigating the question of whether or not a phylogenetic network embeds a tree twice and give a quadratic-time algorithm to solve this problem for a class of networks that is more general than tree-child networks.     

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.     

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.     

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.     

A practical algorithm for reconstructing level-1 phylogenetic networks

Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks--a type of network slightly more general than a phylogenetic tree--from triplets. Our algorithm has been made publicly available as the program LEV1ATHAN. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, LEV1ATHAN runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of LEV1ATHAN is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that LEV1ATHAN is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise.     

Neutral biodiversity theory can explain the imbalance of phylogenetic trees but not the tempo of their diversification

Numerous evolutionary studies have sought to explain the distribution of diversity across the limbs of the tree of life. At the same time, ecological studies have sought to explain differences in diversity and relative abundance within and among ecological communities. Traditionally, these patterns have been considered separately, but models that consider processes operating at the level of individuals, such as neutral biodiversity theory (NBT), can provide a link between them. Here, we compare evolutionary dynamics across a suite of NBT models. We show that NBT can yield phylogenetic tree topologies with imbalance closely resembling empirical observations. In general, metacommunities that exhibit greater disparity in abundance are characterized by more imbalanced phylogenetic trees. However, NBT fails to capture the tempo of diversification as represented by the distribution of branching events through time. We suggest that population-level processes might therefore help explain the asymmetry of phylogenetic trees, but that tree shape might mislead estimates of evolutionary rates unless the diversification process is modeled explicitly.     

High-resolution phylogeny for Helianthus (Asteraceae) using the 18S-26S ribosomal DNA external transcribed spacer

The sunflower genus, Helianthus, is recognized widely for the cultivated sunflower H. annuus and scientifically as a model organism for studying diploid and polyploid hybrid speciation, introgression, and genetic architecture. A resolved phylogeny for the genus is essential for the advancement of these scientific areas. In the past, phylogenetic relationships of the perennial species and polyploid hybrids have been particularly difficult to resolve. Using the external transcribed spacer region of the nuclear 18S-26S rDNA region, we reveal for the first time a highly resolved gene tree for Helianthus. Phylogenetic analysis allowed the determination of a monophyletic annual H. sect. Helianthus, a two-lineage polyphyletic H. sect. Ciliares, and the monotypic H. sect. Agrestis, all of which were nested within a large perennial and polyphyletic H. sect. Divaricati. The distribution of perennial polyploids and known annual diploid hybrids on this phylogeny suggested multiple independent hybrid speciation events that gave rise to at least four polyploids and three diploid hybrids. Also provided by this phylogeny was evidence for homoploid hybrid speciation outside H. sect. Helianthus. Finally, previous hypotheses about the secondary chemistry in the genus were tested in a phylogenetic framework to obtain a better understanding of the evolution of these compounds in Helianthus.     

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.     

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.     

Polyploidy in Asteraceae of the xerophytic scrub of the Ecological Reserve of the Pedregal of San Angel,Mexico City

Asteraceae species diversity is high in the xerophytic scrub of the Ecological Reserve of the Pedregal of San Angel (REPSA), located in the southern part of the Basin of the Valley of Mexico. Here we determined whether the frequency of polyploidy is high in the reserve, given the enhanced ability of polyploids to colonize new habitats. In addition, we compared the frequency of polyploidy in Asteraceae in the reserve with the frequency in three oceanic archipelagos and two continental areas in Mexico. This was done to see how the ‘virtual’ island of the open lava flow in the reserve compares with volcanic islands at different distances from source areas. Chromosome numbers for 75 species of Asteraceae were obtained from published literature. Based on the possession of three or more basic chromosome sets in a nucleus, 33% were polyploids. If taxa with haploid chromosome numbers of n ≥ 14 or n ≥ 11 were considered to be polyploids, the proportion of polyploids rose to 57 and 75%, respectively. When using a phylogenetic approach, the highest percentage of polyploids (84%) was obtained and it could be inferred whether they are palaeo‐ or neopolyploids; thus, we consider that this criterion better reflects the events of polyploidy in Asteraceae. A high frequency of polyploid species in Asteraceae in REPSA suggests that polyploids may have contributed to the species diversity and the vegetation structure of the xerophytic scrub of this reserve. © 2013 The Linnean Society of London, Botanical Journal of the Linnean Society, 2013, 173 , 211–229.     

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.     

Optimal, efficient reconstruction of phylogenetic networks with constrained recombination

A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not tree-like. In a seminal paper, Wang et al.(1) studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a "galled-tree". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.(1) is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree minimizing the number of recombinations is "essentially unique". We also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NP-hard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree. Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in general phylogenetic networks. This paper greatly extends the conference version that appears in an earlier work.(8) PowerPoint slides of the conference talk can be found at our website.(7).     

Polyploids with different origins and ancestors form a single sexual polyploid species

Polyploidization is one of the few mechanisms that can produce instantaneous speciation. Multiple origins of tetraploid lineages from the same two diploid progenitors are common, but here we report the first known instance of a single tetraploid species that originated repeatedly from at least three diploid ancestors. Parallel evolution of advertisement calls in tetraploid lineages of gray tree frogs has allowed these lineages to interbreed, resulting in a single sexually interacting polyploid species despite the separate origins of polyploids from different diploids. Speciation by polyploidization in these frogs has been the source of considerable debate, but the various published hypotheses have assumed that polyploids arose through either autopolyploidy or allopolyploidy of extant diploid species. We utilized molecular markers and advertisement calls to infer the origins of tetraploid gray tree frogs. Previous hypotheses did not sufficiently account for the observed data. Instead, we found that tetraploids originated multiple times from extant diploid gray tree frogs and two other, apparently extinct, lineages of tree frogs. Tetraploid lineages then merged through interbreeding to result in a single species. Thus, polyploid species may have complex origins, especially in systems in which isolating mechanisms (such as advertisement calls) are affected directly through hybridization and polyploidy.     

Constructing splits graphs

Phylogenetic trees correspond one-to-one to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetic algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4.     

Inferring phylogenetic networks by the maximum parsimony criterion: a case study

Horizontal gene transfer (HGT) may result in genes whose evolutionary histories disagree with each other, as well as with the species tree. In this case, reconciling the species and gene trees results in a network of relationships, known as the "phylogenetic network" of the set of species. A phylogenetic network that incorporates HGT consists of an underlying species tree that captures vertical inheritance and a set of edges which model the "horizontal" transfer of genetic material. In a series of papers, Nakhleh and colleagues have recently formulated a maximum parsimony (MP) criterion for phylogenetic networks, provided an array of computationally efficient algorithms and heuristics for computing it, and demonstrated its plausibility on simulated data. In this article, we study the performance and robustness of this criterion on biological data. Our findings indicate that MP is very promising when its application is extended to the domain of phylogenetic network reconstruction and HGT detection. In all cases we investigated, the MP criterion detected the correct number of HGT events required to map the evolutionary history of a gene data set onto the species phylogeny. Furthermore, our results indicate that the criterion is robust with respect to both incomplete taxon sampling and the use of different site substitution matrices. Finally, our results show that the MP criterion is very promising in detecting HGT in chimeric genes, whose evolutionary histories are a mix of vertical and horizontal evolution. Besides the performance analysis of MP, our findings offer new insights into the evolution of 4 biological data sets and new possible explanations of HGT scenarios in their evolutionary history.