Efficient enumeration of monocyclic chemical graphs with given path frequencies.

• Suzuki, Masaki

• 永持, 仁

• Akutsu, Tatsuya

抄録

[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.

収録刊行物

• Journal of cheminformatics

  Journal of cheminformatics 6 31-, 2014-05-30

  Chemistry Central

キーワード

• Chemical graphs
• Enumeration
• Monocyclic structure
• Feature vector

詳細情報

• CRID: 1050845760724371456
• NII論文ID: 120005456003
• ISSN: 17582946
• DOI: 10.1186/1758-2946-6-31
• HANDLE: 2433/188897
• Web Site: http://link.springer.com/article/10.1186/1758-2946-6-31/fulltext.html
• Web Site: http://link.springer.com/content/pdf/10.1186/1758-2946-6-31.pdf
• Web Site: https://link.springer.com/content/pdf/10.1186/1758-2946-6-31.pdf
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN