• Links zu
• Mitarbeitern

  Zum Überblick Mitarbeiter

  Professoren

  • Rüdiger Reischuk
  • Till Tantau
  • Maciej Liskiewicz

  Sekretariat

  • Elisa Merkel-Weißer

  Kontakt

  • Räume • Telefon • E-Mail

  Wissenschaftliche Mitarbeiter

  • Max Bannach
  • Katharina Dannenberg
  Zacharias Heinrich
  • Florian Thaeter
  • Benito van der Zander
  • Marcel Wienöbst

  Technische Mitarbeiter

  • Jens Heinrichs
• Wintersemester 2020

Institut für Theoretische Informatik

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