50 Jahre Uni Lübeck

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

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
genotype matrix without missing data
a block partitioning of the input matrix, where every block fits a perfect path phylogeny
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