Graph Grammars for Molecular Structure Search and Classification

用于分子结构搜索和分类的图文法

• 批准号: 416768284
• 负责人: Professor Dr. Ernst Althaus
• 金额: --
• 依托单位: Arbeitsgruppe Software-Technik und Bioinformatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/416768284?language=en
• 关键词: Graph; Grammars; Molecular; Structure; Search

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.

许多研究领域都集中在小分子上。一个突出的例子是药物设计领域，其中小分子用于抑制或激活蛋白质以达到所需的生物学功能。在这些领域，我们通常希望扫描数据库中包含某些子结构的分子。传统上，这些子结构以化学描述语言（例如Daylight的Smarts）进行建模。这些语言往往非常复杂，并且在描述基础图的拓扑模式的能力上受到非常限制。针对分子数据库的解析和匹配模式是NP完整的。为了解决这些问题，我们提出了一个简单的图形语法来描述子结构。即使是非常简单的图形重写系统，也允许几乎达到智能的高表达能力。要使用这些图形语法进行分子结构搜索，我们必须解决子图匹配问题。尽管此问题仍然是NP完整的，但是如果查询图的每个最小切割尺寸的每个最小切割尺寸都会变为多项式，那么对于标准数据库中包含的大多数分子来说，我们迫切认为这是正确的。我们将研究问题的复杂性，以获取更已知的图形参数，并尝试将最小切割的最大尺寸与其他参数相关联，我们将重点关注通常对于分子图通常很小的参数，我们将使我们的基本算法在实践中更有效。此外，我们希望得出由语法产生的一类图表的过度评估，该语法可以更有效地解决该子图匹配问题。作为第二个研究方向，我们将开发和实施从正面和负面示例中学习图形语法的有效算法。我们的目标是找到尽可能简单的图形语法，并与阳性示例匹配，但与化学组的负面示例不匹配。插值正面和负面例子的微不足道的语法是一种语法，它创建了积极的例子，显然过分适合积极的例子。这项学习任务背后的基本思想是自动识别这些分子的药理的各个方面。这里的挑战是同时防止过度拟合和过度属化。我们计划开发建设性算法，即计算一个简单的图形语法的算法，该算法插入了正面和负面的示例和改进算法，即试图在保留其插值属性同时简化图形语法的算法。