Projects per year
Abstract
Recent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genomewide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for largescale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkagedisequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of noncontiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is
hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
Original language  English 

Journal  Discrete Mathematics 
Volume  2009 
Issue number  309(18) 
Pages (fromto)  56105617 
Publication status  Published  2009 
Projects
 1 Finished

Complexity of haplotyping problems
Tantau, T., Schnoor, I., Elberfeld, M., Kuczewski, J. & Pohlmann, J.
01.01.05 → 31.12.10
Project: DFG Projects › DFG Individual Projects