Title: Algorithmic approaches to the string barcoding problem
Language: English
Authors: Neuner, Philipp 
Qualification level: Diploma
Keywords: Bioinformatik; String Barcoding; Lagrange Relaxierung; Set Cover
bioinformatics; string barcoding; Lagrangian relaxation; set cover
Advisor: Raidl, Günther
Issue Date: 2007
Number of Pages: 72
Qualification level: Diploma
Abstract: 
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.
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.
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.
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.

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.
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.
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.
We evaluated several approaches for the SB as well as the SC problem.
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.
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-16487
http://hdl.handle.net/20.500.12708/14235
Library ID: AC05035649
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Algorithmic approaches to the string barcoding problem.pdf832.07 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

14
checked on Feb 18, 2021

Download(s)

57
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.