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 language | English (US) |
|---|---|
| Pages (from-to) | 391-407 |
| Number of pages | 17 |
| Journal | Journal of Computational Biology |
| Volume | 5 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jan 1 1998 |
| Externally published | Yes |
Fingerprint
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 journal › Article
}
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 -