Search

A novel framework for inverse quantitative structure–activity relationships (inverse QSAR) has recently been proposed and developed using both artificial neural networks and mixed integer linear programming. However, classes of chemical graphs treated by the framework are limited. In order to deal with an arbitrary graph in the framework, we introduce a new model, called a two-layered model, and develop a corresponding method. In this model, each chemical graph is regarded as two parts: the exterior and the interior. The exterior consists of maximal acyclic induced subgraphs with bounded height, the interior is the connected subgraph obtained by ignoring the exterior, and the feature vector consists of the frequency of adjacent atom pairs in the interior and the frequency of chemical acyclic graphs in the exterior. Our method is more flexible than the existing method in the sense that any type of graphs can be inferred. We compared the proposed method with an existing method using several data sets obtained from PubChem database. The new method could infer more general chemical graphs with up to 50 non-hydrogen atoms. The proposed inverse QSAR method can be applied to the inference of more general chemical graphs than before. [ABSTRACT FROM AUTHOR]

Cycle rank is an important notion that is widely used to classify, understand, and discover new chemical compounds. We propose a method to enumerate all non-isomorphic tree-like graphs of a given cycle rank with self-loops and no multiple edges. To achieve this, we develop an algorithm to enumerate all non-isomorphic rooted graphs with the required constraints. The idea of our method is to define a canonical representation of rooted graphs and enumerate all non-isomorphic graphs by generating the canonical representation of rooted graphs. An important feature of our method is that for an integer n ≥ 1 , it generates all required graphs with n vertices in O (n) time per graph and O (n) space in total, without generating invalid intermediate structures. We performed some experiments to enumerate graphs with a given cycle rank from which it is evident that our method is efficient. As an application of our method, we can generate tree-like polymer topologies of a given cycle rank with self-loops and no multiple edges. [ABSTRACT FROM AUTHOR]

Graph enumeration with given constraints is an interesting problem considered to be one of the fundamental problems in graph theory, with many applications in natural sciences and engineering such as bio-informatics and computational chemistry. For any two integers n ≥ 1 and Δ ≥ 0 , we propose a method to count all non-isomorphic trees with n vertices, Δ self-loops, and no multi-edges based on dynamic programming. To achieve this goal, we count the number of non-isomorphic rooted trees with n vertices, Δ self-loops and no multi-edges, in O (n 2 (n + Δ (n + Δ · min { n , Δ }))) time and O (n 2 (Δ 2 + 1)) space, since every tree can be uniquely viewed as a rooted tree by either regarding its unicentroid as the root, or in the case of bicentroid, by introducing a virtual vertex on the bicentroid and assuming the virtual vertex to be the root. By this result, we get a lower bound and an upper bound on the number of tree-like polymer topologies of chemical compounds with any "cycle rank". [ABSTRACT FROM AUTHOR]

Inference of chemical compounds with desired properties is important for drug design, chemo-informatics, and bioinformatics, to which various algorithmic and machine learning techniques have been applied. Recently, a novel method has been proposed for this inference problem using both artificial neural networks (ANN) and mixed integer linear programming (MILP). This method consists of the training phase and the inverse prediction phase. In the training phase, an ANN is trained so that the output of the ANN takes a value nearly equal to a given chemical property for each sample. In the inverse prediction phase, a chemical structure is inferred using MILP and enumeration so that the structure can have a desired output value for the trained ANN. However, the framework has been applied only to the case of acyclic and monocyclic chemical compounds so far. In this paper, we significantly extend the framework and present a new method for the inference problem for rank-2 chemical compounds (chemical graphs with cycle index 2). The results of computational experiments using such chemical properties as octanol/water partition coefficient, melting point, and boiling point suggest that the proposed method is much more useful than the previous method. [ABSTRACT FROM AUTHOR]