{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T21:47:24Z","timestamp":1751406444027},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T00:00:00Z","timestamp":1401408000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cheminform"],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1758-2946-6-31","type":"journal-article","created":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T01:02:31Z","timestamp":1401411751000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Efficient enumeration of monocyclic chemical graphs with given path frequencies"],"prefix":"10.1186","volume":"6","author":[{"given":"Masaki","family":"Suzuki","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]},{"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,30]]},"reference":[{"key":"606_CR1","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1021\/ci980095c","volume":"38","author":"L Bytautas","year":"1998","unstructured":"Bytautas L, Klein DJ: Chemical combinatorics for alkane-isomer enumeration and more. J Chem Inf Comput Sci. 1998, 38: 1063-1078. 10.1021\/ci980095c.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR2","doi-asserted-by":"publisher","first-page":"5565","DOI":"10.1039\/a906137a","volume":"1","author":"L Bytautas","year":"1999","unstructured":"Bytautas L, Klein DJ: Formula periodic table for acyclic hydrocarbon isomer classescombinatorially averaged graph invariants. Phys Chem Chem Phys. 1999, 1: 5565-5572. 10.1039\/a906137a.","journal-title":"Phys Chem Chem Phys"},{"key":"606_CR3","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s002140050455","volume":"101","author":"L Bytautas","year":"1999","unstructured":"Bytautas L, Klein DJ: Isomer combinatorics for acyclic conjugated polyenes: enumeration and beyond. Theoret Chem Acc. 1999, 101: 371-387. 10.1007\/s002140050455.","journal-title":"Theoret Chem Acc"},{"key":"606_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0004-3702(78)90010-3","volume":"11","author":"BG Buchanan","year":"1978","unstructured":"Buchanan BG, Feigenbaum EA: DENDRAL and Meta-DENDRAL: their applications dimension. Artif Intell. 1978, 11: 5-24. 10.1016\/0004-3702(78)90010-3.","journal-title":"Artif Intell"},{"key":"606_CR5","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1021\/ci950152r","volume":"36","author":"K Funatsu","year":"1996","unstructured":"Funatsu K, Sasaki S: Recent advances in the automated structure elucidation system, CHEMICS. Utilization of two-dimensional NMR spectral information and development of peripheral functions for examination of candidates. J Chem Inf Comput Sci. 1996, 36: 190-204. 10.1021\/ci950152r.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR6","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1021\/ci600423u","volume":"47","author":"T Fink","year":"2007","unstructured":"Fink T, Reymond JL: Virtual exploration of the chemical universe up to 11 atoms of C, N, O, F: assembly of 26.4 million structures (110.9 million stereoisomers) and analysis for new ring systems, stereochemistry, physicochemical properties, compound classes, and drug discovery. J Chem Inf Comput Sci. 2007, 47: 342-353. 10.1021\/ci600423u.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR7","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1021\/ci6003652","volume":"47","author":"H Mauser","year":"2007","unstructured":"Mauser H, Stahl M: Chemical fragment spaces for de novo design. J Chem Inf Comput Sci. 2007, 47: 318-324. 10.1021\/ci6003652.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR8","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1021\/ci020346o","volume":"43","author":"JL Faulon","year":"2003","unstructured":"Faulon JL, Churchwell CJ: The signature molecular descriptor. 2. Enumerating molecules from their extended valence sequences. J Chem Inf Comput Sci. 2003, 43: 721-734. 10.1021\/ci020346o.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR9","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1021\/ci00014a012","volume":"33","author":"LH Hall","year":"1993","unstructured":"Hall LH, Dailey ES: Design of molecules from quantitative structure-activity relationship models. 3. Role of higher order path counts: Path 3. J Chem Inf Comput Sci. 1993, 33: 598-603. 10.1021\/ci00014a012.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR10","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1109\/TKDE.2005.127","volume":"17","author":"M Deshpande","year":"2005","unstructured":"Deshpande M, Kuramochi M, Wale N, Karypis G: Frequent substructure-based approaches for classifying chemical compounds. IEEE Trans Knowl Data Eng. 2005, 17: 1036-1050.","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"606_CR11","first-page":"257","volume":"45","author":"A Cayley","year":"1875","unstructured":"Cayley A: On the analytic forms called trees with applications to the theory of chemical combinations. Rep Br Assoc Adv Sci. 1875, 45: 257-305.","journal-title":"Rep Br Assoc Adv Sci"},{"key":"606_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF02546665","volume":"68","author":"G P\u00f3lya","year":"1937","unstructured":"P\u00f3lya G: Kombinatorische anzahlbestimmungen f\u00fcr gruppen, graphen, und chemische verbindungen. Acta Math. 1937, 68: 45-254.","journal-title":"Acta Math"},{"issue":"Suppl 14","key":"606_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1186\/1471-2105-12-S14-S3","volume":"12","author":"M Shimizu","year":"2011","unstructured":"Shimizu M, Nagamochi H, Akutsu T: Enumerating tree-like chemical graphs with given upper and lower bounds on path frequencies. BMC Bioinformatics. 2011, 12 (Suppl 14): 53-","journal-title":"BMC Bioinformatics"},{"issue":"17","key":"606_CR14","first-page":"1","volume":"28","author":"M Suzuki","year":"2012","unstructured":"Suzuki M, Nagamochi H, Akutsu T: A 2-phase algorithm for enumerating tree-like chemical graphs satisfying given upper and lower bounds. IPSJ SIG Technical Reports. BIO 2012, 2012, 28 (17): 1-8.","journal-title":"IPSJ SIG Technical Reports"},{"key":"606_CR15","volume-title":"Nucleic Acids Res","author":"M Kanehisa","year":"2010","unstructured":"Kanehisa M, Goto S, Furumichi M, Tanabe M, Hirakawa M: KEGG for representation and analysis of molecular networks involving diseases and drugs. Nucleic Acids Res. 2010, 38: D355-D360,"},{"key":"606_CR16","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary F: Graph Theory. 1969, MA: Addison Wesley"},{"key":"606_CR17","first-page":"449","volume":"16","author":"GH Bakir","year":"2003","unstructured":"Bakir GH, Weston J, Sch\u00f6lkopf B: Learning to find pre-images. Adv Neural Inform Process Syst. 2003, 16: 449-456.","journal-title":"Adv Neural Inform Process Syst"},{"key":"606_CR18","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-28649-3_31","volume":"3175","author":"GH Bakir","year":"2004","unstructured":"Bakir GH, Zien A, Tsuda K: Learning to find graph pre-images. Lect Notes Comput Sci. 2004, 3175: 253-261. 10.1007\/978-3-540-28649-3_31.","journal-title":"Lect Notes Comput Sci"},{"key":"606_CR19","first-page":"321","volume-title":"Proceedings of the 20th International Conference Machine Learning","author":"H Kashima","year":"2003","unstructured":"Kashima H, Tsuda K, Inokuchi A: Marginalized kernels between labeled graphs. Proceedings of the 20th International Conference Machine Learning. 2003, Palo Alto: AAAI Press, 321-328."},{"key":"606_CR20","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1021\/ci050039t","volume":"45","author":"N Ueda","year":"2005","unstructured":"Ueda N, Akutsu T, Perret JL, Vert JP, Mah\u00e9 P: Graph kernels for molecular structure-activity relationship analysis with support vector machines. J Chem Inf Model. 2005, 45: 939-951. 10.1021\/ci050039t.","journal-title":"J Chem Inf Model"},{"key":"606_CR21","doi-asserted-by":"publisher","first-page":"1882","DOI":"10.1021\/ci0341161","volume":"3","author":"E Byvatov","year":"2003","unstructured":"Byvatov E, Fechner U, Sadowski J, Schneider G: Comparison of support vector machine and artificial neural network systems for drug\/nondrug classification. J Chem Inf Comput Sci. 2003, 3: 1882-1889.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR22","doi-asserted-by":"publisher","first-page":"1416","DOI":"10.1016\/j.dam.2012.02.002","volume":"160","author":"T Akutsu","year":"2012","unstructured":"Akutsu T, Fukagawa D, Jansson J, Sadakane K: Inferring a graph from path frequency. Discrete Appl Math. 2012, 160: 1416-1428. 10.1016\/j.dam.2012.02.002.","journal-title":"Discrete Appl Math"},{"key":"606_CR23","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00453-008-9184-0","volume":"53","author":"H Nagamochi","year":"2009","unstructured":"Nagamochi H: A detachment algorithm for inferring a graph from path frequency. Algorithmica. 2009, 53: 207-224. 10.1007\/s00453-008-9184-0.","journal-title":"Algorithmica"},{"key":"606_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1021\/ci00011a021","volume":"33","author":"L Kier","year":"1993","unstructured":"Kier L, Hall L, Frazer J: Design of molecules from quantitative structure-activity relationship models. 1. Information transfer between path and vertex degree counts. J Chem Inf Comput Sci. 1993, 33: 143-147. 10.1021\/ci00011a021.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/minf.200900038","volume":"29","author":"T Miyao","year":"2010","unstructured":"Miyao T, Arakawa M, Funatsu K: Exhaustive structure generation for inverse-QSPR\/QSAR. Mol Inform. 2010, 29: 111-125. 10.1002\/minf.200900038.","journal-title":"Mol Inform"},{"key":"606_CR26","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/1758-2946-1-4","volume":"1","author":"WWL Wong","year":"2009","unstructured":"Wong WWL, Burkowski FJ: A constructive approach for discovering new drug leads: Using a kernel methodology for the inverse-QSAR problem. J Cheminf. 2009, 1: 4-10.1186\/1758-2946-1-4.","journal-title":"J Cheminf"},{"key":"606_CR27","first-page":"239","volume":"58","author":"R Gugisch","year":"2007","unstructured":"Gugisch R, Kerber A, Laue R, Meringer M, Rucker C: History and progress of the generation of structural formulae in chemistry and its applications. MATCH Comm Math Comput Chem. 2007, 58: 239-280.","journal-title":"MATCH Comm Math Comput Chem"},{"key":"606_CR28","doi-asserted-by":"publisher","first-page":"1345","DOI":"10.1021\/ci700385a","volume":"48","author":"H Fujiwara","year":"2008","unstructured":"Fujiwara H, Wang J, Zhao L, Nagamochi H, Akutsu T: Enumerating tree-like chemical graphs with given path frequency. J Chem Inf Model. 2008, 48: 1345-1357. 10.1021\/ci700385a.","journal-title":"J Chem Inf Model"},{"key":"606_CR29","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/11604686_22","volume":"3787","author":"S Nakano","year":"2005","unstructured":"Nakano S, Uno T: Generating colored trees. Lect Notes Comput Sci. 2005, 3787: 249-260. 10.1007\/11604686_22.","journal-title":"Lect Notes Comput Sci"},{"key":"606_CR30","volume-title":"NII Technical Report","author":"S Nakano","year":"2003","unstructured":"Nakano S, Uno T: Efficient generation of rooted trees. NII Technical Report. 2003, NII-2003-005E,"},{"key":"606_CR31","first-page":"53","volume":"21","author":"Y Ishida","year":"2008","unstructured":"Ishida Y, Zhao L, Nagamochi H, Akutsu T: Improved algorithms for enumerating tree-like chemical graphs with given path frequency. Genome Inform. 2008, 21: 53-64.","journal-title":"Genome Inform"},{"key":"606_CR32","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks EM: Isomorphism of graphs of bounded valence can be tested in polynomial time. J Comput Syst Sci. 1982, 25: 42-65. 10.1016\/0022-0000(82)90009-5.","journal-title":"J Comput Syst Sci"},{"key":"606_CR33","first-page":"161","volume-title":"Proceedings of 15th Annual ACM Symp Theory of Computing","author":"M F\u00fcrer","year":"1983","unstructured":"F\u00fcrer M, Schnyder W, Specker E: Normal forms for trivalent graphs and graphs of bounded valence. Proceedings of 15th Annual ACM Symp Theory of Computing. 1983, NY: ACM Press, 161-170."},{"key":"606_CR34","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1021\/ci9702914","volume":"38","author":"Faulon J-L","year":"1998","unstructured":"Faulon J-L: Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. J Chem Inf Comput Sci. 1998, 38: 432-444. 10.1021\/ci9702914.","journal-title":"J Chem Inf Comput Sci"},{"key":"606_CR35","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1515\/crll.1869.70.185","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan C: Sur les assemblages de lignes. J Reine Angew Math. 1869, 70: 185-190.","journal-title":"J Reine Angew Math"},{"key":"606_CR36","unstructured":"Li J: Enumerating benzene isomers of tree-like chemical graphs. Master\u2019s Thesis. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University 2014,"}],"container-title":["Journal of Cheminformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1758-2946-6-31\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1758-2946-6-31.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1758-2946-6-31.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T03:58:19Z","timestamp":1630555099000},"score":1,"resource":{"primary":{"URL":"https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/1758-2946-6-31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,30]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["606"],"URL":"https:\/\/doi.org\/10.1186\/1758-2946-6-31","relation":{},"ISSN":["1758-2946"],"issn-type":[{"value":"1758-2946","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,30]]},"assertion":[{"value":"28 September 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"31"}}