title: Pure parsimony xor haplotyping.
abstract: The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. The xor-genotype data is a cheaply obtainable type of data distinguishing heterozygous from homozygous sites without identifying the homozygous alleles. In this paper, we propose a formulation based on a well-known model used in haplotype inference: pure parsimony. We exhibit exact solutions of the problem by providing polynomial time algorithms for some restricted cases and a fixed-parameter algorithm for the general case. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Furthermore, we show that the problem has a polynomial time k-approximation, where k is the maximum number of xor-genotypes containing a given single nucleotide polymorphisms (SNP). Finally, we propose a heuristic and produce an experimental analysis showing that it scales to real-world large instances taken from the HapMap project.
authors.affiliation: Dipartimento di Informatica, Sistemistica e Comunicazione, Università Degli Studi di Milano-Bicocca, Viale Sarca 336, Milano 20126, Italy. bonizzoni@disco.unimib.it
authors.forename: Paola
authors.initials: P
authors.lastname: Bonizzoni
authors.forename: Gianluca
authors.initials: G
authors.lastname: Della Vedova
authors.forename: Riccardo
authors.initials: R
authors.lastname: Dondi
authors.forename: Yuri
authors.initials: Y
authors.lastname: Pirola
authors.forename: Romeo
authors.initials: R
authors.lastname: Rizzi
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D005838:Genotype; D006239:Haplotypes; D006579:Heterozygote; D020641:Polymorphism, Single Nucleotide