Home

Home

BPPH

BPPH is a program for inferring haplotypes from genotypes to determine if there are resulting haplotypes that fit a tree model (i.e. a perfect phylogeny, a coalescent).
In more population genetic terms, BPPH determines whether a set of SNP genotypes can be explained by haplotype pairs that could have evolved on a coalescent under the no-recombination, infinite sites model. Hence it determines for SNP genotype data what the three or four gametes test (depending on whether the tree is rooted or not) determines for haplotype data.

Program BPPH solves the same problem solved by program PPH (now called GPPH to distinguish it from the other programs for the PPH problem). However, program BPPH is based on the algorithm of Eskin, Halperin and Karp, described in "Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny" Technical Report UCB/CSD1-1196 August 2002.

This package was written by Ren-Hua Chung 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

A comparison of the various perfecty phylogeny haplotyping algorithms and programs appears in:
"Empirical Evaluation of Perfect Phylogeny Haplotypers and Haplotyping"

by R.H. Chung and D. Gusfield
Proceedings of the 2003 Cocoon Conference, published by Springer in the LNCS series.

Papers can be found at: recent publications

Copyright (C) 2002 R.H. Chung 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: