Better methods for solving parsimony and compatibility

Maria Bonet, Mike Steel, Tandy Warnow, Shibu Yooseph

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

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 reliably 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)
Title of host publicationProceedings of the Annual International Conference on Computational Molecular Biology, RECOMB
Editors Anon
PublisherACM
Pages40-49
Number of pages10
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology - New York, NY, USA
Duration: Mar 22 1998Mar 25 1998

Other

OtherProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology
CityNew York, NY, USA
Period3/22/983/25/98

Fingerprint

Linguistics
Polynomials
Computational complexity
Hardness
Topology

ASJC Scopus subject areas

  • Biochemistry, Genetics and Molecular Biology(all)
  • Computer Science(all)

Cite this

Bonet, M., Steel, M., Warnow, T., & Yooseph, S. (1998). Better methods for solving parsimony and compatibility. In Anon (Ed.), Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB (pp. 40-49). ACM.

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

Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB. ed. / Anon. ACM, 1998. p. 40-49.

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

Bonet, M, Steel, M, Warnow, T & Yooseph, S 1998, Better methods for solving parsimony and compatibility. in Anon (ed.), Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB. ACM, pp. 40-49, Proceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology, New York, NY, USA, 3/22/98.
Bonet M, Steel M, Warnow T, Yooseph S. Better methods for solving parsimony and compatibility. In Anon, editor, Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB. ACM. 1998. p. 40-49
Bonet, Maria ; Steel, Mike ; Warnow, Tandy ; Yooseph, Shibu. / Better methods for solving parsimony and compatibility. Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB. editor / Anon. ACM, 1998. pp. 40-49
@inproceedings{b55cacd5acf5418bb7a70f480af9d803,
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 reliably 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",
language = "English (US)",
pages = "40--49",
editor = "Anon",
booktitle = "Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB",
publisher = "ACM",

}

TY - GEN

T1 - Better methods for solving parsimony and compatibility

AU - Bonet, Maria

AU - Steel, Mike

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1998

Y1 - 1998

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 reliably 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 reliably 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=0031704620&partnerID=8YFLogxK

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

M3 - Conference contribution

AN - SCOPUS:0031704620

SP - 40

EP - 49

BT - Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB

A2 - Anon, null

PB - ACM

ER -