Computational approaches to species phylogeny inference and gene tree reconciliation

Gene tree species tree reconciliation with gene conversion

Gene tree/species tree reconciliation is a recent decisive progress in phylogenetic methods, accounting for the possible differences between gene histories and species histories. Reconciliation consists in explaining these differences by gene-scale events such as duplication, loss, transfer, which translates mathematically into a mapping between gene tree nodes and species tree nodes or branches. Gene conversion is a frequent and important evolutionary event, which results in the replacement of a gene by a copy of another from the same species and in the same gene tree. Including this event in reconciliation models has never been attempted because it introduces a dependency between lineages, and standard algorithms based on dynamic programming become ineffective. We propose here a novel mathematical framework including gene conversion as an evolutionary event in gene tree/species tree reconciliation. We describe a randomized algorithm that finds, in polynomial running time, a reconciliation minimizing the number of duplications, losses and conversions in the case when their weights are equal. We show that the space of optimal reconciliations includes an analog of the last common ancestor reconciliation, but is not limited to it. Our algorithm outputs any optimal reconciliation with a non-null probability. We argue that this study opens a research avenue on including gene conversion in reconciliation, and discuss its possible importance in biology.

Evolutionary Relationships Between the Laccase Genes of Polyporales: Orthology-Based Classification of Laccase Isozymes and Functional Insight From Trametes hirsuta

Laccase is one of the oldest known and intensively studied fungal enzymes capable of oxidizing recalcitrant lignin-resembling phenolic compounds. It is currently well established that fungal genomes almost always contain several non-allelic copies of laccase genes (laccase multigene families); nevertheless, many aspects of laccase multigenicity, for example, their precise biological functions or evolutionary relationships, are mostly unknown. Here, we present a detailed evolutionary analysis of the sensu stricto laccase genes (CAZy - AA1_1) from fungi of the Polyporales order. The conducted analysis provides a better understanding of the Polyporales laccase multigenicity and allows for the systemization of the individual features of different laccase isozymes. In addition, we provide a comparison of the biochemical and catalytic properties of the four laccase isozymes from Trametes hirsuta and suggest their functional diversification within the multigene family.

Guidelines for Inferring and Characterizing a Family of Bacterial trans-Acting Small Noncoding RNAs

So far, every sequenced bacterial transcriptome encompasses hundreds of small regulatory noncoding RNAs (sRNAs). From those sRNAs that have been already characterized, we learned that their regulatory functions could span over almost every bacterial process, mostly acting at the posttranscriptional control of gene expression (Wagner and Romby, Adv Genet 90:133-208, 2015). Canonical molecular mechanisms of sRNA action have been described to rely on both sequence and/or structural traits of the RNA molecule. As for protein-coding genes, the conservation of sRNAs among species suggests conserved and adjusted functions across evolution. Knowing the phylogenetic distribution of an sRNA gene and how its functional traits have evolved may help to get a broad picture of its biological role in each single species. Here, we present a simple computational workflow to identify close and distant sRNA homologs present in sequenced bacterial genomes, which allows defining novel sRNA families. This strategy is based on the use of Covariance Models (CM) and assumes the conservation of sequence and structure of functional sRNA genes throughout evolution. Moreover, by carefully inspecting the conservation of the close genomic context of every member of the RNA family and how the patterns of microsynteny follow the path of species evolution, it is possible to define subgroups of sRNA orthologs, which in turn enables the definition of RNA subfamilies.

Variation Across Mitochondrial Gene Trees Provides Evidence for Systematic Error: How Much Gene Tree Variation Is Biological?

The use of large genomic data sets in phylogenetics has highlighted extensive topological variation across genes. Much of this discordance is assumed to result from biological processes. However, variation among gene trees can also be a consequence of systematic error driven by poor model fit, and the relative importance of biological vs. methodological factors in explaining gene tree variation is a major unresolved question. Using mitochondrial genomes to control for biological causes of gene tree variation, we estimate the extent of gene tree discordance driven by systematic error and employ posterior prediction to highlight the role of model fit in producing this discordance. We find that the amount of discordance among mitochondrial gene trees is similar to the amount of discordance found in other studies that assume only biological causes of variation. This similarity suggests that the role of systematic error in generating gene tree variation is underappreciated and critical evaluation of fit between assumed models and the data used for inference is important for the resolution of unresolved phylogenetic questions.

Genomic study of a novel magnetotactic Alphaproteobacteria uncovers the multiple ancestry of magnetotaxis

Ecological and evolutionary processes involved in magnetotactic bacteria (MTB) adaptation to their environment have been a matter of debate for many years. Ongoing efforts for their characterization are progressively contributing to understand these processes, including the genetic and molecular mechanisms responsible for biomineralization. Despite numerous culture-independent MTB characterizations, essentially within the Proteobacteria phylum, only few species have been isolated in culture because of their complex growth conditions. Here, we report a newly cultivated magnetotactic, microaerophilic and chemoorganoheterotrophic bacterium isolated from the Mediterranean Sea in Marseille, France: Candidatus Terasakiella magnetica strain PR-1 that belongs to an Alphaproteobacteria genus with no magnetotactic relative. By comparing the morphology and the whole genome shotgun sequence of this MTB with those of closer relatives, we brought further evidence that the apparent vertical ancestry of magnetosome genes suggested by previous studies within Alphaproteobacteria hides a more complex evolutionary history involving horizontal gene transfers and/or duplication events before and after the emergence of Magnetospirillum, Magnetovibrio and Magnetospira genera. A genome-scale comparative genomics analysis identified several additional candidate functions and genes that could be specifically associated to MTB lifestyle in this class of bacteria.

