• Links to
• Staff

  Staff Overview

  Professors

  • Rüdiger Reischuk
  • Till Tantau
  • Maciej Liskiewicz

  Secretary

  • Elisa Merkel-Weißer

  Contact

  • Rooms • Phone • Mail

  Research assistants

  • Max Bannach
  • Katharina Dannenberg
  Zacharias Heinrich
  • Florian Thaeter
  • Benito van der Zander
  • Marcel Wienöbst

  Technical staff

  • Jens Heinrichs
• Winter semester 2020

Institute for Theoretical Computer Science

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(m²n) 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