title: Pareto-optimal phylogenetic tree reconciliation.
abstract: BACKGROUND
  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.
  
  
  METHODS
  Our Python tools are freely available at www.cs.hmc.edu/∼hadas/xscape. .
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and Broad Institute, Cambridge, MA 02142, USA.
authors.forename: Ran
authors.initials: R
authors.lastname: Libeskind-Hadas
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and Broad Institute, Cambridge, MA 02142, USA.
authors.forename: Yi-Chieh
authors.initials: YC
authors.lastname: Wu
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and Broad Institute, Cambridge, MA 02142, USA.
authors.forename: Mukul S
authors.initials: MS
authors.lastname: Bansal
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, CA 91711, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and Broad Institute, Cambridge, MA 02142, USADepartment of Computer Science, Harvey Mudd College, Claremont, CA 91711, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269 and Broad Institute, Cambridge, MA 02142, USA.
authors.forename: Manolis
authors.initials: M
authors.lastname: Kellis
mesh_terms: D000465:Algorithms; D023281:Genomics; D005810:Multigene Family; D010802:Phylogeny; D012984:Software