S-Cluster++: a fast program for solving the cluster containment problem for phylogenetic networks

Motivation

Comparative genomic studies indicate that extant genomes are more properly considered to be a fusion product of random mutations over generations (vertical evolution) and genomic material transfers between individuals of different lineages (reticulate transfer). This has motivated biologists to use phylogenetic networks and other general models to study genome evolution. Two fundamental algorithmic problems arising from verification of phylogenetic networks and from computing Robinson-Foulds distance in the space of phylogenetic networks are the tree and cluster containment problems. The former asks how to decide whether or not a phylogenetic tree is displayed in a phylogenetic network. The latter is to decide whether a subset of taxa appears as a cluster in some tree displayed in a phylogenetic network. The cluster containment problem (CCP) is also closely related to testing the infinite site model on a recombination network. Both the tree containment and CCP are NP-complete. Although the CCP was introduced a decade ago, there has been little progress in developing fast algorithms for it on arbitrary phylogenetic networks.

Results

In this work, we present a fast computer program for the CCP. This program is developed on the basis of a linear-time transformation from the small version of the CCP to the SAT problem.

Availability and implementation

The program package is available for download on http://www.math.nus.edu.sg/∼matzlx/ccp.

ALPHA: a toolkit for Automated Local PHylogenomic Analyses

Summary

The evolutionary histories of individual regions across a genomic alignment-called 'local genealogies'-can differ from each other, due to processes such as recombination. Elucidating and analyzing these local genealogies are important for a large number of inference tasks, including those pertaining to species phylogenies, evolutionary processes and trait mapping. In this paper, we present a toolkit for automated local phylogenomic analyses, or ALPHA. The purpose of this toolkit is to provide a wide array of functionalities for automated inference of local genealogies as well as analyses based on these local genealogies. The toolkit uses sliding windows to construct local genealogies and can compute a wide array of local phylogeny based statistics, such as the D-statistic. The toolkit comes with a graphical user interface and several import/export functionalities. Over the last few decades, much emphasis in phylogenomics has been put on developing tools for inferring species phylogenies. This toolkit complements those efforts by emphasizing the 'local' aspect of phylogenomics.

Availability and implementation

ALPHA is freely available for installation and use, including source code, at https://github.com/chilleo/ALPHA.

Embracing Uncertainty in Reconstructing Early Animal Evolution

The origin of animals, one of the major transitions in evolution, remains mysterious. Many key aspects of animal evolution can be reconstructed by comparing living species within a robust phylogenetic framework. However, uncertainty remains regarding the evolutionary relationships between two ancient animal lineages - sponges and ctenophores - and the remaining animal phyla. Comparative morphology and some phylogenomic analyses support the view that sponges represent the sister lineage to the rest of the animals, while other phylogenomic analyses support ctenophores, a phylum of carnivorous, gelatinous marine organisms, as the sister lineage. Here, we explore why different studies yield different answers and discuss the implications of the two alternative hypotheses for understanding the origin of animals. Reconstruction of ancient evolutionary radiations is devilishly difficult and will likely require broader sampling of sponge and ctenophore genomes, improved analytical strategies and critical analyses of the phylogenetic distribution and molecular mechanisms underlying apparently conserved traits. Rather than staking out positions in favor of the ctenophores-sister or the sponges-sister hypothesis, we submit that research programs aimed at understanding the biology of the first animals should instead embrace the uncertainty surrounding early animal evolution in their experimental designs.

Inferring duplication episodes from unrooted gene trees

Background

One of evolutionary molecular biology fundamental issues is to discover genomic duplication events and their correspondence to the species tree. Such events can be reconstructed by clustering single gene duplications inferred by reconciling a set of gene trees with a species tree.

Results

Here we propose the first solutions to the genomic duplication problem in which every reconciliation with the minimal number of single gene duplications is allowed and the method of clustering called minimum episodes under the assumption that input gene trees are unrooted.

Conclusions

We showed new theoretical properties of unrooted reconciliation for the duplication cost and apply them to design several exact and heuristic algorithms for solving the problem. Our evaluation study on empirical dataset confirmed several genomic duplication events from the literature and demonstrate that algorithms can be successfully applied.

Why Concatenation Fails Near the Anomaly Zone

Genome-scale sequencing has been of great benefit in recovering species trees but has not provided final answers. Despite the rapid accumulation of molecular sequences, resolving short and deep branches of the tree of life has remained a challenge and has prompted the development of new strategies that can make the best use of available data. One such strategy-the concatenation of gene alignments-can be successful when coupled with many tree estimation methods, but has also been shown to fail when there are high levels of incomplete lineage sorting. Here, we focus on the failure of likelihood-based methods in retrieving a rooted, asymmetric four-taxon species tree from concatenated data when the species tree is in or near the anomaly zone-a region of parameter space where the most common gene tree does not match the species tree because of incomplete lineage sorting. First, we use coalescent theory to prove that most informative sites will support the species tree in the anomaly zone, and that as a consequence maximum-parsimony succeeds in recovering the species tree from concatenated data. We further show that maximum-likelihood tree estimation from concatenated data fails both inside and outside the anomaly zone, and that this failure cannot be easily predicted from the topology of the most common gene tree. We demonstrate that likelihood-based methods often fail in a region partially overlapping the anomaly zone, likely because of the lower relative cost of substitutions on discordant gene tree branches that are absent from the species tree. Our results confirm and extend previous reports on the performance of these methods applied to concatenated data from a rooted, asymmetric four-taxon species tree, and highlight avenues for future work improving the performance of methods aimed at recovering species tree.

