Molecular structure by the constrained damped least-squares (CDLS) method

A method for simulating three-dimensional molecular structure is presented. The method can satisfy any number of constraints on the molecular structure. The constraints can pertain to the constancy of individual distances and angles or be related to point-group symmetry. A simulated three-dimonsional model is forced to satisfy the required constraints in the least-squares sense. The least-squares optimization is damped to guard against convergence failure. This method is suggested as a tool to obtain approximate molecular structure in situations where a number of quantitative features are known about a molecular structure from preliminary crystallographic results but not the full molecular structure. An application to the structure of enniatin B–K⁺ complex is given to illustrate such a use.     

分子对接的随机聚点搜索算法

随机聚点搜索算法是一种普遍的全局极小化方法,在目标函数自变量数目不很大时,计算效率较高。将该算法应用于分子对接,首先要通过模型分子对接,反复调整算法各控制参数使效率最高。对于HIV－1蛋白酶与苯甲醚配体的刚性对接,算法成功的找到了相互作用能量全局极小,与晶体结构的均方根偏差(RMSD)仅0.2?。这表明,该算法可高效率找到分子对接的能量最适构型。     

An approach to the multiple-minima problem in protein folding by relaxing dimensionality. Tests on enkephalin

An algorithm for locating the region in conformational space containing the global energy minimum of a polypeptide is described. Distances are used as the primary variables in the minimization of an objective function that incorporates both energetic and distance-geometric terms. The latter are obtained from geometry and energy functions, rather than nuclear magnetic resonance experiments, although the algorithm can incorporate distances from nuclear magnetic resonance data if desired. The polypeptide is generated originally in a space of high dimensionality. This has two important consequences. First, all interatomic distances are initially at their energetically most favorable values; i.e. the polypeptide is initially at a global minimum-energy conformation, albeit a high-dimensional one. Second, the relaxation of dimensionality constraints in the early stages of the minimization removes many potential energy barriers that exist in three dimensions, thereby allowing a means of escaping from three-dimensional local minima. These features are used in an algorithm that produces short trajectories of three-dimensional minimum-energy conformations. A conformation in the trajectory is generated by allowing the previous conformation in the trajectory to evolve in a high-dimensional space before returning to three dimensions. The resulting three-dimensional structure is taken to be the next conformation in the trajectory, and the process is iterated. This sequence of conformations results in a limited but efficient sampling of conformational space. Results for test calculations on Met-enkephalin, a pentapeptide with the amino acid sequence H-Tyr-Gly-Gly-Phe-Met-OH, are presented. A tight cluster of conformations (in three-dimensional space) is found with ECEPP energies (Empirical Conformational Energy Program for Peptides) lower than any previously reported. This cluster of conformations defines a region in conformational space in which the global-minimum-energy conformation of enkephalin appears to lie.     

Improving strand pairing prediction through exploring folding cooperativity

The topology of $beta$-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting $beta$-sheet topology. At the same time, finding the correct partners is very difficult due to long range interactions involved in strand pairing. Additionally, patterns of aminoacids involved, in $beta$-sheet formations are very general and therefore difficult to use for computational recognition of specific contacts between strands. In this work, we report a new strand pairing algorithm. To address above mentioned difficulties, our algorithm attempts to mimic elements of the folding process. Namely, in addition to ensuring that the predicted hydrogen bonded strand pairs satisfy basic global consistency constraints, it takes into account hypothetical folding pathways. Consistently with this view, introducing hydrogen bonds between a pair of strands changes the probabilities of forming hydrogen bonds between other pairs of strand. We demonstrate that this approach provides an improvement over previously proposed algorithms. We also compare the performance of this method to that of a global optimization algorithm that poses the problem as integer linear programming optimization problem and solves it using ILOG CPLEXtexttrademark package.     

Systematic solution to homo‐oligomeric structures determined by NMR

Protein structure determination by NMR has predominantly relied on simulated annealing‐based conformational search for a converged fold using primarily distance constraints, including constraints derived from nuclear Overhauser effects, paramagnetic relaxation enhancement, and cysteine crosslinkings. Although there is no guarantee that the converged fold represents the global minimum of the conformational space, it is generally accepted that good convergence is synonymous to the global minimum. Here, we show such a criterion breaks down in the presence of large numbers of ambiguous constraints from NMR experiments on homo‐oligomeric protein complexes. A systematic evaluation of the conformational solutions that satisfy the NMR constraints of a trimeric membrane protein, DAGK, reveals 9 distinct folds, including the reported NMR and crystal structures. This result highlights the fundamental limitation of global fold determination for homo‐oligomeric proteins using ambiguous distance constraints and provides a systematic solution for exhaustive enumeration of all satisfying solutions. Proteins 2015; 83:651–661. © 2015 Wiley Periodicals, Inc.     

Multiple paternity: determining the minimum number of sires of a large brood

We describe an efficient algorithm for determining exactly the minimum number of sires consistent with the multi-locus genotypes of a mother and her progeny. We consider cases where a simple exhaustive search through all possible sets of sires is impossible in practice because it would take too long to complete. Our algorithm for solving this combinatorial optimization problem avoids visiting large parts of search space that would not result in a solution with fewer sires. This improvement is of particular importance when the number of allelic types in the progeny array is large and when the minimum number of sires is expected to be large. Precisely in such cases, it is important to know the minimum number of sires: this number gives an exact bound on the most likely number of sires estimated by a random search algorithm in a parameter region where it may be difficult to determine whether it has converged. We apply our algorithm to data from the marine snail, Littorina saxatilis.     

Protein threading with profiles and distance constraints using clique based algorithms

With the advent of experimental technologies like chemical cross-linking, it has become possible to obtain distances between specific residues of a newly sequenced protein. These types of experiments usually are less time consuming than X-ray crystallography or NMR. Consequently, it is highly desired to develop a method that incorporates this distance information to improve the performance of protein threading methods. However, protein threading with profiles in which constraints on distances between residues are given is known to be NP-hard. By using the notion of a maximum edge-weight clique finding algorithm, we introduce a more efficient method called FTHREAD for profile threading with distance constraints that is 18 times faster than its predecessor CLIQUETHREAD. Moreover, we also present a novel practical algorithm NTHREAD for profile threading with Non-strict constraints. The overall performance of FTHREAD on a data set shows that although our algorithm uses a simple threading function, our algorithm performs equally well as some of the existing methods. Particularly, when there are some unsatisfied constraints, NTHREAD (Non-strict constraints threading algorithm) performs better than threading with FTHREAD (Strict constraints threading algorithm). We have also analyzed the effects of using a number of distance constraints. This algorithm helps the enhancement of alignment quality between the query sequence and template structure, once the corresponding template structure is determined for the target sequence.     

Haplotyping in pedigrees via a genetic algorithm.

Genome-wide screening for localization of disease genes necessitates the efficient reconstruction of haplotypes of members of a pedigree from genotype data at multiple loci. We propose a genetic algorithmic approach to haplotyping and show that it works fast, efficiently and reliably. This algorithm uses certain principles of biological evolution to find optimal solutions to complex problems. The optimality criterion used in the present problem is the minimum number of recombinations over possible haplotype configurations of members of a pedigree. The proposed algorithm is much less demanding in terms of data and assumption requirements compared to the currently used likelihood-based methods of haplotype reconstruction. It also provides multiple optimal haplotype configurations of a pedigree, if such multiple optima exist.     

Hybrid Global Optimization Algorithms for Protein Structure Prediction: Alternating Hybrids

Hybrid global optimization methods attempt to combine the beneficial features of two or more algorithms, and can be powerful methods for solving challenging nonconvex optimization problems. In this paper, novel classes of hybrid global optimization methods, termed alternating hybrids, are introduced for application as a tool in treating the peptide and protein structure prediction problems. In particular, these new optimization methods take the form of hybrids between a deterministic global optimization algorithm, the αBB, and a stochastically based method, conformational space annealing (CSA). The αBB method, as a theoretically proven global optimization approach, exhibits consistency, as it guarantees convergence to the global minimum for twice-continuously differentiable constrained nonlinear programming problems, but can benefit from computationally related enhancements. On the other hand, the independent CSA algorithm is highly efficient, though the method lacks theoretical guarantees of convergence. Furthermore, both the αBB method and the CSA method are found to identify ensembles of low-energy conformers, an important feature for determining the true free energy minimum of the system. The proposed hybrid methods combine the desirable features of efficiency and consistency, thus enabling the accurate prediction of the structures of larger peptides. Computational studies for met-enkephalin and melittin, employing sequential and parallel computing frameworks, demonstrate the promise for these proposed hybrid methods.     

