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

Keywords: Phylogenetic trees, Parsimony, Near-perfect phylogeny

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
School of Computer Science homepage

This page maintained by