Related Experiment Video
Updated: Aug 13, 2026

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
An efficient algorithm for Perfect Phylogeny Haplotyping
Ravi Vijayasatya1, Amar Mukherjee
1School of Computer Science, University of Central Florida, 32816-2362, USA. rvijaya@cs.ucf.edu
Abstract:
The Perfect Phylogeny Haplotyping (PPH) problem is one of the many computational approaches to the Haplotype Inference (HI) problem. Though there are many O(nm(2)) solutions to the PPH problem, the complexity of the PPH problem itself has remained an open question. In this paper, We introduce the FlexTree data structure that represents all the solutions for a PPH instance. We also introduce row-ordering that arranges the genotypes in a more manageable fashion. The column ordering, the FlexTree data structure and the row ordering together make the O(nm) OPPH algorithm possible. We also present some results on simulated data which demonstrate that the OPPH algorithm performs quiet impressively when compared to the earlier O(nm(2)) algorithms.
Related Concept Videos
Evolutionary Relationships through Genome Comparisons
Microbial Phylogeny
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Modern Molecular Taxonomy

