title: DTL-RnB: Algorithms and Tools for Summarizing the Space of DTL Reconciliations.
abstract: Phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of species and genes and other dependent entities. Reconciliation is typically performed in a maximum parsimony framework and the number of optimal reconciliations can grow exponentially with the size of the trees, making it difficult to understand the solution space. This paper demonstrates how a small number of reconciliations can be found that collectively contain the most highly supported events in the solution space. While we show that the formal problem is NP-complete, we give a approximation algorithm, experimental results that indicate its effectiveness, and the new DTL-RnB software tool that uses our algorithms to summarize the space of optimal reconciliations (www.cs.hmc.edu/dtlrnb).
authors.forename: W
authors.initials: W
authors.lastname: Ma
authors.forename: D
authors.initials: D
authors.lastname: Smirnov
authors.forename: J
authors.initials: J
authors.lastname: Forman
authors.forename: A
authors.initials: A
authors.lastname: Schweickart
authors.forename: C
authors.initials: C
authors.lastname: Slocum
authors.forename: S
authors.initials: S
authors.lastname: Srinivasan
authors.forename: R
authors.initials: R
authors.lastname: Libeskind-Hadas
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D008957:Models, Genetic; D010802:Phylogeny; D012984:Software