کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419434 | 683808 | 2012 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: New results for the Longest Haplotype Reconstruction problem New results for the Longest Haplotype Reconstruction problem](/preview/png/419434.png)
The haplotyping problem has emerged in recent years as one of the most relevant problems in Computational Biology. In particular, in the Single Individual Haplotyping (SIH) problem, starting from a matrix of incomplete haplotype fragments, the goal is the reconstruction of the two complete haplotypes of an individual. In this paper we consider one of the variants of the Single Individual Haplotyping problem, the Longest Haplotyping Reconstruction (LHR) problem. We prove that the LHR problem is NP-hard even in the restricted case when the input matrix is error-free. Furthermore, we investigate the approximation complexity of the problem, and we show that the problem cannot be approximated within factor 2logδnm2logδnm for any constant δ<1δ<1, unless NP⊆DTIME[2polylognm]. Finally, we exhibit a fixed-parameter algorithm for the LHR problem, where the parameter is the size of the two reconstructed haplotypes.
Journal: Discrete Applied Mathematics - Volume 160, Issue 9, June 2012, Pages 1299–1310