Graph Grammars for Molecular Structure Search and Classification

许多研究领域都集中在小分子上。一个突出的例子是药物设计领域，其中使用小分子来抑制或激活蛋白质以实现所需的生物功能。在这些领域中，我们经常希望扫描数据库中含有特定子结构的分子。传统上，这些子结构是用化学描述语言建模的，比如Daylight的SMARTS。这些语言往往非常复杂，并且在描述底层图的拓扑模式方面受到很大限制。根据分子数据库解析和匹配模式是np完备的。为了避免这些问题，我们提出了一个简单的图语法来描述子结构。即使是非常简单的图形重写系统也具有几乎达到SMARTS的高表达能力。为了使用这些图语法进行分子结构搜索，我们必须解决子图匹配问题。虽然这个问题仍然是np完全的，但如果查询图的每个最小切割都有有限的大小，它就变成了多项式，我们经验地发现，对于标准数据库中包含的大多数分子来说，这是正确的。我们将研究更多已知图参数问题的复杂性，并尝试将最小切口的最大尺寸与其他参数联系起来，我们将重点关注分子图的典型小参数，我们将使我们的基本算法在实践中更有效。此外，我们希望推导出由语法生成的图类的过近似值，以便更有效地解决子图匹配问题。作为第二个研究方向，我们将开发和实现从正例和负例中学习图语法的有效算法。我们的目标是找到一种尽可能简单的图语法，它与化学基团的正例匹配，但与负例不匹配。一个插入积极和消极例子的平凡语法是一个创造积极例子的语法，它明显过拟合积极例子。这项学习任务背后的基本思想是自动识别这些分子药效团的各个方面。这里的挑战是同时防止过度拟合和过度泛化。我们计划开发建设性算法，即计算插入正例和负例的简单图语法的算法和改进算法，即尝试简化图语法同时保留其插值特性的算法。

Numerous fields of study focus on small molecules. A prominent example is the field of drug design, where small molecules are used to inhibit or activate proteins to achieve a desired biological function. In these fields, we often want to scan databases for molecules containing certain substructures. Traditionally, these substructures are modelled in chemical description languages such as Daylight’s SMARTS. These languages tend to be very complex and are very restricted in their ability to describe the topological patterns of the underlying graphs. Parsing and matching patterns against a database of molecules is NP-complete. To circumvent these problems, we propose a simple graph grammar to describe substructures. Even very simple graph rewriting systems allow a high expressive power that almost reaches that of SMARTS. To use these graph grammars for molecular structure search, we have to solve the subgraph matching problem. Although this problem remains NP-complete, it becomes polynomial if each minimal cut of the query graph has bounded size, which we empirically find to be true for most molecules contained in the standard databases. We will investigate the complexity of the problem for more known graph parameters and try to relate the maximal size of a minimal cut to other parameters and we will focus on parameters that are typically small for molecular graphs and we will make our basic algorithm more efficient in practice. Furthermore, we want to derive over-approximations of the class of graphs generated by a grammar for which the subgraph matching problem can be solved more efficiently. As a second research direction, we will develop and implement efficient algorithms for learning graph grammars from positive and negative examples. We aim to find a graph grammar that is as simple as possible and matches the positive examples but does not match the negative examples for the chemical group. A trivial grammar that interpolates the positive and negative examples is a grammar that creates positive examples that clearly overfit the positive examples. The underlying idea behind this learning task is to automatically identify aspects of the pharmacophore of these molecules. The challenge here is to simultaneously prevent overfitting and overgeneralization. We plan to develop constructive algorithms, i.e. algorithms that compute a simple graph grammar that interpolates the positive and negative examples and improvement algorithms, i.e. algorithms that try to simplify a graph grammar while preserving its interpolating property.