SylvX: a viewer for phylogenetic tree reconciliations.

MOTIVATION: Reconciliation methods aim at recovering the evolutionary processes that shaped the history of a given gene family including events such as duplications, transfers and losses by comparing the discrepancies between the topologies of the associated gene and species trees. These methods are also used in the framework of host/parasite studies to recover co-diversification scenarios including co-speciation events, host-switches and extinctions. These evolutionary processes can be graphically represented as nested trees. These interconnected graphs can be visually messy and hard to interpret, and despite the fact that reconciliations are increasingly used, there is a shortage of tools dedicated to their graphical management. Here we present SylvX, a reconciliation viewer which implements classical phylogenetic graphic operators (swapping, highlighting, etc.) and new methods to ease interpretation and comparison of reconciliations (multiple maps, moving, shrinking sub-reconciliations). AVAILABILITY AND IMPLEMENTATION: SylvX is an open source, cross-platform, standalone editor available for Windows and Unix-like systems including OSX. It is publicly available at www.sylvx.org.

Inferring gene duplications, transfers and losses can be done in a discrete framework.

In the field of phylogenetics, the evolutionary history of a set of organisms is commonly depicted by a species tree-whose internal nodes represent speciation events-while the evolutionary history of a gene family is depicted by a gene tree-whose internal nodes can also represent macro-evolutionary events such as gene duplications and transfers. As speciation events are only part of the events shaping a gene history, the topology of a gene tree can show incongruences with that of the corresponding species tree. These incongruences can be used to infer the macro-evolutionary events undergone by the gene family. This is done by embedding the gene tree inside the species tree and hence providing a reconciliation of those trees. In the past decade, several parsimony-based methods have been developed to infer such reconciliations, accounting for gene duplications ([Formula: see text]), transfers ([Formula: see text]) and losses ([Formula: see text]). The main contribution of this paper is to formally prove an important assumption implicitly made by previous works on these reconciliations, namely that solving the (maximum) parsimony [Formula: see text] reconciliation problem in the discrete framework is equivalent to finding a most parsimonious [Formula: see text] scenario in the continuous framework. In the process, we also prove several intermediate results that are useful on their own and constitute a theoretical toolbox that will likely facilitate future theoretical contributions in the field.

Models, algorithms and programs for phylogeny reconciliation.

Gene sequences contain a gold mine of phylogenetic information. But unfortunately for taxonomists this information does not only tell the story of the species from which it was collected. Genes have their own complex histories which record speciation events, of course, but also many other events. Among them, gene duplications, transfers and losses are especially important to identify. These events are crucial to account for when reconstructing the history of species, and they play a fundamental role in the evolution of genomes, the diversification of organisms and the emergence of new cellular functions. We review reconciliations between gene and species trees, which are rigorous approaches for identifying duplications, transfers and losses that mark the evolution of a gene family. Existing reconciliation models and algorithms are reviewed and difficulties in modeling gene transfers are discussed. We also compare different reconciliation programs along with their advantages and disadvantages.

Branch-and-bound approach for parsimonious inference of a species tree from a set of gene family trees.

We describe a Branch-and-Bound algorithm for computing a parsimonious species tree, given a set of gene family trees. Our algorithm can consider three cost measures: number of gene duplications, number of gene losses, and both combined. Moreover, to cope with intrinsic limitations of Branch-and-Bound algorithms for species trees inference regarding the number of taxa that can be considered, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.

A geography-aware reconciliation method to investigate diversification patterns in host/parasite interactions.

Cospeciation studies aim at investigating whether hosts and symbionts speciate simultaneously or whether the associations diversify through host shifts. This problem is often tackled through reconciliation analyses that map the symbiont phylogeny onto the host phylogeny by mixing different types of diversification events. These reconciliations can be difficult to interpret and are not always biologically realistic. Researchers have underlined that the biogeographic histories of both hosts and symbionts influence the probability of cospeciation and host switches, but up to now no reconciliation software integrates geographic data. We present a new functionality in the Mowgli software that bridges this gap. The user can provide geographic information on both the host and symbiont extant and ancestral taxa. Constraints in the reconciliation algorithm have been implemented to generate biologically realistic codiversification scenarios. We apply our method to the fig/fig wasp association and infer diversification scenarios that differ from reconciliations ignoring geographic information. In addition, we updated the reconciliation viewer SylvX to visualize ancestral character states on the phylogenetic trees and highlight parts of reconciliations that are geographically inconsistent when not accounting for geographic constraints. We suggest that the comparison of reconciliations obtained with and without such constraints can help solving ambiguities in the biogeographic histories of the partners. With the development of robust methods in historical biogeography, and the advent of next-generation sequencing that leads to better-resolved trees, a geography-aware reconciliation method represents a substantial advance that is likely to be useful to researchers studying the evolution of biotic interactions and biogeography.

