Pairwise Distances and the Problem of Multiple Optima.

Discrete optimization problems arise in many biological contexts and, in many cases, we seek to make inferences from the optimal solutions. However, the number of optimal solutions is frequently very large and making inferences from any single solution may result in conclusions that are not supported by other optimal solutions. We describe a general approach for efficiently (polynomial time) and exactly (without sampling) computing statistics on the space of optimal solutions. These statistics provide insights into the space of optimal solutions that can be used to support the use of a single optimum (e.g., when the optimal solutions are similar) or justify the need for selecting multiple optima (e.g., when the solution space is large and diverse) from which to make inferences. We demonstrate this approach on two well-known problems and identify the properties of these problems that make them amenable to this method.

xenoGI 3: using the DTLOR model to reconstruct the evolution of gene families in clades of microbes.

To understand genome evolution in a group of microbes, we need to know the timing of events such as duplications, deletions and horizontal transfers. A common approach is to perform a gene-tree / species-tree reconciliation. While a number of software packages perform this type of analysis, none are geared toward a complete reconstruction for all families in an entire clade. Here we describe an update to the xenoGI software package which allows users to perform such an analysis using the newly developed DTLOR (duplication-transfer-loss-origin-rearrangement) reconciliation model starting from genome sequences as input.

Tree Reconciliation Methods for Host-Symbiont Cophylogenetic Analyses.

Phylogenetic reconciliation is a fundamental method in the study of pairs of coevolving species. This paper provides an overview of the underlying theory of reconciliation in the context of host-symbiont cophylogenetics, identifying some of the major challenges to users of these methods, such as selecting event costs and selecting representative reconciliations. Next, recent advances to address these challenges are discussed followed by a discussion of several established and recent software tools.

A Polynomial-Time Algorithm for Minimizing the Deep Coalescence Cost for Level-1 Species Networks.

Phylogenetic analyses commonly assume that the species history can be represented as a tree. However, in the presence of hybridization, the species history is more accurately captured as a network. Despite several advances in modeling phylogenetic networks, there is no known polynomial-time algorithm for parsimoniously reconciling gene trees with species networks while accounting for incomplete lineage sorting. To address this issue, we present a polynomial-time algorithm for the case of level-1 networks, in which no hybrid species is the direct ancestor of another hybrid species. This work enables more efficient reconciliation of gene trees with species networks, which in turn, enables more efficient reconstruction of species networks.

Maximum parsimony reconciliation in the DTLOR model.

BACKGROUND: Analyses of microbial evolution often use reconciliation methods. However, the standard duplication-transfer-loss (DTL) model does not account for the fact that species trees are often not fully sampled and thus, from the perspective of reconciliation, a gene family may enter the species tree from the outside. Moreover, within the genome, genes are often rearranged, causing them to move to new syntenic regions. RESULTS: We extend the DTL model to account for two events that commonly arise in the evolution of microbes: origin of a gene from outside the sampled species tree and rearrangement of gene syntenic regions. We describe an efficient algorithm for maximum parsimony reconciliation in this new DTLOR model and then show how it can be extended to account for non-binary gene trees to handle uncertainty in gene tree topologies. Finally, we describe preliminary experimental results from the integration of our algorithm into the existing xenoGI tool for reconstructing the histories of genomic islands in closely related bacteria. CONCLUSIONS: Reconciliation in the DTLOR model can offer new insights into the evolution of microbes that is not currently possible under the DTL model.

eMPRess: a systematic cophylogeny reconciliation tool.

SUMMARY: We describe eMPRess, a software program for phylogenetic tree reconciliation under the duplication-transfer-loss model that systematically addresses the problems of choosing event costs and selecting representative solutions, enabling users to make more robust inferences. AVAILABILITY AND IMPLEMENTATION: eMPRess is freely available at http://www.cs.hmc.edu/empress. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Reconciliation Reconsidered: In Search of a Most Representative Reconciliation in the Duplication-Transfer-Loss Model.

Maximum parsimony reconciliation is a fundamental technique for studying the evolutionary histories of pairs of entities such as genes and species, parasites and hosts, and species and their biogeographical habitats. In these contexts, reconciliation is generally performed using the duplication-transfer-loss (DTL) model in a maximum parsimony framework. While efficient maximum parsimony reconciliation algorithms are known for the DTL model, the number of such reconciliations can grow exponentially with the sizes of the two phylogenetic trees. Choosing a maximum parsimony reconciliation arbitrarily may lead to conclusions that are not supported, and may even be contradicted, by other equally optimal reconciliations. This paper addresses the fundamental problem of how well a single reconciliation can represent the entire space of optimal reconciliations.

