• 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

PPPH algorithm by Gramm, Hartman, Nierhoff, Sharan, Tantau

PPPH algorithm by J. Gramm, T. Hartman, T. Nierhoff, R. Sharan and T. Tantau

Paper

J. Gramm, T. Hartmann, T. Nierhoff, R. Sharan, and T. Tantau. On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model, Proceedings of Workshop on Algorithms in Bioinformatics (WABI) Lecture Notes In Computer Science Vol. 4175, 2006, pp. 92 - 102 abstract

Running time

O(mn) m: number of taxa, n: number of characters

Input

genotype matrix without missing data

Output

a block partitioning of the input matrix, where every block fits a perfect path phylogeny

Description

This algorithm tries to get a partition of the input columns in the smallest possible number of sets. After evoking this algorithm each of the sets fits a perfect path phylogeny.
The main idea of this algorithm is the reduction of this problem to the matching problem for an arbitrary graph. The problem was that there are no free optimal matching algorithms implemented in Java available. Instead, we used a (very good) heuristic to calculate the matching.

Source code

GrammHartmanNierhoffSharanTantau.java

Javadocs

GrammHartmanNierhoffSharanTantau.html