A note on solution sizes in the haplotype tagging snps problem

Staal Vinterbo, Stephan Dreiseitl

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review


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)).

Original languageEnglish
Title of host publicationInternational Mediterranean Modelling Multiconference, IMM
Number of pages5
Publication statusPublished - 2006
EventInternational Mediterranean Modelling Multiconference, I3M 2006 - Barcelona, Spain
Duration: 4 Oct 20066 Oct 2006

Publication series

NameInternational Mediterranean Modelling Multiconference, I3M


ConferenceInternational Mediterranean Modelling Multiconference, I3M 2006


  • Combinatorial optimization
  • Haplotype tagging
  • Minimal hitting set
  • Single nucleotide polymorphism


Dive into the research topics of 'A note on solution sizes in the haplotype tagging snps problem'. Together they form a unique fingerprint.

Cite this