DTL-RnB: Algorithms and Tools for Summarizing the Space of DTL Reconciliations

IEEE/ACM Trans Comput Biol Bioinform. 2018 Mar-Apr;15(2):411-421. doi: 10.1109/TCBB.2016.2537319. Epub 2016 Mar 2.

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).

Publication types

  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms*
  • Computational Biology / methods*
  • Models, Genetic*
  • Phylogeny*
  • Software*