A GA-Simplex Hybrid Algorithm for Global Minimization of Molecular Potential Energy Functions

In this paper we propose a hybrid genetic algorithm for minimizing molecular potential energy functions. Experimental evidence shows that the global minimum of the potential energy of a molecule corresponds to its most stable conformation, which dictates its properties. The search for the global minimum of a potential energy function is very difficult since the number of local minima grows exponentially with molecule size. The proposed approach was successfully applied to two cases: (i) a simplified version of more general molecular potential energy functions in problems with up to 100 degrees of freedom, and (ii) a realistic potential energy function modeling two different molecules.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

Global minimum potential energy conformations of small molecules

A global optimization algorithm is proposed for finding the global minimum potential energy conformations of small molecules. The minimization of the total potential energy is formulated on an independent set of internal coordinates involving only torsion (dihedral) angles. Analytical expressions for the Euclidean distances between non-bonded atoms, which are required for evaluating the individual pairwise potential terms, are obtained as functions of bond lengths, covalent bond angles, and torsion angles. A novel procedure for deriving convex lower bounding functions for the total potential energy function is also introduced. These underestimating functions satisfy a number of important theoretical properties. A global optimization algorithm is then proposed based on an efficient partitioning strategy which is guaranteed to attain -convergence to the global minimum potential energy configuration of a molecule through the solution of a series of nonlinear convex optimization problems. Moreover, lower and upper bounds on the total finite number of required iterations are also provided. Finally, this global optimization approach is illustrated with a number of example problems.     

Prediction of Oligopeptide Conformations via Deterministic Global Optimization

A deterministic global optimization method is described for identifying the global minimum potential energy conformation of oligopeptides. The ECEPP/3 detailed potential energy model is utilized for describing the energetics of the atomic interactions posed in the space of the peptide dihedral angles. Based on previous work on the microcluster and molecular structure determination [21, 22, 23, 24], a procedure for deriving convex lower bounding functions for the total potential energy function is developed. A procedure that allows the exclusion of domains of the (ø, ) space based on the analysis of experimentally determined native protein structures is presented. The reduced disjoint sub-domains are appropriately combined thus defining the starting regions for the search. The proposed approach provides valuable information on (i) the global minimum potential energy conformation, (ii) upper and lower bounds of the global minimum energy structure and (iii) low energy conformers close to the global minimum one. The proposed approach is illustrated with Ac-Ala4-Pro-NHMe, Met-enkephalin, Leu-enkephalin, and Decaglycine.     

Molecular conformation of n-alkanes using terrain/funneling methods

Understanding molecular conformation is a first step in understanding the waxing (or formation of crystals) of petroleum fuels. In this work, we study the molecular conformation of typical fuel oils modeled as pure n-alkanes. A multi-scale global optimization methodology based on terrain methods and funneling algorithms is used to find minimum energy molecular conformations of united atom n-alkane models for diesel, home heating, and residual fuel oils. The terrain method is used to gather average gradient and average Hessian matrix information at the small length scale while funneling is used to generate conformational changes at the large length scale that drive iterates to a global minimum on the potential energy surface. In addition, the funneling method uses a mixture of average and point-wise derivative information to produce a monotonically decreasing sequence of objective function values and to avoid getting trapped at local minima on the potential energy surface. Computational results clearly show that the calculated united atom molecular conformations are comprised of zigzag structure with considerable wrapping at the ends of the molecule and that planar zigzag conformations usually correspond to saddle points. Furthermore, the numerical results clearly demonstrate that our terrain/funneling approach is robust and fast.     

Iterative Convex Quadratic Approximation for Global Optimization in Protein Docking

An algorithm for finding an approximate global minimum of a funnel shaped function with many local minima is described. It is applied to compute the minimum energy docking position of a ligand with respect to a protein molecule. The method is based on the iterative use of a convex, general quadratic approximation that underestimates a set of local minima, where the error in the approximation is minimized in the L¹ norm. The quadratic approximation is used to generate a reduced domain, which is assumed to contain the global minimum of the funnel shaped function. Additional local minima are computed in this reduced domain, and an improved approximation is computed. This process is iterated until a convergence tolerance is satisfied. The algorithm has been applied to find the global minimum of the energy function generated by the Docking Mesh Evaluator program. Results for three different protein docking examples are presented. Each of these energy functions has thousands of local minima. Convergence of the algorithm to an approximate global minimum is shown for all three examples.     

A Function to Test Methods Applied to Global Minimization of Potential Energy of Molecules

In this paper we develop a function with a functional form similar to general potential energy functions and whose global minimum is known. We prove that the number of local minimizers of this function increases exponentially with the size of the problem, which characterizes the principal difficulty in minimizing molecular potential energy functions. In order to guarantee the global optimality and to show the difficulty in obtaining the global minimum of this function, we propose the utilization of a deterministic algorithm. The algorithm is based on a branch and bound scheme that uses interval analysis techniques to calculate the lower bounds. Computational results for problems with up to 25 degrees of freedom are presented.     

A Hybrid grey wolf optimizer and genetic algorithm for minimizing potential energy function

