Better methods for solving parsimony and compatibility

Maria Bonet, Mike Steel, Tandy Warnow, Shibu Yooseph

Research output: Contribution to journalArticle

Abstract

Evolutionary tree reconstruction is a challenging problem with important applications in biology and linguistics. In biology, one of the most promising approaches to tree reconstruction is to find the 'maximum parsimony' tree, while in linguistics, the use of the 'maximum compatibility' method has been very useful. However, these problems are NP-hard, and current approaches to solving these problems amount to heuristic searches through the space of possible tree topologies (a search which can, on large trees, take months to complete). In this paper, we present a new technique, Optimal Tree Refinement, for reconstructing very large trees. Our technique is motivated by recent experimental studies which have shown that certain polynomial time methods often return contractions of the true tree. We study the use of this technique in solving maximum parsimony and maximum compatibility, and present both hardness results and polynomial time algorithms.

Original languageEnglish (US)
Pages (from-to)391-407
Number of pages17
JournalJournal of Computational Biology
Volume5
Issue number3
DOIs
StatePublished - Jan 1 1998
Externally publishedYes

Fingerprint

Parsimony
Linguistics
Compatibility
Polynomials
Computational complexity
Maximum Parsimony
Hardness
Topology
Biology
Evolutionary Tree
Heuristic Search
Polynomial-time Algorithm
Contraction
Experimental Study
Polynomial time
Refinement
NP-complete problem

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

Better methods for solving parsimony and compatibility. / Bonet, Maria; Steel, Mike; Warnow, Tandy; Yooseph, Shibu.

In: Journal of Computational Biology, Vol. 5, No. 3, 01.01.1998, p. 391-407.

Research output: Contribution to journalArticle

Bonet, Maria ; Steel, Mike ; Warnow, Tandy ; Yooseph, Shibu. / Better methods for solving parsimony and compatibility. In: Journal of Computational Biology. 1998 ; Vol. 5, No. 3. pp. 391-407.
@article{a278fd3ad6e34ef0bfa66cce2b3724ab,
title = "Better methods for solving parsimony and compatibility",
abstract = "Evolutionary tree reconstruction is a challenging problem with important applications in biology and linguistics. In biology, one of the most promising approaches to tree reconstruction is to find the 'maximum parsimony' tree, while in linguistics, the use of the 'maximum compatibility' method has been very useful. However, these problems are NP-hard, and current approaches to solving these problems amount to heuristic searches through the space of possible tree topologies (a search which can, on large trees, take months to complete). In this paper, we present a new technique, Optimal Tree Refinement, for reconstructing very large trees. Our technique is motivated by recent experimental studies which have shown that certain polynomial time methods often return contractions of the true tree. We study the use of this technique in solving maximum parsimony and maximum compatibility, and present both hardness results and polynomial time algorithms.",
author = "Maria Bonet and Mike Steel and Tandy Warnow and Shibu Yooseph",
year = "1998",
month = "1",
day = "1",
doi = "10.1089/cmb.1998.5.391",
language = "English (US)",
volume = "5",
pages = "391--407",
journal = "Journal of Computational Biology",
issn = "1066-5277",
publisher = "Mary Ann Liebert Inc.",
number = "3",

}

TY - JOUR

T1 - Better methods for solving parsimony and compatibility

AU - Bonet, Maria

AU - Steel, Mike

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1998/1/1

Y1 - 1998/1/1

N2 - Evolutionary tree reconstruction is a challenging problem with important applications in biology and linguistics. In biology, one of the most promising approaches to tree reconstruction is to find the 'maximum parsimony' tree, while in linguistics, the use of the 'maximum compatibility' method has been very useful. However, these problems are NP-hard, and current approaches to solving these problems amount to heuristic searches through the space of possible tree topologies (a search which can, on large trees, take months to complete). In this paper, we present a new technique, Optimal Tree Refinement, for reconstructing very large trees. Our technique is motivated by recent experimental studies which have shown that certain polynomial time methods often return contractions of the true tree. We study the use of this technique in solving maximum parsimony and maximum compatibility, and present both hardness results and polynomial time algorithms.

AB - Evolutionary tree reconstruction is a challenging problem with important applications in biology and linguistics. In biology, one of the most promising approaches to tree reconstruction is to find the 'maximum parsimony' tree, while in linguistics, the use of the 'maximum compatibility' method has been very useful. However, these problems are NP-hard, and current approaches to solving these problems amount to heuristic searches through the space of possible tree topologies (a search which can, on large trees, take months to complete). In this paper, we present a new technique, Optimal Tree Refinement, for reconstructing very large trees. Our technique is motivated by recent experimental studies which have shown that certain polynomial time methods often return contractions of the true tree. We study the use of this technique in solving maximum parsimony and maximum compatibility, and present both hardness results and polynomial time algorithms.

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

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

U2 - 10.1089/cmb.1998.5.391

DO - 10.1089/cmb.1998.5.391

M3 - Article

C2 - 9773340

AN - SCOPUS:0031721445

VL - 5

SP - 391

EP - 407

JO - Journal of Computational Biology

JF - Journal of Computational Biology

SN - 1066-5277

IS - 3

ER -