A consensus line search algorithm for molecular potential energy functions

Force field based energy minimization of molecular structures is a central task in computational chemistry and biology. Solving this problem usually requires efficient local minimization techniques, i.e., iterative two‐step methods that search first for a descent direction and then try to estimate the step width. The second step, the so called line search, typically uses polynomial interpolation schemes to estimate the next trial step. However, dependent on local properties of the objective function alternative schemes may be more appropriate especially if the objective function shows singularities or exponential behavior. As the choice of the best interpolation scheme cannot be made a priori, we propose a new consensus line search approach that performs several different interpolation schemes at each step and then decides which one is the most reliable at the current position. Although a naive consensus approach would lead to severe performance impacts, our method does not require additional evaluations of the energy function, imposing only negligible computational overhead. Additionally, our method can be easily adapted to the local behavior of other objective functions by incorporating suitable interpolation schemes or omitting non‐fitting schemes. The performance of our consensus line search approach has been evaluated and compared to established standard line search algorithms by minimizing the structures of a large set of molecules using different force fields. The proposed algorithm shows better performance in almost all test cases, i.e., it reduces the number of iterations and function and gradient evaluations, leading to significantly reduced run times. © 2008 Wiley Periodicals, Inc. J Comput Chem, 2009     

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     

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.     

Conformational analysis of methylphenidate: comparison of molecular orbital and molecular mechanics methods

Summary Methylphenidate (MP) binds to the cocaine binding site on the dopamine transporter and inhibits reuptake of dopamine, but does not appear to have the same abuse potential as cocaine. This study, part of a comprehensive effort to identify a drug treatment for cocaine abuse, investigates the effect of choice of calculation technique and of solvent model on the conformational potential energy surface (PES) of MP and a rigid methylphenidate (RMP) analogue which exhibits the same dopamine transporter binding affinity as MP. Conformational analysis was carried out by the AM1 and AM1/SM5.4 semiempirical molecular orbital methods, a molecular mechanics method (Tripos force field with the dielectric set equal to that of vacuum or water) and the HF/6-31G* molecular orbital method in vacuum phase. Although all three methods differ somewhat in the local details of the PES, the general trends are the same for neutral and protonated MP. In vacuum phase, protonation has a distinctive effect in decreasing the regions of space available to the local conformational minima. Solvent has little effect on the PES of the neutral molecule and tends to stabilize the protonated species. The random search (RS) conformational analysis technique using the Tripos force field was found to be capable of locating the minima found by the molecular orbital methods using systematic grid search. This suggests that the RS/Tripos force field/vacuum phase protocol is a reasonable choice for locating the local minima of MP. However, the Tripos force field gave significantly larger phenyl ring rotational barriers than the molecular orbital methods for MP and RMP. For both the neutral and protonated cases, all three methods found the phenyl ring rotational barriers for the RMP conformers/invertamers (denoted as cte, tte, and cta) to be: cte, tte> MP > cta. Solvation has negligible effect on the phenyl ring rotational barrier of RMP. The B3LYP/6-31G* density functional method was used to calculate the phenyl ring rotational barrier for neutral MP and gave results very similar to those of the HF/6-31G* method.     

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.     

Assessing search strategies for flexible docking

We assess the efficiency of molecular dynamics (MD), Monte Carlo (MC), and genetic algorithms (GA) for docking five representative ligand–receptor complexes. All three algorithms employ a modified CHARMM-based energy function. The algorithms are also compared with an established docking algorithm, AutoDock. The receptors are kept rigid while flexibility of ligands is permitted. To test the efficiency of the algorithms, two search spaces are used: an 11-Å-radius sphere and a 2.5-Å-radius sphere, both centered on the active site. We find MD is most efficient in the case of the large search space, and GA outperforms the other methods in the small search space. We also find that MD provides structures that are, on average, lower in energy and closer to the crystallographic conformation. The GA obtains good solutions over the course of the fewest energy evaluations. However, due to the nature of the nonbonded interaction calculations, the GA requires the longest time for a single energy evaluation, which results in a decreased efficiency. The GA and MC search algorithms are implemented in the CHARMM macromolecular package. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1623–1631, 1998     

