A polynomial case of the parsimony haplotyping problem

A polynomial case of the parsimony haplotyping problem

0.00 Avg rating—0 Votes
Article ID: iaor20062845
Country: Netherlands
Volume: 34
Issue: 3
Start Page Number: 289
End Page Number: 295
Publication Date: May 2006
Journal: Operations Research Letters
Authors: ,
Keywords: heuristics
Abstract:

The parsimony haplotyping problem was shown to be NP-hard when each genotype had k⩽3 ambiguous positions, while the case for k⩽2 was open. In this paper, we show that the case for k≤2 is polynomial, and we give approximation and FPT algorithms for the general case of k⩾0 ambiguous positions.

Reviews

Required fields are marked *. Your email address will not be published.