{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T18:43:24Z","timestamp":1761677004734,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["18H04113"],"award-info":[{"award-number":["18H04113"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Analysis of chemical graphs is becoming a major research topic in computational molecular biology due to its potential applications to drug design. One of the major approaches in such a study is inverse quantitative structure activity\/property relationship (inverse QSAR\/QSPR) analysis, which is to infer chemical structures from given chemical activities\/properties. Recently, a novel two-phase framework has been proposed for inverse QSAR\/QSPR, where in the first phase an artificial neural network (ANN) is used to construct a prediction function. In the second phase, a mixed integer linear program (MILP) formulated on the trained ANN and a graph search algorithm are used to infer desired chemical structures. The framework has been applied to the case of chemical compounds with cycle index up to 2 so far. The computational results conducted on instances with<jats:italic>n<\/jats:italic>non-hydrogen atoms show that a feature vector can be inferred by solving an MILP for up to<jats:inline-formula><jats:alternatives><jats:tex-math>$$n=40$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>40<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, whereas graphs can be enumerated for up to<jats:inline-formula><jats:alternatives><jats:tex-math>$$n=15$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>15<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. When applied to the case of chemical acyclic graphs, the maximum computable diameter of a chemical structure was up to\u00a08. In this paper, we introduce a new characterization of graph structure, called \u201cbranch-height\u201d based on which a new MILP formulation and a new graph search algorithm are designed for chemical acyclic graphs. The results of computational experiments using such chemical properties as octanol\/water partition coefficient, boiling point and heat of combustion suggest that the proposed method can infer chemical acyclic graphs with around<jats:inline-formula><jats:alternatives><jats:tex-math>$$n=50$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>50<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and diameter 30.<\/jats:p>","DOI":"10.1186\/s13015-021-00197-2","type":"journal-article","created":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T08:03:02Z","timestamp":1628928182000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming"],"prefix":"10.1186","volume":"16","author":[{"given":"Naveed Ahmed","family":"Azam","sequence":"first","affiliation":[]},{"given":"Jianshen","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Yanming","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Yu","family":"Shi","sequence":"additional","affiliation":[]},{"given":"Aleksandar","family":"Shurbevski","sequence":"additional","affiliation":[]},{"given":"Liang","family":"Zhao","sequence":"additional","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9763-797X","authenticated-orcid":false,"given":"Tatsuya","family":"Akutsu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"issue":"2","key":"197_CR1","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1021\/acs.jcim.5b00628","volume":"56","author":"T Miyao","year":"2016","unstructured":"Miyao T, Kaneko H, Funatsu K. Inverse QSPR\/QSAR analysis for chemical structure generation (from y to x). J Chem Inf Model. 2016;56(2):286\u201399.","journal-title":"J Chem Inf Model"},{"issue":"4","key":"197_CR2","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1021\/ci00014a017","volume":"33","author":"MI Skvortsova","year":"1993","unstructured":"Skvortsova MI, Baskin II, Slovokhotova OL, Palyulin VA, Zefirov NS. Inverse problem in QSAR\/QSPR studies for the case of topological indices characterizing molecular shape (Kier indices). J Chem Inf Comput Sci. 1993;33(4):630\u20134.","journal-title":"J Chem Inf Comput Sci"},{"issue":"4","key":"197_CR3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s10822-016-0008-z","volume":"31","author":"H Ikebata","year":"2017","unstructured":"Ikebata H, Hongo K, Isomura T, Maezono R, Yoshida R. Bayesian molecular design with a chemical language model. J Comput Aided Mol Design. 2017;31(4):379\u201391.","journal-title":"J Comput Aided Mol Design"},{"issue":"3","key":"197_CR4","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1021\/ci500749q","volume":"55","author":"C Rupakheti","year":"2015","unstructured":"Rupakheti C, Virshup A, Yang W, Beratan DN. Strategy to discover diverse optimal molecules in the small molecule universe. J Chem Inf Model. 2015;55(3):529\u201337.","journal-title":"J Chem Inf Model"},{"issue":"7","key":"197_CR5","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 treelike chemical graphs with given path frequency. J Chem Inf Model. 2008;48(7):1345\u201357.","journal-title":"J Chem Inf Model"},{"key":"197_CR6","first-page":"205","volume":"37","author":"A Kerber","year":"1998","unstructured":"Kerber A, Laue R, Gr\u00fcner T, Meringer M. MOLGEN 4.0. Match Commun Math Comput Chem. 1998;37:205\u20138.","journal-title":"Match Commun Math Comput Chem"},{"issue":"2","key":"197_CR7","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1109\/TCBB.2016.2628888","volume":"15","author":"J Li","year":"2016","unstructured":"Li J, Nagamochi H, Akutsu T. Enumerating substituted benzene isomers of tree-like chemical graphs. IEEE\/ACM Trans Comput Biol Bioinf. 2016;15(2):633\u201346.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"3","key":"197_CR8","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1021\/ar500432k","volume":"48","author":"J-L Reymond","year":"2015","unstructured":"Reymond J-L. The chemical space project. Accounts Chem Res. 2015;48(3):722\u201330.","journal-title":"Accounts Chem Res"},{"issue":"10\u201311","key":"197_CR9","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(10\u201311):1416\u201328.","journal-title":"Discrete Appl Math"},{"issue":"2","key":"197_CR10","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(2):207\u201324.","journal-title":"Algorithmica"},{"issue":"1","key":"197_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/(SICI)1098-1128(199601)16:1<3::AID-MED1>3.0.CO;2-6","volume":"16","author":"RS Bohacek","year":"1996","unstructured":"Bohacek RS, McMartin C, Guida WC. The art and practice of structure-based drug design: a molecular modeling perspective. Med Res Rev. 1996;16(1):3\u201350.","journal-title":"Med Res Rev"},{"issue":"2","key":"197_CR12","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1021\/acscentsci.7b00572","volume":"4","author":"R G\u00f3mez-Bombarelli","year":"2018","unstructured":"G\u00f3mez-Bombarelli R, Wei JN, Duvenaud D, Hern\u00e1ndez-Lobato JM, S\u00e1nchez-Lengeling B, Sheberla D, Aguilera-Iparraguirre J, Hirzel TD, Adams RP, Aspuru-Guzik A. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Sci. 2018;4(2):268\u201376.","journal-title":"ACS Central Sci"},{"issue":"1","key":"197_CR13","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1021\/acscentsci.7b00512","volume":"4","author":"MHS Segler","year":"2017","unstructured":"Segler MHS, Kogej T, Tyrchan C, Waller MP. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS Central Sci. 2017;4(1):120\u201331.","journal-title":"ACS Central Sci"},{"issue":"1","key":"197_CR14","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1080\/14686996.2017.1401424","volume":"18","author":"X Yang","year":"2017","unstructured":"Yang X, Zhang J, Yoshizoe K, Terayama K, Tsuda K. ChemTS: an efficient python library for de novo molecular generation. Sci Technol Adv Mater. 2017;18(1):972\u20136.","journal-title":"Sci Technol Adv Mater"},{"key":"197_CR15","unstructured":"Kusner MJ, Paige B, Hern\u00e1ndez-Lobato JM. Grammar variational autoencoder. In: Proceedings of the 34th International Conference on Machine Learning, vol 70; 2017. p. 1945\u201354"},{"key":"197_CR16","doi-asserted-by":"crossref","unstructured":"Akutsu T, Nagamochi H. A mixed integer linear programming formulation to artificial neural networks. In: Proceedings of the 2nd international conference on information science and systems, Tokyo, Japan, ACM; 2019. p. 215\u201320.","DOI":"10.1145\/3322645.3322683"},{"key":"197_CR17","doi-asserted-by":"crossref","unstructured":"Azam NA, Chiewvanichakorn R, Zhang F, Shurbevski A, Nagamochi H, Akutsu T. A method for the inverse QSAR\/QSPR based on artificial neural networks and mixed integer linear programming with guaranteed admissibility. In: Proceedings of the 13th international joint conference on biomedical engineering systems and technologies, vol 3: BIOINFORMATICS, Valetta, Malta; 2020. p. 101\u2013108","DOI":"10.5220\/0008876801010108"},{"key":"197_CR18","doi-asserted-by":"publisher","unstructured":"Chiewvanichakorn R, Wang C, Zhang Z, Shurbevski A, Nagamochi H, Akutsu T. A method for the inverse QSAR\/QSPR based on artificial neural networks and mixed integer linear programming. In: Proceedings of the 2020 10th international conference on bioscience, biochemistry and bioinformatics, Kyoto, Japan; 2020. p. 40\u201346. https:\/\/doi.org\/10.1145\/3386052.3386054","DOI":"10.1145\/3386052.3386054"},{"key":"197_CR19","doi-asserted-by":"publisher","unstructured":"Zhang F, Zhu J, Chiewvanichakorn R, Shurbevski A, Nagamochi H, Akutsu T. A new integer linear programming formulation to the inverse QSAR\/QSPR for acyclic chemical compounds using skeleton trees. In: Proceedings of the 33rd international conference on industrial, engineering and other applications of applied intelligent systems, Kitakyushu, Japan; 2020. p. 433\u2013444. https:\/\/doi.org\/10.1007\/978-3-030-55789-8_38","DOI":"10.1007\/978-3-030-55789-8_38"},{"key":"197_CR20","doi-asserted-by":"crossref","unstructured":"Ito R, Azam NA, Wang C, Shurbevski A, Nagamochi H, Akutsu T. A novel method for the inverse QSAR\/QSPR to monocyclic chemical compounds based on artificial neural networks and integer programming. In: Proceedings of the 21st international conference on bioinformatics and computational biology; 2020","DOI":"10.5220\/0008876801010108"},{"key":"197_CR21","doi-asserted-by":"publisher","unstructured":"Zhu J, Wang C, Shurbevski A, Nagamochi H, Akutsu T. A novel method for inference of chemical compounds of cycle index two with desired properties based on artificial neural networks and integer programming. Algorithms. 13:5. doi: https:\/\/doi.org\/10.3390\/a13050124.124.","DOI":"10.3390\/a13050124.124."},{"issue":"1","key":"197_CR22","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1186\/1758-2946-6-31","volume":"6","author":"M Suzuki","year":"2014","unstructured":"Suzuki M, Nagamochi H, Akutsu T. Efficient enumeration of monocyclic chemical graphs with given path frequencies. J Cheminf. 2014;6(1):31.","journal-title":"J Cheminf"},{"key":"197_CR23","unstructured":"Tamura Y, Nishiyama Y, Wang C, Sun Y, Shurbevski A, Nagamochi H, Akutsu T. Enumerating chemical graphs with mono-block 2-augmented tree structure from given upper and lower bounds on path frequencies; 2020. arXiv preprint arXiv:2004.06367"},{"key":"197_CR24","unstructured":"Yamashita K, Masui R, Zhou X, Wang C, Shurbevski A, Nagamochi H, Akutsu T. Enumerating chemical graphs with two disjoint cycles satisfying given path frequency specifications; 2020. arXiv preprint arXiv:2004.08381"},{"issue":"D1","key":"197_CR25","doi-asserted-by":"publisher","first-page":"D1388","DOI":"10.1093\/nar\/gkaa971","volume":"49","author":"S Kim","year":"2021","unstructured":"Kim S, et al. PubChem in 2021: new data content and improved web interfaces. Nucleic Acids Res. 2021;49(D1):D1388\u201395.","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"197_CR26","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1177\/026119290503300209","volume":"33","author":"TI Netzeva","year":"2005","unstructured":"Netzeva TI, et al. Current status of methods for defining the applicability domain of (quantitative) structure-activity relationships: the report and recommendations of ECVAM workshop 52. Altern Lab Anim. 2005;33(2):155\u201373.","journal-title":"Altern Lab Anim"},{"key":"197_CR27","unstructured":"Nagamochi H, Akutsu T. A novel method for inference of chemical compounds with prescribed topological substructures based on integer programming; 2020. arXiv preprint arXiv:2010.09203"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00197-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00197-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00197-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T10:57:15Z","timestamp":1673089035000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00197-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["197"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00197-2","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"24 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"18"}}