50 Jahre Uni Lübeck

Institut für Theoretische Informatik

PPH algorithm by Eskin, Halperin and Karp

PPH algorithm by E. Eskin, E. Halperin and R. M. Karp

E. Eskin, E. Halperin, and R. M. Karp. Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny, Journal of Bioinformatics and Computational Biology Vol. 1, No. 1, 2003, pp. 1 - 20 abstract author
Running time
O(m2n) 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
This Algorithm does a sample of transformations to the input genotype matrix and then starts again recursively with the new matrix. For the transformations, temporal graphs are produced and it is checked whether they are bipartite. After every transformation the matrix is simplified, so a recursion can start.
Source code