Downloads: 131

Files in This Item:
File Description SizeFormat 
1758-2946-6-31.pdf1.33 MBAdobe PDFView/Open
Title: Efficient enumeration of monocyclic chemical graphs with given path frequencies.
Authors: Suzuki, Masaki
Nagamochi, Hiroshi  kyouindb  KAKEN_id
Akutsu, Tatsuya  kyouindb  KAKEN_id  orcid (unconfirmed)
Author's alias: 永持, 仁
Keywords: Chemical graphs
Monocyclic structure
Feature vector
Issue Date: 30-May-2014
Publisher: Chemistry Central
Journal title: Journal of cheminformatics
Volume: 6
Thesis number: 31
Abstract: [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.
Rights: © 2014 Suzuki et al.; licensee Chemistry Central Ltd.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.
DOI(Published Version): 10.1186/1758-2946-6-31
PubMed ID: 24955135
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.