• Links zu
• Mitarbeitern

  Zum Überblick Mitarbeiter

  Professoren

  • Rüdiger Reischuk
  • Till Tantau
  • Maciej Liskiewicz

  Sekretariat

  • Elisa Merkel-Weißer

  Kontakt

  • Räume • Telefon • E-Mail

  Wissenschaftliche Mitarbeiter

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

  Technische Mitarbeiter

  • Jens Heinrichs
• Wintersemester 2020

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(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