A Novel Method for Inferring Chemical Compounds With Prescribed Topological Substructures Based on Integer Programming.

Drug discovery is one of the major goals of computational biology and bioinformatics. A novel framework has recently been proposed for the design of chemical graphs using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase.

A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming.

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.

Enumerating Tree-Like Graphs and Polymer Topologies with a Given Cycle Rank.

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.

An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops.

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 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 vertices, Δ self-loops and no multi-edges, in O(n2(n+Δ(n+Δ·min{n,Δ}))) time and O(n2(Δ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.

Resource Cut, a New Bounding Procedure to Algorithms for Enumerating Tree-Like Chemical Graphs.

Enumerating chemical compounds with given structural properties plays an important role in structure elucidation, with applications such as drug design. We focus on the problem of enumerating tree-like chemical graphs specified by upper and lower bounds on feature vectors, where chemical graphs represent compounds, and a feature vector characterizes frequencies of finite paths in a graph. Building on the branch-and-bound algorithm proposed in earlier work, we propose a new bounding procedure, called Resource Cut, to speed up the enumeration process.