Program LPPH solves the same problem solved by programs DPPH, GPPH and BPPH.
However, program LPPH is faster in both theory
and practice than all prior programs.
NOTE: The current version assumes that the ancestral sequence is the all-zero sequence, so the ancestral
state of every site is 0. It can happen that there will be a perfect phylogeny solution with some ancestral
sequence other than all-zero, and not with the all-zero sequence. We will post a general version shortly that
handles the case when no ancestral sequence is known in advance, and the case that a specified ancestral sequence
other than all-zero is known.
This package was written by Zhihong Ding
at U.C. Davis Computer Science under the
direction of Dan Gusfield.
To cite the general problem and first results, please use:
"Haplotyping as Perfect Phylogeny: Conceptual
Framework and Efficient Solutions" D. Gusfield
In Proceedings of RECOMB, Sixth Annual Conference on Research in
Computational Molecular Biology, April 2002
To cite the specific method implemented in program LPPH, please use:
A Linear-Time Solution to the Perfect Phylogeny Haplotyping (PPH) Problem.
Z. Ding, V. Filkov and D. Gusfield
Proceedings of RECOMB 2005
Papers can be found at:
recent papers
Copyright (C) 2005 Z. Ding and D. Gusfield
We give no warranties, and no rights for commercial use.
Executable versions of this program are now available for the following platforms: