Graph-Grammatiken zur Suche und Klassifikation von molekularen Strukturen

Abstract

We define a graph rewriting system that is easily understandable by humans, but rich enough to allow very general queries to molecule databases. It is based on the substitution of a single node in a nodeand edge-labeled graph by an arbitrary graph, explicitly assigning new endpoints to the edges incident to the replaced node. For these graph rewriting systems, we are interested in the subgraph-matching problem. We show that the problem is NP-complete, even on graphs that are stars. As a positive result, we give an algorithm which is polynomial if both rules and the query graph have bounded degree and bounded cut size. We demonstrate that molecular graphs of practically relevant molecules in drug discovery conform with this property. The algorithm is not a fixed-parameter algorithm. Indeed, we show that the problem is W[1]-hard on trees with the degree as the parameter. Different approaches for learning graph grammars are presented. It is shown to what extent they can be used for substructure search or classification of molecules. Different aspects of production are considered, e.g., that a special structure is used, which was recognized in presented molecules. The results of the presented approaches are compared and evaluated with different machine learning approaches.

In dieser Arbeit wird ein Modell zum Umschreiben von Graphen präsentiert, das sowohl einfach und 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 Teilgraphen. Hierbei spielt das Subgraphmatching eine entscheidende Rolle. Wir zeigen, dass das Problem auch auf Sterngraphen NP-vollständig ist. Es wird ein Algorithmus 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. Zusätzlich werden unterschiedliche Ansätze zum Lernen von Graph-Grammatiken vorgestellt. Anschließend wird aufgezeigt, in welchem Umfang diese zur Substruktursuche oder Klassifizierung von Molekülen genutzt werden können und welche Ergebnisse sie hierbei erzielen. Die Ergebnisse der vorgestellten Ansätze werden mit unterschiedlichen Ansätzen des maschinellen Lernens miteinander verglichen und bewertet.