1. Startpage
  2. Johannes Gutenberg-Universität Mainz
  3. JGU-Publikationen
Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-2387
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMosca, Domenico
dc.date.accessioned2019-12-04T08:42:43Z
dc.date.available2019-12-04T09:42:43Z
dc.date.issued2019
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/2389-
dc.description.abstractWe 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.en_GB
dc.description.abstractIn 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.de_DE
dc.language.isoger
dc.rightsInCopyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc004 Informatikde_DE
dc.subject.ddc004 Data processingen_GB
dc.titleGraph-Grammatiken zur Suche und Klassifikation von molekularen Strukturende_DE
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-diss-1000031994
dc.identifier.doihttp://doi.org/10.25358/openscience-2387-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.description.extentxi, 146 Seiten
jgu.organisation.departmentFB 08 Physik, Mathematik u. Informatik-
jgu.organisation.year2019
jgu.organisation.number7940-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode004
opus.date.accessioned2019-12-04T08:42:43Z
opus.date.modified2019-12-04T10:15:41Z
opus.date.available2019-12-04T09:42:43
opus.subject.dfgcode00-000
opus.organisation.stringFB 08: Physik, Mathematik und Informatik: Institut für Informatikde_DE
opus.identifier.opusid100003199
opus.institute.number0805
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
jgu.organisation.rorhttps://ror.org/023b0x485
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
100003199.pdf2.23 MBAdobe PDFView/Open
Show simple item record