Daniel H. Huson, Lisa Vawter and Tandy J. Warnow
Abstract
In an earlier paper, we described a new method for phylogenetic
tree reconstruction, called the Disk Covering Method, or DCM.
This is a general method which can be used with any existing phylogenetic
method in order to improve its performance. We showed analytically
and experimentally that when DCM is used in conjunction with polynomial
time distance-based methods, it improves the accuracy of the trees
reconstructed. In this paper, we discuss a variant on DCM, which
we call DCM2, that is designed to be used with phylogenetic methods
whose objective is the solution of NP-hard optimization problems.
We show that DCM2 can be used to accelerate searches for Maximum
Parsimony trees. We also motivate the need for solutions to NP-hard
optimization problems by showing that on some very large and important
datasets, the most popular (and presumably best performing) polynomial
time methods have poor accuracy.