Accounting for Uncertainty in Gene Tree Estimation: Summary-Coalescent Species Tree Inference in a Challenging Radiation of Australian Lizards

Accurate gene tree inference is an important aspect of species tree estimation in a summary-coalescent framework. Yet, in empirical studies, inferred gene trees differ in accuracy due to stochastic variation in phylogenetic signal between targeted loci. Empiricists should, therefore, examine the consistency of species tree inference, while accounting for the observed heterogeneity in gene tree resolution of phylogenomic data sets. Here, we assess the impact of gene tree estimation error on summary-coalescent species tree inference by screening ${\sim}2000$ exonic loci based on gene tree resolution prior to phylogenetic inference. We focus on a phylogenetically challenging radiation of Australian lizards (genus Cryptoblepharus, Scincidae) and explore effects on topology and support. We identify a well-supported topology based on all loci and find that a relatively small number of high-resolution gene trees can be sufficient to converge on the same topology. Adding gene trees with decreasing resolution produced a generally consistent topology, and increased confidence for specific bipartitions that were poorly supported when using a small number of informative loci. This corroborates coalescent-based simulation studies that have highlighted the need for a large number of loci to confidently resolve challenging relationships and refutes the notion that low-resolution gene trees introduce phylogenetic noise. Further, our study also highlights the value of quantifying changes in nodal support across locus subsets of increasing size (but decreasing gene tree resolution). Such detailed analyses can reveal anomalous fluctuations in support at some nodes, suggesting the possibility of model violation. By characterizing the heterogeneity in phylogenetic signal among loci, we can account for uncertainty in gene tree estimation and assess its effect on the consistency of the species tree estimate. We suggest that the evaluation of gene tree resolution should be incorporated in the analysis of empirical phylogenomic data sets. This will ultimately increase our confidence in species tree estimation using summary-coalescent methods and enable us to exploit genomic data for phylogenetic inference. [Coalescence; concatenation; Cryptoblepharus; exon capture; gene tree; phylogenomics; species tree.].

Displayed Trees Do Not Determine Distinguishability Under the Network Multispecies Coalescent

Recent work in estimating species relationships from gene trees has included inferring networks assuming that past hybridization has occurred between species. Probabilistic models using the multispecies coalescent can be used in this framework for likelihood-based inference of both network topologies and parameters, including branch lengths and hybridization parameters. A difficulty for such methods is that it is not always clear whether, or to what extent, networks are identifiable-that is whether there could be two distinct networks that lead to the same distribution of gene trees. For cases in which incomplete lineage sorting occurs in addition to hybridization, we demonstrate a new representation of the species network likelihood that expresses the probability distribution of the gene tree topologies as a linear combination of gene tree distributions given a set of species trees. This representation makes it clear that in some cases in which two distinct networks give the same distribution of gene trees when sampling one allele per species, the two networks can be distinguished theoretically when multiple individuals are sampled per species. This result means that network identifiability is not only a function of the trees displayed by the networks but also depends on allele sampling within species. We additionally give an example in which two networks that display exactly the same trees can be distinguished from their gene trees even when there is only one lineage sampled per species. [gene tree, hybridization, identifiability, maximum likelihood, species tree, phylogeny.].

Gene flow analysis method, the D-statistic, is robust in a wide parameter space

Background

We evaluated the sensitivity of the D-statistic, a parsimony-like method widely used to detect gene flow between closely related species. This method has been applied to a variety of taxa with a wide range of divergence times. However, its parameter space and thus its applicability to a wide taxonomic range has not been systematically studied. Divergence time, population size, time of gene flow, distance of outgroup and number of loci were examined in a sensitivity analysis.

Result

The sensitivity study shows that the primary determinant of the D-statistic is the relative population size, i.e. the population size scaled by the number of generations since divergence. This is consistent with the fact that the main confounding factor in gene flow detection is incomplete lineage sorting by diluting the signal. The sensitivity of the D-statistic is also affected by the direction of gene flow, size and number of loci. In addition, we examined the ability of the f-statistics, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\widehat{f}}_G $$\end{document}f^G and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\widehat{f}}_{hom} $$\end{document}f^hom, to estimate the fraction of a genome affected by gene flow; while these statistics are difficult to implement to practical questions in biology due to lack of knowledge of when the gene flow happened, they can be used to compare datasets with identical or similar demographic background.

Conclusions

The D-statistic, as a method to detect gene flow, is robust against a wide range of genetic distances (divergence times) but it is sensitive to population size. The D-statistic should only be applied with critical reservation to taxa where population sizes are large relative to branch lengths in generations.

Electronic supplementary material

The online version of this article (10.1186/s12859-017-2002-4) contains supplementary material, which is available to authorized users.

Comparative Methods for Reconstructing Ancient Genome Organization

Comparative genomics considers the detection of similarities and differences between extant genomes, and, based on more or less formalized hypotheses regarding the involved evolutionary processes, inferring ancestral states explaining the similarities and an evolutionary history explaining the differences. In this chapter, we focus on the reconstruction of the organization of ancient genomes into chromosomes. We review different methodological approaches and software, applied to a wide range of datasets from different kingdoms of life and at different evolutionary depths. We discuss relations with genome assembly, and potential approaches to validate computational predictions on ancient genomes that are almost always only accessible through these predictions.

