betaFeedback

WorksComputer Science

Molecular Design Based on Integer Programming and Splitting Data Sets by Hyperplanes

Abstract

A novel framework for designing the molecular structure of chemical compounds with a desired chemical property has recently been proposed. The framework infers a desired chemical graph by solving a mixed integer linear program (MILP) that simulates the computation process of a feature function defined by a two-layered model on chemical graphs and a prediction function constructed by a machine learning method. To improve the learning performance of prediction functions in the framework, we design a method that splits a given data set C\mathcal{C} into two subsets C(i),i=1,2\mathcal{C}^{(i)},i=1,2 by a hyperplane in a chemical space so that most compounds in the first (resp., second) subset have observed values lower (resp., higher) than a threshold θθ. We construct a prediction function ψψ to the data set C\mathcal{C} by combining prediction functions ψi,i=1,2ψ_i,i=1,2 each of which is constructed on C(i)\mathcal{C}^{(i)} independently. The results of our computational experiments suggest that the proposed method improved the learning performance for several chemical properties to which a good prediction function has been difficult to construct.

Introduction

Background Among various application areas of bioinformatics and machine learning, drug design is gathering interest [1, 2]. Accordingly, extensive studies have been done on computational analysis of chemical structures. There are two major topics in such studies: prediction of the chemical property of a given chemical structure, and design of a chemical structure having a desired chemical property. These topics have also been extensively studied in the field of cheminformatics, where the former one is referred to as quantitative structure activity relationship (QSAR) [3] and the latter as inverse quantitative structure activity relationship (inverse QSAR) [4, 5, 6].

For the prediction task, statistical methods and machine learning methods have been extensively utilized [3]. In most of such studies, there are two phases: learning phase and prediction phase. In the learning phase, a prediction function is derived from training data consisting of pairs of chemical structures and their activities (or properties), where each chemical structure is given as an undirected graph (called a chemical graph) and then is transformed into a vector of real numbers called features or descriptors. In the prediction phase, the prediction function derived as above is simply applied to the feature vector obtained from a given chemical graph. To derive a prediction function, regression-based methods have been utilized in traditional QSAR studies [3], where machine learning-based methods, including artificial neural network (ANN)-based methods [7, 8], have recently been extensively utilized. It is to be noted that when using graph convolutional networks (GCNs) [9], chemical graphs can be directly handled and thus transformation to feature vectors is not necessarily required.

For the design task, prediction functions are also utilized and are usually derived from existing data as in the above. Then, chemical structures are inferred from given chemical activities through a prediction function [4, 5, 6] where additional constraints may be imposed to restrict the possible structures. In the traditional approach, this inference task consists of two phases, (i) derivation of feature vectors from given chemical activities using the inverse of the prediction function, and (ii) reconstruction of chemical structures from given feature vectors, where these two phases are often mixed. For (i), some optimization methods and/or sampling methods are usually employed. For (ii), some enumeration methods are often applied. However, both are inverse problems and are computationally difficult. For example, it is known that the number of possible chemical graphs is huge [10] and inference of a chemical graph from a given feature vector is NP-hard in general [11]. Therefore, most existing methods employ heuristic methods for both (i) and (ii), and thus do not guarantee optimal or exact solutions.

Recently, different approaches have been proposed for the design task using ANNs. One of the attractive points of ANNs is that generative models are available, which include autoencoders and generative adversarial networks. Furthermore, as mentioned before, chemical structures can be directly handled by using GCNs [9]. By combining these techniques, it might be possible to design novel chemical structures without solving the inverse problems [12]. Indeed, extensive studies have recently been done using various ANN models, which include variational autoencoders [13], grammar variational autoencoders [14], generative adversarial networks [15], recurrent neural networks [16, 17], and invertible flow models [18, 19]. However, these are heuristic methods (although based on some statistical models) and thus do not guarantee optimality or exactness of the solutions.

