On Contract-and-Refine Transformations Between Phylogenetic Trees

Ganeshkumar Ganapathy, Vijaya Ramachandran, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The inference of evolutionary trees using approaches which attempt to solve the maximum parsimony (MP) and maximum likelihood (ML) optimization problems is a standard part of much of biological data analysis. However, both problems are hard to solve: MP provably NP-hard, and ML even harder in practice. Consequently, hill-climbing heuristics are used to analyze datasets for phylogeny reconstruction. Two primary topological transformations have been used in the most popular heuristics: TBR (tree-bisection-and-reconnection) and ECR (edge-contractions-and-refinements). While most of the popular heuristics exclusively use TBR moves to explore tree space, some recent methods have used ECR in conjunction with TBR and found significant improvements in the speed and accuracy with which they can analyze datasets. In this paper we analyze ECR moves in detail, and provide results on the diameter of the tree space, the neighborhood intersection with TBR, structural analysis of the ECR operation, and an efficient method for sampling uniformly from the 2-ECR neighborhood of a tree. Our results should lead to a better understanding of the impact of ECR moves on the performance of heuristic searches.

Original languageEnglish (US)
Title of host publicationProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages893-902
Number of pages10
Volume15
StatePublished - 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

ASJC Scopus subject areas

  • Software
  • Discrete Mathematics and Combinatorics
  • Safety, Risk, Reliability and Quality
  • Chemical Health and Safety

Fingerprint Dive into the research topics of 'On Contract-and-Refine Transformations Between Phylogenetic Trees'. Together they form a unique fingerprint.

  • Cite this

    Ganapathy, G., Ramachandran, V., & Warnow, T. (2004). On Contract-and-Refine Transformations Between Phylogenetic Trees. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 15, pp. 893-902)