Deterministic global optimization algorithm based on outer approximation for the parameter estima- tion of nonlinear dynamic biological systems

ABSTRACT: BACKGROUND: The estimation of parameter values for mathematical models of biological systems is an optimization problem that is particularly challenging due to the nonlinearities involved. One major difficulty is the existence of multiple minima in which standard optimization methods may fall during the search. Deterministic global optimization methods overcome this limitation, ensuring convergence to the global optimum within a desired tolerance. Global optimization techniques are typically classified into stochastic and deterministic. The former typically lead to lower CPU times but offer no guarantee of convergence to the global minimum in a finite number of iterations. In contrast, deterministic methods provide solutions of a given quality (i.e., optimality gap), but tend to lead to large computational burdens. RESULTS: This work presents a deterministic outer approximation-based algorithm for the global optimization of dynamic problems arising in the parameter estimation of models of biological systems. Our approach, which offers a theoretical guarantee of convergence to the global minimum, reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. CONCLUSION: The capabilities of our approach were tested in two benchmark problems, in which the performance of our algorithm was compared with that of the commercial global optimization package BARON. The proposed strategy produced near optimal solutions (i.e., within a desired tolerance) in a fraction of the CPU time required by BARON.     

A distance geometry program for determining the structures of small proteins and other macromolecules from nuclear magnetic resonance measurements of intramolecular1H−1H proximities in solution

DISGEO is a new implementation of a distance geometry algorithm which has been specialized for the calculation of macromolecular conformation from distance measurements obtained by two-dimensional nuclear Overhauser enhancement spectroscopy. The improvements include (1) a decomposition of the complete embedding process into two successive, more tractable calculations by the use of “substructures”, (2) a compact data structure for storing incomplete distance information on a structure, (3) a more efficient shortest-path algorithm for computing the triangle inequality limits on all distances from this information, (4) a new algorithm for selecting random metric spaces from within these limits, (5) the use of chirality constraints to obtain good covalent geometry without the use ofad hoc weights or excessive optimization. The utility of the resultant program with nuclear magnetic resonance data is demonstrated by embedding complete spatial structures for the protein basic pancreatic trypsin inhibitor vs all 508 intramolecular, interresidue proton-proton contacts shorter than 4.0 Å that were present in its crystal structure. The crystal structure could be reproduced from this data set to within 1.3 Å minimum root mean square coordinate difference between the backbone atoms. We conclude that the information potentially available from nuclear magnetic resonance experiments in solution is sufficient to define the spatial structure of small proteins.     

Determination of three-dimensional protein structures from nuclear magnetic resonance data using fragments of known structures

A method to build a three-dimensional protein model from nuclear magnetic resonance (NMR) data using fragments from a data base of crystallographically determined protein structures is presented. The interproton distances derived from the nuclear Overhauser effect (NOE) data are compared to the precalculated distances in the known protein structures. An efficient search algorithm is used, which arranges the distances in matrices akin to a C alpha diagonal distance plot, and compares the NOE distance matrices for short sequential zones of the protein to the data base matrices. After cluster analysis of the fragments found in this way, the structure is built by aligning fragments in overlapping zones. The sequentially long-range NOEs cannot be used in the initial fragments search but are vital to discriminate between several possible combinations of different groups of fragments. The method has been tested on one simulated NOE data set derived from a crystal structure and one experimental NMR data set. The method produces models that have good local structure, but may contain larger global errors. These models can be used as the starting point for further refinement, e.g., by restrained molecular dynamics or interactive graphics.     

基于遗传算法的渔情预报HSI建模与智能优化

