The complexity of the single individual SNP haplotyping problem

DOI10.1007/S00453-007-0029-ZMaRDI QIDQ2461636zbMATH OpenOpenAlexFDO

Authors Leo Van Iersel, Steven Kelk, John Tromp, Rudi L. Cilibrasi

Publication date 28 November 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/q-bio/0508012

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Abstract: 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.

Recommendations

• Polynomial and APX-hard cases of the individual haplotyping problem
• New results for the longest haplotype reconstruction problem
• scientific article; zbMATH DE number 1945152
• scientific article; zbMATH DE number 1877046
• The Longest Haplotype Reconstruction Problem Revisited

Cited in

(23)

• NP-hardness of Euclidean sum-of-squares clustering
• On the complexity of SNP block partitioning under the perfect phylogeny model
• Polynomial and APX-hard cases of the individual haplotyping problem
• On a fixed haplotype variant of the minimum error correction problem
• A guided tour to computational haplotyping
• Parameterized low-rank binary matrix approximation
• Haplotype assembly from aligned weighted SNP fragments
• Algorithmic approaches for the single individual haplotyping problem
• On the complexity of MMSNP
• On the fixed parameter tractability and approximability of the minimum error correction problem
• The Longest Haplotype Reconstruction Problem Revisited
• Parameterizing MAX SNP Problems Above Guaranteed Values
• Haplotype Inferring Via Galled-Tree Networks Is NP-Complete
• On the Approximability of Some Haplotyping Problems
• New results for the longest haplotype reconstruction problem
• scientific article; zbMATH DE number 2040938 (Why is no real title available?)
• scientific article; zbMATH DE number 1877046 (Why is no real title available?)
• Parameterized low-rank binary matrix approximation
• scientific article; zbMATH DE number 7378704 (Why is no real title available?)
• Parameterized complexity of categorical clustering with size constraints
• Parameterized complexity of categorical clustering with size constraints
• A practical exact algorithm for the individual haplotyping problem MEC/GI
• An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs

This page was built for publication: The complexity of the single individual SNP haplotyping problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461636)