Better hill-climbing searches for parsimony

Ganeshkumar Ganapathy, Vijaya Ramachandran, Tandy Warnow

Research output: Contribution to journalArticlepeer-review

Abstract

The reconstruction of evolutionary trees is a major problem in biology, and many evolutionary trees are estimated using heuristics for the NP-hard optimization problem Maximum Parsimony. The current heuristics for searching through tree space use a particular technique, called "tree-bisection and reconnection", or TBR, to transform one tree into another tree; other less-frequently used transformations, such as SPR and NNI, are special cases of TBR. In this paper, we describe a new tree-rearrangement operation which we call the p-ECR move, for p-Edge-Contract-and-Refine. Our results include an efficient algorithm for computing the best 2-ECR neighbors of a given tree, based upon a simple data structure which also allows us to efficiently calculate the best neighbors under NNI, SPR, and TBR operations (as well as efficiently running the greedy sequence addition technique for maximum parsimony). More significantly, we show that the 2-ECR neighborhood of a given tree is incomparable to the neighborhood defined by TBR, and properly contains all trees within two NNI moves. Hence, the use of the 2-ECR move, in conjunction with TBR and/or NNI moves, may be a more effective technique for exploring tree space than TBR alone.

Original languageEnglish (US)
Pages (from-to)245-258
Number of pages14
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2812
DOIs
StatePublished - 2003
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Better hill-climbing searches for parsimony'. Together they form a unique fingerprint.

Cite this