50 years Univerity of Lübeck

Institute for Theoretical Computer Science

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

Keine deutsche Version
Uni Lübeck ResearchProjectsHaplo-ComplexityHaplo AlgorithmsPPPH algorithm

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