Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs
Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs
复制标题
DOI：
10.1109/tcbb.2016.2628888
复制
发表时间：
2018-03-01
影响因子：
4.5
通讯作者：
Akutsu, Tatsuya
中科院分区：
文献类型：
--
作者：
Li, Jinghui;Nagamochi, Hiroshi;Akutsu, Tatsuya
化学结构的枚举对于药物设计很有用，这是计算生物学和生物信息学的主要目标之一。除苯环外没有其他环的化学图C称为树状化学图C，如果我们将每个苯环收缩为6价的单个虚拟原子，则它可能成为具有多个边的树T。具有给定树表示T的所有树状化学图被称为T的取代苯异构体。当我们用苯环替换T中的每个虚拟原子以获得取代苯异构体时，由于苯环周围原子团排列的差异而导致T的不同异构体。在本文中，我们提出了一种有效的算法，可以枚举给定树表示 T 的所有取代苯异构体。我们的算法首先通过动态规划方法计算树表示的所有异构体的数量 f。为了枚举所有异构体，对于每个 k = 1,2, ... , f，我们的算法然后通过回溯动态规划的计数阶段生成第 6 个异构体。我们还实现了用于计算实验的算法。
Enumeration of chemical structures is useful for drug design, which is one of the main targets of computational biology and bioinformatics. A chemical graph C with no other cycles than benzene rings is called tree-like, and becomes a tree T possibly with multiple edges if we contract each benzene ring into a single virtual atom of valence 6. All tree-like chemical graphs with a given tree representation T are called the substituted benzene isomers of T. When we replace each virtual atom in T with a benzene ring to obtain a substituted benzene isomer, distinct isomers of T are caused by the difference in arrangements of atom groups around a benzene ring. In this paper, we propose an efficient algorithm that enumerates all substituted benzene isomers of a given tree representation T. Our algorithm first counts the number f of all the isomers of the tree representation by a dynamic programming method. To enumerate all the isomers, for each k = 1,2, ... , f, our algorithm then generates the 6th isomer by backtracking the counting phase of the dynamic programming. We also implemented our algorithm for computational experiments.