Better methods for solving parsimony and compatibility
Marı́a Luisa Bonet, Mike Steel, Tandy J. Warnow, Shibu Yooseph · 1998
Evolutionary tree reconstruction is a challenging problem with important applications in Biology and Liiguistics.In Biology, one of the most promising approaches to tree reconstruction is to 6nd the "maximum parsimony" tree, while in Liignistics, the use of the "m&mum 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, Uptimmnl l+ee 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.