Phylogenomics

Phylogenomics aims at reconstructing the evolutionary histories of organisms taking into account whole genomes or large fractions of genomes. The abundance of genomic data for an enormous variety of organisms has enabled phylogenomic inference of many groups, and this has motivated the development of many computer programs implementing the associated methods. This chapter surveys phylogenetic concepts and methods aimed at both gene tree and species tree reconstruction while also addressing common pitfalls, providing references to relevant computer programs. A practical phylogenomic analysis example including bacterial genomes is presented at the end of the chapter.

Xenolog classification

Motivation

Orthology analysis is a fundamental tool in comparative genomics. Sophisticated methods have been developed to distinguish between orthologs and paralogs and to classify paralogs into subtypes depending on the duplication mechanism and timing, relative to speciation. However, no comparable framework exists for xenologs: gene pairs whose history, since their divergence, includes a horizontal transfer. Further, the diversity of gene pairs that meet this broad definition calls for classification of xenologs with similar properties into subtypes.

Results

We present a xenolog classification that uses phylogenetic reconciliation to assign each pair of genes to a class based on the event responsible for their divergence and the historical association between genes and species. Our classes distinguish between genes related through transfer alone and genes related through duplication and transfer. Further, they separate closely-related genes in distantly-related species from distantly-related genes in closely-related species. We present formal rules that assign gene pairs to specific xenolog classes, given a reconciled gene tree with an arbitrary number of duplications and transfers. These xenology classification rules have been implemented in software and tested on a collection of ∼13 000 prokaryotic gene families. In addition, we present a case study demonstrating the connection between xenolog classification and gene function prediction.

Availability and Implementation

The xenolog classification rules have been implemented in N otung 2.9, a freely available phylogenetic reconciliation software package. http://www.cs.cmu.edu/~durand/Notung . Gene trees are available at http://dx.doi.org/10.7488/ds/1503 .

Contact

durand@cmu.edu.

Supplementary information

Supplementary data are available at Bioinformatics online.

Reticulation, divergence, and the phylogeography-phylogenetics continuum

Phylogeography, and its extensions into comparative phylogeography, have their roots in the layering of gene trees across geography, a paradigm that was greatly facilitated by the nonrecombining, fast evolution provided by animal mtDNA. As phylogeography moves into the era of next-generation sequencing, the specter of reticulation at several levels-within loci and genomes in the form of recombination and across populations and species in the form of introgression-has raised its head with a prominence even greater than glimpsed during the nuclear gene PCR era. Here we explore the theme of reticulation in comparative phylogeography, speciation analysis, and phylogenomics, and ask how the centrality of gene trees has fared in the next-generation era. To frame these issues, we first provide a snapshot of multilocus phylogeographic studies across the Carpentarian Barrier, a prominent biogeographic barrier dividing faunas spanning the monsoon tropics in northern Australia. We find that divergence across this barrier is evident in most species, but is heterogeneous in time and demographic history, often reflecting the taxonomic distinctness of lineages spanning it. We then discuss a variety of forces generating reticulate patterns in phylogeography, including introgression, contact zones, and the potential selection-driven outliers on next-generation molecular markers. We emphasize the continued need for demographic models incorporating reticulation at the level of genomes and populations, and conclude that gene trees, whether explicit or implicit, should continue to play a role in the future of phylogeography.

Phylogenomics reveals a complex evolutionary history of lobed-leaf white oaks in western North America

Species within the genus Quercus (oak) hybridize in complex patterns that have yet to be fully explored with phylogenomic data. Analyses to date have recovered reasonable divergent patterns, suggesting that the impact of introgression may not always be obvious in inferred oak phylogenies. We explore this phenomenon using RADseq data for 136 samples representing 54 oak species by conducting phylogenetic analyses designed to distinguish signals of lineage diversification and hybridization, focusing on the lobed-leaf species Quercus gambelii, Q. lobata, and Q. garryana in the context of a broad sampling of allied white oaks (Quercus section Quercus), and particularly the midwestern Q. macrocarpa. We demonstrate that historical introgressive hybridization between once sympatric species affects phylogeny estimation. Historical range expansion during periods of favorable climate likely explains our observations; analyses support genetic exchange between ancestral populations of Q. gambelii and Q. macrocarpa. We conclude that the genomic consequences of introgression caused the attraction of distant lineages in phylogenetic tree space, and that introgressive and divergent signals can be disentangled to produce a robust estimate of the phylogenetic history of the species.

IDXL: Species Tree Inference Using Internode Distance and Excess Gene Leaf Count

We propose an extension of the distance matrix methods NJst and ASTRID to infer species trees from incongruent gene trees having Incomplete Lineage Sorting. Both approaches consider the average internode distance (ID) between individual taxa pairs as the distance measure. The measure ID does not use the root of a tree, and thus may not always infer the relative position of a taxon with respect to the root. We define a novel distance measure excess gene leaf count (XL) between individual couplets. The XL measure is computed using the root of a tree. It is proved to be additive, and is shown to infer the relative order of divergence among individual couplets better. We propose a novel method IDXL which uses both the XL and ID measures for species tree construction. IDXL is shown to perform better than NJst and other distance matrix approaches for most of the biological and simulated datasets. Having the same computational complexity as NJst, IDXL can be applied for species tree inference on large-scale biological datasets.

Rapid radiations of both kiwifruit hybrid lineages and their parents shed light on a two-layer mode of species diversification

Reticulate speciation caused by interspecific hybridization is now recognized as an important mechanism in the creation of biological diversity. However, depicting the patterns of phylogenetic networks for lineages that have undergone interspecific gene flow is challenging. Here we sequenced 25 taxa representing natural diversity in the genus Actinidia with an average mapping depth of 26× on the reference genome to reconstruct their reticulate history. We found evidence, including significant gene tree discordance, cytonuclear conflicts, and changes in genome-wide heterozygosity across taxa, collectively supporting extensive reticulation in the genus. Furthermore, at least two separate parental species pairs were involved in the repeated origin of the hybrid lineages, in some of which a further phase of syngameon was triggered. On the basis of the elucidated hybridization relationships, we obtained a highly resolved backbone phylogeny consisting of taxa exhibiting no evidence of hybrid origin. The backbone taxa have distinct demographic histories and are the product of recent rounds of rapid radiations via sorting of ancestral variation under variable climatic and ecological conditions. Our results suggest a mode for consecutive plant diversification through two layers of radiations, consisting of the rapid evolution of backbone lineages and the formation of hybrid swarms derived from these lineages.

The evolutionary history of bears is characterized by gene flow across species

Bears are iconic mammals with a complex evolutionary history. Natural bear hybrids and studies of few nuclear genes indicate that gene flow among bears may be more common than expected and not limited to polar and brown bears. Here we present a genome analysis of the bear family with representatives of all living species. Phylogenomic analyses of 869 mega base pairs divided into 18,621 genome fragments yielded a well-resolved coalescent species tree despite signals for extensive gene flow across species. However, genome analyses using different statistical methods show that gene flow is not limited to closely related species pairs. Strong ancestral gene flow between the Asiatic black bear and the ancestor to polar, brown and American black bear explains uncertainties in reconstructing the bear phylogeny. Gene flow across the bear clade may be mediated by intermediate species such as the geographically wide-spread brown bears leading to large amounts of phylogenetic conflict. Genome-scale analyses lead to a more complete understanding of complex evolutionary processes. Evidence for extensive inter-specific gene flow, found also in other animal species, necessitates shifting the attention from speciation processes achieving genome-wide reproductive isolation to the selective processes that maintain species divergence in the face of gene flow.

Contentious relationships in phylogenomic studies can be driven by a handful of genes

Phylogenomic studies have resolved countless branches of the tree of life, but remain strongly contradictory on certain, contentious relationships. Here, we use a maximum likelihood framework to quantify the distribution of phylogenetic signal among genes and sites for 17 contentious branches and 6 well-established control branches in plant, animal and fungal phylogenomic data matrices. We find that resolution in some of these 17 branches rests on a single gene or a few sites, and that removal of a single gene in concatenation analyses or a single site from every gene in coalescence-based analyses diminishes support and can alter the inferred topology. These results suggest that tiny subsets of very large data matrices drive the resolution of specific internodes, providing a dissection of the distribution of support and observed incongruence in phylogenomic analyses. We submit that quantifying the distribution of phylogenetic signal in phylogenomic data is essential for evaluating whether branches, especially contentious ones, are truly resolved. Finally, we offer one detailed example of such an evaluation for the controversy regarding the earliest-branching metazoan phylum, for which examination of the distributions of gene-wise and site-wise phylogenetic signal across eight data matrices consistently supports ctenophores as the sister group to all other metazoans.

Deep reticulation and incomplete lineage sorting obscure the diploid phylogeny of rain-lilies and allies (Amaryllidaceae tribe Hippeastreae)

Hybridization is a frequent and important force in plant evolution. Next-generation sequencing (NGS) methods offer new possibilities for clade resolution and ambitious sampling of gene genealogies, yet difficulty remains in detecting deep reticulation events using currently available methods. We reconstructed the phylogeny of diploid representatives of Amaryllidaceae tribe Hippeastreae to test the hypothesis of ancient hybridizations preceding the radiation of its major subclade, Hippeastrinae. Through hybrid enrichment of DNA libraries and NGS, we obtained data for 18 nuclear loci through a curated assembly approach and nearly complete plastid genomes for 35 ingroup taxa plus 5 outgroups. Additionally, we obtained alignments for 39 loci through an automated assembly algorithm. These data were analyzed with diverse phylogenetic methods, including concatenation, coalescence-based species tree estimation, Bayesian concordance analysis, and network reconstructions, to provide insights into the evolutionary relationships of Hippeastreae. Causes for gene tree heterogeneity and cytonuclear discordance were examined through a Bayesian posterior predictive approach (JML) and coalescent simulations. Two major clades were found, Hippeastrinae and Traubiinae, as previously reported. Our results suggest the presence of two major nuclear lineages in Hippeastrinae characterized by different chromosome numbers: (1) Tocantinia and Hippeastrum with 2n=22, and (2) Eithea, Habranthus, Rhodophiala, and Zephyranthes mostly with 2n=12, 14, and 18. Strong cytonuclear discordance was confirmed in Hippeastrinae, and a network scenario with at least six hybridization events is proposed to reconcile nuclear and plastid signals, along a backbone that may also have been affected by incomplete lineage sorting at the base of each major subclade.

Simulation-Based Evaluation of Hybridization Network Reconstruction Methods in the Presence of Incomplete Lineage Sorting

Hybridization events generate reticulate species relationships, giving rise to species networks rather than species trees. We report a comparative study of consensus, maximum parsimony, and maximum likelihood methods of species network reconstruction using gene trees simulated assuming a known species history. We evaluate the role of the divergence time between species involved in a hybridization event, the relative contributions of the hybridizing species, and the error in gene tree estimation. When gene tree discordance is mostly due to hybridization and not due to incomplete lineage sorting (ILS), most of the methods can detect even highly skewed hybridization events between highly divergent species. For recent divergences between hybridizing species, when the influence of ILS is sufficiently high, likelihood methods outperform parsimony and consensus methods, which erroneously identify extra hybridizations. The more sophisticated likelihood methods, however, are affected by gene tree errors to a greater extent than are consensus and parsimony.

The mitochondrial genome sequences of the round goby and the sand goby reveal patterns of recent evolution in gobiid fish

Background

Vertebrate mitochondrial genomes are optimized for fast replication and low cost of RNA expression. Accordingly, they are devoid of introns, are transcribed as polycistrons and contain very little intergenic sequences. Usually, vertebrate mitochondrial genomes measure between 16.5 and 17 kilobases (kb).

Results

During genome sequencing projects for two novel vertebrate models, the invasive round goby and the sand goby, we found that the sand goby genome is exceptionally small (16.4 kb), while the mitochondrial genome of the round goby is much larger than expected for a vertebrate. It is 19 kb in size and is thus one of the largest fish and even vertebrate mitochondrial genomes known to date. The expansion is attributable to a sequence insertion downstream of the putative transcriptional start site. This insertion carries traces of repeats from the control region, but is mostly novel. To get more information about this phenomenon, we gathered all available mitochondrial genomes of Gobiidae and of nine gobioid species, performed phylogenetic analyses, analysed gene arrangements, and compared gobiid mitochondrial genome sizes, ecological information and other species characteristics with respect to the mitochondrial phylogeny. This allowed us amongst others to identify a unique arrangement of tRNAs among Ponto-Caspian gobies.

Conclusions

Our results indicate that the round goby mitochondrial genome may contain novel features. Since mitochondrial genome organisation is tightly linked to energy metabolism, these features may be linked to its invasion success. Also, the unique tRNA arrangement among Ponto-Caspian gobies may be helpful in studying the evolution of this highly adaptive and invasive species group. Finally, we find that the phylogeny of gobiids can be further refined by the use of longer stretches of linked DNA sequence.

Electronic supplementary material

The online version of this article (doi:10.1186/s12864-017-3550-8) contains supplementary material, which is available to authorized users.

Chromosomal Speciation in the Genomics Era: Disentangling Phylogenetic Evolution of Rock-wallabies

The association of chromosome rearrangements (CRs) with speciation is well established, and there is a long history of theory and evidence relating to "chromosomal speciation." Genomic sequencing has the potential to provide new insights into how reorganization of genome structure promotes divergence, and in model systems has demonstrated reduced gene flow in rearranged segments. However, there are limits to what we can understand from a small number of model systems, which each only tell us about one episode of chromosomal speciation. Progressing from patterns of association between chromosome (and genic) change, to understanding processes of speciation requires both comparative studies across diverse systems and integration of genome-scale sequence comparisons with other lines of evidence. Here, we showcase a promising example of chromosomal speciation in a non-model organism, the endemic Australian marsupial genus Petrogale. We present initial phylogenetic results from exon-capture that resolve a history of divergence associated with extensive and repeated CRs. Yet it remains challenging to disentangle gene tree heterogeneity caused by recent divergence and gene flow in this and other such recent radiations. We outline a way forward for better integration of comparative genomic sequence data with evidence from molecular cytogenetics, and analyses of shifts in the recombination landscape and potential disruption of meiotic segregation and epigenetic programming. In all likelihood, CRs impact multiple cellular processes and these effects need to be considered together, along with effects of genic divergence. Understanding the effects of CRs together with genic divergence will require development of more integrative theory and inference methods. Together, new data and analysis tools will combine to shed light on long standing questions of how chromosome and genic divergence promote speciation.

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.

A scalability study of phylogenetic network inference methods using empirical datasets and simulations involving a single reticulation

BACKGROUND

Branching events in phylogenetic trees reflect bifurcating and/or multifurcating speciation and splitting events. In the presence of gene flow, a phylogeny cannot be described by a tree but is instead a directed acyclic graph known as a phylogenetic network. Both phylogenetic trees and networks are typically reconstructed using computational analysis of multi-locus sequence data. The advent of high-throughput sequencing technologies has brought about two main scalability challenges: (1) dataset size in terms of the number of taxa and (2) the evolutionary divergence of the taxa in a study. The impact of both dimensions of scale on phylogenetic tree inference has been well characterized by recent studies; in contrast, the scalability limits of phylogenetic network inference methods are largely unknown.

RESULTS

In this study, we quantify the performance of state-of-the-art phylogenetic network inference methods on large-scale datasets using empirical data sampled from natural mouse populations and a range of simulations using model phylogenies with a single reticulation. We find that, as in the case of phylogenetic tree inference, the performance of leading network inference methods is negatively impacted by both dimensions of dataset scale. In general, we found that topological accuracy degrades as the number of taxa increases; a similar effect was observed with increased sequence mutation rate. The most accurate methods were probabilistic inference methods which maximize either likelihood under coalescent-based models or pseudo-likelihood approximations to the model likelihood. The improved accuracy obtained with probabilistic inference methods comes at a computational cost in terms of runtime and main memory usage, which become prohibitive as dataset size grows past twenty-five taxa. None of the probabilistic methods completed analyses of datasets with 30 taxa or more after many weeks of CPU runtime.

CONCLUSIONS

We conclude that the state of the art of phylogenetic network inference lags well behind the scope of current phylogenomic studies. New algorithmic development is critically needed to address this methodological gap.

Colonization and diversification of aquatic insects on three Macaronesian archipelagos using 59 nuclear loci derived from a draft genome

The study of processes driving diversification requires a fully sampled and well resolved phylogeny, although a lack of phylogenetic markers remains a limitation for many non-model groups. Multilocus approaches to the study of recent diversification provide a powerful means to study the evolutionary process, but their application remains restricted because multiple unlinked loci with suitable variation for phylogenetic or coalescent analysis are not available for most non-model taxa. Here we identify novel, putative single-copy nuclear DNA (nDNA) phylogenetic markers to study the colonization and diversification of an aquatic insect species complex, Cloeon dipterum L. 1761 (Ephemeroptera: Baetidae), in Macaronesia. Whole-genome sequencing data from one member of the species complex were used to identify 59 nDNA loci (32,213 base pairs), followed by Sanger sequencing of 29 individuals sampled from 13 islands of three Macaronesian archipelagos. Multispecies coalescent analyses established six putative species. Three island species formed a monophyletic clade, with one species occurring on the Azores, Europe and North America. Ancestral state reconstruction indicated at least two colonization events from the mainland (to the Canaries, respectively Azores) and one within the archipelago (between Madeira and the Canaries). Random subsets of the 59 loci showed a positive linear relationship between number of loci and node support. In contrast, node support in the multispecies coalescent tree was negatively correlated with mean number of phylogenetically informative sites per locus, suggesting a complex relationship between tree resolution and marker variability. Our approach highlights the value of combining genomics, coalescent-based phylogeography, species delimitation, and phylogenetic reconstruction to resolve recent diversification events in an archipelago species complex.

A program for verification of phylogenetic network models

MOTIVATION

Genetic material is transferred in a non-reproductive manner across species more frequently than commonly thought, particularly in the bacteria kingdom. On one hand, extant genomes are thus more properly considered as a fusion product of both reproductive and non-reproductive genetic transfers. This has motivated researchers to adopt phylogenetic networks to study genome evolution. On the other hand, a gene's evolution is usually tree-like and has been studied for over half a century. Accordingly, the relationships between phylogenetic trees and networks are the basis for the reconstruction and verification of phylogenetic networks. One important problem in verifying a network model is determining whether or not certain existing phylogenetic trees are displayed in a phylogenetic network. This problem is formally called the tree containment problem. It is NP-complete even for binary phylogenetic networks.

RESULTS

We design an exponential time but efficient method for determining whether or not a phylogenetic tree is displayed in an arbitrary phylogenetic network. It is developed on the basis of the so-called reticulation-visible property of phylogenetic networks.

AVAILABILITY AND IMPLEMENTATION

A C-program is available for download on http://www.math.nus.edu.sg/∼matzlx/tcp_package

CONTACT

matzlx@nus.edu.sg

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

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.

Trees have long formed in biology the basic structure with which to represent and understand evolutionary relationships. Mathematical models, computational methods, and software tools for inferring phylogenetic trees and studying their mathematical properties are currently the norm in biology. The availability of genomic data from closely related species, as well as from multiple individuals within species, have brought the two fields of phylogenetics and population genetics closer than ever. In particular, the last two decades have witnessed a great flourish in the development and implementation of phylogenetic methods based on the multispecies coalescent model to capture the intricate relationship between gene and genome evolution. However, when reticulation processes such as hybridization occur, the phylogenetic history is best represented by a network. In this work, we demonstrate how the multispecies coalescent model can be adapted to reticulate evolutionary histories and report on a Bayesian method for inference of such histories under this extended model. As networks subsume trees, the model and method provide a principled and unified statistical framework for inferring treelike and non-treelike evolutionary relationships.

Population Genomic Analysis Reveals Differential Evolutionary Histories and Patterns of Diversity across Subgenomes and Subpopulations of Brassica napus L

The allotetraploid species Brassica napus L. is a global crop of major economic importance, providing canola oil (seed) and vegetables for human consumption and fodder and meal for livestock feed. Characterizing the genetic diversity present in the extant germplasm pool of B. napus is fundamental to better conserve, manage and utilize the genetic resources of this species. We used sequence-based genotyping to identify and genotype 30,881 SNPs in a diversity panel of 782 B. napus accessions, representing samples of winter and spring growth habits originating from 33 countries across Europe, Asia, and America. We detected strong population structure broadly concordant with growth habit and geography, and identified three major genetic groups: spring (SP), winter Europe (WE), and winter Asia (WA). Subpopulation-specific polymorphism patterns suggest enriched genetic diversity within the WA group and a smaller effective breeding population for the SP group compared to WE. Interestingly, the two subgenomes of B. napus appear to have different geographic origins, with phylogenetic analysis placing WE and WA as basal clades for the other subpopulations in the C and A subgenomes, respectively. Finally, we identified 16 genomic regions where the patterns of diversity differed markedly from the genome-wide average, several of which are suggestive of genomic inversions. The results obtained in this study constitute a valuable resource for worldwide breeding efforts and the genetic dissection and prediction of complex B. napus traits.

