Resource Cut, a New Bounding Procedure to Algorithms for Enumerating Tree-Like Chemical Graphs
Resource Cut, a New Bounding Procedure to Algorithms for Enumerating Tree-Like Chemical Graphs
复制标题
资源削减，树状化学图枚举算法的新边界过程
DOI：
10.1109/tcbb.2018.2832061
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tatsuya Akutsu
中科院分区：
文献类型：
--
作者：
Yuhei Nishiyama;Aleksandar Shurbevski ;Hiroshi Nagamochi;Tatsuya Akutsu
列举具有给定结构特性的化合物在结构解析中起着重要作用，其应用例如药物设计。我们专注于枚举树型化学图的特征向量，其中化学图表示化合物的上界和下界指定的问题，和一个特征向量表征在一个图形中的有限路径的频率。建立在早期的工作中提出的分支定界算法，我们提出了一个新的定界过程，称为资源削减，以加快枚举过程。树状化学图被建模为顶点着色树，颜色代表化学元素。该算法是基于一个计划，产生每一个唯一的彩色树与指定数目的顶点。着色树是通过重复添加顶点来构造的。给定一个setofcolored顶点，我们发现，该算法往往构造的树，不能扩展到一个唯一的表示的着色树，无论如何在集合中剩余的未使用的着色顶点是追加。我们推导出一个数学条件来检测和丢弃这样的树。实验结果表明，资源切割显著地减小了搜索空间.我们已经能够获得确切的化学图的数量高达17个顶点不包括氢原子。
Enumerating chemical compounds with given structural properties plays an important role in structure elucidation, with applications such as drug design. We focus on the problem of enumerating tree-like chemical graphs specified by upper and lower bounds on feature vectors, where chemical graphs represent compounds, and a feature vector characterizes frequencies of finite paths in a graph. Building on the branch-and-bound algorithm proposed in earlier work, we propose a new bounding procedure, calledResource Cut, to speed up the enumeration process. Tree-like chemical graphs are modeled as vertex-colored trees, colors representing chemical elements. The algorithm is based on a scheme of generating each unique colored tree with a specified numberof vertices. A colored tree is constructed by repeatedly appending vertices. Given a setofcolored vertices, we found that the algorithm often constructs trees that cannot be extended to a unique representation of a colored tree no matter how the remaining unused colored vertices in the setare appended. We derive a mathematical condition to detect and discard such trees. Experimental results show thatResource Cutsignificantly reduces the search space. We have been able to obtain exact numbers of chemical graphs with up to 17 vertices excluding hydrogen atoms.