• 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

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