Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems

Details Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems

2006-05-16

arxiv.org/abs/q-bio/0605024v3

Biology

Quantitative Biology

Other Quantitative Biology

Updated version of our "Beaches of Islands of Tractability..." paper (which appeared in WABI2006 and as a Technische Universit

Scientific paper

The problem Parsimony Haplotyping (PH) asks for the smallest set of haplotypes which can explain a given set of genotypes, and the problem Minimum Perfect Phylogeny Haplotyping (MPPH) asks for the smallest such set which also allows the haplotypes to be embedded in a perfect phylogeny, an evolutionary tree with biologically-motivated restrictions. For PH, we extend recent work by further mapping the interface between ``easy'' and ``hard'' instances, within the framework of (k,l)-bounded instances where the number of 2's per column and row of the input matrix is restricted. By exploring, in the same way, the tractability frontier of MPPH we provide the first concrete, positive results for this problem, and the algorithms underpinning these results offer new insights about how MPPH might be further tackled in the future. In addition, we construct for both PH and MPPH polynomial time approximation algorithms, based on properties of the columns of the input matrix. We conclude with an overview of intriguing open problems in PH and MPPH.

Affiliated with

Also associated with

No associations

Rating

Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny 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 Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-276165