Computer Science Department
School of Computer Science, Carnegie Mellon University
A New Algorithm for the Reconstruction of
Near-Perfect Binary Phylogenetic Trees
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch,
Eran Halperin*, Ramamoorthi Ravi**, Russell Schwartz***
March 2005
CMU-CS-05-119.ps
CMU-CS-05-119.pdf
In this paper, we consider the problem of reconstructing near-perfect
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
near-perfect 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 near-perfect phylogeny is bounded by q,
then we can reconstruct the optimal near-perfect phylogenetic tree
in time 2O(q2)nm2
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 nmO(q)2O(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 qO(q)nm2.
20 pages
* ICSI, University of California at Berkeley
** Tepper School of Business, Carnegie Mellon University
*** Department of Biological Sciences, Carnegie Mellon University
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu
School of Computer Science homepage