Branch-And-Cut-Algorithmen fuer Sequenz-Alignment-Probleme

Hier wurde schon jahrzehntelang geforscht, bevor der Begriff Bioinformatik geformt wurde.
Mit Hilfe von Sequenz-Alignments wurden die Ursachen von genetisch bedingten Krankheiten
aufgekl"art. Sie spielen ferner eine wichtige Rolle bei der Interpretation
von Protein- und DNA-Sequenzen und beim Wirkstoffdesign.
Es wurden zahlreiche Algorithmen f\"ur die verschiedenen Alignment-Probleme ver\"offentlicht.
Fast alle ver\"offentlichten nicht-heuristischen Algorithmen basieren auf dynamischer Programmierung.
Da die Komplexit\"at der auf dynamischer Programmierung basierenden Verfahren exponentiell
mit der Zahl der Sequenzen w"achst, k\"onnen diese Algorithmen nur relativ kleine Probleminstanzen
zur Optimalit\"at l\"osen.
In enger Zusammenarbeit mit Arbeitsgruppen der Universit\"at von Georgia in Athens und
des Deutschen Krebsforschungszentrums in Heidelberg haben wir f\"uer verschiedene Alignment-Probleme
neue Branch-And-Cut-Algorithmen entwickelt, die Probleminstanzen handhaben k\"onnen, welche mittels dynamischen
Programmierens nicht gel\"ost werden k\"onnen.
Im Rahmen des Vortrags werden zwei dieser Alignment-Probleme, das sogenannte Generalized-Maximum-Trace-Problem und
das Structural-Maximum-Trace-Problem, vorgestellt.
Diese beiden Probleme werden als ganzzahlige lineare Programme formuliert.
Anschlie"send werden Branch-And-Cut-Algorithmen f\"ur diese Probleme skizziert.
Ferner werden die Vor- und Nachteile der neuen Branch-And-Cut-Algorithmen
anhand von Alignment-Beispielen diskutiert.