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