Pure Parsimony Xor Haplotyping

Details Pure Parsimony Xor Haplotyping Pure Parsimony Xor Haplotyping

2010-01-08

arxiv.org/abs/1001.1210v1

Computer Science

Computational Engineering, Finance, and Science

Scientific paper

10.1109/TCBB.2010.52

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 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.

Affiliated with

Also associated with

No associations

Rating

Pure Parsimony Xor Haplotyping does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pure Parsimony Xor Haplotyping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pure Parsimony Xor Haplotyping will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-501972