BETTER METHODS FOR SOLVING PARSIMONY AND COMPATIBILITY

Evolutionary tree reconstruction is a challenging problem with importa nt applications in biology and linguistics, In biology, one of the mos t promising approaches to tree reconstruction is to find the ''maximum parsimony'' tree, while in linguistics, the use of the ''maximum comp atibility'' method has been very useful. However, these problems are N P-hard, and current approaches to solving these problems amount to heu ristic searches through the space of possible tree topologies (a searc h which can, on large trees, take months to complete), In this paper, we present a new technique, Optimal Tree Refinement, for reconstructin g very large trees. Our technique is motivated by recent experimental studies which have shown that certain polynomial time methods often re turn contractions of the true tree. We study the use of this technique in solving maximum parsimony and maximum compatibility, and present b oth hardness results and polynomial time algorithms.