In this paper, we propose a new hybrid algorithm between the grey wolf optimizer algorithm and the genetic algorithm in order to minimize a simplified model of the energy function of the molecule. We call the proposed algorithm by Hybrid Grey Wolf Optimizer and Genetic Algorithm (HGWOGA). We employ three procedures in the HGWOGA. In the first procedure, we apply the grey wolf optimizer algorithm to balance between the exploration and the exploitation process in the proposed algorithm. In the second procedure, we utilize the dimensionality reduction and the population partitioning processes by dividing the population into sub-populations and using the arithmetical crossover operator in each sub-population in order to increase the diversity of the search in the algorithm. In the last procedure, we apply the genetic mutation operator in the whole population in order to refrain from the premature convergence and trapping in local minima. We implement the proposed algorithm with various molecule size with up to 200 dimensions and compare the proposed algorithm with 8 benchmark algorithms in order to validate its efficiency for solving molecular potential energy function. The numerical experiment results show that the proposed algorithm is a promising, competent, and capable of finding the global minimum or near global minimum of the molecular energy function faster than the other comparative algorithms.     

Global Optimization on Funneling Landscapes

Molecular conformation problems arising in computational chemistry require the global minimization of a non-convex potential energy function representing the interactions of, for example, the component atoms in a molecular system. Typically the number of local minima on the potential energy surface grows exponentially with system size, and often becomes enormous even for relatively modestly sized systems. Thus the simple multistart strategy of randomly sampling local minima becomes impractical. However, for many molecular conformation potential energy surfaces the local minima can be organized by a simple adjacency relation into a single or at most a small number of funnels. A distinguished local minimum lies at the bottom of each funnel and a monotonically descending sequence of adjacent local minima connects every local minimum in the funnel with the funnel bottom. Thus the global minimum can be found among the comparatively small number of funnel bottoms, and a multistart strategy based on sampling funnel bottoms becomes viable. In this paper we present such an algorithm of the basin-hopping type and apply it to the Lennard–Jones cluster problem, an intensely studied molecular conformation problem which has become a benchmark for global optimization algorithms. Results of numerical experiments are presented which confirm both the multifunneling character of the Lennard–Jones potential surface as well as the efficiency of the algorithm. The algorithm has found all of the current putative global minima in the literature up to 110 atoms, as well as discovered a new global minimum for the 98-atom cluster of a novel geometrical class.     

Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

蛋白质空间结构预测的一种优化模型及算法

用理论方法预测蛋白质结构有两个难点,第一是要有一个合理的势函数,第二是要有一个有效的寻优方法找到势函数的全局极小点,本文采用联合残基力场建立了蛋白质空间结构预测模型,然后用我们给出的一种改进模拟退火算法搜索势函数的全局极小点,对脑啡肽的空间结构进行了预测和分析。     

Docking of Atomic Clusters Through Nonlinear Optimization

The problem of molecular docking is defined as that of finding a minimum energy configuration of a pair of molecular structures (usually consisting of proteins, DNA or RNA fragments). It is often assumed that the two interacting structures can be considered as rigid bodies and that it is of interest to researchers to develop methods which enable to discover the potential binding sites. Many different models have been proposed in the literature for the definition of the potential energy between two molecular structures, most of which contain at least a term (known as Van Der Waals interaction) which accounts for pairwise attraction between atoms, a repulsion term and a term which takes into account electrostatic forces (Coulomb interaction). Some well known models, and in particular those used in rigid docking, are based on the assumption that the only terms which are relevant in the process of docking are pairwise interactions between atoms belonging to the two different parts of the structure. In this paper the problem of finding the lowest energy configuration of a pair of biomolecular structures, considered as rigid bodies, is defined and formulated as a global optimization problem. In terms of dimension of the search space this formulation is not 'high-dimensional', as there are only six degrees of freedom: 3 translation and 3 rotation parameters. However the energy surface of the docking problem is characterized by a huge number of local minima; moreover each function evaluation is quite expensive (interesting structures usually possess a few thousand atoms each). So there is a strong need both of local and of global optimization procedures. In this paper a local optimization technique, based upon standard non linear programming software and a penalized objective function, is introduced and its potential usefulness in the context of global optimization is outlined.     

Minimum Inter-Particle Distance at Global Minimizers of Lennard-Jones Clusters

In computer simulations of molecular conformation and protein folding, a significant part of computing time is spent in the evaluation of potential energy functions and force fields. Therefore many algorithms for fast evaluation of potential energy functions and force fields are proposed in the literature. However, most of these algorithms assume that the particles are uniformly distributed in order to guarantee good performance. In this paper, we prove that the minimum inter-particle distance at any global minimizer of Lennard-Jones clusters is bounded away from zero by a positive constant which is independent of the number of particles. As a by-product, we also prove that the global minimum of an n particle Lennard-Jones cluster is bounded between two linear functions. Our first result is useful in the design of fast algorithms for potential function and force field evaluation. Our second result can be used to decide how good a local minimizer is.     

A multi-start global minimization algorithm with dynamic search trajectories