鱼类栖息地适宜性指数模型(HSI)基于鱼类分布与海洋环境之间存在的非线性关系而构建。然而,海洋环境因子之间存在着传统方法无法消除的相关性,导致获取的HSI参数较难准确表达环境因子与渔场之间的复杂关系。基于遗传算法(GA),自动消除海洋环境因子之间的相关性,构建了一种通用的鱼类HSI建模与智能优化框架(GeneHSI)。GeneHSI框架的核心是HSI建模空间向遗传算法空间的映射以及GA适应度函数的构建。该函数构建的思想是HSI预测的渔场概率与商业捕捞获取的渔场概率之间的累计误差值达到最小化。GeneHSI由待解问题构建、GA初始化和GA优化策略3部分组成。利用随机生成的标准化海洋环境数据与渔场概率数据,验证了GeneHSI模型框架的有效性。研究表明,GeneHSI能够有效优化HSI的建模并能自动获取HSI参数。不同限制条件下,遗传算法获取的HSI具有较大的差异,其中一般优化策略下获取的HSI参数最差;不等式、等式和上下界条件下,GeneHSI优化过程显著地更加合理,因此获取的HSI参数也更准确。此外,100、1000、5000和10000样本量下的优化建模表明,GeneHSI具有处理海量样本数据的能力。     

Three-dimensional structure of a DNA hairpin in solution: two-dimensional NMR studies and distance geometry calculations on d(CGCGTTTTCGCG)

The three-dimensional structure of d(CGCGTTTTCGCG) in solution has been determined from proton NMR data by using distance geometry methods. The rate of dipolar cross-relaxation between protons close together in space is used to calculate distances between proton pairs within 5 A of each other; these distances are used as input to a distance geometry algorithm that embeds this distance matrix in three-dimensional space. The resulting refined structures that best agree with the input distances are all very similar to each other and show that the DNA sequence forms a hairpin in solution; the bases of the loop region are stacked, and the stem region forms a right-handed helix. The advantages and limitations of the technique, as well as the computer requirements of the algorithm, are discussed.     

Effects of Experimentally Achievable Improvements in the Quality of NMR Distance Constraints on the Accuracy of Calculated Protein Structures

New methods for collecting cross-relaxation data from proteins and nucleic acids make it possible to improve the accuracy and precision of interproton distance measurements used as input for NMR solution structure determinations. It thus is of interest to determine whether such experimentally achievable improvements in input distance constraints have significant effects on the precision and accuracy of the resulting structures. To answer this question, we have turned to a computational procedure involving the use of data simulated from a known structure, in order to allow unambiguous assessments of accuracy. The approach to improved distances evaluated here is that afforded by magnetization exchange network editing (MENE); MENE pulse sequences break the network of cross-relaxation interactions into regions that are manipulated so as to defeat certain spin-diffusion terms. A target structure was prepared from the X-ray structure of a small protein, turkey ovomucoid third domain (OMTKY3). A normal NOESY spectrum and two varieties of MENE spectra, BD-NOESY and CBD-NOESY, were simulated by means of complete relaxation matrix analysis. These results were used to create different input data sets with the same number of constraints (perfectly accurate distances derived from the target structure, more accurate distances derived from the MENE simulations, and less accurate distances derived from the NOESY simulation), and these, interpreted at different levels of precision, were used as input for solution structure calculations. The results showed that the use of more precise input data measurably improves the local precision and accuracy of calculated structures, but only if the more precise data include the actual target distance. Incorporation of the experimentally achievable, accurate distances with higher precision afforded by the MENE pulse sequences into the set of input distances was found to improve the accuracy of the resulting structures, particularly in terms of side-chain conformation.     

A dual optimization method for the material parameter identification of a biphasic poroviscoelastic hydrogel: Potential application to hypercompliant soft tissues

A dual-indentation creep and stress relaxation methodology was developed and validated for the material characterization of very soft biological tissue within the framework of the biphasic poroviscoelastic (BPVE) constitutive model. Agarose hydrogel, a generic porous medium with mobile fluid, served as a mechanical tissue analogue for validation of the experimental procedure. Indentation creep and stress relaxation tests with a solid plane-ended cylindrical indenter were performed at identical sites on a gel sample with dimensions large enough with respect to indenter size in order to satisfy an infinite layer assumption. A finite element (FE) formulation coupled to a global optimization algorithm was utilized to simultaneously curve-fit the creep and stress relaxation data and extract the BPVE model parameters for the agarose gel. A numerical analysis with artificial data was conducted to validate the uniqueness of the computational procedure. The BPVE model was able to successfully cross-predict both creep and stress relaxation behavior for each pair of experiments with a single unique set of material parameters. Optimized elastic moduli were consistent with those reported in the literature for agarose gel. With the incorporation of appropriately-sized indenters to satisfy more stringent geometric constraints, this simple yet powerful indentation methodology can provide a straightforward means by which to obtain the BPVE model parameters of biological soft tissues that are difficult to manipulate (such as brain and adipose) while maintaining a realistic in situ loading environment.     

