title: DTL reconciliation repair.
abstract: BACKGROUND
  Maximum parsimony phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of hosts and parasites, genes and species, and other interdependent pairs. Since the problem of finding temporally feasible maximum parsimony reconciliations is NP-complete, current methods use either exact algorithms with exponential worst-case running time or heuristics that do not guarantee optimal solutions.
  
  
  RESULTS
  We offer an efficient new approach that begins with a potentially infeasible maximum parsimony reconciliation and iteratively "repairs" it until it becomes temporally feasible.
  
  
  CONCLUSIONS
  In a non-trivial number of cases, this approach finds solutions that are better than those found by the widely-used Jane heuristic.
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, California, USA.
authors.forename: Weiyun
authors.initials: W
authors.lastname: Ma
authors.affiliation: Pomona College, Claremont, California, USA.
authors.forename: Dmitriy
authors.initials: D
authors.lastname: Smirnov
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, California, USA. hadas@cs.hmc.edu.
authors.forename: Ran
authors.initials: R
authors.lastname: Libeskind-Hadas
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D005240:Feasibility Studies; D008962:Models, Theoretical; D010802:Phylogeny; D012984:Software
keywords: DTL reconciliation; Phylogenetic reconciliation; Undated trees