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

Fingerprint

Phylogenetic Tree
Contraction
Refinement
Bisection
Maximum Parsimony
Maximum likelihood
Heuristics
Maximum Likelihood
Evolutionary Tree
Hill Climbing
Phylogeny
Structural analysis
Heuristic Search
Structural Analysis
Data analysis
Sampling
NP-complete problem
Intersection
Optimization Problem

ASJC Scopus subject areas

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

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)

On Contract-and-Refine Transformations Between Phylogenetic Trees. / Ganapathy, Ganeshkumar; Ramachandran, Vijaya; Warnow, Tandy.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 15 2004. p. 893-902.

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

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, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States, 1/11/04.
Ganapathy G, Ramachandran V, Warnow T. On Contract-and-Refine Transformations Between Phylogenetic Trees. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 15. 2004. p. 893-902
Ganapathy, Ganeshkumar ; Ramachandran, Vijaya ; Warnow, Tandy. / On Contract-and-Refine Transformations Between Phylogenetic Trees. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 15 2004. pp. 893-902
@inproceedings{a66293fdd4ca49feaf14eaea1deb54d1,
title = "On Contract-and-Refine Transformations Between Phylogenetic Trees",
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.",
author = "Ganeshkumar Ganapathy and Vijaya Ramachandran and Tandy Warnow",
year = "2004",
language = "English (US)",
volume = "15",
pages = "893--902",
booktitle = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms",

}

TY - GEN

T1 - On Contract-and-Refine Transformations Between Phylogenetic Trees

AU - Ganapathy, Ganeshkumar

AU - Ramachandran, Vijaya

AU - Warnow, Tandy

PY - 2004

Y1 - 2004

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

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

UR - http://www.scopus.com/inward/record.url?scp=1842591342&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1842591342&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:1842591342

VL - 15

SP - 893

EP - 902

BT - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

ER -