50 Jahre Uni Lübeck

Institut für Theoretische Informatik

PPH algorithm by Ding, Filkov and Gusfield

PPH algorithm by Z. Ding, V. Filkov and D. Gusfield

Z. Ding, V. Filkov, and D. Gusfield. A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem, Journal Of Computational Biology Vol. 13, No. 2, 2006, pp. 522-553 abstract author
Running time
O(mn) m: number of taxa, n: number of characters
genotype matrix without missing data
pairs of haplotypes that fit a perfect phylogeny if any exists with the given input matrix
The idea of this algorithm is, to build a structure called shadow tree. This structure stores all information about all so far possible perfect phylogenies for the input genotype matrix. This data structure is rather complex, since it not only save one tree, but all possible trees. The algorithm consists of several methods that process the rows of the matrix one after another. The information that are induced by this row are then inserted into the data structure to refine the shadow tree.
Source code