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     

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.     

Dramatic performance enhancements for the FASTER optimization algorithm

FASTER is a combinatorial optimization algorithm useful for finding low-energy side-chain configurations in side-chain placement and protein design calculations. We present two simple enhancements to FASTER that together improve the computational efficiency of these calculations by as much as two orders of magnitude with no loss of accuracy. Our results highlight the importance of choosing appropriate initial configurations, and show that efficiency can be improved by stringently limiting the number of positions that are allowed to relax in response to a perturbation. The changes we describe improve the quality of solutions found for large-scale designs, and allow them to be found in hours rather than days. The improved FASTER algorithm finds low-energy solutions more efficiently than common optimization schemes based on the dead-end elimination theorem and Monte Carlo. These advances have prompted investigations into new methods for force field parameterization and multiple state design.     

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     

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.     

Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem

Recent advances in protein design have demonstrated the effectiveness of optimization algorithms based on the dead-end elimination theorem. The algorithms solve the combinatorial problem of finding the optimal placement of side chains for a set of backbone coordinates. Although they are powerful tools, these algorithms have severe limitations when the number of side chain rotamers is large. This is due to the high-order time dependence of the aspect of the calculation that deals with rotamer doubles. We present three independent algorithmic enhancements that significantly increase the speed of the doubles computation. These methods work by using quantities that are inexpensive to compute as a basis for forecasting which expensive calculations are worthwhile. One of the methods, the comparison of extrema, is derived from analytical considerations, and the remaining two, the “magic-bullet” and the “q_rs” and “q_uv” metrics, are based on empirical observation of the distribution of energies in the system. When used together, these methods effect an overall speed improvement of as much as a factor of 47, and for the doubles aspect of the calculation, a factor of 95. Together, these enhancements extend the envelope of inverse folding to larger proteins by making formerly intractable calculations attainable in reasonable computer time. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1505–1514, 1998     

Pareto optimization in computational protein design with multiple objectives

The optimization for function in computational design requires the treatment of, often competing, multiple objectives. Current algorithms reduce the problem to a single objective optimization problem, with the consequent loss of relevant solutions. We present a procedure, based on a variant of a Pareto algorithm, to optimize various competing objectives in protein design that allows reducing in several orders of magnitude the search of the solution space. Our methodology maintains the diversity of solutions and provides an iterative way to incorporate automatic design methods in the design of functional proteins. We have applied our systematic procedure to design enzymes optimized for both catalysis and stability. However, this methodology can be applied to any computational chemistry application requiring multi-objective combinatorial optimization techniques.     

Reference energy extremal optimization: a stochastic search algorithm applied to computational protein design

We adapt a combinatorial optimization algorithm, extremal optimization (EO), for the search problem in computational protein design. This algorithm takes advantage of the knowledge of local energy information and systematically improves on the residues that have high local energies. Power-law probability distributions are used to select the backbone sites to be improved on and the rotamer choices to be changed to. We compare this method with simulated annealing (SA) and motivate and present an improved method, which we call reference energy extremal optimization (REEO). REEO uses reference energies to convert a problem with a structured local-energy profile to one with more random profile, and extremal optimization proves to be extremely efficient for the latter problem. We show in detail the large improvement we have achieved using REEO as compared to simulated annealing and discuss a number of other heuristics we have attempted to date.     

Maintaining solvent accessible surface area under rotamer substitution for protein design

Although quantities derived from solvent accessible surface areas (SASA) are useful in many applications in protein design and structural biology, the computational cost of accurate SASA calculation makes SASA-based scores difficult to integrate into commonly used protein design methodologies. We demonstrate a method for maintaining accurate SASA during a Monte Carlo search of sequence and rotamer space for a fixed protein backbone. We extend the fast Le Grand and Merz algorithm (Le Grand and Merz, J Comput Chem, 14, 349), which discretizes the solvent accessible surface for each atom by placing dots on a sphere and combines Boolean masks to determine which dots are exposed. By replacing semigroup operations with group operations (from Boolean logic to counting dot coverage) we support SASA updates. Our algorithm takes time proportional to the number of atoms affected by rotamer substitution, rather than the number of atoms in the protein. For design simulations with a one hundred residue protein our approach is approximately 145 times faster than performing a Le Grand and Merz SASA calculation from scratch following each rotamer substitution. To demonstrate practical effectiveness, we optimize a SASA-based measure of protein packing in the complete redesign of a large set of proteins and protein-protein interfaces.     