Consistency and inconsistency of consensus methods for inferring species trees from gene trees in the presence of ancestral population structure

In the last few years, several statistically consistent consensus methods for species tree inference have been devised that are robust to the gene tree discordance caused by incomplete lineage sorting in unstructured ancestral populations. One source of gene tree discordance that has only recently been identified as a potential obstacle for phylogenetic inference is ancestral population structure. In this article, we describe a general model of ancestral population structure, and by relying on a single carefully constructed example scenario, we show that the consensus methods Democratic Vote, STEAC, STAR, R(∗) Consensus, Rooted Triple Consensus, Minimize Deep Coalescences, and Majority-Rule Consensus are statistically inconsistent under the model. We find that among the consensus methods evaluated, the only method that is statistically consistent in the presence of ancestral population structure is GLASS/Maximum Tree. We use simulations to evaluate the behavior of the various consensus methods in a model with ancestral population structure, showing that as the number of gene trees increases, estimates on the basis of GLASS/Maximum Tree approach the true species tree topology irrespective of the level of population structure, whereas estimates based on the remaining methods only approach the true species tree topology if the level of structure is low. However, through simulations using species trees both with and without ancestral population structure, we show that GLASS/Maximum Tree performs unusually poorly on gene trees inferred from alignments with little information. This practical limitation of GLASS/Maximum Tree together with the inconsistency of other methods prompts the need for both further testing of additional existing methods and development of novel methods under conditions that incorporate ancestral population structure.

Reticulate evolutionary history and extensive introgression in mosquito species revealed by phylogenetic network analysis

The role of hybridization and subsequent introgression has been demonstrated in an increasing number of species. Recently, Fontaine et al. (Science, 347, 2015, 1258524) conducted a phylogenomic analysis of six members of the Anopheles gambiae species complex. Their analysis revealed a reticulate evolutionary history and pointed to extensive introgression on all four autosomal arms. The study further highlighted the complex evolutionary signals that the co-occurrence of incomplete lineage sorting (ILS) and introgression can give rise to in phylogenomic analyses. While tree-based methodologies were used in the study, phylogenetic networks provide a more natural model to capture reticulate evolutionary histories. In this work, we reanalyse the Anopheles data using a recently devised framework that combines the multispecies coalescent with phylogenetic networks. This framework allows us to capture ILS and introgression simultaneously, and forms the basis for statistical methods for inferring reticulate evolutionary histories. The new analysis reveals a phylogenetic network with multiple hybridization events, some of which differ from those reported in the original study. To elucidate the extent and patterns of introgression across the genome, we devise a new method that quantifies the use of reticulation branches in the phylogenetic network by each genomic region. Applying the method to the mosquito data set reveals the evolutionary history of all the chromosomes. This study highlights the utility of 'network thinking' and the new insights it can uncover, in particular in phylogenomic analyses of large data sets with extensive gene tree incongruence.

Histories of molecules: Reconciling the past

Molecular data and methods have become centrally important to evolutionary analysis, largely because they have enabled global phylogenetic reconstructions of the relationships between organisms in the tree of life. Often, however, molecular stories conflict dramatically with morphology-based histories of lineages. The evolutionary origin of animal groups provides one such case. In other instances, different molecular analyses have so far proved irreconcilable. The ancient and major divergence of eukaryotes from prokaryotic ancestors is an example of this sort of problem. Efforts to overcome these conflicts highlight the role models play in phylogenetic reconstruction. One crucial model is the molecular clock; another is that of 'simple-to-complex' modification. I will examine animal and eukaryote evolution against a backdrop of increasing methodological sophistication in molecular phylogeny, and conclude with some reflections on the nature of historical science in the molecular era of phylogeny.

Mapping the genomic architecture of adaptive traits with interspecific introgressive origin: a coalescent-based approach

Recent studies of eukaryotes including human and Neandertal, mice, and butterflies have highlighted the major role that interspecific introgression has played in adaptive trait evolution. A common question arises in each case: what is the genomic architecture of the introgressed traits? One common approach that can be used to address this question is association mapping, which looks for genotypic markers that have significant statistical association with a trait. It is well understood that sample relatedness can be a confounding factor in association mapping studies if not properly accounted for. Introgression and other evolutionary processes (e.g., incomplete lineage sorting) typically introduce variation among local genealogies, which can also differ from global sample structure measured across all genomic loci. In contrast, state-of-the-art association mapping methods assume fixed sample relatedness across the genome, which can lead to spurious inference. We therefore propose a new association mapping method called Coal-Map, which uses coalescent-based models to capture local genealogical variation alongside global sample structure. Using simulated and empirical data reflecting a range of evolutionary scenarios, we compare the performance of Coal-Map against EIGENSTRAT, a leading association mapping method in terms of its popularity, power, and type I error control. Our empirical data makes use of hundreds of mouse genomes for which adaptive interspecific introgression has recently been described. We found that Coal-Map's performance is comparable or better than EIGENSTRAT in terms of statistical power and false positive rate. Coal-Map's performance advantage was greatest on model conditions that most closely resembled empirically observed scenarios of adaptive introgression. These conditions had: (1) causal SNPs contained in one or a few introgressed genomic loci and (2) varying rates of gene flow - from high rates to very low rates where incomplete lineage sorting dominated as a primary cause of local genealogical variation.