A new multi-start algorithm for global unconstrained minimization is presented in which the search trajectories are derived from the equation of motion of a particle in a conservative force field, where the function to be minimized represents the potential energy. The trajectories are modified to increase the probability of convergence to a comparatively low local minimum, thus increasing the region of convergence of the global minimum. A Bayesian argument is adopted by which, under mild assumptions, the confidence level that the global minimum has been attained may be computed. When applied to standard and other test functions, the algorithm never failed to yield the global minimum.The first author wishes to thank Prof. M. Levitt of the Department of Chemical Physics of the Weizmann Institute of Science for suggesting this line of research and also Drs. T. B. Scheffler and E. A. Evangelidis for fruitful discussions regarding Conjecture 2.1. He also acknowledges the exchange agreement award received from the National Council for Research and Development in Israel and the Council for Scientific and Industrial Research in South Africa, which made possible the visit to the Weizmann Institute where this work was initiated.     

Global optimization for molecular conformation problems

A primal-relaxed dual global optimization algorithm is presented along with an extensive review for finding the global minimum energy configurations of microclusters composed by particles interacting with any type of two-body central forces. First, the original nonconvex expression for the total potential energy is transformed to the difference of two convex functions (DC transformation) via an eigenvalue analysis performed for each pair potential that constitutes the total potential energy function. Then, a decomposition strategy based on the GOP algorithm [1–4] is designed to provide tight upper and lower bounds on the global minimum through the solutions of a sequence of relaxed dual subproblems. A number of theoretical results are included which expedite the computational effort by exploiting the special mathematical structure of the problem. The proposed approach attains-convergence to the global minimum in a finite number of iterations. Based on this procedure global optimum solutions are generated for small Lennard-Jones and Morse (a=3) microclustersn7. For larger clusters (8N24 for Lennard-Jones and 8N30 for Morse), tight lower and upper bounds on the global solution are provided which serve as excellent initial points for local optimization approaches.     

Multi-funnel optimization using Gaussian underestimation

In several applications, underestimation of functions has proven to be a helpful tool for global optimization. In protein–ligand docking problems as well as in protein structure prediction, single convex quadratic underestimators have been used to approximate the location of the global minimum point. While this approach has been successful for basin-shaped functions, it is not suitable for energy functions with more than one distinct local minimum with a large magnitude. Such functions may contain several basin-shaped components and, thus, cannot be underfitted by a single convex underestimator. In this paper, we propose using an underestimator composed of several negative Gaussian functions. Such an underestimator can be computed by solving a nonlinear programming problem, which minimizes the error between the data points and the underestimator in the L ¹ norm. Numerical results for simulated and actual docking energy functions are presented.     

A Smoothing Method of Global Optimization that Preserves Global Minima

A new smoothing method of global optimization is proposed in the present paper, which prevents shifting of global minima. In this method, smoothed functions are solutions of a heat diffusion equation with external heat source. The source helps to control the diffusion such that a global minimum of the smoothed function is again a global minimum of the cost function. This property, and the existence and uniqueness of the solution are proved using results in theory of viscosity solutions. Moreover, we devise an iterative equation by which smoothed functions can be obtained analytically for a class of cost functions. The effectiveness and potential of our method are then demonstrated with some experimental results.     

Unifying local–global type properties in vector optimization

It is well-known that all local minimum points of a semistrictly quasiconvex real-valued function are global minimum points. Also, any local maximum point of an explicitly quasiconvex real-valued function is a global minimum point, provided that it belongs to the intrinsic core of the function’s domain. The aim of this paper is to show that these “local min–global min” and “local max–global min” type properties can be extended and unified by a single general local–global extremality principle for certain generalized convex vector-valued functions with respect to two proper subsets of the outcome space. For particular choices of these two sets, we recover and refine several local–global properties known in the literature, concerning unified vector optimization (where optimality is defined with respect to an arbitrary set, not necessarily a convex cone) and, in particular, classical vector/multicriteria optimization.     

A Note on the Griewank Test Function

In this paper we analyze a widely employed test function for global optimization, the Griewank function. While this function has an exponentially increasing number of local minima as its dimension increases, it turns out that a simple Multistart algorithm is able to detect its global minimum more and more easily as the dimension increases. A justification of this counterintuitive behavior is given. Some modifications of the Griewank function are also proposed in order to make it challenging also for large dimensions.     

Finite element calculations for systems with multiple Coulomb centers

The presence of multiple Coulomb centers in molecules or solids poses a challenge when solving the effective Schrödinger equation, required as a crucial ingredient in density functional or Hartree–Fock calculations. This is primarily because Kato’s cusp condition needs to be satisfied close to each nucleus and the matrix elements of the Coulomb potential at the nuclei are rather difficult to evaluate when using global basis functions. A novel method for dealing with these challenges is introduced, rewriting the wavefunction as a product of a function satisfying the nuclear cusp conditions and a smooth function, resulting in a transformed variational principle and a regularized potential. Results of three-dimensional finite element calculations based on this ansatz for the ground state of the molecule H₂⁺ in the Born–Oppenheimer approximation are presented, which were obtained using custom written Python/Fortran code.