Graph Grammars for Molecular Structure Search and Classification
Final Report Abstract
Es wird ein Modell zum Umschreiben von Graphen präsentiert, das sowohl einfach als auch intuitiv ist, aber mächtig genug, um allgemeine Abfragen in Moleküldatenbanken zu ermöglichen. Das Modell basiert auf der Ersetzung eines einzelnen Knotens in einem knoten- und kantengelabelten Graphen ohne Schleifen. Dies ermöglicht es, ein Modell vorzustellen, bei dem die Regeln vorgeben, wie die Kanten umgelenkt werden müssen, die einen Endpunkt verlieren, weil ein Knoten des Graphen entfernt wurde. Eine Regel ersetzt hierbei einen einzelnen Knoten mit einem bestimmten Label und deren inzidenten Kanten, die ebenfalls spezifische Label aufweisen, durch einen Subgraphen. Hierbei spielt das Subgraphmatching eine entscheidende Rolle. Es wird gezeigt, dass das Problem NP-vollständig ist. Ein Algorithmus wird vorgestellt, der eine polynomielle Laufzeit aufweist, falls die zugrundeliegenden Regeln einen begrenzten Grad aufweisen und der Anfragegraph eine begrenzte Größe des minimalen Schnittes inne hat. Wir zeigen, dass das Modell keinen FPT-Algorithmus darstellt und dass das Problem W[1]-schwer auf Bäumen ist, mit dem Grad als Parameter. Das Suchen und Finden von molekularen Substrukturen stellt eine sehr komplexe und zeitintensive Abfrage in Datenbanken dar. Dieses Suchproblem ist NP-vollständig. Ein Problem, das bei der Suche nach Molekülen auftreten kann, ist, dass die Struktur der interessierenden Moleküle unbekannt ist. Besitzt man nur eine kleine Anzahl an Molekülen mit einer bestimmten Eigenschaft kann man mit dem vorgestellt Graph-Grammatik Ansatz nun weitere Moleküle mit dieser Eigenschaft in einer Datenbank finden. Dies kann als Lernen in Verbindung mit dem vorgestellten Graph-Grammatik-Ansatz von Molekülklassen aus einer kleinen Anzahl von positiven Beispielen beschrieben werden. Beim Lernen von Graph-Grammatiken werden Regeln erzeugt, die in den positiven Beispielen vorkommen aber bereits so spezifisch sind, dass mit diesen Regeln nur die gesuchten Mölekülklassen gematched werden. Man klassifiziert ein Molekül zu einer Klasse, wenn es mit der erstellten Graph-Grammatik übereinstimmt. Abstrakt betrachtet kann unser Ansatz als Definition eines neuen Merkmalsraums interpretiert werden, nämlich der Menge aller Graph-Grammatiken. Aus den gegebenen Beispielen konstruieren wir eine bestimmte Teilmenge dieser Merkmale. Davon ausgehend verwenden wir einen Lernalgorithmus für diese Merkmale. Wir verwenden einen Ansatz zur Vorhersage der Spezifität eines Merkmals und wählen die Merkmale aus, die über einer Spezifitätsschwelle liegen und die größte Anzahl positiver Beispiele aufweisen. Um zu zeigen, dass dieser neue Merkmalsraum spezifisch ist, haben wir unseren Ansatz mit Lernansätzen des Maschinellen-Lernens verglichen. Es wird gezeigt, dass für die von uns untersuchten Molekülklassen dieser Lernansatz für sehr gute Zuordnungswerte ausreicht und ein einfacher Lernansatz verwenden kann, um Moleküle mit einer kleinen Anzahl an positiven Beispielen erfolgreich zu klassifizieren, falls bestimmte Graph-Grammatik-Regeln als Merkmale verwendet werden. Es wird gezeigt, dass diese Merkmale effizient für die betrachteten Beispiele genutzt werden können.
Publications
-
Graph-Grammatiken zur Suche und Klassifikation von molekularen Strukturen. PhD thesis, Johannes Gutenberg-Universität Mainz, 2019.
D. Mosca
-
Learning molecular classes from small numbers of positive examples using graph grammars. In International Conference on Algorithms for Computational Biology, pages 3–15. Springer, 2021.
E. Althaus, A. Hildebrandt & D. Mosca
