Research PapersNo Access

THE INCOMPLETE PERFECT PHYLOGENY HAPLOTYPE PROBLEM

GAD KIMMEL

School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Search for more papers by this author

and

RON SHAMIR

School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Search for more papers by this author

https://doi.org/10.1142/S0219720005001090Cited by:13 (Source: Crossref)

Abstract

The problem of resolving genotypes into haplotypes, under the perfect phylogeny model, has been under intensive study recently. All studies so far handled missing data entries in a heuristic manner. We prove that the perfect phylogeny haplotype problem is NP-complete when some of the data entries are missing, even when the phylogeny is rooted. We define a biologically motivated probabilistic model for genotype generation and for the way missing data occur. Under this model, we provide an algorithm, which takes an expected polynomial time. In tests on simulated data, our algorithm quickly resolves the genotypes under high rates of missing entries.

Keywords:

References

N. Alon and J. H. Spencer , The Probabilistic Method ( John Wiley and Sons, Inc. , 2000 ) . Crossref, Google Scholar
V. Bafnaet al., J. Comput. Biol. 10(3–4), 323 (2003). Crossref, Medline, Google Scholar
A. Clark, Mol. Biol. Evol. 7(2), 111 (1990). Medline, Google Scholar
M. J. Dalyet al., Nature Genet. 29(2), 229 (2001). Crossref, Medline, Google Scholar
E. Eskin, E. Halperin and R. M. Karp, Proceedings of the Seventh Annual International Conference on Research in Computational Molecular Biology (RECOMB 03) (The Association for Computing Machinery, 2003) pp. 104–113. Google Scholar
L. Excoffier and M. Slatkin, Mol. Biol. Evol. 12(5), 912 (1995). Google Scholar
S. B. Gabrielet al., Science 296, 2225 (2002). Crossref, Medline, Google Scholar
Gramm J., Nierhoff T., Sharan R., Tantau T., On the complexity of haplotyping via perfect phylogeny, in Proceedings of the Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, pp. 35–46, 2004 . Google Scholar
D. Gusfield, Networks 21, 19 (1991). Crossref, Google Scholar
D. Gusfield, Proceedings of the Sixth Annual International Conference on Research in Computational Molecular Biology (RECOMB 02) (The Association for Computing Machinery, 2002) pp. 166–175. Crossref, Google Scholar
B. V. Halldorssonet al., Proceedings of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS), Lecture Notes in Computer Science 2731 (Springer, 2003) pp. 26–47. Crossref, Google Scholar
E. Halperin and R. M. Karp, Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 04) (The Association for Computing Machinery, 2004) pp. 10–19. Crossref, Google Scholar
G. H. Hardy, Science 18, 49 (1908). Google Scholar
M. R. Hoehe, Pharmacogenomics 4(5), 547 (2003). Crossref, Medline, Google Scholar
M. R. Hoeheet al., Hum. Mol. Genet. 9, 2895 (2000). Crossref, Medline, Google Scholar
R. Shamiret al., SIAM J. Comp. 33(3), 590 (2004). Google Scholar
Kimmel G., Shamir R., The incomplete perfect phylogeny haplotype problem, in Proceedings of the Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, pp. 59–70, 2004 . Google Scholar
L. Kruglyak and D. A. Nickerson, Nature Genet. 27, 234 (2001). Crossref, Medline, Google Scholar
J. Long, R. C. Williams and M. Urbanek, Amer. J. Hum. Genet. 56(3), 799 (1995). Medline, Google Scholar
T. Niuet al., Amer. J. Hum. Genet. 70(1), 157 (2002). Crossref, Medline, Google Scholar
N. Patilet al., Science 294, 1719 (2001). Crossref, Medline, Google Scholar
R. Sachidanandamet al., Nature 291, 1298 (2001). Google Scholar
M. A. Steel, J. Classif. 9, 91 (1992). Crossref, Google Scholar
M. Stephens, N. J. Smith and P. Donnelly, Amer. J. Hum. Genet. 68(4), 978 (2001). Crossref, Medline, Google Scholar