Fast gap‐free enumeration of conformations and sequences for protein design

Despite significant successes in structure‐based computational protein design in recent years, protein design algorithms must be improved to increase the biological accuracy of new designs. Protein design algorithms search through an exponential number of protein conformations, protein ensembles, and amino acid sequences in an attempt to find globally optimal structures with a desired biological function. To improve the biological accuracy of protein designs, it is necessary to increase both the amount of protein flexibility allowed during the search and the overall size of the design, while guaranteeing that the lowest‐energy structures and sequences are found. DEE/A*‐based algorithms are the most prevalent provable algorithms in the field of protein design and can provably enumerate a gap‐free list of low‐energy protein conformations, which is necessary for ensemble‐based algorithms that predict protein binding. We present two classes of algorithmic improvements to the A* algorithm that greatly increase the efficiency of A*. First, we analyze the effect of ordering the expansion of mutable residue positions within the A* tree and present a dynamic residue ordering that reduces the number of A* nodes that must be visited during the search. Second, we propose new methods to improve the conformational bounds used to estimate the energies of partial conformations during the A* search. The residue ordering techniques and improved bounds can be combined for additional increases in A* efficiency. Our enhancements enable all A*‐based methods to more fully search protein conformation space, which will ultimately improve the accuracy of complex biomedically relevant designs. Proteins 2015; 83:1859–1877. © 2015 Wiley Periodicals, Inc.     

Protein design using continuous rotamers

Optimizing amino acid conformation and identity is a central problem in computational protein design. Protein design algorithms must allow realistic protein flexibility to occur during this optimization, or they may fail to find the best sequence with the lowest energy. Most design algorithms implement side-chain flexibility by allowing the side chains to move between a small set of discrete, low-energy states, which we call rigid rotamers. In this work we show that allowing continuous side-chain flexibility (which we call continuous rotamers) greatly improves protein flexibility modeling. We present a large-scale study that compares the sequences and best energy conformations in 69 protein-core redesigns using a rigid-rotamer model versus a continuous-rotamer model. We show that in nearly all of our redesigns the sequence found by the continuous-rotamer model is different and has a lower energy than the one found by the rigid-rotamer model. Moreover, the sequences found by the continuous-rotamer model are more similar to the native sequences. We then show that the seemingly easy solution of sampling more rigid rotamers within the continuous region is not a practical alternative to a continuous-rotamer model: at computationally feasible resolutions, using more rigid rotamers was never better than a continuous-rotamer model and almost always resulted in higher energies. Finally, we present a new protein design algorithm based on the dead-end elimination (DEE) algorithm, which we call iMinDEE, that makes the use of continuous rotamers feasible in larger systems. iMinDEE guarantees finding the optimal answer while pruning the search space with close to the same efficiency of DEE. Availability: Software is available under the Lesser GNU Public License v3. Contact the authors for source code.     

Beyond rotamers: a generative,probabilistic model of side chains in proteins

Background  

Accurately covering the conformational space of amino acid side chains is essential for important applications such as protein design, docking and high resolution structure prediction. Today, the most common way to capture this conformational space is through rotamer libraries - discrete collections of side chain conformations derived from experimentally determined protein structures. The discretization can be exploited to efficiently search the conformational space. However, discretizing this naturally continuous space comes at the cost of losing detailed information that is crucial for certain applications. For example, rigorously combining rotamers with physical force fields is associated with numerous problems.     

PLUG (Pruning of Local Unrealistic Geometries) removes restrictions on biophysical modeling for protein design