Microscopic basis for kinetic gating in cytochrome c oxidase: insights from QM/MM analysis

Understanding the mechanism of vectorial proton pumping in biomolecules requires establishing the microscopic basis for the regulation of both thermodynamic and kinetic features of the relevant proton transfer steps. For the proton pump cytochrome c oxidase, while the regulation of thermodynamic driving force for key proton transfers has been discussed in great detail, the microscopic basis for the control of proton transfer kinetics has been poorly understood. Here we carry out extensive QM/MM free energy simulations to probe the kinetics of relevant proton transfer steps and analyze the effects of local structure and hydration level. We show that protonation of the proton loading site (PLS, taken to be a propionate of heme a₃) requires a concerted process in which a key glutamic acid (Glu286H) delivers the proton to the PLS while being reprotonated by an excess proton coming from the D-channel. The concerted nature of the mechanism is a crucial feature that enables the loading of the PLS before the cavity containing Glu286 is better hydrated to lower its pK _a to experimentally measured range; the charged rather than dipolar nature of the process also ensures a tight coupling with heme a reduction, as emphasized by Siegbahn and Blomberg. In addition, we find that rotational flexibility of the PLS allows its protonation before that of the binuclear center (the site where oxygen gets reduced to water). Together with our recent study (P. Goyal, et al., Proc. Natl. Acad. Sci. U. S. A., 2013, 110, 18886–18891) that focused on the modulation of Glu286 pK _a, the current work suggests a mechanism that builds in a natural sequence for the protonation of the PLS prior to that of the binuclear center. This provides microscopic support to the kinetic constraints revealed by kinetic network analysis as essential elements that ensure an efficient vectorial proton transport in cytochrome c oxidase.     

A High-Performance and Flexible Chemical Structure & Data Search Engine Built on CouchDB & ElasticSearch

Computer-assisted chemical structure searching plays a critical role for efficient structure screening in cheminformatics. We designed a high-performance chemical structure & data search engine called DCAIKU, built on CouchDB and ElasticSearch engines. DCAIKU converts the chemical structure similarity search problem into a general text search problem to utilize off-the-shelf full-text search engines. DCAIKU also supports flexible document structures and heterogeneous datasets with the help of schema-less document database. Our evaluations show that DCAIKU can handle both keyword search and structural search against millions of records with both high accuracy and low latency. We expect that DCAIKU will lay the foundation towards large-scale and cost-effective structural search in materials science and chemistry research.     

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.     

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.     

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.     

SODOCK: swarm optimization for highly flexible protein-ligand docking

Protein-ligand docking can be formulated as a parameter optimization problem associated with an accurate scoring function, which aims to identify the translation, orientation, and conformation of a docked ligand with the lowest energy. The parameter optimization problem for highly flexible ligands with many rotatable bonds is more difficult than that for less flexible ligands using genetic algorithm (GA)-based approaches, due to the large numbers of parameters and high correlations among these parameters. This investigation presents a novel optimization algorithm SODOCK based on particle swarm optimization (PSO) for solving flexible protein-ligand docking problems. To improve efficiency and robustness of PSO, an efficient local search strategy is incorporated into SODOCK. The implementation of SODOCK adopts the environment and energy function of AutoDock 3.05. Computer simulation results reveal that SODOCK is superior to the Lamarckian genetic algorithm (LGA) of AutoDock, in terms of convergence performance, robustness, and obtained energy, especially for highly flexible ligands. The results also reveal that PSO is more suitable than the conventional GA in dealing with flexible docking problems with high correlations among parameters. This investigation also compared SODOCK with four state-of-the-art docking methods, namely GOLD 1.2, DOCK 4.0, FlexX 1.8, and LGA of AutoDock 3.05. SODOCK obtained the smallest RMSD in 19 of 37 cases. The average 2.29 A of the 37 RMSD values of SODOCK was better than those of other docking programs, which were all above 3.0 A.     

An alternative to the “Star Path” enhancement of the ADMA linear scaling method for protein modeling

