The complexity of the single individual SNP haplotyping problem
The complexity of the single individual SNP haplotyping problem
复制标题
DOI：
10.1007/s00453-007-0029-z
复制
发表时间：
2007-09-01
期刊：
影响因子：
1.1
通讯作者：
Tromp, John
中科院分区：
文献类型：
--
作者：
Cilibrasi, Rudi;van Iersel, Leo;Tromp, John
我们提出了几个新的结果有关单倍型。这些结果涉及从不完整和/或不完全测序的单倍型片段重建单倍型的组合问题。我们考虑了最小误差校正（MEC）和最长单体型重建（LHR）问题的复杂性，对输入数据的不同限制。具体来说，我们研究了无间隙的情况，其中输入的每一行对应于无间隙的单体型片段，以及1-间隙的情况，其中每个片段最多允许一个间隙。我们证明了MEC是APX硬的1间隙的情况下，仍然NP硬的无间隙的情况下。此外，我们质疑早先的说法，MEC是NP难的，即使输入矩阵被限制为完全二进制。关于LHR，我们表明，这个问题是NP-难和APX-硬在1间隙的情况下（因此也在一般情况下），但在无间隙的情况下是多项式时间可解的。
We present several new results pertaining to haplotyping. These results concern the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype fragments. We consider the complexity of the problems Minimum Error Correction (MEC) and Longest Haplotype Reconstruction (LHR) for different restrictions on the input data. Specifically, we look at the gapless case, where every row of the input corresponds to a gapless haplotype-fragment, and the 1-gap case, where at most one gap per fragment is allowed. We prove that MEC is APX-hard in the 1-gap case and still NP-hard in the gapless case. In addition, we question earlier claims that MEC is NP-hard even when the input matrix is restricted to being completely binary. Concerning LHR, we show that this problem is NP-hard and APX-hard in the 1-gap case (and thus also in the general case), but is polynomial time solvable in the gapless case.