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

Paper
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
Input
genotype matrix without missing data
Output
pairs of haplotypes that fit a perfect phylogeny if any exists with the given input matrix
Description
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
EskinHalperinKarp.java
Javadocs
EskinHalperinKarp.html