With the aim of improving the performance of macromolecular quantum chemistry conformation analysis and reaction path following methods, the Adjustable Density Matrix Assembler (ADMA) method has already been combined with some faster although less accurate density matrix extrapolation methods, such as the Löwdin‐Inverse‐Löwdin (LIL) extrapolation along a potential energy surface, and a strategically arranged back‐and‐forth switching between these methods has been proven to be advantageous. Here, an alternative approach is proposed and investigated, based on several actual test calculations, where the “inexpensive” LIL density matrix extrapolation steps are replaced by only somewhat more expensive, but still ADMA‐based calculations, where in the “rough‐search stage,” only interactions of shorter distances within the macromolecule are considered. It is shown that this approach is viable, as an alternative to the “Star Path” method including both ADMA and LIL steps. © 2017 Wiley Periodicals, Inc.     

MALDI-MS and multivariate analysis for the detection and quantification of different milk species

The extensive consumption of milk and dairy products makes these foodstuffs targets for potential adulteration with financial gains for unscrupulous producers. Such practices must be detected as these can impact negatively on product quality, labelling and even health. Matrix-assisted laser desorption/ionisation time-of-flight mass spectrometry (MALDI-ToF-MS) is a potentially useful technique, with proven abilities in protein identification and more recently through the use of internal standards for quantification purposes of specific proteins or peptides. In the current work, we therefore aim to explore the accuracy and attributes of MALDI-ToF-MS with chemometrics for the detection and quantification of milk adulteration. Three binary mixtures containing cows' and goats', cows' and sheep's, and goats' and sheep's milk and a fourth tertiary mixture containing all types of milk were prepared and analysed directly using MALDI-ToF-MS. In these mixtures, the milk concentrations of each milk varied from 0% to 100% in 5% steps. Multivariate statistical methods including partial least squares (PLS) regression and non-linear Kernel PLS regression were employed for multivariate calibration and final interpretation of the results. The results for PLS and KPLS were encouraging with between 2% and 13% root mean squared error of prediction on independent data; KPLS slightly outperformed PLS. We believe that these results show that MALDI-ToF-MS has excellent potential for future use in the dairy industry as a rapid method of detection and enumeration in milk adulteration.     

Stochastic protein folding simulation in the three-dimensional HP-model

We present results from three-dimensional protein folding simulations in the HP-model on ten benchmark problems. The simulations are executed by a simulated annealing-based algorithm with a time-dependent cooling schedule. The neighbourhood relation is determined by the pull-move set. The results provide experimental evidence that the maximum depth D of local minima of the underlying energy landscape can be upper bounded by D相似文献   

段式正交信号校正方法及在小麦近红外光谱数据分析中的应用

针对光谱数据峰宽、局部效应显著、含有噪音、变量个数多及彼此间常存在严重的复共线性等问题,改进和设计一种光谱数据局部校正方法:基于窗口平滑的段式正交信号校正方法,并将之结合偏最小二乘回归,以实现光谱数据的预处理及定量分析。通过NIPALS算法初始化将滤去的正交成分,以近邻分段方式进行逐个波长点的正交信号校正。而后将去噪后的光谱矩阵作为新的自变量阵,通过偏最小二乘回归构建其与性质参变量间的校正模型。通过小麦近红外漫反射光谱数据的应用实验结果表明,本方法正交成分估计稳定,去噪明显,模型的预报性能优于其它方法,PLS成分数减少,模型更加简洁。     

Ab initio vibrational state calculations with a quartic force field: applications to H2CO, C2H4, CH3OH, CH3CCH, and C6H6

For polyatomic molecules, n-mode coupling representations of the quartic force field (nMR-QFF) are presented, which include terms up to n normal coordinate couplings in a fourth-order polynomial potential energy function. The computational scheme to evaluate third-and fourth-order derivatives by finite differentiations of the energy is fully described. The code to generate the nMR-QFF has been implemented into GAMESS program package and interfaced with the vibrational self-consistent field (VSCF) and correlation corrected VSCF (cc-VSCF) methods. As a demonstration, fundamental frequencies have been calculated by the cc-VSCF method based on 2MR-QFF for formaldehyde, ethylene, methanol, propyne, and benzene. The applications show that 2MR-QFF is a highly accurate potential energy function, with errors of 1.0-1.9% relative to the experimental value in fundamental frequencies. This approach will help quantitative evaluations of vibrational energies of a general molecule with a reasonable computational cost.