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

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

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)

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

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)