CMU-CS-05-181Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-05-181
Srinath Sridhar, Kedar Dhamdhere*, Guy E. Blelloch,
CMU-CS-05-181.ps
Keywords: Phylogenetic trees, Parsimony, Near-perfect phylogeny
O(nm where
^{2})k is the number f characters that sharefour gametes with some other character. A second, more involved algorithm shows the problem to be fixed parameter tractable in q by solving it in time
q + ^{O(q)}nmO(nm
where ^{2})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, where^{O(q)}2^{O(q2s2)}s is the number of states per character (2 for binary).
We implement the first algorithm and show that it
finds the optimal solution quickly for a selection of population
datasets including mitochondrial and Y chromosome samples from
humans and other primates. Our results describe the first practical
phylogenetic tree reconstruction algorithm that finds guaranteed
optimal solutions while being easily implemented and computationally
feasible for data sets of biologically meaningful size and complexity.
37 pages
*Google, Inc. Mountain View, CA
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |