
CMUCS05119
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS05119
A New Algorithm for the Reconstruction of
NearPerfect Binary Phylogenetic Trees
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch,
Eran Halperin*, Ramamoorthi Ravi**, Russell Schwartz***
March 2005
CMUCS05119.ps
CMUCS05119.pdf
Keywords: Phylogenetic trees, Parsimony, Nearperfect phylogeny
In this paper, we consider the problem of reconstructing nearperfect
phylogenetic trees using binary characters. A perfect phylogeny assumes that
every character mutates at most once in the evolutionary tree. The algorithm
for reconstructing a perfect phylogeny for binary characters is
computationally efficient but impractical in most real settings. A
nearperfect phylogeny relaxes this assumption by allowing characters to
mutate a constant number of times. We show that if the number of additional
mutations required by the nearperfect phylogeny is bounded by q,
then we can reconstruct the optimal nearperfect phylogenetic tree
in time 2^{O(q2)}nm^{2}
where n is the number of taxa and m is the number of
characters. This is a significant improvement over the previous
best result of nm^{O(q)}2^{O(q2r2)}
where r is the number of states per character (2 for binary).
This improvement could lead to the first practical phylogenetic
tree reconstruction algorithm that is both computationally feasible
and biologically meaningful. We finally outline a method to improve
the bound to q^{O(q)}nm^{2}.
20 pages
* ICSI, University of California at Berkeley
** Tepper School of Business, Carnegie Mellon University
*** Department of Biological Sciences, Carnegie Mellon University