Nanometer distance measurements in RNA using site-directed spin labeling

The method of site-directed spin labeling (SDSL) utilizes a stable nitroxide radical to obtain structural and dynamic information on biomolecules. Measuring dipolar interactions between pairs of nitroxides yields internitroxide distances, from which quantitative structural information can be derived. This study evaluates SDSL distance measurements in RNA using a nitroxide probe, designated as R5, which is attached in an efficient and cost-effective manner to backbone phosphorothioate sites that are chemically substituted in arbitrary sequences. It is shown that R5 does not perturb the global structure of the A-form RNA helix. Six sets of internitroxide distances, ranging from 20 to 50 A, were measured on an RNA duplex with a known X-ray crystal structure. The measured distances strongly correlate (R(2) = 0.97) with those predicted using an efficient algorithm for determining the expected internitroxide distances from the parent RNA structure. The results enable future studies of global RNA structures for which high-resolution structural data are absent.     

Chaotic Artificial Bee Colony algorithm: A new approach to the problem of minimization of energy of the 3D protein structure

Prediction of the three-dimensional structure of a protein from its amino acid sequence can be considered as a global optimization problem. In this paper, the Chaotic Artificial Bee Colony (CABC) algorithm was introduced and applied to 3D protein structure prediction. Based on the 3D off-lattice AB model, the CABC algorithm combines global search and local search of the Artificial Bee Colony (ABC) algorithm with the chaotic search algorithm to avoid the problem of premature convergence and easily trapping the local optimum solution. The experiments carried out with the popular Fibonacci sequences demonstrate that the proposed algorithm provides an effective and high-performance method for protein structure prediction.     

Minimum energy configurations of the 2-dimensional HP-model of proteins by self-organizing networks.

We use self-organizing maps (SOM) as an efficient tool to find the minimum energy configurations of the 2-dimensional HP-models of proteins. The usage of the SOM for the protein folding problem is similar to that for the Traveling Salesman Problem. The lattice nodes represent the cities whereas the neurons in the network represent the amino acids moving towards the closest cities, subject to the HH interactions. The valid path that maximizes the HH contacts corresponds to the minimum energy configuration of the protein. We report promising results for the cases when the protein completely fills a lattice and discuss the current problems and possible extensions. In all the test sequences up to 36 amino acids, the algorithm was able to find the global minimum and its degeneracies.     

Evaluation of a particle swarm algorithm for biomechanical optimization

Optimization is frequently employed in biomechanics research to solve system identification problems, predict human movement, or estimate muscle or other internal forces that cannot be measured directly. Unfortunately, biomechanical optimization problems often possess multiple local minima, making it difficult to find the best solution. Furthermore, convergence in gradient-based algorithms can be affected by scaling to account for design variables with different length scales or units. In this study we evaluate a recently-developed version of the particle swarm optimization (PSO) algorithm to address these problems. The algorithm's global search capabilities were investigated using a suite of difficult analytical test problems, while its scale-independent nature was proven mathematically and verified using a biomechanical test problem. For comparison, all test problems were also solved with three off-the-shelf optimization algorithms--a global genetic algorithm (GA) and multistart gradient-based sequential quadratic programming (SQP) and quasi-Newton (BFGS) algorithms. For the analytical test problems, only the PSO algorithm was successful on the majority of the problems. When compared to previously published results for the same problems, PSO was more robust than a global simulated annealing algorithm but less robust than a different, more complex genetic algorithm. For the biomechanical test problem, only the PSO algorithm was insensitive to design variable scaling, with the GA algorithm being mildly sensitive and the SQP and BFGS algorithms being highly sensitive. The proposed PSO algorithm provides a new off-the-shelf global optimization option for difficult biomechanical problems, especially those utilizing design variables with different length scales or units.