Abstract
Various intelligent methods have recently been applied to the design of novel chemical graphs. As one of such approaches, a framework using both artificial neural networks (ANNs) and mixed integer linear programming (MILP) has been proposed. The method first constructs an ANN so that a specified chemical property is predicted from a feature vector f(G) of a chemical graph G. Next an MILP is formulated so that it simulates the construction of f(G) from G and the computation process in the ANN. Then a novel chemical graph with a given target chemical property is inferred by solving the MILP. Based on the framework, the class of graphs to which the above MILP can be formulated has been extended from the graphs with cycle index 0 to the graphs with cycle index 1 and 2. Recently an MILP has been designed to deal with a graph with any cycle index and the computational results on a system with the MILP showed that chemical graphs with around up to 50 non-hydrogen atoms can be inferred. However, this MILP is computationally costly for some instances, e.g., it takes about 10 h to solve some instances with 50 atoms. One of the main reasons for this is that the number of constraints and variables in the MILP is relatively large. In this paper, we improve the MILP by reducing the number of constraints and variables. For this purpose, we drive and utilize a characterization of a chemical acyclic graph in terms of the frequency of some configurations of atom-pairs, by which we can omit part of the construction of f(G) in the MILP. Our experimental results show that the improved MILP can be solved around 20 times faster than the previous MILP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akutsu, T., Nagamochi, H.: A novel method for inference of chemical compounds with prescribed topological substructures based on integer programming. arXiv: 2010.09203 (2020)
Azam, N.A., 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. In: Proceedings 14th International Conference Biomedical Engineering Systems and Technologies, Malta, pp. 101–108 (2020)
Azam, N.A., et al.: A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming, arXiv:2009.09646 (2020)
Bohacek, R.S., McMartin, C., Guida, W.C.: The art and practice of structure-based drug design: a molecular modeling perspective. Med. Res. Rev. 16, 3–50 (1996)
De, N., Kipf, C.T.: MolGAN: an implicit generative model for small molecular graphs, arXiv:1805.11973 (2018)
Gómez-Bombarelli, R., et al.: Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Sci. 4, 268–276 (2018)
Ikebata, H., Hongo, K., Isomura, T., Maezono, R., Yoshida, R.: Bayesian molecular design with a chemical language model. J. Comput.-Aid. Mol. Des. 31(4), 379–391 (2017). https://doi.org/10.1007/s10822-016-0008-z
Ito, R., Azam, N.A., 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 21st International Conference Bioinformatics and Computational Biology, Las Vegas, Nevada, USA, 27–30 July 2020
Kerber, A., Laue, R., Grüner, T., Meringer, M.: MOLGEN 4.0. Match Commun. Math. Comput. Chem. 37, 205–208 (1998)
Kusner, M.J., Paige, B., Hernández-Lobato, J.M.: Grammar variational autoencoder. In: Proceedings of 34th International Conference Machine Learning-Volume 70, 1945–1954 (2017)
Madhawa, K., Ishiguro, K., Nakago, K., Abe, M.: GraphNVP: an invertible flow model for generating molecular graphs. arXiv:1905.11600 (2019)
Miyao, T., Kaneko, H., Funatsu, K.: Inverse QSPR/QSAR analysis for chemical structure generation (from y to x). J. Chem. Inform. Model. 56 286–299 (2016)
Reymond, J.-L.: The chemical space project. Acc. Chem. Res. 48, 722–730 (2015)
Rupakheti, C., Virshup, A., Yang, W., Beratan, D.N.: Strategy to discover diverse optimal molecules in the small molecule universe. J. Chem. Inf. Model. 55, 529–537 (2015)
Segler, M.H.S., Kogej, T., Tyrchan, C., Waller, M.P.: Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS Central Sci. 4, 120–131 (2017)
Shi, C., Xu, M., Zhu, Z., Zhang, W., Zhang, M., Tang, J.: GraphAF: a flow-based autoregressive model for molecular graph generation. arXiv:2001.09382 (2020)
Yang, X., Zhang, J., Yoshizoe, K., Terayama, K., Tsuda, K.: ChemTS: an efficient python library for de novo molecular generation. Sci. Technol. Adv. Mater. 18, 972–976 (2017)
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: Fujita, H., Fournier-Viger, P., Ali, M., Sasaki, J. (eds.) IEA/AIE 2020. LNCS (LNAI), vol. 12144, pp. 433–444. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55789-8_38
Zhu, J., et al: Akutsu, a novel method for inferring of chemical compounds with prescribed topological substructures based on integer programming. IEEE/ACM Trans. Comput. Biol. Bioinform. (submitted) (2020)
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, 124 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhu, J., Azam, N.A., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T. (2021). An Improved Integer Programming Formulation for Inferring Chemical Compounds with Prescribed Topological Structures. In: Fujita, H., Selamat, A., Lin, J.CW., Ali, M. (eds) Advances and Trends in Artificial Intelligence. Artificial Intelligence Practices. IEA/AIE 2021. Lecture Notes in Computer Science(), vol 12798. Springer, Cham. https://doi.org/10.1007/978-3-030-79457-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-79457-6_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79456-9
Online ISBN: 978-3-030-79457-6
eBook Packages: Computer ScienceComputer Science (R0)