On the Complexity of Several Haplotyping Problems

Details On the Complexity of Several Haplotyping Problems On the Complexity of Several Haplotyping Problems

2005-05-13

arxiv.org/abs/q-bio/0505023v1

Biology

Quantitative Biology

Genomics

12 pages. Submitted to WABI2005, are awaiting a decision on whether it has been accepted

Scientific paper

In this paper we present a collection of results pertaining to haplotyping. The first set of results concerns the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype data. More specifically, we show that an interesting, restricted case of Minimum Error Correction (MEC) is NP-hard, point out problems in earlier claims about a related problem, and present a polynomial-time algorithm for the ungapped case of Longest Haplotype Reconstruction (LHR). Secondly, we present a polynomial time algorithm for the problem of resolving genotype data using as few haplotypes as possible (the Pure Parsimony Haplotyping Problem, PPH) where each genotype has at most two ambiguous positions, thus solving an open problem posed by Lancia et al in "Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms."

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650207