Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming
Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming
复制标题
使用动态规划有效枚举外平面化学图的立体异构体
DOI：
10.1021/ci200084b
复制
发表时间：
2011
影响因子：
5.6
通讯作者：
T.Akutsu
中科院分区：
文献类型：
--
作者：
T.Imada;S.Ota;H.Nagamochi;T.Akutsu
化合物立体异构体的穷举和非冗余生成是分子结构解析和分子设计的重要工具。已知许多化合物具有外平面图结构。在本文中，我们处理的化合物组成的碳，氢，氧，氮原子的图形结构是外平面和考虑立体异构体所造成的碳原子周围的不对称性。基于动态规划，我们提出了一个生成所有立体异构体的算法。我们把一个给定的外平面图看作一个根在其结构中心的图。我们的算法首先递归地计算每个顶点的后代所诱导的子图的立体异构体的数目，然后通过回溯计算立体异构体的数目的过程来构造每个立体异构体。我们的算法在O（n）时间和空间上正确地计数了立体异构体的数目，并且在O（n 3）时间和O（n）空间上正确地计数了每个立体异构体的所有立体异构体，其中n是给定结构中的原子数。
Exhaustive and nonredundant generation of stereoisomers of a chemical compound with a specified constitution is an important tool for molecular structure elucidation and molecular design. It is known that many chemical compounds have outerplanar graph structures. In this paper we deal with chemical compounds composed of carbon, hydrogen, oxygen, and nitrogen atoms whose graphical structures are outerplanar and consider stereoisomers caused only by asymmetry around carbon atoms. Based on dynamic programming, we propose an algorithm of generating all stereoisomers without duplication. We treat a given outerplanar graph as a graph rooted at its structural center. Our algorithm first recursively computes the number of stereoisomers of the subgraph induced by the descendants of each vertex and then constructs each stereoisomer by backtracking the process of computing the numbers of stereoisomers. Our algorithm correctly counts the number of stereoisomers inO(n) time and space and correctly enumerates all of the stereoisomers inO(n3) time per stereoisomer on average and inO(n) space, wherenis the number of atoms in a given structure.