On the Complexity of the Single Individual SNP Haplotyping Problem

Details On the Complexity of the Single Individual SNP Haplotyping Problem On the Complexity of the Single Individual SNP Haplotyping Problem

2005-08-11

arxiv.org/abs/q-bio/0508012v2

Biology

Quantitative Biology

Genomics

26 pages. Related to the WABI2005 paper, "On the Complexity of Several Haplotyping Problems", but with more/different results.

Scientific paper

We present several new results pertaining to haplotyping. These results concern the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype fragments. We consider the complexity of the problems Minimum Error Correction (MEC) and Longest Haplotype Reconstruction (LHR) for different restrictions on the input data. Specifically, we look at the gapless case, where every row of the input corresponds to a gapless haplotype-fragment, and the 1-gap case, where at most one gap per fragment is allowed. We prove that MEC is APX-hard in the 1-gap case and still NP-hard in the gapless case. In addition, we question earlier claims that MEC is NP-hard even when the input matrix is restricted to being completely binary. Concerning LHR, we show that this problem is NP-hard and APX-hard in the 1-gap case (and thus also in the general case), but is polynomial time solvable in the gapless case.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of the Single Individual SNP Haplotyping Problem 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 On the Complexity of the Single Individual SNP Haplotyping Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the Single Individual SNP Haplotyping Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-277758