PMID- 16597255
OWN - NLM
STAT- MEDLINE
DCOM- 20060615
LR  - 20061115
IS  - 1066-5277 (Print)
IS  - 1066-5277 (Linking)
VI  - 13
IP  - 2
DP  - 2006 Mar
TI  - A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem.
PG  - 522-53
AB  - Since the introduction of the Perfect Phylogeny Haplotyping (PPH) Problem in 
      RECOMB 2002 (Gusfield, 2002), the problem of finding a linear-time 
      (deterministic, worst-case) solution for it has remained open, despite broad 
      interest in the PPH problem and a series of papers on various aspects of it. In 
      this paper, we solve the open problem, giving a practical, deterministic 
      linear-time algorithm based on a simple data structure and simple operations on 
      it. The method is straightforward to program and has been fully implemented. 
      Simulations show that it is much faster in practice than prior nonlinear methods. 
      The value of a linear-time solution to the PPH problem is partly conceptual and 
      partly for use in the inner loop of algorithms for more complex problems, where 
      the PPH problem must be solved repeatedly.
FAU - Ding, Zhihong
AU  - Ding Z
AD  - Department of Computer Science, University of California, Davis, 95616, USA. 
      dingz@cs.ucdavis.edu
FAU - Filkov, Vladimir
AU  - Filkov V
FAU - Gusfield, Dan
AU  - Gusfield D
LA  - eng
PT  - Comparative Study
PT  - Journal Article
PT  - Research Support, U.S. Gov't, Non-P.H.S.
PL  - United States
TA  - J Comput Biol
JT  - Journal of computational biology : a journal of computational molecular cell 
      biology
JID - 9433358
SB  - IM
MH  - *Algorithms
MH  - *Computational Biology
MH  - Data Interpretation, Statistical
MH  - Genetic Predisposition to Disease
MH  - *Haplotypes
MH  - Humans
MH  - *Phylogeny
EDAT- 2006/04/07 09:00
MHDA- 2006/06/16 09:00
CRDT- 2006/04/07 09:00
PHST- 2006/04/07 09:00 [pubmed]
PHST- 2006/06/16 09:00 [medline]
PHST- 2006/04/07 09:00 [entrez]
AID - 10.1089/cmb.2006.13.522 [doi]
PST - ppublish
SO  - J Comput Biol. 2006 Mar;13(2):522-53. doi: 10.1089/cmb.2006.13.522.