Framework A novel framework for inferring chemical graphs has been developed [20, 21, 22, 23] based on an idea of formulating as a mixed integer linear programming (MILP), the computation process of a prediction function constructed by a machine learning method. The unique point of this framework is that once a prediction function is formulated, the inverse problem can be solved exactly by applying an MILP solver. It consists of two main phases: the first phase constructs a prediction function η\eta for a chemical property and the second phase infers a chemical graph with a target value of the property based on the function η\eta. For a chemical property π\pi, let CπC_{\pi} be a data set of chemical graphs such that the observed value a(C)a(C) of property π\pi for every chemical graph C∈CπC \in C_{\pi} is available. In the first phase, we introduce a feature function f:G→RKf:\mathcal{G} \to\mathbb{R}^{K} for a positive integer KK, where the descriptors of a chemical graph are defined based on local graph structures in a special way called a two-layered model. We then construct a prediction function

η\eta by a machine learning method such as linear regression, decision tree and an ANN so that the output y=η(x)∈Ry=\eta(x)\in\mathbb{R} of the feature vector x=f(C)∈RKx=f(\mathcal{C})\in\mathbb{R}^{K} for each C∈Cπ\mathcal{C}\in\mathcal{C}_{\pi} serves as a predicted value to the real value a(C)a(\mathcal{C}). In the second phase of inferring a desired chemical graph, we specify not only a target chemical value for property π\pi but also an abstract structure for a chemical graph to be inferred. The latter is described by a set of rules based on the two-layered model called a topological specification σ\sigma, and denote by Gσ\mathcal{G}_{\sigma} the set of all chemical graphs that satisfy the rules in σ\sigma. The users select topological specification σ\sigma and two reals y‾∗\underline{y}^{*} and y‾∗\overline{y}^{*} as an interval for a target chemical value. The task of the second phase is to infer chemical graphs C∗∈Gσ\mathcal{C}^{*}\in\mathcal{G}_{\sigma} such that y‾∗≤η(f(C∗))≤y‾∗\underline{y}^{*}\leq\eta(f(\mathcal{C}^{*}))\leq\overline{y}^{*} (see Figure 1 for an illustration). For this, we formulate an MILP Mf,η,σ\mathcal{M}_{f,\eta,\sigma} that represents (i) the computation process of x:=f(C)x:=f(\mathcal{C}) from a chemical graph C\mathcal{C} in the feature function ff; (ii) the computation process of y:=η(x)y:=\eta(x) from a vector x∈RKx\in\mathbb{R}^{K} in the prediction function η\eta; and (iii) the constraint for C∈Gσ\mathcal{C}\in\mathcal{G}_{\sigma}. Given an interval with y‾∗,y‾∗∈R\underline{y}^{*},\overline{y}^{*}\in\mathbb{R}, we solve the MILP Mf,η,σ\mathcal{M}_{f,\eta,\sigma} to find a feature vector x∗∈RKx^{*}\in\mathbb{R}^{K} and a chemical graph C†∈Gσ\mathcal{C}^{\dagger}\in\mathcal{G}_{\sigma} such that f(C†)=x∗f(\mathcal{C}^{\dagger})=x^{*} and y‾∗≤η(x∗)≤y‾∗\underline{y}^{*}\leq\eta(x^{*})\leq\overline{y}^{*} (where if the MILP instance is infeasible then this suggests that Gσ\mathcal{G}_{\sigma} does not contain such a desired chemical graph). In the second phase, we next generate some other desired chemical graphs based on the solution C†\mathcal{C}^{\dagger}. For this, the following two methods have been designed.

Illustration of inferring desired chemical graphs

Figure 1. An illustration of inferring desired chemical graphs C∈Gσ\mathcal{C} \in\mathcal{G}_{\sigma} with y‾∗≤η(f(C))≤y‾∗\underline{y}^{*} \leq\eta(f(\mathcal{C})) \leq\overline{y}^{*}.

The first method constructs isomers of C†\mathcal{C}^{\dagger} without solving any new MILP. In this method, we first decompose the chemical graph C†\mathcal{C}^{\dagger} into a set of chemical acyclic graphs T1†,T2†,…,Tq†T_{1}^{\dagger},T_{2}^{\dagger},\ldots,T_{q}^{\dagger}, and next construct a set Ti\mathcal{T}_{i} of isomers Ti∗T_{i}^{*} of each tree Ti†T_{i}^{\dagger} such that f(Ti∗)=f(Ti†)f(T_{i}^{*})=f(T_{i}^{\dagger}) by a dynamic programming algorithm due to Azam et al. [24]. Finally we choose an isomer Ti∗∈TiT_{i}^{*}\in\mathcal{T}_{i} for each i=1,2,…,qi=1,2,\ldots,q and assemble them into an isomer C∗∈Gσ\mathcal{C}^{*}\in\mathcal{G}_{\sigma} of C†\mathcal{C}^{\dagger} such that f(C∗)=x∗=f(C†)f(\mathcal{C}^{*})=x^{*}=f(\mathcal{C}^{\dagger}). The first method generates such isomers C1∗,C2∗,…\mathcal{C}_{1}^{*},\mathcal{C}_{2}^{*},\ldots which we call recombination solutions of C†\mathcal{C}^{\dagger}.