Multiple Optimal Reconciliations Under the Duplication-Loss-Coalescence Model.

Gene trees can differ from species trees due to a variety of biological phenomena, the most prevalent being gene duplication, horizontal gene transfer, gene loss, and coalescence. To explain topological incongruence between the two trees, researchers apply reconciliation methods, often relying on a maximum parsimony framework. However, while several studies have investigated the space of maximum parsimony reconciliations (MPRs) under the duplication-loss and duplication-transfer-loss models, the space of MPRs under the duplication-loss-coalescence (DLC) model remains poorly understood. To address this problem, we present new algorithms for computing the size of MPR space under the DLC model and sampling from this space uniformly at random. Our algorithms are efficient in practice, with runtime polynomial in the size of the species and gene tree when the number of genes that map to any given species is fixed, thus proving that the MPR problem is fixed-parameter tractable. We have applied our methods to a biological data set of 16 fungal species to provide the first key insights in the space of MPRs under the DLC model. Our results show that a plurality reconciliation, and underlying events, are likely to be representative of MPR space.

Inferring Pareto-optimal reconciliations across multiple event costs under the duplication-loss-coalescence model.

BACKGROUND: Reconciliation methods are widely used to explain incongruence between a gene tree and species tree. However, the common approach of inferring maximum parsimony reconciliations (MPRs) relies on user-defined costs for each type of event, which can be difficult to estimate. Prior work has explored the relationship between event costs and maximum parsimony reconciliations in the duplication-loss and duplication-transfer-loss models, but no studies have addressed this relationship in the more complicated duplication-loss-coalescence model. RESULTS: We provide a fixed-parameter tractable algorithm for computing Pareto-optimal reconciliations and recording all events that arise in those reconciliations, along with their frequencies. We apply this method to a case study of 16 fungi to systematically characterize the complexity of MPR space across event costs and identify events supported across this space. CONCLUSION: This work provides a new framework for studying the relationship between event costs and reconciliations that incorporates both macro-evolutionary events and population effects and is thus broadly applicable across eukaryotic species.

An efficient exact algorithm for computing all pairwise distances between reconciliations in the duplication-transfer-loss model.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is widely used in studying the evolutionary histories of genes and species and in studying coevolution of parasites and their hosts and pairs of symbionts. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of reconciliations can grow exponentially in the size of the trees. An understanding of the space of maximum parsimony reconciliations is necessary to determine whether a single reconciliation can adequately represent the space or whether multiple representative reconciliations are needed. RESULTS: We show that for any instance of the reconciliation problem, the distribution of pairwise distances can be computed exactly by an efficient polynomial-time algorithm with respect to several different distance metrics. We describe the algorithm, analyze its asymptotic worst-case running time, and demonstrate its utility and viability on a large biological dataset. CONCLUSIONS: This result provides new insights into the structure of the space of maximum parsimony reconciliations. These insights are likely to be useful in the wide range of applications that employ reconciliation methods.

Hierarchical clustering of maximum parsimony reconciliations.

BACKGROUND: Maximum parsimony reconciliation in the duplication-transfer-loss model is a widely-used method for analyzing the evolutionary histories of pairs of entities such as hosts and parasites, symbiont species, and species and genes. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of such reconciliations can be exponential in the size of the trees. Since these reconciliations can differ substantially from one another, making inferences from any one reconciliation may lead to conclusions that are not supported, or may even be contradicted, by other maximum parsimony reconciliations. Therefore, there is a need to find small sets of best representative reconciliations when the space of solutions is large and diverse. RESULTS: We provide a general framework for hierarchical clustering the space of maximum parsimony reconciliations. We demonstrate this framework for two specific linkage criteria, one that seeks to maximize the average support of the events found in the reconciliations in each cluster and the other that seeks to minimize the distance between reconciliations in each cluster. We analyze the asymptotic worst-case running times and provide experimental results that demonstrate the viability and utility of this approach. CONCLUSIONS: The hierarchical clustering algorithm method proposed here provides a new approach to find a set of representative reconciliations in the potentially vast and diverse space of maximum parsimony reconciliations.

Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model.

