• 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

PP algorithm by Gusfield

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