Article ID Journal Published Year Pages File Type
1143374 Operations Research Letters 2006 7 Pages PDF
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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A polynomial case of the parsimony haplotyping problem
Authors
, ,