Graph Grammatiken für die Suche und Klassifikation molekularer Strukturen

• Antragsteller: Professor Dr. Ernst Althaus; Professor Dr. Andreas Hildebrandt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416768284

Zahlreiche Forschungsgebiete konzentrieren sich auf kleine Moleküle. Ein bekanntes Beispiel aus der Forschung, in der kleine Moleküle verwendet werden, ist das Gebiet des Wirkstoffdesigns. Eine gewünschte biologische Funktion kann dadurch erzielt werden, indem Proteine in Molekülen aktiviert oder deaktiviert werden. Wir möchten Datenbanken nach Molekülen mit bestimmten Substrukturen durchsuchen. Traditionell werden diese Substrukturen mittels chemischen Nomenklaturen, wie die der Daylights SMARTS modelliert. Diese Nomenklaturen sind in der Regel sehr komplex und in ihrer Fähigkeit eingeschränkt, topologische Muster der zugrunde liegenden Graphen zu beschreiben. Erschwerend kommt hinzu, dass das Parsen und Zuordnen von Substrukturen in Molekülen eine sehr komplexe und zeitintensive Abfrage in Datenbanken darstellt, da dieses Suchproblem NP-vollständig ist. Um dieses Problem zu umgehen, werden wir eine einfache Graph-Grammatik entwickeln, um Substrukturen zu beschreiben. Graph-Grammatiken in ihrer einfachsten Form ermöglichen eine ähnliche Ausdruckskraft, wie die der SMARTS. Damit Graph-Grammatiken zur molekularen Struktursuche verwendet werden können, müssen wir das Subgraph-Matching-Problem lösen. Das NP-vollständige Problem wird polynomiell, falls jeder minimale Schnitt des Anfragegraphen eine beschränkte Größe aufweist. Diese beschränkte Größe können wir für die meisten Moleküle in den Standarddatenbanken empirisch bestätigen.Wir werden die Komplexität des Problems anhand von bekannten Graph Parametern untersuchen und versuchen, die maximale Größe eines minimalen Schnitts mit anderen Graph Parametern in Beziehung zu setzen. Wir werden uns auf Parameter konzentrieren, die typischerweise klein für molekulare Graphen sind und unseren Basisalgorithmus effizienter implementieren. Darüber hinaus wollen wir Über-Approximationen für Klassen von Graphen herleiten, um das Subgraph-Matching-Problem effektiver zu lösen.Die zweite Forschungsfrage besteht darin, effiziente Algorithmen zum Erlernen von Graph-Grammatiken zu entwickeln und zu implementieren. Das Ziel ist es, eine möglichst einfache Graph-Grammatik zu konzipieren, die die positiven von den negativen Eingaben, für ausgewählte chemische Gruppen, voneinender trennt. Eine triviale Grammatik, die die positiven und negativen Beispiele interpoliert, ist eine Grammatik, die genau die positiven Beispiele erzeugt und diese eindeutig überlagert. Die zugrunde liegende Idee ist es, die automatische Identifizierung des Pharmakophors in Molekülen zu erzielen. Die Herausforderung besteht darin, gleichzeitig Überanpassungen und Übergeneralisierungen zu verhindern. Wir werden konstruktive Algorithmen entwickeln, die zum Einen einfache Graph-Grammatiken erzeugen, die die positiven und negativen Beispiele interpolieren und zum Anderen Verbesserungsalgorithmen, die eine gegebene Graph-Grammatik versuchen zu vereinfachen, während ihre Interpolationseigenschaft erhalten bleibt.

• DFG-Verfahren: Sachbeihilfen