50 years Univerity of Lübeck

Institute for Theoretical Computer Science

PP algorithm by Gusfield

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

PP algorithm by D. Gusfield

Paper
D. Gusfield. Efficient Algorithms for Inferring Evolutionary Trees, Networks Vol. 21, 1991, pp. 19 - 28 abstract author
Running time
O(mn) m: number of taxa, n: number of characters
Input
haplotype matrix without missing data
Output
true if input matrix fits a perfect phylogeny, false otherwise
Description
This simple algorithm checks whether a given set of haplotypes fits in a perfect phylogeny. We use this algorithm to check the output data of the other algorithms.
Source code
Gusfield.java
Javadocs
Gusfield.html