• 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 Ding, Filkov and Gusfield

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

Paper

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

Input

genotype matrix without missing data

Output

pairs of haplotypes that fit a perfect phylogeny if any exists with the given input matrix

Description

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

DingFilkovGusfield.java

Javadocs

DingFilkovGusfield.html