Protein design algorithms must search an enormous conformational space to identify favorable conformations. As a result, those that perform this search with guarantees of accuracy generally start with a conformational pruning step, such as dead-end elimination (DEE). However, the mathematical assumptions of DEE-based pruning algorithms have up to now severely restricted the biophysical model that can feasibly be used in protein design. To lift these restrictions, I propose to prune local unrealistic geometries (PLUG) using a linear programming-based method. PLUG's biophysical model consists only of well-known lower bounds on interatomic distances. PLUG is intended as preprocessing for energy-based protein design calculations, whose biophysical model need not support DEE pruning. Based on 96 test cases, PLUG is at least as effective at pruning as DEE for larger protein designs—the type that most require pruning. When combined with the LUTE protein design algorithm, PLUG greatly facilitates designs that account for continuous entropy, large multistate designs with continuous flexibility, and designs with extensive continuous backbone flexibility and advanced nonpairwise energy functions. Many of these designs are tractable only with PLUG, either for empirical reasons (LUTE's machine learning step achieves an accurate fit only after PLUG pruning), or for theoretical reasons (many energy functions are fundamentally incompatible with DEE).     

Motif‐directed redesign of enzyme specificity

Computational protein design relies on several approximations, including the use of fixed backbones and rotamers, to reduce protein design to a computationally tractable problem. However, allowing backbone and off‐rotamer flexibility leads to more accurate designs and greater conformational diversity. Exhaustive sampling of this additional conformational space is challenging, and often impossible. Here, we report a computational method that utilizes a preselected library of native interactions to direct backbone flexibility to accommodate placement of these functional contacts. Using these native interaction modules, termed motifs, improves the likelihood that the interaction can be realized, provided that suitable backbone perturbations can be identified. Furthermore, it allows a directed search of the conformational space, reducing the sampling needed to find low energy conformations. We implemented the motif‐based design algorithm in Rosetta, and tested the efficacy of this method by redesigning the substrate specificity of methionine aminopeptidase. In summary, native enzymes have evolved to catalyze a wide range of chemical reactions with extraordinary specificity. Computational enzyme design seeks to generate novel chemical activities by altering the target substrates of these existing enzymes. We have implemented a novel approach to redesign the specificity of an enzyme and demonstrated its effectiveness on a model system.     

Using quantum mechanics to improve estimates of amino acid side chain rotamer energies

Amino acid side chains adopt a discrete set of favorable conformations typically referred to as rotamers. The relative energies of rotamers partially determine which side chain conformations are more often observed in protein structures and accurate estimates of these energies are important for predicting protein structure and designing new proteins. Protein modelers typically calculate side chain rotamer energies by using molecular mechanics (MM) potentials or by converting rotamer probabilities from the protein database (PDB) into relative free energies. One limitation of the knowledge‐based energies is that rotamer preferences observed in the PDB can reflect internal side chain energies as well as longer‐range interactions with the rest of the protein. Here, we test an alternative approach for calculating rotamer energies. We use three different quantum mechanics (QM) methods (second order Møller‐Plesset (MP2), density functional theory (DFT) energy calculation using the B3LYP functional, and Hartree‐Fock) to calculate the energy of amino acid rotamers in a dipeptide model system, and then use these pre‐calculated values in side chain placement simulations. Energies were calculated for over 36,000 different conformations of leucine, isoleucine, and valine dipeptides with backbone torsion angles from the helical and strand regions of the Ramachandran plot. In a subset of cases these energies differ significantly from those calculated with standard molecular mechanics potentials or those derived from PDB statistics. We find that in these cases the energies from the QM methods result in more accurate placement of amino acid side chains in structure prediction tests. Proteins 2008. © 2007 Wiley‐Liss, Inc.     

Modeling the anti-CEA antibody combining site by homology and conformational search.

A model for an antibody specific for the carcinoembryonic antigen (CEA) has been constructed using a method which combines the concept of canonical structures with conformational search. A conformational search technique is introduced which couples random generation of backbone loop conformations to a simulated annealing method for assigning side chain conformations. This technique was used both to verify conformations selected from the set of known canonical structures and to explore conformations available to the H3 loop in CEA ab initio. Canonical structures are not available for H3 due to its variability in length, sequence, and observed conformation in known antibody structures. Analysis of the results of conformational search resulted in three equally probable conformations for H3 loop in CEA. Force field energies, solvation free energies, exposure of charged residues and burial of hydrophobic residues, and packing of hydrophobic residues at the base of the loop were used as selection criteria. The existence of three equally plausible structures may reflect the high degree of flexibility expected for an exposed loop of this length. The nature of the combining site and features which could be important to interaction with antigen are discussed.     

Dead-end elimination with backbone flexibility

MOTIVATION: Dead-End Elimination (DEE) is a powerful algorithm capable of reducing the search space for structure-based protein design by a combinatorial factor. By using a fixed backbone template, a rotamer library, and a potential energy function, DEE identifies and prunes rotamer choices that are provably not part of the Global Minimum Energy Conformation (GMEC), effectively eliminating the majority of the conformations that must be subsequently enumerated to obtain the GMEC. Since a fixed-backbone model biases the algorithm predictions against protein sequences for which even small backbone movements may result in a significantly enhanced stability, the incorporation of backbone flexibility can improve the accuracy of the design predictions. If explicit backbone flexibility is incorporated into the model, however, the traditional DEE criteria can no longer guarantee that the flexible-backbone GMEC, the lowest-energy conformation when the backbone is allowed to flex, will not be pruned. RESULTS: We derive a novel DEE pruning criterion, flexible-backbone DEE (BD), that is provably accurate with backbone flexibility, guaranteeing that no rotamers belonging to the flexible-backbone GMEC are pruned; we also present further enhancements to BD for improved pruning efficiency. The results from applying our novel algorithms to redesign the beta1 domain of protein G and to switch the substrate specificity of the NRPS enzyme GrsA-PheA are then compared against the results from previous fixed-backbone DEE algorithms. We confirm experimentally that traditional-DEE is indeed not provably-accurate with backbone flexibility and that BD is capable of generating conformations with significantly lower energies, thus confirming the feasibility of our novel algorithms. AVAILABILITY: Contact authors for source code.     

Statistical and conformational analysis of the electron density of protein side chains

Protein side chains make most of the specific contacts between proteins and other molecules, and their conformational properties have been studied for many years. These properties have been analyzed primarily in the form of rotamer libraries, which cluster the observed conformations into groups and provide frequencies and average dihedral angles for these groups. In recent years, these libraries have improved with higher resolution structures and using various criteria such as high thermal factors to eliminate side chains that may be misplaced within the crystallographic model coordinates. Many of these side chains have highly non-rotameric dihedral angles. The origin of side chains with high B-factors and/or with non-rotameric dihedral angles is of interest in the determination of protein structures and in assessing the prediction of side chain conformations. In this paper, using a statistical analysis of the electron density of a large set of proteins, it is shown that: (1) most non-rotameric side chains have low electron density compared to rotameric side chains; (2) up to 15% of chi1 non-rotameric side chains in PDB models can clearly be fit to density at a single rotameric conformation and in some cases multiple rotameric conformations; (3) a further 47% of non-rotameric side chains have highly dispersed electron density, indicating potentially interconverting rotameric conformations; (4) the entropy of these side chains is close to that of side chains annotated as having more than one chi(1) rotamer in the crystallographic model; (5) many rotameric side chains with high entropy clearly show multiple conformations that are not annotated in the crystallographic model. These results indicate that modeling of side chains alternating between rotamers in the electron density is important and needs further improvement, both in structure determination and in structure prediction.     

IRECS: a new algorithm for the selection of most probable ensembles of side-chain conformations in protein models

We introduce a new algorithm, IRECS (Iterative REduction of Conformational Space), for identifying ensembles of most probable side-chain conformations for homology modeling. On the basis of a given rotamer library, IRECS ranks all side-chain rotamers of a protein according to the probability with which each side chain adopts the respective rotamer conformation. This ranking enables the user to select small rotamer sets that are most likely to contain a near-native rotamer for each side chain. IRECS can therefore act as a fast heuristic alternative to the Dead-End-Elimination algorithm (DEE). In contrast to DEE, IRECS allows for the selection of rotamer subsets of arbitrary size, thus being able to define structure ensembles for a protein. We show that the selection of more than one rotamer per side chain is generally meaningful, since the selected rotamers represent the conformational space of flexible side chains. A knowledge-based statistical potential ROTA was constructed for the IRECS algorithm. The potential was optimized to discriminate between side-chain conformations of native and rotameric decoys of protein structures. By restricting the number of rotamers per side chain to one, IRECS can optimize side chains for a single conformation model. The average accuracy of IRECS for the chi1 and chi1+2 dihedral angles amounts to 84.7% and 71.6%, respectively, using a 40 degrees cutoff. When we compared IRECS with SCWRL and SCAP, the performance of IRECS was comparable to that of both methods. IRECS and the ROTA potential are available for download from the URL http://irecs.bioinf.mpi-inf.mpg.de.     

Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm

We describe an algorithm which enables us to search the conformational space of the side chains of a protein to identify the global minimum energy combination of side chain conformations as well as all other conformations within a specified energy cutoff of the global energy minimum. The program is used to explore the side chain conformational energy surface of a number of proteins, to investigate how this surface varies with the energy model used to describe the interactions within the system and the rotamer library. Enumeration of the rotamer combinations enables us to directly evaluate the partition function, and thus calculate the side chain contribution to the conformational entropy of the folded protein. An investigation of these conformations and the relationships between them shows that most of the conformations near to the global energy minimum arise from changes in side chain conformations that are essentially independent; very few result from a concerted change in conformation of two or more residues. Some of the limitations of the approach are discussed. Proteins 33:227–239, 1998. © 1998 Wiley-Liss, Inc.     

Packing and recognition of protein structural elements: A new approach applied to the 4-helix bundle of myohemerythrin

We present a novel search strategy for determining the optimal packing of protein secondary structure elements. The approach is based on conformational energy optimization using a predetermined set of side chain rotamers and appropriate methods for sampling the conformational space of peptide fragments having fixed backbone geometries. An application to the 4-helix bundle of myohemerythrin is presented. It is shown that the conformations of the amino acid side chains are largely determined at the level of helix pairs and that superposition of these results can be used to construct the full bundle. The final solution obtained, taking into account restrictions due to the lateral amphiphilicity of the helices, differs from the native structure by only a 20° rotation of a single helix. © 1993 Wiley-Liss, Inc.     

Excluded volume in protein side-chain packing

The excluded volume occupied by protein side-chains and the requirement of high packing density in the protein interior should severely limit the number of side-chain conformations compatible with a given native backbone. To examine the relationship between side-chain geometry and side-chain packing, we use an all-atom Monte Carlo simulation to sample the large space of side-chain conformations. We study three models of excluded volume and use umbrella sampling to effectively explore the entire space. We find that while excluded volume constraints reduce the size of conformational space by many orders of magnitude, the number of allowed conformations is still large. An average repacked conformation has 20 % of its chi angles in a non-native state, a marked reduction from the expected 67 % in the absence of excluded volume. Interestingly, well-packed conformations with up to 50 % non-native chi angles exist. The repacked conformations have native packing density as measured by a standard Voronoi procedure. Entropy is distributed non-uniformly over positions, and we partially explain the observed distribution using rotamer probabilities derived from the Protein Data Bank database. In several cases, native rotamers that occur infrequently in the database are seen with high probability in our simulation, indicating that sequence-specific excluded volume interactions can stabilize rotamers that are rare for a given backbone. In spite of our finding that 65 % of the native rotamers and 85 % of chi(1) angles can be predicted correctly on the basis of excluded volume only, 95 % of positions can accommodate more than one rotamer in simulation. We estimate that, in order to quench the side-chain entropy observed in the presence of excluded volume interactions, other interactions (hydrophobic, polar, electrostatic) must provide an additional stabilization of at least 0.6 kT per residue in order to single out the native state.     

Rotamer libraries and probabilities of transition between rotamers for the side chains in protein-protein binding

