The incomplete perfect phylogeny haplotype problem.
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.
Kimmel
Gad
G
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. kgad@tau.ac.il
Shamir
Ron
R
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods*; D014644:Genetic Variation / Q000235:genetics; D006239:Haplotypes / Q000235:genetics*; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid