מיכל זיו-יוקלסון

One of the core classical problems in computational biology is that of constructing the most parsimonious phylogenetic tree interpreting an input set of sequences from the genomes of evolutionarily related organisms. We re-examine the classical Maximum Parsimony (MP) optimization problem for the general (asymmetric) scoring matrix case, where rooted phylogenies are implied, and analyze theworst case bounds of three approaches to MP: The approach of Cavalli-Sforza and Edwards [5], the approach of Hendy and Penny [12], and a new agglomerative, "bottomup" approach we present in this paper. We show that the second and third approaches are faster than the first by a factor of and Θ(n), respectively.