Finding a Perfect Phylogeny

This work is based on the paper ‘Incomplete perfect phylogeny ’ by Pe’er et al. (2000). The goal of this paper is to review some important findings concerning the problem of constructing a perfect phylogeny if one exists. In the first section, I will present some concepts used in phylogenetics in general. Then, we will discuss the complete directed perfect phylogeny problem and review Gusfield’s algorithm (Gusfield, 1991), which solves this problem in linear time. In the third section, I introduce the problem of incomplete data, where some character states are missing, and we ask if the missing states can be completed in a way admitting a perfect phylogeny. Pe’er et al. (2000) described an algorithm, which solves this problem in near-linear time. Concluding, we will discuss some applications and extensions of the algorithm by Pe’er et al. (2000) in the forth section.