Diese Diplomarbeit behandelt einen auf Lagrange-Relaxierung beruhenden, heuristischen Ansatz zum String Barcoding Problem (SBP). Dabei handelt es sich um ein kombinatorisches Optimierungsproblem, das im Kern einen Spezialfall des Set Cover Problems (SCP) darstellt und wie dieses NP-schwer ist. Es existieren zahlreiche Anwendungen mit biologischem und medizinischem Hintergrund.<br />Ausgehend von einer Menge von bekannten Sequenzen über einem beliebigen Alphabet, beispielsweise DNA, suchen wir eine Menge kurzer Teilsequenzen, so genannte Probes, so dass wir in der Lage sind, eine unbekannte Sequenz (Sample) eindeutig als eine der bekannten zu identifizieren, indem wir jene Probes bestimmen, welche als Teilsequenzen im Sample vorkommen. Das Problem umfasst zwei wesentliche Aspekte: die Bestimmung aller möglichen Probes und die Auswahl einer geeigneten Teilmenge mit minimaler Kardinalität.<br />Das Problem wurde unter verschiedenen Namen behandelt und in dieser Form 2002 von Rash und Gusfield vorgestellt. Ihr Lösungsansatz liefert optimale Lösungen und beruht auf Integer Linear Programming sowie der Verwendung von Suffix Trees zur Generierung einer vollständigen, nicht-redundanten Menge von Probes.<br />Wir haben mehrere SBP und SCP Ansätze untersucht. Eine der erfolgreichsten SCP Heuristiken, basierend auf dem Prinzip der Lagrange-Relaxierung, wurde 1999 von Caprara et al. publiziert. Wir haben den Algorithmus adaptiert, um herauszufinden, ob er, angewandt auf das strukturell sehr ähnliche SBP, Ergebnisse vergleichbarer Qualität liefert. Obwohl unsere Resultate diese Annahme nicht generell stützen, zeigt die Heuristik vor allem bei sehr komplexen Instanzen ihre Stärke und generiert hier wesentlich bessere Lösungen als einfachere Heuristiken.<br />
de
dc.description.abstract
This thesis deals with a heuristic approach based on Lagrangian relaxation to the string barcoding (SB) problem, a close cousin to the well-known combinatorial set cover (SC) problem. It has recently been proven to be NP-hard and has many real-world applications, particularly in the fields of medicine and biology.<br />Given a set of sequences over some alphabet, DNA for instance, we aim at finding a set of short sequences, so-called probes, such that we are able to identify an unknown sample sequence as one of the input sequences by determining which probes are subsequences of the sample, and which are not. The problem is twofold: the determination of all possible probes and the selection of a suitable subset of minimum cardinality.<br />The problem has been dealt with under various other names and has in this form been introduced by Rash and Gusfield in 2002. They proposed an exact approach based on integer linear programming and the use of suffix trees to generate a complete, non-redundant set of candidate probes.<br />We evaluated several approaches for the SB as well as the SC problem.<br />One of the leading heuristics for the SC problem, based on Lagrangian relaxation, has been proposed by Caprara et al. in 1999. We adapted the algorithm to see if it works equally well when applied to the structurally very similar SB problem.<br />Though the results we obtained are somewhat mixed, the heuristic shows its strength with very complex instances and delivers much better results compared to simpler heuristics.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Bioinformatik
de
dc.subject
String Barcoding
de
dc.subject
Lagrange Relaxierung
de
dc.subject
Set Cover
de
dc.subject
bioinformatics
en
dc.subject
string barcoding
en
dc.subject
Lagrangian relaxation
en
dc.subject
set cover
en
dc.title
Algorithmic approaches to the string barcoding problem
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Philipp Neuner
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen