Abgeschlossene Arbeiten

Studentische Arbeiten

Erkennung und effiziente Behandlung von disjunkten Graphmustern

Typ der Arbeit: Bachelor-Thesis
Bearbeitungsstand: Abgeschlossene Arbeiten
Möglicher Beginn der Arbeit: jederzeit
Arbeit abgeschlossen am: 13.09.2020
Betreuer*in: M.Sc. Sebastian Ehmes
Student*in: Isabella N. Grieser

Zurück zur Übersicht

Motivation

Graphen und Graphtransformationen eignen sich besonders um Veränderungsprozesse auf strukturell stark vernetzten Modellen zu beschreiben. Ein Anwendungsbeispiel hierfür ist die Simulation von biochemischen Prozessen mit Hilfe von Graphen und Graphtransformationen.

Hierbei werden Proteine oder andere Molekülkomplexe durch Knoten und ihre Bindungen durch Kanten dargestellt. Reaktionen, die das Verbinden mehrerer Proteine und damit die Bildung von Molekülkomplexen beschreiben, werden bei Simulationen dieser Art durch Graphtransformationsregeln modelliert. Ein klassisches Beispiel ist hierfür das Auffinden zweier ungebundener Moleküle und das darauffolgende Verbinden dieser Moleküle zu einem Molekülkomplex.

Das Auffinden von ungebundenen Molekülen wird in regelbasierten Simulationen mit Hilfe von Graphmustererkennungswerkzeugen bewerkstelligt, die nach unverbundenen Knoten im Modellgraphen der Simulation suchen. In vorangegangenen Arbeiten (z.B. in dieser Masterarbeit) hat sich herausgestellt, dass aktuelle Werkzeuge nur sehr schlecht mit dieser Art von Muster umgehen können. Die Anzahl der Musterfunde explodiert und die Graphmustersuche wird zum Flaschenhals bei Simulationen, was zu enormen Laufzeitsteigerungen führt. Das macht Simulationen dieser Art unattraktiv obwohl sie große Vorteile bieten, wie z.B. höhere Abstraktion und komfortablere Modellierung, im Vergleich zu Simulationsverfahren die auf Systemen gewöhnlicher Differentialgleichungen (ODE) basieren.

Aufgabenstellung

Im Rahmen dieser Arbeit werden wir daher zunächst eine Methode zur Erkennung dieser problematischen Muster entwickeln. Außerdem werden wir verschiedene Ansätze zur Performanzsteigerung der Graphmustersuche entwickeln, wie z.B. das Abschätzen von Musterfunden. Zuletzt wird die neue Erkennung und Behandlung der disjunkten Graphmuster in unser fachgebietseigenes Tool (eMoflon) eingebaut und dann evaluiert werden.

Voraussetzungen

  • gute Java-Kenntnisse

Zurück zur Übersicht