Phylogenetic tree reconciliation is widely used in the fields of molecular evolution, cophylogenetics, parasitology, and biogeography to study the evolutionary histories of pairs of entities. In these contexts, reconciliation is often performed using maximum parsimony under the Duplication-Transfer-Loss (DTL) event model. In general, the number of maximum parsimony reconciliations (MPRs) can grow exponentially with the size of the trees. While a number of previous efforts have been made to count the number of MPRs, find representative MPRs, and compute the frequencies of events across the space of MPRs, little is known about the structure of MPR space. In particular, how different are MPRs in terms of the events that they comprise? One way to address this question is to compute the diameter of MPR space, defined to be the maximum number of DTL events that distinguish any two MPRs in the solution space. We show how to compute the diameter of MPR space in polynomial time and then apply this algorithm to a large biological dataset to study the variability of events.

DTL reconciliation repair.

BACKGROUND: Maximum parsimony phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of hosts and parasites, genes and species, and other interdependent pairs. Since the problem of finding temporally feasible maximum parsimony reconciliations is NP-complete, current methods use either exact algorithms with exponential worst-case running time or heuristics that do not guarantee optimal solutions. RESULTS: We offer an efficient new approach that begins with a potentially infeasible maximum parsimony reconciliation and iteratively "repairs" it until it becomes temporally feasible. CONCLUSIONS: In a non-trivial number of cases, this approach finds solutions that are better than those found by the widely-used Jane heuristic.

On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model.

BACKGROUND: Phylogenetic tree reconciliation is a widely-used method for inferring the evolutionary histories of genes and species. In the duplication-loss-coalescence (DLC) model, we seek a reconciliation that explains the incongruence between a gene and species tree using gene duplication, loss, and deep coalescence events. In the maximum parsimony framework, costs are associated with these event types and a reconciliation is sought that minimizes the total cost of the events required to map the gene tree onto the species tree. RESULTS: We show that this problem is NP-hard even for the special case of minimizing the number of duplications. We then show that the problem is APX-hard when both duplications and losses are considered, implying that no polynomial-time approximation scheme can exist for the problem unless P = NP. CONCLUSIONS: These intractability results are likely to guide future research on algorithmic aspects of the DLC-reconciliation problem.

Discordant phylogenies suggest repeated host shifts in the Fusarium-Euwallacea ambrosia beetle mutualism.

The mutualism between xyleborine beetles in the genus Euwallacea (Coleoptera: Curculionidae: Scolytinae) and members of the Ambrosia Fusarium Clade (AFC) represents one of 11 known evolutionary origins of fungiculture by ambrosia beetles. Female Euwallacea beetles transport fusarial symbionts in paired mandibular mycangia from their natal gallery to woody hosts where they are cultivated in galleries as a source of food. Native to Asia, several exotic Euwallacea species were introduced into the United States and Israel within the past two decades and they now threaten urban landscapes, forests and avocado production. To assess species limits and to date the evolutionary diversification of the mutualists, we reconstructed the evolutionary histories of key representatives of the Fusarium and Euwallacea clades using maximum parsimony and maximum likelihood methods. Twelve species-level lineages, termed AF 1-12, were identified within the monophyletic AFC and seven among the Fusarium-farming Euwallacea. Bayesian diversification-time estimates placed the origin of the Euwallacea-Fusarium mutualism near the Oligocene-Miocene boundary ∼19-24 Mya. Most Euwallacea spp. appear to be associated with one species of Fusarium, but two species farmed two closely related fusaria. Euwallacea sp. #2 in Miami-Dade County, Florida cultivated Fusarium spp. AF-6 and AF-8 on avocado, and Euwallacea sp. #4 farmed Fusarium ambrosium AF-1 and Fusarium sp. AF-11 on Chinese tea in Sri Lanka. Cophylogenetic analyses indicated that the Euwallacea and Fusarium phylogenies were largely incongruent, apparently due to the beetles switching fusarial symbionts (i.e., host shifts) at least five times during the evolution of this mutualism. Three cospeciation events between Euwallacea and their AFC symbionts were detected, but randomization tests failed to reject the null hypothesis that the putative parallel cladogenesis is a stochastic pattern. Lastly, two collections of Euwallacea sp. #2 from Miami-Dade County, Florida shared an identical cytochrome oxidase subunit 1 (CO1) allele with Euwallacea validus, suggesting introgressive hybridization between these species and/or pseudogenous nature of this marker. Results of the present study highlight the importance of understanding the potential for and frequency of host-switching between Euwallacea and members of the AFC, and that these shifts may bring together more aggressive and virulent combinations of these invasive mutualists.

