Jane: a new tool for the cophylogeny reconstruction problem.

Conow C, Fielder D, Ovadia Y, Libeskind-Hadas R. · 2010

Read Jane: a new tool for the cophylogeny reconstruction problem. by Conow C, Fielder D, Ovadia Y, Libeskind-Hadas R. (2010) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc2830923.txt.

Introduction

Conow, Fielder, Ovadia, and Libeskind-Hadas built Jane in 2010, a software tool for untangling the shared history of hosts and their parasites. When a parasite's family tree is laid over its host's tree, the mismatch pattern tells how the pair evolved together. Events behind the pattern include splitting together, jumping hosts, or vanishing from a host line.

Jane finds low-cost histories that explain both trees with those events. It pairs a fast step-by-step algorithm with a genetic algorithm, a search that breeds good answers toward better ones, and it finds near-best solutions even for large tree pairs. Users can feed in timing data, cap how far a parasite may jump, and test edits by hand in a graphical screen.

Catalog record

CREATORConow C, Fielder D, Ovadia Y, Libeskind-Hadas R.
YEAR2010
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC2830923

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Jane: a new tool for the cophylogeny reconstruction problem By Chris Conow, Daniel Fielder, Yaniv Ovadia, Ran Libeskind-Hadas Published in: Algorithms for Molecular Biology : AMB DOI: 10.1186/1748-7188-5-16 ABSTRACT Abstract 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. BACKGROUND One widely-used approach to the study of host-parasite relationships involves reconciling host and parasite phylogenetic trees via event-cost methods. In this approach, each event in the parasite phylogeny is mapped onto the host tree and a mapping is sought that minimizes the total cost with respect to a given cost metric. Such mappings allow us to examine sets of events that may have led to the coevolution of the host and parasite phylogenies and are the basis of statistical tests for assessing congruence. Specifically, in the cophylogeny reconstruction problem we are given a host tree H; a parasite tree P; a function φ mapping the leaves or "tips" of P, representing the extant taxa, to the tips of H; and costs associated with each of four biologically plausible operations: cospeciation, duplication, host switching, and loss (Figure 1). Cospeciation occurs when a vertex (speciation event) in the parasite tree is associated with a vertex (speciation event) in the host tree. Duplication occurs when a vertex in the parasite tree is associated with an edge in the host tree. This event implies that the parasite lineage speciated independently of the host lineage. Host switching occurs when a duplication event is accompanied by one of the two descendants of the parasite vertex switching to an edge in a different part of the host tree. Once the parasite vertices are mapped onto the host tree, loss occurs when the path between a parasite vertex and its child passes through a host vertex. The objective is to find a least cost association of the trees that can be constructed with these four types of events. [Figure: Top: A simple tanglegram with host tree in black at left and parasite tree in gray on right. The associations φ between tips is shown in dotted lines. Bottom: Two possible reconstructions that explain the relationship between H and P with events labeled.] We have recently shown that the cophylogeny reconstruction problem is NP-complete [1,2], and thus polynomial-time algorithms that find optimal solutions are unlikely to exist. Therefore, heuristics are required to find good, but not necessarily optimal, solutions. A number of computational approaches for the cophylogeny reconstruction problem have been proposed and implemented in software. TreeFitter [3] and Component [4] were the first two programs for cophylogeny reconstruction. TreeFitter, according to its documentation, employs two methods: one provides a lower bound on the optimal solution but may introduce invalid solutions due to inconsistent host-switching events [3] while the other method is not described in detail but reportedly finds upper bounds on the cost. This software runs only on a limited number of platforms, some no longer available. While Component has several useful features, it does not consider host switching events and such events are known to be important in coevolution. The computational intractability of the cophylogeny reconstruction problem is, in fact, due to host switching events. If host switching events are not considered then the problem can be solved optimally in polynomial time by a simple greedy algorithm. Host switching events can induce complex timing relationships between events. Figure 2(a) shows how a set of host switching events can result in a solution that is not valid because of an inconsistent sequence of timing events. Such a set of host switching events is called strongly incompatible [5]. In other cases, a set of host switching events may cause timing inconsistencies that can be resolved by moving the landing sites of one or more host switches to an earlier time at the expense of adding extra loss events. Such a set of switching events is called weakly incompatible [5]. Figure 2(b) shows a set of associations with weakly incompatible host switches and Figure 2(c) shows how these host switches can be modified to construct a valid mapping. [Figure: (a) Strongly incompatible host switching events. Parasite a on edge (u, w) switches to child b on edge (t, v) implying that v occurs after u. Similarly, parasite c on edge (v, y) switches to child d on edge (t, u) implying that u occurs before v. This results in an irreconcilable timing conflict. (b) Weakly incompatible host switching events. Parasite a on edge (t, v) switches to child b on edge (u, w) implying that a occurs after u and thus after c. Similarly, parasite c on edge (t, u) switches to child d on edge (v, z) implying that c occurs after v and thus after a. (c) This conflict can be resolved, for example, by moving one of the landing sites of a host switch earlier in time, incurring an additional loss event at u.] In seminal work on this problem, Charleston developed a data structure and algorithm called Jungles that solves the cophylogeny reconstruction problem optimally [5]. The Jungles approach discards all solutions with strong incompatibilities and optimally resolves weak incompatibilities. Jungles are implemented in the TreeMap software package [6]. While TreeMap is powerful and feature-rich, the worst-case time complexity of the Jungles algorithm is inherently exponential in the size of the host and parasite trees. Therefore, TreeMap is very useful for relatively small trees but it cannot be used for larger trees (e.g. pairs of trees with 25 tips each run for over two days on a commodity personal computer and eventually exceed available memory). More recently, Merkle and Middendorf have proposed a heuristic for the cophylogeny reconstruction problem [7] and this heuristic has been implemented in the Tarzan software tool [8]. Tarzan is very fast (e.g. running in under one second on trees with 50 tips on a commodity personal computer) and in some cases can produce solutions that can be shown to be

Read the complete text