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

Abstract

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
Pages659-663
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

Conference

ConferenceInternational Mediterranean Modelling Multiconference, I3M 2006
Country/TerritorySpain
CityBarcelona
Period04.10.200606.10.2006

Keywords

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

Fingerprint

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