Polynomial and APX-hard cases of the individual haplotyping problem

DOI10.1016/j.tcs.2004.12.017zbMath1080.68037OpenAlexW2022170497MaRDI QIDQ1781994

Giuseppe Lancia, Vineet Bafna, Romeo Rizzi, Sorin Istrail

Publication date: 10 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.017

zbMATH Keywords

APX-hardnessFixed-parameter tractabilityHaplotyping

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Related Items

The complexity of binary matrix completion under diameter constraints, Parameterized complexity analysis for the closest string with wildcards problem, An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs, A practical algorithm based on particle swarm optimization for haplotype reconstruction, Algorithmic approaches for the single individual haplotyping problem, On the Approximability of Some Haplotyping Problems

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item