A note on solution sizes in the haplotype tagging snps problem

Staal Vinterbo, Stephan Dreiseitl

Publikation: Beitrag in Buch/Bericht/TagungsbandKonferenzbeitragBegutachtung

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

OriginalspracheEnglisch
TitelInternational Mediterranean Modelling Multiconference, IMM
Seiten659-663
Seitenumfang5
PublikationsstatusVeröffentlicht - 2006
VeranstaltungInternational Mediterranean Modelling Multiconference, I3M 2006 - Barcelona, Spanien
Dauer: 4 Okt 20066 Okt 2006

Publikationsreihe

NameInternational Mediterranean Modelling Multiconference, I3M

Konferenz

KonferenzInternational Mediterranean Modelling Multiconference, I3M 2006
LandSpanien
OrtBarcelona
Zeitraum04.10.200606.10.2006

Fingerprint Untersuchen Sie die Forschungsthemen von „A note on solution sizes in the haplotype tagging snps problem“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren