Studentische Arbeiten
Erkennung und effiziente Behandlung von disjunkten Graphmustern
Type of thesis:
Bachelor-Thesis
State: Abgeschlossene Arbeiten
Possible start of thesis: jederzeit
Thesis closed on: 13.09.2020
Tutor: M.Sc. Sebastian Ehmes
Student: Isabella N. Grieser
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.
Task
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.
Preconditions
- gute Java-Kenntnisse
