Journal Article

Pareto-optimal phylogenetic tree reconciliation

Ran Libeskind-Hadas, Yi-Chieh Wu, Mukul S. Bansal and Manolis Kellis

in Bioinformatics

Volume 30, issue 12, pages i87-i95
Published in print June 2014 | ISSN: 1367-4803
Published online June 2014 | e-ISSN: 1460-2059 | DOI: https://dx.doi.org/10.1093/bioinformatics/btu289

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology

GO

Show Summary Details

Preview

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.

Contact: mukul@engr.uconn.edu

Supplementary information: Supplementary data are available at Bioinformatics online.

Journal Article.  7780 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.