The second method constructs new solutions by solving the MILP Mf,η,σ\mathcal{M}_{f,\eta,\sigma} with an additional set Θ\Theta of new linear constraints [23]. We first prepare arbitrary pdimp_{\mathrm{dim}} linear functions θj:RK→R,j=1,2,…,pdim\theta_{j}:\mathbb{R}^{K}\to\mathbb{R},j=1,2,\ldots,p_{\mathrm{dim}} and consider a neighbor of C†\mathcal{C}^{\dagger} defined by a set of chemical graphs C∗\mathcal{C}^{*} that satisfy linear constraints (k−0.5)δ≤∣θj(f(C∗))−θj(f(C†))∣≤(k+0.5)δ,j=1,2,…,pdim(k-0.5)\delta\leq\left|\theta_{j}(f(\mathcal{C}^{*}))-\theta_{j}(f(\mathcal{C}^{\dagger}))\right|\leq(k+0.5)\delta,j=1,2,\ldots,p_{\mathrm{dim}} for a small real δ>0\delta> 0 and an integer k≥1k \ge1. By changing the integer kk systematically, we can search for new solutions C1†,C2†,…∈Gσ\mathrm{C}^{\dagger}_{1},\mathrm{C}^{\dagger}_{2},\ldots\in\mathcal{G}_{\sigma} of MILP Mf,η,σ\mathcal{M}_{f,\eta,\sigma} with constraint Θ\Theta such that the feature vectors x∗=f(C1†),x1∗=f(C1†),x2∗=f(C2†),…\boldsymbol{x}^{*}=f(\mathrm{C}^{\dagger}_{1}),\boldsymbol{x}^{*}_{1}=f(\mathrm{C}^{\dagger}_{1}),\boldsymbol{x}^{*}_{2}=f(\mathrm{C}^{\dagger}_{2}),\ldots are all slightly different. We call these chemical graphs C1†,C2†,…\mathrm{C}^{\dagger}_{1},\mathrm{C}^{\dagger}_{2},\ldots neighbor solutions of C1†\mathrm{C}^{\dagger}_{1}.

The main reason why the framework can infer a chemical compound with 50 non-hydrogen atoms is that the descriptors of a chemical graph are defined on local graph structures in the two-layered model and thereby an MILP necessary to represent a chemical graph can be formulated as a considerably compact form that is efficiently solvable by a standard solver.

Contribution The descriptors in the framework mainly consists of the frequencies of local graph structures based on the two-layered model by which a chemical graph C\mathrm{C} is regarded as a pair of interior and exterior structures (see § 3 for details). To derive a compact MILP formulation to infer a chemical graph, it is important to use the current definition of descriptors. However, there are some chemical properties for which the performance of a prediction function constructed with the feature function ff remains rather low. To improve the learning performance of prediction functions with the same two-layered model, we propose a method of splitting a given data set with a hyperplane in the feature space into two subsets, where we construct a prediction function to each of the subsets independently before a prediction function η\eta to the original set is obtained by combining these prediction functions (see § 5 for details). Based on the same MILP Mf,η,σ\mathcal{M}_{f,\eta,\sigma} formulation proposed by Zhu et al. [21], we implemented the framework to treat the newly proposed type of prediction. From the results of our computational experiments on over some chemical properties such as odor threshold [30], we observe that our new method of splitting data sets and combining prediction functions improved the performance of a prediction function for these chemical properties. It is to be noted that extensive studies have been done on prediction problems using hyperplanes since the development of support vector machines [25]. However, existing methods can only be applied to prediction problems. The novel and unique point of our study is that an efficient MILP formulation for chemical graphs is developed, which makes the inverse problem (i.e., design problem) tractable.

