Enumerating treelike chemical graphs with given path frequency
Enumerating treelike chemical graphs with given path frequency
复制标题
DOI：
10.1021/ci700385a
复制
发表时间：
2008-07-01
影响因子：
5.6
通讯作者：
Akutsu, Tatsuya
中科院分区：
文献类型：
--
作者：
Fujiwara, Hiroki;Wang, Jiexun;Akutsu, Tatsuya
满足给定约束的化学图的枚举是化学信息学的基本问题之一。在本文中，我们考虑从给定的路径频率枚举（即列出）所有树状化学图的问题。在分支定界法的基础上，提出了一种精确的枚举该问题所有解的算法。为了进一步提高枚举的效率，我们引入了复合枚举问题的一种新变体，在输入中增加了对多重键数的规范，并设计了另一种精确的枚举算法。实验结果表明，我们的算法可以有效地解决以前的方法无法解决的更大的实例。特别地，我们将后一种算法应用于特殊的树状化学结构-烷烃异构体的枚举问题。理论和实验结果表明，我们的算法至少与专门用于生成烷烃异构体的最先进算法一样快，但使用的存储空间要小得多。
The enumeration of chemical graphs satisfying given constraints is one of the fundamental problems in chemoinformatics. In this paper, we consider the problem of enumerating (i.e., listing) all treelike chemical graphs from a given path frequency. We propose an exact algorithm for enumerating all Solutions to this problem on the basis of the branch-and-bound method. To further improve the efficiency of the enumeration, we introduce a new variant of the compound enumeration problem by adding a specification on the number of multiple bonds to the input and design another exact enumeration algorithm. The experimental results show that our algorithms can efficiently solve instances with larger sizes that are impossible to solve by the previous methods. In particular, we apply the latter algorithm to the enumeration problem of the special treelike chemical structures-alkane isomers. The theoretical and experimental results show that our algorithm works at least as fast as the state-of-the-art algorithms specially designed for generating alkane isomers, however using much less memory space.