Who is Who in Phylogenetic Networks

Publications of Ran Libeskind-Hadas     Order by:   Type | Year

Associated keywords

cophylogeny duplication heuristic lateral-gene-transfer loss NP-complete parsimony phylogenetic-network phylogeny polynomial Program-Xscape reconstruction

2014

1 Ran Libeskind-Hadas, Yi-Chieh Wu, Mukul S. Bansal and Manolis Kellis. Pareto-optimal phylogenetic tree reconciliation. In ISMB14, Vol. 30:i87-i95 of BIO, 2014. Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Xscape, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btu289.         Toggle abstract "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. © 2014 The Author. Published by Oxford University Press. All rights reserved."

2009

2 Ran Libeskind-Hadas and Michael A. Charleston. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. In JCB, Vol. 16(1):105-117, 2009. Keywords: cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2008.0084.         Toggle abstract "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. © Mary Ann Liebert, Inc. 2009."