The paper is organized as follows. Section 2 introduces some notions on graphs and a modeling of chemical compounds. Section 3 reviews the two-layered model and descriptors defined by the model. Section 4 reviews prediction functions constructed by linear regression. Section 5 proposes a method of splitting a data set by a hyperplane and a linear programming formulation for finding such a hyperplane. Section 6 reports the results on computational experiments conducted for 22 chemical properties such as autoignition temperature, flammable limits and odor threshold. Section 7 makes some concluding remarks. Some technical details are given in Appendices: Appendix A for all descriptors in our feature function; Appendix B for a full description of a topological specification; and Appendix C for the detail of test instances used in our computational experiment.

Preliminary

This section introduces some notions and terminologies on graphs, modeling of chemical compounds and our choice of descriptors.

Let R\mathbb{R}, R+\mathbb{R}_{+}, Z\mathbb{Z} and Z+\mathbb{Z}_{+} denote the sets of reals, non-negative reals, integers and non-negative integers, respectively. For two integers aa and bb, let [a,b][a,b] denote the set of integers ii with a≤i≤ba \le i \le b. For a vector x∈Rpx \in\mathbb{R}^{p}, the jj-th entry of xx is denoted by x(j)x(j).

References

  1. [1]Lo, Y.-C., Rensi, S. E., Torng, W., Altman, R. B.: Machine learning in chemoinformatics and drug discovery. Drug Discovery Today 23, 1538–1546 (2018)DOI
  2. [2]Tetko, I. V., Engkvist, O.: From big data to artificial intelligence: chemoinformatics meets new challenges. J. Cheminformatics 12, 74 (2020)DOI
  3. [3]Cherkasov, A., Muratov, E. N., Fourches, D., Varnek, A., Baskin, I. I., Cronin, M., Dearden, J., Gramatica, P., Martin, Y. C., Todeschini, R., et al. QSAR modeling: where have you been? Where are you going to? J. Med. Chem. 57, 4977–5010 (2014)DOI
  4. [4]Miyao, T., Kaneko, H., Funatsu, K.: Inverse QSPR/QSAR analysis for chemical structure generation (from y to x). J. Chem. Inf. Model. 56, 286–299 (2016)
  5. [5]Ikebata, H., Hongo, K., Isomura, T., Maezono, R., Yoshida, R.: Bayesian molecular design with a chemical language model. J. Comput. Aided Mol. Des. 31, 379–391 (2017)DOI
  6. [6]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)DOI
  7. [7]Ghasemi, F., Mehridehnavi, A., Pérez-Garrido, A., Pérez-Sánchez, H.: Neural network and deep-learning algorithms used in QSAR studies: merits and drawbacks. Drug Discovery Today 23, 1784–1790 (2018)DOI
  8. [8]Kim, J., Park, S., Min, D., Kim, W.: Comprehensive survey of recent drug discovery using deep learning. Int. J. Molecular Science 22(18), 9983 (2022)DOI
  9. [9]Kipf, T. N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv:1609.02907 (2016)arxiv.org/abs/1609.02907
  10. [10]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)pubmed.ncbi.nlm.nih.gov/8788213
  11. [11]Akutsu, T., Fukagawa, D., Jansson, J., Sadakane, K.: Inferring a graph from path frequency. Discrete Appl. Math. 160, 10-11, 1416–1428 (2012)
  12. [12]Xiong, J., Xiong, Z., Chen, K., Jiang, H., Zheng, M.: Graph neural networks for automated de novo drug design. Drug Discovery Today 26, 1382–1393 (2022)DOI
  13. [13]Gómez-Bombarelli, R., Wei, J. N., Duvenaud, D., Hernández-Lobato, J. M., Sánchez-Lengeling, B., Sheberla, D., Aguilera-Iparraguirre, J., Hirzel, T. D., Adams, R. P., Aspuru-Guzik, A.: Automatic chemical design using a data-driven continuous representation of molecules. ACS Cent. Sci. 4, 268–276 (2018)
  14. [14]Kusner, M. J., Paige, B., Hernández-Lobato, J. M.: Grammar variational autoencoder. Proc. of the 34th International Conference on Machine Learning-Volume 70, 1945–1954 (2017)arxiv.org/abs/1703.01925
  15. [15]De Cao, N., Kipf, T.: MolGAN: An implicit generative model for small molecular graphs. arXiv:1805.11973 (2018)arxiv.org/abs/1805.11973
  16. [16]Segler, M. H. S., Kogej, T., Tyrchan, C., Waller, M. P.: Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS Cent. Sci. 4, 120–131 (2017)DOI
  17. [17]Yang, X., Zhang, J., Yoshizoe, K., Terayama, K., Tsuda, K.: ChemTS: an efficient python library for de novo molecular generation. STAM 18, 972–976 (2017)DOI
  18. [18]Madhawa, K., Ishiguro, K., Nakago, K., Abe, M.: GraphNVP: an invertible flow model for generating molecular graphs. arXiv:1905.11600 (2019)arxiv.org/abs/1905.11600
  19. [19]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)arxiv.org/abs/2001.09382
  20. [20]Shi, Y., Zhu, J., Azam, N. A., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T.: An inverse QSAR method based on a two-layered model and integer programming. Int. J. Molecular Sciences 22, 2847 (2021)DOI
  21. [21]Zhu, J., Azam, N. A., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T.: A method for molecular design based on linear regression and integer programming. 12th International Conference on Bioscience, Biochemistry and Bioinformatics, Tokyo, Japan, January 7-10, #TJ0002, 21–28 (2022)DOI
  22. [22]Ido, R., Cao, S., Zhu, J., Azam, N. A., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T.: A method for inferring polymers based on linear regression and integer programming. The 20th Asia Pacific Bioinformatics Conference (APBC2022) April 26-28, 2022arxiv.org/abs/2109.02628
  23. [23]Azam, N. A., Zhu, J., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T.: Molecular design based on artificial neural networks, integer programming and grid neighbor search. BIBM 2021: 360–363 (2021)arxiv.org/abs/2108.10266
  24. [24]Azam, N. A., Zhu, J., Sun, Y., Shi, Y., Shurbevski, A., Zhao, L., Nagamochi, H., Akutsu, T.: A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming. Algorithms for Molecular Biology 16, 18 (2021)
  25. [25]Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20, 273-297 (1995)DOI
  26. [26]Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Statist. Soc. B 58, 267–288 (1996)
  27. [27]Zhu, J., Haraguchi, K., Nagamochi, H., Akutsu, T.: Adjustive linear regression and its application to the inverse QSAR. 13th International Conference on Bioinformatics Models, Methods and Algorithms, February 9-11. #14, 144–151 (2022)DOI
  28. [28]Zhu, J., Azam, N. A., Cao, S., Ido, R., Haraguchi, K., Zhao, L., Nagamochi, H., Akutsu, T.: Molecular design based on integer programming and quadratic descriptors in a two-layered model. The 21st International Conference on Bioinformatics (InCoB2022), November 21-23 (2022)arxiv.org/abs/2209.13527
  29. [29]Freed, N., Glover, F.: Simple but powerful goal programming models for discriminant problems. Europian J. Operations Research 7, 44–60 (1981)DOI
  30. [30]Annotations from HSDB (on pubchem): |https://pubchem.ncbi.nlm.nih.gov/—
  31. [31]ESOL at MoleculeNet: |http://moleculenet.ai/datasets-1—
  32. [32]Dashti, A., Jokar, M., AmirKhani, F., Mohammadi, A. H..: Quantitative structure property relationship schemes for estimation of autoignition temperatures of organic compounds. J. Molecular Liquids Feb 15; 300: 111797 (2020)DOI
  33. [33]Yuan, S., Jiao, Z., Quddus, N., Kwon, J. S., Mashuga, C. V.: Developing quantitative structure–property relationship models to predict the upper flammability limit using machine learning. Industrial & Engineering Chemistry Research 58(8):3531-7 (2019)DOI
  34. [34]Kondo S., Urano, Y., Tokuhashi, K., Takahashi, A., Tanaka, K.: Prediction of flammability of gases by using F-number analysis. J. Hazardous Materials Mar 30; 82(2): 113-28 (2001)pubmed.ncbi.nlm.nih.gov/11230911
  35. [35]QM9 at MoleculeNet: |http://moleculenet.ai—

Paper details

vlnc:W_7wzz9b5x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents