Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins

The protein structure prediction problem is a classical NP hard problem in bioinformatics. The lack of an effective global optimization method is the key obstacle in solving this problem. As one of the global optimization algorithms, tabu search (TS) algorithm has been successfully applied in many optimization problems. We define the new neighborhood conformation, tabu object and acceptance criteria of current conformation based on the original TS algorithm and put forward an improved TS algorithm. By integrating the heuristic initialization mechanism, the heuristic conformation updating mechanism, and the gradient method into the improved TS algorithm, a heuristic-based tabu search (HTS) algorithm is presented for predicting the two-dimensional (2D) protein folding structure in AB off-lattice model which consists of hydrophobic (A) and hydrophilic (B) monomers. The tabu search minimization leads to the basins of local minima, near which a local search mechanism is then proposed to further search for lower-energy conformations. To test the performance of the proposed algorithm, experiments are performed on four Fibonacci sequences and two real protein sequences. The experimental results show that the proposed algorithm has found the lowest-energy conformations so far for three shorter Fibonacci sequences and renewed the results for the longest one, as well as two real protein sequences, demonstrating that the HTS algorithm is quite promising in finding the ground states for AB off-lattice model proteins.     

Population-based local search for protein folding simulation in the MJ energy model and cubic lattices

We present experimental results on benchmark problems in 3D cubic lattice structures with the Miyazawa–Jernigan energy function for two local search procedures that utilise the pull-move set: (i) population-based local search (PLS) that traverses the energy landscape with greedy steps towards (potential) local minima followed by upward steps up to a certain level of the objective function; (ii) simulated annealing with a logarithmic cooling schedule (LSA). The parameter settings for PLS are derived from short LSA-runs executed in pre-processing and the procedure utilises tabu lists generated for each member of the population. In terms of the total number of energy function evaluations both methods perform equally well, however, PLS has the potential of being parallelised with an expected speed-up in the region of the population size. Furthermore, both methods require a significant smaller number of function evaluations when compared to Monte Carlo simulations with kink-jump moves.     

Semiglobal simplex optimization and its application to determining the preferred solvation sites of proteins

The classical simplex method is extended into the Semiglobal Simplex (SGS) algorithm. Although SGS does not guarantee finding the global minimum, it affords a much more thorough exploration of the local minima than any traditional minimization method. The basic idea of SGS is to perform a local minimization in each step of the simplex algorithm, and thus, similarly to the Convex Global Underestimator (CGU) method, the search is carried out on a surface spanned by local minima. The SGS and CGU methods are compared by minimizing a set of test functions of increasing complexity, each with a known global minimum and many local minima. Although CGU delivers substantially better success rates in simple problems, the two methods become comparable as the complexity of the problems increases. Because SGS is generally faster than CGU, it is the method of choice for solving optimization problems in which function evaluation is computationally inexpensive and the search region is large. The extreme simplicity of the method is also a factor. The SGS method is applied here to the problem of finding the most preferred (i.e., minimum free energy) solvation sites on a streptavidin monomer. It is shown that the SGS method locates the same lowest free energy positions as an exhaustive multistart Simplex search of the protein surface, with less than one-tenth the number of minizations. The combination of the two methods, i.e.. multistart simplex and SGS, provides a reliable procedure for predicting all potential solvation sites of a protein.     

Hybrid particle swarm optimization and tabu search approach for selecting genes for tumor classification using gene expression data

Gene expression data are characterized by thousands even tens of thousands of measured genes on only a few tissue samples. This can lead either to possible overfitting and dimensional curse or even to a complete failure in analysis of microarray data. Gene selection is an important component for gene expression-based tumor classification systems. In this paper, we develop a hybrid particle swarm optimization (PSO) and tabu search (HPSOTS) approach for gene selection for tumor classification. The incorporation of tabu search (TS) as a local improvement procedure enables the algorithm HPSOTS to overleap local optima and show satisfactory performance. The proposed approach is applied to three different microarray data sets. Moreover, we compare the performance of HPSOTS on these datasets to that of stepwise selection, the pure TS and PSO algorithm. It has been demonstrated that the HPSOTS is a useful tool for gene selection and mining high dimension data.     

Protein structure prediction using a combination of sequence homology and global energy minimization I. Global energy minimization of surface loops

A procedure has been developed for global energy minimization of surface loops of proteins in the presence of a fixed core. The ECEPP potential function has been modified to allow more accurate representations of hydrogen bond interactions and intrinsic torsional energies. A computationally efficient representation of hydration free energy has been introduced. A local minimization procedure has been developed that uses a cutoff distance, minimization with respect to subsets of degrees of freedom, analytical second derivatives, and distance constraints between rigid segments to achieve efficiency in applications to surface loops. Efficient procedures have been developed for deforming segments of the initial backbone structure and for removing overlaps. Global energy minimization of a surface loop is accomplished by generating a sequence (or a trajectory) of local minima, the component steps of which are generated by searching collections of local minima obtained by deforming seven-residue segments of the surface loop. The search at each component step consists of the following calculations: (1) A large collection of backbone structures is generated by deforming a seven-residue segment of the initial backbone structure. (2) A collection of low-energy backbone structures is generated by applying local energy minimization to the resulting collection of backbone structures (interactions involving side chains that will be searched in this component step are not included in the energy). (3) One low-energy side-chain structure is generated for each of the resulting low-energy backbone structures. (4) A collection of low-energy local minima is generated by applying local energy minimization to the resulting collection of structures. (5) The local minimum with the lowest energy is retained as the next point of the trajectory. Applications of our global search procedure to surface segments of bovine pancreatic trypsin inhibitor (BPTI) and bovine trypsin suggest that component-step searches are reasonably complete. The computational efficiency of component-step searches is such that trajectories consisting of about 10 component steps are feasible using an FPS-5200 array processor. Our procedure for global energy minimization of surface loops is being used to identify and correct problems with the potential function and to calculate protein structure using a combination of sequence homology and global energy minimization.     

Simulated annealing to locate various stationary points in semiempirical methods

In this work, an algorithm was developed to study the potential energy surfaces in the coordinate spaces of molecules by a nonlocal way, in contrast to classic energy minimizers as the BFGS or the DFP method. This algorithm, based on the specificities of semiempirical methods, mixes simulated annealing and local searches to reduce computation costs. By this technique, the global energy minimum can be localized. Moreover, local minima that are close in energy to the global minimum are also obtained. If the search is not only for minima but for all stationary points (minima, saddle points…), then the energy is replaced by the gradient norm, which reaches its minimum values at stationary points. The annealing process is stopped before having accurately reached the global minimum and generates a list of geometries whose energies (respectively, whose gradients) are optimized by local minimizers. This list of geometries is shortened from the nearly equivalent geometries by a dynamic single-clustering analysis. The energy/gradient local minimizers act on the clustered list to produce a set of minima/stationary points. A targeted search of these points and reduction of the costs are reached by the way of several penalty functions. They eliminate—without energy calculation—most of the points generated by random walks on the potential energy surface. These penalty functions (on the total moment of inertia or on interatomic distances) are specific to the class of problem studied. They account for the nonrupture of either specific chemical bonds or rings in cyclic molecules, they assure that molecular systems are kept bonded, and they avoid the collapsing of atoms. © 1992 John Wiley & Sons, Inc.     

On the investigation of the low-energy conformational space of molecules

A new perspective on traditional energy minimization problems is provided by a connection between statistical thermodynamics and combinatorial optimization (finding the minimum of a function depending on many variables). The joint use of a new method for uncovering the global minimum of intramolecular potential energy functions, based on following the asymptotic behavior of a system of stochastic differential equations, and an iterative-improvement technique, whereby a search for relative minima is made by carrying out local quasi-Newton minimizations starting from many distinct points of the energy hypersurface, proved most effective for investigating the low-energy conformational space of molecules.     

Calculating all local minima on liquidus surfaces using the FactSage software and databases and the Mesh Adaptive Direct Search algorithm

It is often of interest, for a multicomponent system, to identify the low melting compositions at which local minima of the liquidus surface occur. The experimental determination of these minima can be very time-consuming. An alternative is to employ the CALPHAD approach using evaluated thermodynamic databases containing optimized model parameters giving the thermodynamic properties of all phases as functions of composition and temperature. Liquidus temperatures are then calculated by Gibbs free energy minimization algorithms which access the databases. Several such large databases for many multicomponent systems have been developed over the last 40 years, and calculated liquidus temperatures are generally quite accurate. In principle, one could then search for local liquidus minima by simply calculating liquidus temperatures over a compositional grid. In practice, such an approach is prohibitively time-consuming for all but the simplest systems since the required number of grid points is extremely large. In the present article, the FactSage database computing system is coupled with the powerful Mesh Adaptive Direct Search (MADS) algorithm in order to search for and calculate automatically all liquidus minima in a multicomponent system. Sample calculations for a 4-component oxide system, a 7-component chloride system, and a 9-component ferrous alloy system are presented. It is shown that the algorithm is robust and rapid.     

A parallel tabu search for conformational energy optimization of oligopeptides

We have developed and implemented a tabu search heuristic (TS) to determine the best energy minimum for oligopeptides. Our test molecule was Met‐enkephalin, a pentapetide that over the years has been used as a validation model for many global optimizers. The test potential energy function was ECEPP/3. Our tabu search implementation is based on assigning integer values to the variables to be optimized, and in facilitating the diversification and intensification of the search. The final output from the TS is treated with a local optimizer, and our best result competes both in quality and CPU time with those reported in the literature. The results indicate that TS is an efficient algorithm for conformational searches. We present a parallel TS version along with experimental results that show that this algorithm allows significant increases in speed. © 2000 John Wiley & Sons, Inc. J Comput Chem 21: 147–156, 2000     

Global exploration of the energy landscape of solids on the ab initio level

Predicting which crystalline modifications can be present in a chemical system requires the global exploration of its energy landscape. Due to the large computational effort involved, in the past this search for sufficiently stable minima has been performed employing a variety of empirical potentials and cost functions followed by a local optimization on the ab initio level. However, this entails the risk of overlooking important modifications that are not modeled accurately using empirical potentials. In order to overcome this critical limitation, we develop an approach to employ ab initio energy functions during the global optimization phase of the structure prediction. As an example, we perform a global exploration of the landscape of LiF on the ab initio level and show that the relevant crystalline modifications are found during the search.     

A comparison of heuristic search algorithms for molecular docking

This paper describes the implementation and comparison of four heuristic search algorithms (genetic algorithm, evolutionary programming, simulated annealing and tabu search) and a random search procedure for flexible molecular docking. To our knowledge, this is the first application of the tabu search algorithm in this area. The algorithms are compared using a recently described fast molecular recognition potential function and a diverse set of five protein–ligand systems. Statistical analysis of the results indicates that overall the genetic algorithm performs best in terms of the median energy of the solutions located. However, tabu search shows a better performance in terms of locating solutions close to the crystallographic ligand conformation. These results suggest that a hybrid search algorithm may give superior results to any of the algorithms alone.     

Efficiency of tabu‐search‐based conformational search algorithms

Efficient conformational search or sampling approaches play an integral role in molecular modeling, leading to a strong demand for even faster and more reliable conformer search algorithms. This article compares the efficiency of a molecular dynamics method, a simulated annealing method, and the basin hopping (BH) approach (which are widely used in this field) with a previously suggested tabu‐search‐based approach called gradient only tabu search (GOTS). The study emphasizes the success of the GOTS procedure and, more importantly, shows that an approach which combines BH and GOTS outperforms the single methods in efficiency and speed. We also show that ring structures built by a hydrogen bond are useful as starting points for conformational search investigations of peptides and organic ligands with biological activities, especially in structures that contain multiple rings. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011     

Structure and dynamics of the aniline-argon complex as derived from its potential energy surface

The structure and dynamics of the van der Waals (vdW) complex of aniline (An) with argon (Ar) are studied using ab initio methods. The inversion potential of the aniline-argon (AnAr) complex perturbed by the weak vdW interaction is calculated taking into account subtle corrections from the zero-point energy of the vdW modes and from the frequency shifts of the An normal modes modified by the complexation. The intermolecular potential energy surface (PES) of the AnAr complex is determined by performing a large-scale computation of the interaction energy and the fitting of the analytical many-body expansion to the set of single-point interaction energies. The PES determined shows two deep local minima corresponding to the anti and syn AnAr conformers. The difference in the energies of these two minima is only 15 cm-1, but it is sufficient to localize the inversion wave functions and to form the two conformers. In the conformer anti (syn) of lower (higher) energy, Ar is bound to the An ring opposite (adjacent) the amino-hydrogens. In the additional local minima higher in energy, Ar approaches the aniline ring between the C-H bonds near its plane. An additional local minimum is located opposite of nitrogen between the two N-H bonds. The high-energy minima are, however, too flat to form stable conformers. The perturbation of the interaction of Ar with the phenyl ring by the NH2 group is described by the vdW hole, which is responsible for unusually strong intermode mixing in the excited intermolecular vibrational states. The analysis of these states calculated for the ground (S0) as well as the first excited electronic state (S1) resolves difficulties faced earlier with the assignment of the observed vibronic bands of AnAr.     

Finding pathways between distant local minima

We report a new algorithm for constructing pathways between local minima that involve a large number of intervening transition states on the potential energy surface. A significant improvement in efficiency has been achieved by changing the strategy for choosing successive pairs of local minima that serve as endpoints for the next search. We employ Dijkstra's algorithm [E. W. Dijkstra, Numer. Math. 1, 269 (1959)] to identify the "shortest" path corresponding to missing connections within an evolving database of local minima and the transition states that connect them. The metric employed to determine the shortest missing connection is a function of the minimized Euclidean distance. We present applications to the formation of buckminsterfullerene and to the folding of various biomolecules: the B1 domain of protein G, tryptophan zippers, and the villin headpiece subdomain. The corresponding pathways contain up to 163 transition states and will be used in future discrete path sampling calculations.     

Finite-state and reduced-parameter representations of protein backbone conformations

This article studies the representation of protein backbone conformations using a finite number of values for the backbone dihedral angles. We develop a combinatorial search algorithm that guarantees finding the global minima of functions over the configuration space of discrete protein conformations, and use this procedure to fit finite-state models to the backbones of globular proteins. It is demonstrated that a finite-state representation with a reasonably small number of states yields either a small root-mean-square error or a small dihedral angle deviation from the native structure, but not both at the same time. The problem can be resolved by introducing limited local optimization in each step of the combinatorial search. In addition, it is shown that acceptable approximation is achieved using a single dihedral angle as an independent variable in local optimization. Results for 11 proteins demonstrate the advantages and shortcomings of both the finite-state and reduced-parameter approximations of protein backbone conformations. © 1994 by John Wiley & Sons, Inc.     

A strategy to find minimal energy nanocluster structures

An unbiased strategy to search for the global and local minimal energy structures of free standing nanoclusters is presented. Our objectives are twofold: to find a diverse set of low lying local minima, as well as the global minimum. To do so, we use massively the fast inertial relaxation engine algorithm as an efficient local minimizer. This procedure turns out to be quite efficient to reach the global minimum, and also most of the local minima. We test the method with the Lennard–Jones (LJ) potential, for which an abundant literature does exist, and obtain novel results, which include a new local minimum for LJ₁₃, 10 new local minima for LJ₁₄, and thousands of new local minima for . Insights on how to choose the initial configurations, analyzing the effectiveness of the method in reaching low‐energy structures, including the global minimum, are developed as a function of the number of atoms of the cluster. Also, a novel characterization of the potential energy surface, analyzing properties of the local minima basins, is provided. The procedure constitutes a promising tool to generate a diverse set of cluster conformations, both two‐ and three‐dimensional, that can be used as an input for refinement by means of ab initio methods. © 2013 Wiley Periodicals, Inc.     

Searching and optimizing structure ensembles for complex flexible sugars

NMR restrictions are suitable to specify the geometry of a molecule when a single well-defined global free energy minimum exists that is significantly lower than other local minima. Carbohydrates are quite flexible, and therefore, NMR observables do not always correlate with a single conformer but instead with an ensemble of low free energy conformers that can be accessed by thermal fluctuations. In this communication, we describe a novel procedure to identify and weight the contribution to the ensemble of local minima conformers based on comparison to residual dipolar couplings (RDCs) or other NMR observables, such as scalar couplings. A genetic algorithm is implemented to globally minimize the R factor comparing calculated RDCs to experiment. This is done by optimizing the weights of different conformers derived from the exhaustive local minima conformational search program, fast sugar structure prediction software (FSPS). We apply this framework to six human milk sugars, LND-1, LNF-1, LNF-2, LNF-3, LNnT, and LNT, and are able to determine corresponding population weights for the ensemble of conformers. Interestingly, our results indicate that in all cases the RDCs can be well represented by only a few most important conformers. This confirms that several, but not all of the glycosidic linkages in histo-blood group "epitopes" are quite rigid.     

More on the melting of Lennard-Jones clusters

The melting of 13-atom clusters interacting via Lennard-Jones potentials has been revisited using molecular dynamics coupled to steepest descent quenches. A procedure was devised to account for the fraction of times the global and local minima of the potential energy surface are accessed during a long trajectory. This quantity presents a sigmoid shape. A phenomenological model of melting is given in terms of a correlated walk that maps the short time excursions among the global and local minima in configuration space. Comparison between the simulation results and the theoretical model shows that the melting transition is well described in terms of the temperature changes of the fraction of high energy minima accessed during the cluster trajectory. Cooperativity is clear from the S shape of this quantity, i.e., the access to a local minimum favours the access to other local minima.     

Improving the Accuracy of Small-Molecule Crystal Structures Solved from Powder X-Ray Diffraction Data by Using External Sources

Structural analysis using powder X-ray diffraction data has overcome many obstacles and nowadays is readily applicable for structural analysis of all types of compounds and materials. Being less straightforward than single crystal diffraction, it requires significant users’ input and consequently, implementation of standardized tools to assess the accuracy of crystal structures. This article discusses potential errors in crystal structure solution and refinement of small-molecule structures obtained from PXRD data. Moreover, it proposes how accuracy of these structures can be improved by using high-quality PXRD data, complementary external analytical techniques, knowledge stored in crystal structure databases, as well as an approach to search the parameter space to avoid local minima in testing different sets of geometry restraints.     

A powerful truncated Newton method for potential energy minimization

With advances in computer architecture and software, Newton methods are becoming not only feasible for large-scale nonlinear optimization problems, but also reliable, fast and efficient. Truncated Newton methods, in particular, are emerging as a versatile subclass. In this article we present a truncated Newton algorithm specifically developed for potential energy minimization. The method is globally convergent with local quadratic convergence. Its key ingredients are: (1) approximation of the Newton direction far away from local minima, (2) solution of the Newton equation iteratively by the linear Conjugate Gradient method, and (3) preconditioning of the Newton equation by the analytic second-derivative components of the “local” chemical interactions: bond length, bond angle and torsional potentials. Relaxation of the required accuracy of the Newton search direction diverts the minimization search away from regions where the function is nonconvex and towards physically interesting regions. The preconditioning strategy significantly accelerates the iterative solution for the Newton search direction, and therefore reduces the computation time for each iteration. With algorithmic variations, the truncated Newton method can be formulated so that storage and computational requirements are comparable to those of the nonlinear Conjugate Gradient method. As the convergence rate of nonlinear Conjugate Gradient methods is linear and performance less predictable, the application of the truncated Newton code to potential energy functions is promising.