TY - GEN
T1 - A note on solution sizes in the haplotype tagging snps problem
AU - Vinterbo, Staal
AU - Dreiseitl, Stephan
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - The problem of finding a minimal set of single nucleotide polymorphisms that can distinguish between given haplotypes is known to be NP-hard. In this paper, we summarize the properties of a simple polynomial-time approximation algorithm. We investigate which regions of the solution space contain a phase transition, i.e., the range of solution sizes which are neither trivially easy nor impossibly hard to solve. We give empirical results showing that the phase transition region is an interval of length O(log(n)) centered around O(log(n)).
AB - The problem of finding a minimal set of single nucleotide polymorphisms that can distinguish between given haplotypes is known to be NP-hard. In this paper, we summarize the properties of a simple polynomial-time approximation algorithm. We investigate which regions of the solution space contain a phase transition, i.e., the range of solution sizes which are neither trivially easy nor impossibly hard to solve. We give empirical results showing that the phase transition region is an interval of length O(log(n)) centered around O(log(n)).
KW - Combinatorial optimization
KW - Haplotype tagging
KW - Minimal hitting set
KW - Single nucleotide polymorphism
UR - http://www.scopus.com/inward/record.url?scp=84870175116&partnerID=8YFLogxK
M3 - Conference contribution
SN - 8469007262
SN - 9788469007266
T3 - International Mediterranean Modelling Multiconference, I3M
SP - 659
EP - 663
BT - International Mediterranean Modelling Multiconference, IMM
T2 - International Mediterranean Modelling Multiconference, I3M 2006
Y2 - 4 October 2006 through 6 October 2006
ER -