Algorithmic approaches to the string barcoding problem

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

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.