Adaptation of a fast Fourier transform-based docking algorithm for protein design

Designing proteins with novel protein/protein binding properties can be achieved by combining the tools that have been developed independently for protein docking and protein design. We describe here the sequence-independent generation of protein dimer orientations by protein docking for use as scaffolds in protein sequence design algorithms. To dock monomers into sequence-independent dimer conformations, we use a reduced representation in which the side chains are approximated by spheres with atomic radii derived from known C2 symmetry-related homodimers. The interfaces of C2-related homodimers are usually more hydrophobic and protein core-like than the interfaces of heterodimers; we parameterize the radii for docking against this feature to capture and recreate the spatial characteristics of a hydrophobic interface. A fast Fourier transform-based geometric recognition algorithm is used for docking the reduced representation protein models. The resulting docking algorithm successfully predicted the wild-type homodimer orientations in 65 out of 121 dimer test cases. The success rate increases to approximately 70% for the subset of molecules with large surface area burial in the interface relative to their chain length. Forty-five of the predictions exhibited less than 1 A C(alpha) RMSD compared to the native X-ray structures. The reduced protein representation therefore appears to be a reasonable approximation and can be used to position protein backbones in plausible orientations for homodimer design.     

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.     

The minimized dead-end elimination criterion and its application to protein redesign in a hybrid scoring and search algorithm for computing partition functions over molecular ensembles

One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly-observed low-energy side-chain conformations, further increases the complexity of the redesign problem. A dominant algorithm for protein redesign is dead-end elimination (DEE), which prunes the majority of candidate conformations by eliminating rigid rotamers that provably are not part of the global minimum energy conformation (GMEC). The identified GMEC consists of rigid rotamers (i.e., rotamers that have not been energy-minimized) and is thus referred to as the rigid-GMEC. As a postprocessing step, the conformations that survive DEE may be energy-minimized. When energy minimization is performed after pruning with DEE, the combined protein design process becomes heuristic, and is no longer provably accurate: a conformation that is pruned using rigid-rotamer energies may subsequently minimize to a lower energy than the rigid-GMEC. That is, the rigid-GMEC and the conformation with the lowest energy among all energy-minimized conformations (the minimized-GMEC) are likely to be different. While the traditional DEE algorithm succeeds in not pruning rotamers that are part of the rigid-GMEC, it makes no guarantees regarding the identification of the minimized-GMEC. In this paper we derive a novel, provable, and efficient DEE-like algorithm, called minimized-DEE (MinDEE), that guarantees that rotamers belonging to the minimized-GMEC will not be pruned, while still pruning a combinatorial number of conformations. We show that MinDEE is useful not only in identifying the minimized-GMEC, but also as a filter in an ensemble-based scoring and search algorithm for protein redesign that exploits energy-minimized conformations. We compare our results both to our previous computational predictions of protein designs and to biological activity assays of predicted protein mutants. Our provable and efficient minimized-DEE algorithm is applicable in protein redesign, protein-ligand binding prediction, and computer-aided drug design.     

Fast search algorithms for computational protein design

One of the main challenges in computational protein design (CPD) is the huge size of the protein sequence and conformational space that has to be computationally explored. Recently, we showed that state‐of‐the‐art combinatorial optimization technologies based on Cost Function Network (CFN) processing allow speeding up provable rigid backbone protein design methods by several orders of magnitudes. Building up on this, we improved and injected CFN technology into the well‐established CPD package Osprey to allow all Osprey CPD algorithms to benefit from associated speedups. Because Osprey fundamentally relies on the ability of to produce conformations in increasing order of energy, we defined new strategies combining CFN lower bounds, with new side‐chain positioning‐based branching scheme. Beyond the speedups obtained in the new ‐CFN combination, this novel branching scheme enables a much faster enumeration of suboptimal sequences, far beyond what is reachable without it. Together with the immediate and important speedups provided by CFN technology, these developments directly benefit to all the algorithms that previously relied on the DEE/ combination inside Osprey* and make it possible to solve larger CPD problems with provable algorithms. © 2016 Wiley Periodicals, Inc.     

Systematic and efficient side chain optimization for molecular docking using a cheapest‐path procedure

Molecular docking of small‐molecules is an important procedure for computer‐aided drug design. Modeling receptor side chain flexibility is often important or even crucial, as it allows the receptor to adopt new conformations as induced by ligand binding. However, the accurate and efficient incorporation of receptor side chain flexibility has proven to be a challenge due to the huge computational complexity required to adequately address this problem. Here we describe a new docking approach with a very fast, graph‐based optimization algorithm for assignment of the near‐optimal set of residue rotamers. We extensively validate our approach using the 40 DUD target benchmarks commonly used to assess virtual screening performance and demonstrate a large improvement using the developed side chain optimization over rigid receptor docking (average ROC AUC of 0.693 vs. 0.623). Compared to numerous benchmarks, the overall performance is better than nearly all other commonly used procedures. Furthermore, we provide a detailed analysis of the level of receptor flexibility observed in docking results for different classes of residues and elucidate potential avenues for further improvement. © 2013 Wiley Periodicals, Inc.     

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     

A novel method for enzyme design

Rational design of enzymes is a stringent test of our understanding of protein structure and function relationship, which also has numerous potential applications. We present a novel method for enzyme design that can find good candidate protein scaffolds in a protein-ligand database based on vector matching of key residues. Residues in the vicinity of the active site were also compared according to a similarity score between the scaffold protein and the target enzyme. Suitable scaffold proteins were selected, and the side chains of residues around the active sites were rebuilt using a previously developed side-chain packing program. Triose phosphate isomerase (TIM) was used as a validation test for enzyme design. Selected scaffold proteins were found to accommodate the enzyme active sites and successfully form a good transition state complex. This method overcomes the limitations of the current enzyme design methods that use limited number of protein scaffold and based on the position of ligands. As there are a large number of protein scaffolds available in the Protein Data Band, this method should be widely applicable for various types of enzyme design.     

An object-oriented library for computational protein design

Recent advances in computational protein design have established it as a viable technique for the rational generation of stable protein sequences, novel protein folds, and even enzymatic activity. We present a new and object-oriented library of code, written specifically for protein design applications in C(++), called EGAD Library. The modular fashion in which this library is written allows developers to tailor various energy functions and minimizers for a specific purpose. It also allows for the generation of novel protein design applications with a minimal amount of code investment. It is our hope that this will permit labs that have not considered protein design to apply it to their own systems, thereby increasing its potential as a tool in biology. We also present various uses of EGAD Library: in the development of Interaction Viewer, a PyMOL plug-in for viewing interactions between protein residues; in the repacking of protein cores; and in the prediction of protein-protein complex stabilities.     

A quantum chemical method for rapid optimization of protein structures

A quantum chemical method for rapid optimization of protein structures is proposed. In this method, a protein structure is treated as an assembly of amino acid units, and the geometry optimization of each unit is performed with taking the effect of its surrounding environment into account. The optimized geometry of a whole protein is obtained by repeated application of such a local optimization procedure over the entire part of the protein. Here, we implemented this method in the MOPAC program and performed geometry optimization for three different sizes of proteins. Consequently, these results demonstrate that the total energies of the proteins are much efficiently minimized compared with the use of conventional optimization methods, including the MOZYME algorithm (a representative linear-scaling method) with the BFGS routine. The proposed method is superior to the conventional methods in both CPU time and memory requirements.     

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.