Reconciliation and local gene tree rearrangement can be of mutual profit.

BACKGROUND: Reconciliation methods compare gene trees and species trees to recover evolutionary events such as duplications, transfers and losses explaining the history and composition of genomes. It is well-known that gene trees inferred from molecular sequences can be partly erroneous due to incorrect sequence alignments as well as phylogenetic reconstruction artifacts such as long branch attraction. In practice, this leads reconciliation methods to overestimate the number of evolutionary events. Several methods have been proposed to circumvent this problem, by collapsing the unsupported edges and then resolving the obtained multifurcating nodes, or by directly rearranging the binary gene trees. Yet these methods have been defined for models of evolution accounting only for duplications and losses, i.e. can not be applied to handle prokaryotic gene families. RESULTS: We propose a reconciliation method accounting for gene duplications, losses and horizontal transfers, that specifically takes into account the uncertainties in gene trees by rearranging their weakly supported edges. Rearrangements are performed on edges having a low confidence value, and are accepted whenever they improve the reconciliation cost. We prove useful properties on the dynamic programming matrix used to compute reconciliations, which allows to speed-up the tree space exploration when rearrangements are generated by Nearest Neighbor Interchanges (NNI) edit operations. Experiments on synthetic data show that gene trees modified by such NNI rearrangements are closer to the correct simulated trees and lead to better event predictions on average. Experiments on real data demonstrate that the proposed method leads to a decrease in the reconciliation cost and the number of inferred events. Finally on a dataset of 30 k gene families, this reconciliation method shows a ranking of prokaryotic phyla by transfer rates identical to that proposed by a different approach dedicated to transfer detection [BMCBIOINF 11:324, 2010, PNAS 109(13):4962-4967, 2012]. CONCLUSIONS: Prokaryotic gene trees can now be reconciled with their species phylogeny while accounting for the uncertainty of the gene tree. More accurate and more precise reconciliations are obtained with respect to previous parsimony algorithms not accounting for such uncertainties [LNCS 6398:93-108, 2010, BIOINF 28(12): i283-i291, 2012].A software implementing the method is freely available at http://www.atgc-montpellier.fr/Mowgli/.

An efficient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework.

BACKGROUND: Inferring an evolutionary scenario for a gene family is a fundamental problem with applications both in functional and evolutionary genomics. The gene tree/species tree reconciliation approach has been widely used to address this problem, but mostly in a discrete parsimony framework that aims at minimizing the number of gene duplications and/or gene losses. Recently, a probabilistic approach has been developed, based on the classical birth-and-death process, including efficient algorithms for computing posterior probabilities of reconciliations and orthology prediction. RESULTS: In previous work, we described an algorithm for exploring the whole space of gene tree/species tree reconciliations, that we adapt here to compute efficiently the posterior probability of such reconciliations. These posterior probabilities can be either computed exactly or approximated, depending on the reconciliation space size. We use this algorithm to analyze the probabilistic landscape of the space of reconciliations for a real data set of fungal gene families and several data sets of synthetic gene trees. CONCLUSION: The results of our simulations suggest that, with exact gene trees obtained by a simple birth-and-death process and realistic gene duplication/loss rates, a very small subset of all reconciliations needs to be explored in order to approximate very closely the posterior probability of the most likely reconciliations. For cases where the posterior probability mass is more evenly dispersed, our method allows to explore efficiently the required subspace of reconciliations.

Space of gene/species trees reconciliations and parsimonious models.

We describe algorithms to study the space of all possible reconciliations between a gene tree and a species tree, that is counting the size of this space, uniformly generate a random reconciliation, and exploring this space in optimal time using combinatorial operators. We also extend these algorithms for optimal and sub-optimal reconciliations according to the three usual combinatorial costs (duplication, loss, and mutation). Applying these algorithms to simulated and real gene family evolutionary scenarios, we observe that the LCA (Last Common Ancestor) based reconciliation is almost always identical to the real one.

Gene family evolution by duplication, speciation, and loss.

We consider two algorithmic questions related to the evolution of gene families. First, given a gene tree for a gene family, can the evolutionary history of this family be explained with only speciation and duplication events? Such gene trees are called DS-trees. We show that this question can be answered in linear time, and that a DS-tree induces a single species tree. We then study a natural extension of this problem: what is the minimum number of gene losses involved in an evolutionary history leading to an observed gene tree or set of gene trees? Based on our characterization of DS-trees, we propose a heuristic for this problem, and evaluate it on a dataset of plants gene families and on simulated data.