Pareto-optimal phylogenetic tree reconciliation.

MOTIVATION: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem. RESULTS: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies. AVAILABILITY AND IMPLEMENTATION: Our Python tools are freely available at www.cs.hmc.edu/∼hadas/xscape. .

A first course in computing with applications to biology.

We believe that undergraduate biology students must acquire a foundational background in computing including how to formulate a computational problem; develop an algorithmic solution; implement their solution in software and then test, document and use their code to explore biological phenomena. Moreover, by learning these skills in the first year, students acquire a powerful tool set that they can use and build on throughout their studies. To address this need, we have developed a first-year undergraduate course that teaches students the foundations of computational thinking and programming in the context of problems in biology. This article describes the structure and content of the course and summarizes assessment data on both affective and learning outcomes.

An extreme case of plant-insect codiversification: figs and fig-pollinating wasps.

It is thought that speciation in phytophagous insects is often due to colonization of novel host plants, because radiations of plant and insect lineages are typically asynchronous. Recent phylogenetic comparisons have supported this model of diversification for both insect herbivores and specialized pollinators. An exceptional case where contemporaneous plant-insect diversification might be expected is the obligate mutualism between fig trees (Ficus species, Moraceae) and their pollinating wasps (Agaonidae, Hymenoptera). The ubiquity and ecological significance of this mutualism in tropical and subtropical ecosystems has long intrigued biologists, but the systematic challenge posed by >750 interacting species pairs has hindered progress toward understanding its evolutionary history. In particular, taxon sampling and analytical tools have been insufficient for large-scale cophylogenetic analyses. Here, we sampled nearly 200 interacting pairs of fig and wasp species from across the globe. Two supermatrices were assembled: on an average, wasps had sequences from 77% of 6 genes (5.6 kb), figs had sequences from 60% of 5 genes (5.5 kb), and overall 850 new DNA sequences were generated for this study. We also developed a new analytical tool, Jane 2, for event-based phylogenetic reconciliation analysis of very large data sets. Separate Bayesian phylogenetic analyses for figs and fig wasps under relaxed molecular clock assumptions indicate Cretaceous diversification of crown groups and contemporaneous divergence for nearly half of all fig and pollinator lineages. Event-based cophylogenetic analyses further support the codiversification hypothesis. Biogeographic analyses indicate that the present-day distribution of fig and pollinator lineages is consistent with a Eurasian origin and subsequent dispersal, rather than with Gondwanan vicariance. Overall, our findings indicate that the fig-pollinator mutualism represents an extreme case among plant-insect interactions of coordinated dispersal and long-term codiversification. [Biogeography; coevolution; cospeciation; host switching; long-branch attraction; phylogeny.].

Jane: a new tool for the cophylogeny reconstruction problem.

BACKGROUND: This paper describes the theory and implementation of a new software tool, called Jane, for the study of historical associations. This problem arises in parasitology (associations of hosts and parasites), molecular systematics (associations of orderings and genes), and biogeography (associations of regions and orderings). The underlying problem is that of reconciling pairs of trees subject to biologically plausible events and costs associated with these events. Existing software tools for this problem have strengths and limitations, and the new Jane tool described here provides functionality that complements existing tools. RESULTS: The Jane software tool uses a polynomial time dynamic programming algorithm in conjunction with a genetic algorithm to find very good, and often optimal, solutions even for relatively large pairs of trees. The tool allows the user to provide rich timing information on both the host and parasite trees. In addition the user can limit host switch distance and specify multiple host switch costs by specifying regions in the host tree and costs for host switches between pairs of regions. Jane also provides a graphical user interface that allows the user to interactively experiment with modifications to the solutions found by the program. CONCLUSIONS: Jane is shown to be a useful tool for cophylogenetic reconstruction. Its functionality complements existing tools and it is therefore likely to be of use to researchers in the areas of parasitology, molecular systematics, and biogeography.

On the computational complexity of the reticulate cophylogeny reconstruction problem.

The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem.