Restricted dead‐end elimination: Protein redesign with a bounded number of residue mutations

Dead‐end elimination (DEE) has emerged as a powerful structure‐based, conformational search technique enabling computational protein redesign. Given a protein with n mutable residues, the DEE criteria guide the search toward identifying the sequence of amino acids with the global minimum energy conformation (GMEC). This approach does not restrict the number of permitted mutations and allows the identified GMEC to differ from the original sequence in up to n residues. In practice, redesigns containing a large number of mutations are often problematic when taken into the wet‐lab for creation via site‐directed mutagenesis. The large number of point mutations required for the redesigns makes the process difficult, and increases the risk of major unpredicted and undesirable conformational changes. Preselecting a limited subset of mutable residues is not a satisfactory solution because it is unclear how to select this set before the search has been performed. Therefore, the ideal approach is what we define as the κ‐restricted redesign problem in which any κ of the n residues are allowed to mutate. We introduce restricted dead‐end elimination (rDEE) as a solution of choice to efficiently identify the GMEC of the restricted redesign (the κGMEC). Whereas existing approaches require n‐choose‐κ individual runs to identify the κGMEC, the rDEE criteria can perform the redesign in a single search. We derive a number of extensions to rDEE and present a restricted form of the A* conformation search. We also demonstrate a 10‐fold speed‐up of rDEE over traditional DEE approaches on three different experimental systems. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2010     

Rotamer optimization for protein design through MAP estimation and problem‐size reduction

The search for the global minimum energy conformation (GMEC) of protein side chains is an important computational challenge in protein structure prediction and design. Using rotamer models, the problem is formulated as a NP‐hard optimization problem. Dead‐end elimination (DEE) methods combined with systematic A* search (DEE/A*) has proven useful, but may not be strong enough as we attempt to solve protein design problems where a large number of similar rotamers is eligible and the network of interactions between residues is dense. In this work, we present an exact solution method, named BroMAP (branch‐and‐bound rotamer optimization using MAP estimation), for such protein design problems. The design goal of BroMAP is to be able to expand smaller search trees than conventional branch‐and‐bound methods while performing only a moderate amount of computation in each node, thereby reducing the total running time. To achieve that, BroMAP attempts reduction of the problem size within each node through DEE and elimination by lower bounds from approximate maximum‐a‐posteriori (MAP) estimation. The lower bounds are also exploited in branching and subproblem selection for fast discovery of strong upper bounds. Our computational results show that BroMAP tends to be faster than DEE/A* for large protein design cases. BroMAP also solved cases that were not solved by DEE/A* within the maximum allowed time, and did not incur significant disadvantage for cases where DEE/A* performed well. Therefore, BroMAP is particularly applicable to large protein design problems where DEE/A* struggles and can also substitute for DEE/A* in general GMEC search. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2009     

Conformational splitting: A more powerful criterion for dead‐end elimination

Dead‐end elimination (DEE) is a powerful theorem for selecting optimal protein side‐chain orientations from a large set of discrete conformations. The present work describes a new approach to dead‐end elimination that effectively splits conformational space into partitions to more efficiently eliminate dead‐ending rotamers. Split DEE makes it possible to complete protein design calculations that were previously intractable due to the combinatorial explosion of intermediate conformations generated during the convergence process. © 2000 John Wiley & Sons, Inc. J Comput Chem 21: 999–1009, 2000     

Determination of the major solution conformation of tyrocidine A,using molecular mechanics energy minimization and NMR-derived distance and torsion angle constraints

Molecular mechanics energy calculations coupled with nuclear magnetic resonance-determined distance and torsion angle constraints have been used to determine the three-dimensional structure of tyrocidine A, a cyclic decapeptide which exists largely as a single conformation in solution. Two open-chain polyalanine models were used to represent separate halves of the peptide backbone and a combinatorial method of searching conformation space used to generate candidate structures consistent with experimental distance constraints. These structures were energy-minimized using the AMBER molecular mechanics forcefield and the resulting conformations classified by factor analysis of their Cartesian coordinates. Representative low-energy conformers of the two halves of the backbone were fused together and two candidate conformations of the completed backbone refined by further minimization using both distance and torsional constraints. Side chains were then added as their experimentally preferred rotamers and the whole molecule minimized without constraints to give the final model structure. This shows type II' and III ß turns at residues 4–5 and 9–10, respectively, coupled by twisted antiparallel strands which show hydrogen bonds between all four pairs of opposing peptide groups. The backbone conformation of residues 2–6 closely resembles that found in the crystal structure of gramicidin S.     

Comparing three stochastic search algorithms for computational protein design: Monte Carlo,replica exchange Monte Carlo,and a multistart,steepest‐descent heuristic

Computational protein design depends on an energy function and an algorithm to search the sequence/conformation space. We compare three stochastic search algorithms: a heuristic, Monte Carlo (MC), and a Replica Exchange Monte Carlo method (REMC). The heuristic performs a steepest‐descent minimization starting from thousands of random starting points. The methods are applied to nine test proteins from three structural families, with a fixed backbone structure, a molecular mechanics energy function, and with 1, 5, 10, 20, 30, or all amino acids allowed to mutate. Results are compared to an exact, “Cost Function Network” method that identifies the global minimum energy conformation (GMEC) in favorable cases. The designed sequences accurately reproduce experimental sequences in the hydrophobic core. The heuristic and REMC agree closely and reproduce the GMEC when it is known, with a few exceptions. Plain MC performs well for most cases, occasionally departing from the GMEC by 3–4 kcal/mol. With REMC, the diversity of the sequences sampled agrees with exact enumeration where the latter is possible: up to 2 kcal/mol above the GMEC. Beyond, room temperature replicas sample sequences up to 10 kcal/mol above the GMEC, providing thermal averages and a solution to the inverse protein folding problem. © 2016 Wiley Periodicals, Inc.     

Dead-end elimination for multistate protein design

Multistate protein design is the task of predicting the amino acid sequence that is best suited to selectively and stably fold to one state out of a set of competing structures. Computationally, it entails solving a challenging optimization problem. Therefore, notwithstanding the increased interest in multistate design, the only implementations reported are based on either genetic algorithms or Monte Carlo methods. The dead-end elimination (DEE) theorem cannot be readily transfered to multistate design problems despite its successful application to single-state protein design. In this article we propose a variant of the standard DEE, called type-dependent DEE. Our method reduces the size of the conformational space of the multistate design problem, while provably preserving the minimal energy conformational assignment for any choice of amino acid sequence. Type-dependent DEE can therefore be used as a preprocessing step in any computational multistate design scheme. We demonstrate the applicability of type-dependent DEE on a set of multistate design problems and discuss its strength and limitations.     

Genetic algorithms for protein conformation sampling and optimization in a discrete backbone dihedral angle space

We have investigated protein conformation sampling and optimization based on the genetic algorithm and discrete main chain dihedral state model. An efficient approach combining the genetic algorithm with local minimization and with a niche technique based on the sharing function is proposed. Using two different types of potential energy functions, a Go-type potential function and a knowledge-based pairwise potential energy function, and a test set containing small proteins of varying sizes and secondary structure compositions, we demonstrated the importance of local minimization and population diversity in protein conformation optimization with genetic algorithms. Some general properties of the sampled conformations such as their native-likeness and the influences of including side-chains are discussed.     

Preprocessing of rotamers for protein design calculations

We have developed a process that significantly reduces the number of rotamers in computational protein design calculations. This process, which we call Vegas, results in dramatic computational performance increases when used with algorithms based on the dead-end elimination (DEE) theorem. Vegas estimates the energy of each rotamer at each position by fixing each rotamer in turn and utilizing various search algorithms to optimize the remaining positions. Algorithms used for this context specific optimization can include Monte Carlo, self-consistent mean field, and the evaluation of an expression that generates a lower bound energy for the fixed rotamer. Rotamers with energies above a user-defined cutoff value are eliminated. We found that using Vegas to preprocess rotamers significantly reduced the calculation time of subsequent DEE-based algorithms while retaining the global minimum energy conformation. For a full boundary design of a 51 amino acid fragment of engrailed homeodomain, the total calculation time was reduced by 12-fold.     

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.     

Polarizable protein packing

To incorporate protein polarization effects within a protein combinatorial optimization framework, we decompose the polarizable force field AMOEBA into low order terms. Including terms up to the third-order provides a fair approximation to the full energy while maintaining tractability. We represent the polarizable packing problem for protein G as a hypergraph and solve for optimal rotamers with the FASTER combinatorial optimization algorithm. These approximate energy models can be improved to high accuracy [root mean square deviation (rmsd) < 1 kJ mol(-1)] via ridge regression. The resulting trained approximations are used to efficiently identify new, low-energy solutions. The approach is general and should allow combinatorial optimization of other many-body problems.     

An extended dead-end elimination algorithm to determine gap-free lists of low energy states

Proteins are flexible systems and commonly populate several functionally important states. To understand protein function, these states and their energies have to be identified. We introduce an algorithm that allows the determination of a gap-free list of the low energy states. This algorithm is based on the dead-end elimination (DEE) theorem and is termed X-DEE (extended DEE). X-DEE is applicable to discrete systems whose state energy can be formulated as pairwise interaction between sites and their intrinsic energies. In this article, the computational performance of X-DEE is analyzed and discussed. X-DEE is implemented to determine the lowest energy protonation states of proteins, a problem to which DEE has not been applied so far. We use X-DEE to calculate a list of low energy protonation states for two bacteriorhodopsin structures that represent the first proton transfer step of the bacteriorhodopsin photocycle.     

DFT conformational studies of alpha-maltotriose

Recent DFT optimization studies on alpha-maltose improved our understanding of the preferred conformations of alpha-maltose. The present study extends these studies to alpha-maltotriose with three alpha-D-glucopyranose residues linked by two alpha-[1-->4] bridges, denoted herein as DP-3's. Combinations of gg, gt, and tg hydroxymethyl groups are included for both "c" and "r" hydroxyl rotamers. When the hydroxymethyl groups are for example, gg-gg-gg, and the hydroxyl groups are rotated from all clockwise, "c", to all counterclockwise, "r", the minimum energy positions of the bridging dihedral angles (phi(H) and psi(H)) move from the region of conformational space of (-, -), relative to (0 degrees , 0 degrees), to a new position defined by (+, +). Further, it was found previously that the relative energies of alpha-maltose gg-gg-c and "r" conformations were very close to one another; however, the DP-3's relative energies between hydroxyl "c" or "r" rotamers differ by more than one kcal/mol, in favor of the "c" form, even though the lowest energy DP-3 conformations have glycosidic dihedral angles similar to those found in the alpha-maltose study. Preliminary solvation studies using COSMO, a dielectric solvation method, point to important solvent contributions that reverse the energy profiles, showing an energy preference for the "r" forms. Only structures in which the rings are in the chair conformation are presented here.     

Calculation of number and free energy of the conformers of linear alkanes with medium and long chains. Implications for catalysis

A method for calculating the number of rotamers of a linear alkane and of the number of rotamers with a given number of gauche conformations along the chain as a function of the total number of atoms in the chain, using general equations, is presented. A graphical method for generating individual rotamers was applied to the homologs up to decane, which has 1134 rotamers. The steric energies calculated by molecular mechanics (MM2 force field) were used as measures of the heat of formation for the coiled conformations relative to the anti conformer for each molecule, whereas the statistical entropy differences were calculated for classes of coiled rotamers grouped by the number of gauche bonds and steric energy. The free energy values calculated from these components show that already at 400 K hexane exists preferentially in conformations containing gauche bonds. For larger chains the free energy advantage for the coiled chains increases very steeply. The implications for the question of reactions of linear alkanes occurring on the surface or inside the channels of small- and medium-pore zeolites are briefly examined.     

Flexible protein‐protein docking based on Best‐First search algorithm

We developed a new high resolution protein‐protein docking method based on Best‐First search algorithm that loosely imitates protein‐protein associations. The method operates in two stages: first, we perform a rigid search on the unbound proteins. Second, we search alternately on rigid and flexible degrees of freedom starting from multiple configurations from the rigid search. Both stages use heuristics added to the energy function, which causes the proteins to rapidly approach each other and remain adjacent, while optimizing on the energy. The method deals with backbone flexibility explicitly by searching over ensembles of conformations generated before docking. We ran the rigid docking stage on 66 complexes and grouped the results into four classes according to evaluation criteria used in Critical Assessment of Predicted Interactions (CAPRI; “high,” “medium,” “acceptable,” and “incorrect”). Our method found medium binding conformations for 26% of the complexes and acceptable for additional 44% among the top 10 configurations. Considering all the configurations, we found medium binding conformations for 55% of the complexes and acceptable for additional 39% of the complexes. Introducing side‐chains flexibility in the second stage improves the best found binding conformation but harms the ranking. However, introducing side‐chains and backbone flexibility improve both the best found binding conformation and the best found conformation in the top 10. Our approach is a basis for incorporating multiple flexible motions into protein‐protein docking and is of interest even with the current use of a simple energy function. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2010     

Eclipsed Isopropyl Conformations of Two Dimeric Hydrazines

The X-ray structures of 4,10-di-tert-butyl-5,9-diisopropyl-4,5,9,10-tetraazatetracyclo[6.2.2.2(3,6)]tetradecane (s4iPr) and its 4,9-di-tert-butyl-5,10-diisopropyl isomer (a4iPr) are reported. Both compounds are in conformations having their in-N-alkyl groups (directed toward the central CH-CH bond of the molecule) anti to each other, as expected from previous work. The principal feature of interest is that one in-isopropyl group in each compound is in an eclipsed conformation, NN,C(alpha)Me twist angle -0.5(5) degrees for s4iPr and -6.4(4) degrees for a4iPr. Low energy (somewhat less) eclipsed in-isopropyl conformations are predicted by both molecular mechanics (MM2) and semiempirical quantum mechanical (AM1) calculations. The asymmetry of the potentially C(2) symmetric a4iPr because the two in-isopropyl groups are in different rotamers is apparently not a result of crystal packing forces, because a conformation with different isopropyl rotamers is the more stable one by at least 1.0 kcal/mol in solution, determined by (13)C-NMR spectroscopy. This result is not predicted by either calculation method. The "monomer", 2-tert-butyl-3-isopropyl-2,3-diazabicyclo[2.2.2]octane (3), proves to be a poor model for the conformations of 4iPr.     

Peptide backbone reconstruction using dead-end elimination and a knowledge-based forcefield

A novel, yet simple and automated, protocol for reconstruction of complete peptide backbones from C(alpha) coordinates only is described, validated, and benchmarked. The described method collates a set of possible backbone conformations for each set of residue triads from a structural library derived from the PDB. The optimal permutation of these three residue segments of backbone conformations is determined using the dead-end elimination (DEE) algorithm. Putative conformations are evaluated using a pairwise-additive knowledge-based forcefield term and a fragment overlap term. The protocol described in this report is able to restore the full backbone coordinates to within 0.2-0.6 A of the actual crystal structure from C(alpha) coordinates only. In addition, it is insensitive to errors in the input C(alpha) coordinates with RMSDs of 3.0 A, and this is illustrated through application to deliberately distorted C(alpha) traces. The entire process, as described, is rapid, requiring of the order of a few minutes for a typical protein on a typical desktop PC. Approximations enable this to be reduced to a few seconds, although this is at the expense of prediction accuracy. This compares very favorably to previously published methods, being sufficiently fast for general use and being one of the most accurate methods. Because the method is not restricted to the reconstruction from only C(alpha) coordinates, reconstruction based on C(beta) coordinates is also demonstrated.     

Powerful simulated-annealing algorithm locates global minimum of protein-folding potentials from multiple starting conformations

Protein-folding potentials, designed with the explicit goal that the global energy minimum correspond to crystallographically observed conformations of protein molecules, may offer great promise toward calculating native protein structures. Achieving this promise, however, depends on finding an effective means of dealing with the multiple-minimum problem inherent in such potentials. In this study, a protein-folding-potential test system has been developed that exhibits the properties of general protein-folding potentials yet has a unique well-defined global energy minimum corresponding to the crystallographically determined conformation of the test molecule. A simulated-annealing algorithm is developed that locates the global minimum of this potential in four of eight test runs from random starting conformations. Exploration of the energy-conformation surface of the potential indicates that it contains the numerous local minima typical of protein-folding potentials and that the global minimum is not easily located by conventional minimization procedures. When the annealing algorithm is applied to a previously developed actual folding potential to analyze the conformation of avian pancreatic polypeptide, a new conformer is located that is lower in energy than any conformer located in previous studies using a variety of minimization techniques.     

Conformational Analysis of Planar Enol Rotamers of 2,4-Pentanedione: an Ab Initio Study

All conformations among different planar enol conformers (rotamers) of 2,4-pentanedione were studied by means of the Hartree-Fock method using the STO-3G** basis set. The calculations were carried out with the Gaussian-98 program. For each conformation, stationary points with the highest energy on the energy curve were found graphically. Several conformations have low energy barriers and correspond to rotations around single bonds. They describe the spatial motion of only one (in most cases, hydrogen) atom or a small molecular fragment. All low energy barriers are in the interval 13-59 kJ·mol^-1. As would be expected, the lowest energy barrier is exhibited by the conformation that leads to the formation of an enol rotamer having an intramolecular H-bond (so-called -shaped form). On the other hand, conformations in which rotation around a bond leads to a break of the intramolecular hydrogen bond have the highest energy barriers. Conformations in which rotation occurs around the double bond have high energy barriers. The influence of the solvents CHCl₃ and CH₃CN on the intramolecular H-bond has also been studied by means of IPCM at the HF/6-31G** level.     

Kinetics of cooperative protein folding involving two separate conformational families

The master equation that describes the kinetics of protein folding is solved numerically for a portion of Staphylococcal Protein A by a Laplace transformation. The calculations are carried out with 50 local-minimum conformations belonging to two conformational families. The master equation allows for transitions among all the 50 conformations in the evolution toward the final folded equilibrium distribution of conformations. It is concluded that the native protein folds in a fast cooperative process. The global energy minimum of a native protein can be reached after a sufficiently long folding time regardless of the initial state and the existence of a large number of local energy minima. Conformations representing non-native states of the protein can transform to the native state even if they do not belong to the native conformational family. Given a starting conformation, the protein molecule can fold to its final conformation through different paths. Finally, when the folding reaches the equilibrium distribution, the protein molecule adopts a set of conformations in which the global minimum has the largest average probability.     

Statistically based reduced representation of amino acid side chains

Preferred conformations of amino acid side chains have been well established through statistically obtained rotamer libraries. Typically, these provide bond torsion angles allowing a side chain to be traced atom by atom. In cases where it is desirable to reduce the complexity of a protein representation or prediction, fixing all side-chain atoms may prove unwieldy. Therefore, we introduce a general parametrization to allow positions of representative atoms (in the present study, these are terminal atoms) to be predicted directly given backbone atom coordinates. Using a large, culled data set of amino acid residues from high-resolution protein crystal structures, anywhere from 1 to 7 preferred conformations were observed for each terminal atom of the non-glycine residues. Side-chain length from the backbone C(alpha) is one of the parameters determined for each conformation, which should itself be useful. Prediction of terminal atoms was then carried out for a second, nonredundant set of protein structures to validate the data set. Using four simple probabilistic approaches, the Monte Carlo style prediction of terminal atom locations given only backbone coordinates produced an average root mean-square deviation (RMSD) of approximately 3 A from the experimentally determined terminal atom positions. With prediction using conditional probabilities based on the side-chain chi(1) rotamer, this average RMSD was improved to 1.74 A. The observed terminal atom conformations therefore provide reasonable and potentially highly accurate representations of side-chain conformation, offering a viable alternative to existing all-atom rotamers for any case where reduction in protein model complexity, or in the amount of data to be handled, is desired. One application of this representation with strong potential is the prediction of charge density in proteins. This would likely be especially valuable on protein surfaces, where side chains are much less likely to be fixed in single rotamers. Prediction of ensembles of structures provides a method to determine the probability density of charge and atom location; such a prediction is demonstrated graphically.