Conformational changes in the side chains are essential for protein-protein binding. Rotameric states and unbound- to-bound conformational changes in the surface residues were systematically studied on a representative set of protein complexes. The side-chain conformations were mapped onto dihedral angles space. The variable threshold algorithm was developed to cluster the dihedral angle distributions and to derive rotamers, defined as the most probable conformation in a cluster. Six rotamer libraries were generated: full surface, surface noninterface, and surface interface-each for bound and unbound states. The libraries were used to calculate the probabilities of the rotamer transitions upon binding. The stability of amino acids was quantified based on the transition maps. The noninterface residues' stability was higher than that of the interface. Long side chains with three or four dihedral angles were less stable than the shorter ones. The transitions between the rotamers at the interface occurred more frequently than on the noninterface surface. Most side chains changed conformation within the same rotamer or moved to an adjacent rotamer. The highest percentage of the transitions was observed primarily between the two most occupied rotamers. The probability of the transition between rotamers increased with the decrease of the rotamer stability. The analysis revealed characteristics of the surface side-chain conformational transitions that can be utilized in flexible docking protocols.     

Side-chain conformational changes upon Protein-Protein Association

Conformational changes upon protein-protein association are the key element of the binding mechanism. The study presents a systematic large-scale analysis of such conformational changes in the side chains. The results indicate that short and long side chains have different propensities for the conformational changes. Long side chains with three or more dihedral angles are often subject to large conformational transition. Shorter residues with one or two dihedral angles typically undergo local conformational changes not leading to a conformational transition. A relationship between the local readjustments and the equilibrium fluctuations of a side chain around its unbound conformation is suggested. Most of the side chains undergo larger changes in the dihedral angle most distant from the backbone. The frequencies of the core-to-surface interface transitions of six nonpolar residues and Tyr are larger than the frequencies of the opposite surface-to-core transitions. The binding increases both polar and nonpolar interface areas. However, the increase of the nonpolar area is larger for all considered classes of protein complexes, suggesting that the protein association perturbs the unbound interfaces to increase the hydrophobic contribution to the binding free energy. To test modeling approaches to side-chain flexibility in protein docking, conformational changes in the X-ray set were compared with those in the docking decoy sets. The results lead to a better understanding of the conformational changes in proteins and suggest directions for efficient conformational sampling in docking protocols.     

Discrete restraint-based protein modeling and the Calpha-trace problem

We present a novel de novo method to generate protein models from sparse, discretized restraints on the conformation of the main chain and side chain atoms. We focus on Calpha-trace generation, the problem of constructing an accurate and complete model from approximate knowledge of the positions of the Calpha atoms and, in some cases, the side chain centroids. Spatial restraints on the Calpha atoms and side chain centroids are supplemented by constraints on main chain geometry, phi/xi angles, rotameric side chain conformations, and inter-atomic separations derived from analyses of known protein structures. A novel conformational search algorithm, combining features of tree-search and genetic algorithms, generates models consistent with these restraints by propensity-weighted dihedral angle sampling. Models with ideal geometry, good phi/xi angles, and no inter-atomic overlaps are produced with 0.8 A main chain and, with side chain centroid restraints, 1.0 A all-atom root-mean-square deviation (RMSD) from the crystal structure over a diverse set of target proteins. The mean model derived from 50 independently generated models is closer to the crystal structure than any individual model, with 0.5 A main chain RMSD under only Calpha restraints and 0.7 A all-atom RMSD under both Calpha and centroid restraints. The method is insensitive to randomly distributed errors of up to 4 A in the Calpha restraints. The conformational search algorithm is efficient, with computational cost increasing linearly with protein size. Issues relating to decoy set generation, experimental structure determination, efficiency of conformational sampling, and homology modeling are discussed.     

Dead‐end elimination with perturbations (DEEPer): A provable protein design algorithm with continuous sidechain and backbone flexibility

Computational protein and drug design generally require accurate modeling of protein conformations. This modeling typically starts with an experimentally determined protein structure and considers possible conformational changes due to mutations or new ligands. The DEE/A* algorithm provably finds the global minimum‐energy conformation (GMEC) of a protein assuming that the backbone does not move and the sidechains take on conformations from a set of discrete, experimentally observed conformations called rotamers. DEE/A* can efficiently find the overall GMEC for exponentially many mutant sequences. Previous improvements to DEE/A* include modeling ensembles of sidechain conformations and either continuous sidechain or backbone flexibility. We present a new algorithm, DEEPer (D ead‐E nd E limination with Per turbations), that combines these advantages and can also handle much more extensive backbone flexibility and backbone ensembles. DEEPer provably finds the GMEC or, if desired by the user, all conformations and sequences within a specified energy window of the GMEC. It includes the new abilities to handle arbitrarily large backbone perturbations and to generate ensembles of backbone conformations. It also incorporates the shear, an experimentally observed local backbone motion never before used in design. Additionally, we derive a new method to accelerate DEE/A*‐based calculations, indirect pruning, that is particularly useful for DEEPer. In 67 benchmark tests on 64 proteins, DEEPer consistently identified lower‐energy conformations than previous methods did, indicating more accurate modeling. Additional tests demonstrated its ability to incorporate larger, experimentally observed backbone conformational changes and to model realistic conformational ensembles. These capabilities provide significant advantages for modeling protein mutations and protein–ligand interactions. Proteins 2013. © 2012 Wiley Periodicals, Inc.     

Conformational energy calculations on glycosylated turns in glycoproteins

Analysis of the amino acid sequence of glycoproteins has suggested the β-turn as a likely site of glycosylation in glycoproteins. According to this model, the peptide chain traverses the interior of a globular protein, reversing its direction at the protein surface, a likely point for the attachment of hydrophilic carbohydrate residues. In order to search for plausible conformations of glycosylated β-turns in asparagine-linked glycoproteins, we have adapted the conformational energy calculation method of Scheraga and coworkers for use in carbohydrates. The parameters for nonbonded and hydrogen-bonded interactions have been published, and electrostatic parameters are derived from a CNDO calculation on a model glycopeptide. Our results indicate that the orientation of the glycosyl amide bond having the amide proton nearly trans to the anomeric proton of the sugar has the lowest energy. Although CD and nmr experiments in our laboratory have consistently found this conformation, our calculations show the conformation having these two protons in a cis relationship to lie very close in energy. Calculations on the glycopeptide linkage model, α-N-acetyl, δ-N(2-acetamido-1,2-dideoxy-β-D -glucopyranosyl)-N′-methyl-L -asparaginyl amide show that several distinct geometries are allowed for glycosylated β-turns. For a type I β-turn, three conformations of the glycosylated side chain are found within 4 kcal of the minimum, while two conformations of the glycosylated side chain are allowed for a type II turn. The hydrogen-bonded C7 conformation is also allowed. Stereoviews of the low-energy conformations reveal no major hydrogen-bonding interaction between the peptide and sugar.     

Salt bridges: geometrically specific, designable interactions

Salt bridges occur frequently in proteins, providing conformational specificity and contributing to molecular recognition and catalysis. We present a comprehensive analysis of these interactions in protein structures by surveying a large database of protein structures. Salt bridges between Asp or Glu and His, Arg, or Lys display extremely well-defined geometric preferences. Several previously observed preferences are confirmed, and others that were previously unrecognized are discovered. Salt bridges are explored for their preferences for different separations in sequence and in space, geometric preferences within proteins and at protein-protein interfaces, co-operativity in networked salt bridges, inclusion within metal-binding sites, preference for acidic electrons, apparent conformational side chain entropy reduction on formation, and degree of burial. Salt bridges occur far more frequently between residues at close than distant sequence separations, but, at close distances, there remain strong preferences for salt bridges at specific separations. Specific types of complex salt bridges, involving three or more members, are also discovered. As we observe a strong relationship between the propensity to form a salt bridge and the placement of salt-bridging residues in protein sequences, we discuss the role that salt bridges might play in kinetically influencing protein folding and thermodynamically stabilizing the native conformation. We also develop a quantitative method to select appropriate crystal structure resolution and B-factor cutoffs. Detailed knowledge of these geometric and sequence dependences should aid de novo design and prediction algorithms.