Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2010 Feb 3:5:16.
doi: 10.1186/1748-7188-5-16.

Jane: a new tool for the cophylogeny reconstruction problem

Chris Conow  1 , Daniel Fielder, Yaniv Ovadia, Ran Libeskind-Hadas
Affiliations

Jane: a new tool for the cophylogeny reconstruction problem

Chris Conow et al. Algorithms Mol Biol. .

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.

PubMed Disclaimer

Figures

Figure 1
Figure 1
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.
Figure 2
Figure 2
(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.
Figure 3
Figure 3
(a) A host tree with three different timings shown in (b), (c), and (d). The numbers underneath each timing indicate the relative time of each vertex in that timing. The timings in (c) and (d) differ only in the relative times of nodes b and c, two nodes that occur at consecutive relative times but such that neither is the parent of the other. Thus, these two timings are said to be neighbors.
Figure 4
Figure 4
The host tree with a randomly selected subtree.
Figure 5
Figure 5
At left, two selected timings, τ1 and τ2. The subtree T is removed from τ1 while only T is kept in τ2, as indicated by grayed edges and vertices. The new timing τnew is shown on the right.
Figure 6
Figure 6
The Jane graphical user interface with a selected solution shown in the inset window.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

See all "Cited by" articles

References

    1. Libeskind-Hadas R, Charleston M. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. Journal of Computational Biology. 2009;16:105–117. doi: 10.1089/cmb.2008.0084. - DOI - PubMed
    1. Conow C, Fielder D, Ovadia Y, Libeskind-Hadas R. The Cophylogeny Reticulation Problem is NP-complete. http://www.cs.hmc.edu/~hadas/research/CophyNPC.pdf Harvey Mudd College Technical Report 2009-01.
    1. Ronquist F. TreeFitter. http://www.ebc.uu.se/systzoo/research/treefitter/treefitter.html
    1. Page RDM. COMPONENT User's Manual. http://taxonomy.zoology.gla.ac.uk/rod/cpw.html
    1. Charleston M. Jungles: A new solution to the hostparasite phylogeny reconciliation problem. Mathematical Biosciences. 1998;149:191–223. doi: 10.1016/S0025-5564(97)10012-8. - DOI - PubMed

LinkOut - more resources