A new approach to the design of acyclic chemical compounds using skeleton trees and integer linear programming

Abstract Intelligent systems are applied in a wide range of areas, and computer-aided drug design is a highly important one. One major approach to drug design is the inverse QSAR/QSPR (quantitative structure-activity and structure-property relationship), for which a method that uses both artificial neural networks (ANN) and mixed integer linear programming (MILP) has been proposed recently. This method consists of two phases: a forward prediction phase, and an inverse, inference phase. In the prediction phase, a feature function f over chemical compounds is defined, whereby a chemical compound G is represented as a vector f ( G ) of descriptors. Following, for a given chemical property $$\pi$$ , using a dataset of chemical compounds with known values for property $$\pi$$ , a regressive prediction function $$\psi$$ is computed by an ANN. It is desired that $$\psi (f(G))$$ takes a value that is close to the true value of property $$\pi$$ for the compound G for many of the compounds in the dataset. In the inference phase, one starts with a target value $$y^*$$ of the chemical property $$\pi$$ , and then a chemical structure $$G^*$$ such that $$\psi (f(G^*))$$ is within a certain tolerance level of $$y^*$$ is constructed from the solution to a specially formulated MILP. This method has been used for the case of inferring acyclic chemical compounds. With this paper, we propose a new concept on acyclic chemical graphs, called a skeleton tree, and based on it develop a new MILP formulation for inferring acyclic chemical compounds. Our computational experiments indicate that our newly proposed method significantly outperforms the existing method when the diameter of graphs is up to 8. In a particular example where we inferred acyclic chemical compounds with 38 non-hydrogen atoms from the set { C , O , S } times faster.