direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Parametrisierte Algorithmik für Consistent Cut mit Anwendungen für multiple Sequenzalignments

Sven Thiel (Friedrich-Schiller-Universität Jena)
Der Vortrag gibt einen Überblick über das Graphmodifikationsproblem Consistent Cut. Als Eingabe dient ein ungerichteter k-gefärbter Graph sowie eine natürliche Zahl l. Dabei entspricht k der Anzahl der Farben des Graphen. Die Frage ist ob eine Menge von Kantenlöschungen für den Graphen der Größe höchstens l existiert, so dass jede Zusammenhangskomponente höchstens einen Knoten jeder Farbe beinhaltet. Es wird gezeigt, dass Consistent Cut für das bioinformatisch relevante Problem der multiplen Sequenzalignments (MSA) anwendbar ist. Außerdem wird sowohl die klassische als auch die parametrisierte Komplexität von Consistent Cut vorgestellt. Dabei wird gezeigt, dass das Problem NP-hart sowie festparameter-handhabbar bezüglich des kombinierten Parameters (k, l) ist. Darüber hinaus werden einige Datenreduktionsregeln vorgestellt und Spezialfälle des Problems betrachtet, bei denen bspw. die Anzahl der Farben beschränkt ist.


Der Vortragstermin vom 06.07.2011 wurde kurzfristig abgesagt.

Zeit
Vortragender
Ort
Sprache
?? ??
Sven Thiel

FR 6510
deutsch

Back to the research colloquium site.