2014年5月
Efficient enumeration of monocyclic chemical graphs with given path frequencies
JOURNAL OF CHEMINFORMATICS
- ,
- ,
- 巻
- 6
- 号
- 1
- 開始ページ
- 31
- 終了ページ
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1186/1758-2946-6-31
- 出版者・発行元
- BIOMED CENTRAL LTD
Background: The enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds.
Results: We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds.
Conclusions: We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently.
Results: We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds.
Conclusions: We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently.
- リンク情報
-
- DOI
- https://doi.org/10.1186/1758-2946-6-31
- DBLP
- https://dblp.uni-trier.de/rec/journals/jcheminf/SuzukiNA14
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702209212168441
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000336992600001&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/jcheminf/jcheminf6.html#journals/jcheminf/SuzukiNA14
- ID情報
-
- DOI : 10.1186/1758-2946-6-31
- ISSN : 1758-2946
- DBLP ID : journals/jcheminf/SuzukiNA14
- J-Global ID : 201702209212168441
- Web of Science ID : WOS:000336992600001