Breadth-first search approach to enumeration of tree-like chemical compounds
Breadth-first search approach to enumeration of tree-like chemical compounds
复制标题
树状化合物枚举的广度优先搜索方法
DOI：
10.1142/s0219720013430075
复制
发表时间：
2013
影响因子：
1
通讯作者：
H. Nagamochi and T. Akutsu
中科院分区：
文献类型：
--
作者：
Y. Zhao;M. Hayashida;J. Jindalertudomdee;H. Nagamochi and T. Akutsu
分子计数在药物设计中起着基础性的作用，数学家、计算机科学家和化学家对此进行了很长时间的研究。尽管许多研究人员致力于开发特定于药物设计系统的枚举算法，但由于分子枚举的搜索空间呈指数级增长，原子数量较多，因此分子枚举至今仍是一个难题。为了缓解这一缺陷，我们提出了有效的算法BfsSimEnum和BfsMulEnum来分别枚举没有键和有多个键的树状分子，其中化合物被表示为分子图。为了减少较大的搜索空间，我们将一些重要的概念，如左重、中心根和正规形式，调整为分子树图。与现有的许多方法不同，BfsSimEnum和BfsMulEnum首先按照广度优先的搜索顺序枚举树状化合物。进行了计算实验，并与现有的几种方法进行了比较。结果表明，我们提出的方法是准确的和更有效的。
Molecular enumeration plays a basic role in the design of drugs, which has been studied by mathematicians, computer scientists, and chemists for quite a long time. Although many researchers are involved in developing enumeration algorithms specific to drug design systems, molecular enumeration is still a hard problem to date due to its exponentially increasing large search space with larger number of atoms. To alleviate this defect, we propose efficient algorithms,BfsSimEnumandBfsMulEnumto enumerate tree-like molecules without and with multiple bonds, respectively, where chemical compounds are represented as molecular graphs. In order to reduce the large search space, we adjust some important concepts such asleft-heavy,center-rooted, andnormal formto molecular tree graphs. Different from many existing approaches, BfsSimEnum and BfsMulEnum firstly enumerate tree-like compounds by breadth-first search order. Computational experiments are performed to compare with several existing methods. The results suggest that our proposed methods are exact and more efficient.