Chapter 12Nonribosomal Code and K* Algorithms for Ensemble-Based Protein Design

12 Nonribosomal Code and K*K^* Algorithms for Ensemble-Based Protein Design

Protein redesign plays an important role in the realization of novel molecular function and drug design. In this chapter, we introduce an algorithm for the protein redesign problem, which combines a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm [13, 22]. The algorithm has been applied to redesign enzymes [2], and we begin by describing those enzymes’ biological function.

Nonribosomal Peptide Synthetase (NRPS) Enzymes

Nonribosomal peptide synthetase (NRPS) enzymes, usually expressed in microorganisms like bacteria and fungi, complement the traditional ribosomal peptide synthesis pathway. They are also the sources of hundreds of peptidelike products with pharmaceutical properties, including natural antibiotics, antifungals, antivirals, anticancer therapeutics, immunosuppressants, and siderophores. Enzymes of the NRPS pathway have multiple domains with individual functions acting in an assemblyline fashion. The ribosomal machinery is not used. It is commonly believed that the substrate specificity of the NRPS enzymes is dictated primarily by the “gatekeeper” adenylation (A) domain, and recent evidence also indicates that the condensation (C), thiolation (T), and epimerization (E) domains carry some specificity as well.

NRPS enzyme redesign methods can be divided into two main techniques, domain-swapping and active site modification through site-directed mutagenesis. Domain-swapping techniques modify NRPS enzymes by swapping an adenylation domain of an existing NRPS enzyme for an adenylation domain from a second, different NRPS enzyme. Active site modification through site-directed mutagenesis utilizes structural information of the GrsA-PheA NRPS enzyme. GrsA-PheA is the phenylalanine (Phe) adenylation domain (PheA) of the of gramicidin synthetase A (GrsA) enzyme (figure 12.1, plate 11). Gramicidin synthetase has two modules, A and B. Confusingly, the “A” in PheA stands for adenylation whereas the “A” in GrsA stands for the A (as opposed to B) module.

From sequence alignment of GrsA-PheA with 160 other known adenylation domains, a “signature sequence” can be derived for each adenylation domain by extracting those residues that align with the structurally determined substrate-binding pocket of the GrsA-PheA crystal structure [27]. The mapping between substrate specificity and the amino acid sequence of NRPS domains is sometimes called the nonribosomal code. Structure-based protein design algorithms provide a powerful tool for predicting, deciphering, and extending the nonribosomal code.

Figure 12.1 (plate 11) (Top) Gramicidin S synthetase is composed of two NRPS proteins, GrsA (3 domains) and GrsB (13 domains). Gramicidin S is produced in an assemblyline manner where two D-Phe-L-Pro-L-Val-L-Orn-L-Leu peptides are joined and cyclized. (A, Adenylation; T, Thiolation (peptidyl carrier protein); E, Epimerization; C, Condensation; TE, Thioesterase). (Bottom) The GrsA-PheA domain controls incorporation of the first amino acid in the synthesis of the antibiotic gramicidin. (Left) The natural gramicidin construct is shown with the incorporated phenylalanine shown in red. By changing the substrate specificity of the GrsA-PheA domain to accept leucine, it may be possible to create a modified gramicidin (right) where the phenylalanines have been replaced by leucine (blue).

K-star (K*K^*) Algorithm Basics

Georgiev et al. and Lilien et al. [13, 22] developed an ensemble scoring method K*K^* (pronounced “K star”) to model the protein-ligand binding in active-site mutants. Since it is not currently possible to compute exact partition functions for complex molecular species, K*K^* approximates these partition functions with the use of rotamerically based conformational ensembles.

Protein-ligand binding for a predicted mutant protein is modeled using the following K*K^* equation:

K*=qPLqPqL.(12.1)K^* = \frac{q_{PL}}{q_P q_L}. \quad (12.1)

K*K^* is derived to be an approximation to the true association (binding) constant KA=1/KDK_A = 1/K_D by expressing each species’ chemical potential as a function of the species partition function qq and solving for the equilibrium condition (further details are provided in [22]). To compute exact partition functions for complex molecular species appears to require integrating an exact energy function over a molecule’s entire conformational space. We therefore approximate these partition functions with the use of rotamerically based conformational ensembles:

qPL=∑b∈Bexp⁡(−Eb/RT),qP=∑f∈Fexp⁡(−Ef/RT),qL=∑l∈Lexp⁡(−El/RT),(12.2)q_{PL} = \sum_{b \in B} \exp(-E_b/RT), \quad q_P = \sum_{f \in F} \exp(-E_f/RT), \quad q_L = \sum_{l \in L} \exp(-E_l/RT), \quad (12.2) where BB , FF , and LL represent rotamer-based ensembles for the bound protein-ligand complex (PLPL), the free protein (PP), and the free ligand (LL), respectively, EsE_s is the energy of conformation ss , RR is the gas constant, and TT is the temperature in Kelvin. The accuracy with which K*K^* approximates KAK_A is proportional to the accuracy of the partition function approximation used.

When applying K*K^* to a protein-ligand system, a number of choices must be made with respect to ensemble generation and single-structure scoring, where single-structure scoring is the method by which each individual member of the ensemble is scored. The choices made in ensemble scoring should strike a balance between fidelity to the underlying physical biochemistry and computational feasibility. Lilien et al. [22] first posit a hypothetical brute-force algorithm for mutation search: (1) generate all conformations in each of the molecular ensembles by fixing the protein backbone and using a rotamer library to vary the side-chain conformations; (2) use a numerical minimization procedure with the AMBER energy function [4] (plus the EEF1 [20] solvation model) to energy-minimize each generated conformation [13, 2]; (3) compute each partition function (eq. 12.2) and then combine them to obtain an overall K*K^* score (eq. 12.1).

However, more efficient algorithms than brute-force are developed in Georgiev et al. and Lilien et al. [22, 13]. To search for the optimal mutation sequence more efficiently, mutation space filters and conformation space pruning are employed. Mutation space filters include two filters: the sequence-space filter, a residue type filter, which restricts the mutation search to include only a subset of amino acids based on compatibility with the target substrate; and the volume filter, which removes mutations that significantly over-or underpack the substrate-bound active site relative to the wildtype. These two filters prune a combinatorial number of conformations from consideration and eliminate the majority of conformations early in the mutation search.

Next, since conformations with large energies are unlikely to be assumed and contribute only a vanishingly small amount to the partition function, it is reasonable to prune high-energy conformations from consideration. Chen et al. and Georgiev et al. [13, 2] employed a minimized dead-end elimination (“minDEE”) strategy (see chapter 11, and section 12.5) that generates conformations and prunes high-energy conformations and mutations (figure 12.2) to enumerate structures and sequences in gap-free order of energy. By regarding these low-energy conformations as an ensemble of structures, and observing that high-energy structures contribute little to the partition functions, a rigorous threshold for stopping the enumeration can be proven, guaranteeing that a partition function within (1−ε)(1 - \varepsilon) of the correct answer will be computed. This allows the construction of a provably good ε\varepsilon -approximation algorithm for the binding constant [13]. Figure 12.2 illustrates pruning by a steric filter: DEE and minDEE operate by reducing the branching factor in the tree, at many nodes at once.

Figure 12.2 An example conformation tree. The rotamers of flexible residue ii are represented by the branches at depth ii . Internal nodes of a conformation tree represent partially assigned conformations. 𝒙\mathbf{x} ’s represent nodes of the conformation tree where steric clash has been identified among a partially assigned conformation. All children of 𝒙\mathbf{x} nodes are pruned and not considered.

Here is the basic intuition behind the K*K^* algorithm. When ignoring the pruned conformations, a so-called intramutation pruning is then applied during the computation of the partition function for a single mutation. The intramutation pruning algorithm is capable of guaranteeing any desired approximation accuracy to the true partition function, as shown in figure 12.3. That is, a conformation cj+1c_{j+1} can be pruned if it satisfies B(cj+1)≥−RTln⁡(qj*ε−pj*)B(c_{j+1}) \geq -RT \ln(q_j^* \varepsilon - p_j^*) , and by induction, if all pruned conformations satisfy this condition, then at the end of the computation, qj+1*q_{j+1}^* will be an ε\varepsilon -approximation to qnq_n , the true partition function.

The algorithm in figure 12.3 still has to examine every conformation, and therefore provides a merely constant-factor speed-up over a naïve algorithm. The improved algorithm of Georgiev et al. [13] uses the minDEE/ A*A^* algorithm as a preprocessing filter for K*K^* . A simplified sketch of this algorithm is shown in figure 12.4. MinDEE/ A*/K*A^*/K^* is an efficient algorithm for computing the qpLq_{pL} , qpq_p , and qLq_L partition functions, which are used to compute a K*K^* approximation score for a given mutation sequence. Using the A*A^* algorithm with minDEE, we can generate the conformations of a rotamerically based ensemble in order of increasing lower bounds on the conformation’s minimized energy. We can efficiently compute the lower bound on a conformation’s energy as a sum of precomputed pairwise minimum energy terms [13]. As each conformation cc is generated from the conformation tree, we compare its lower bound B(c)B(c) on the conformational energy to a moving stop-threshold and halt the A*A^* search once B(c)B(c) becomes greater than the threshold. The A*A^* algorithm guarantees that all remaining conformations will have minimized energies above the stop-threshold. Georgiev et al. [13] prove that a partial partition function q*q^* computed using only those conformations with energies below (i.e., better than) the stop-threshold will lie within a factor of ε\varepsilon of the true partition function qq . Note that, by definition, q≥q*q \geq q^* . Thus, q*q^* is an ε\varepsilon -approximation to qq , that is, q*≥(1−ε)qq^* \geq (1 - \varepsilon)q .

Let n←n \leftarrow Number of rotameric conformations
Let c←c \leftarrow Rotameric conformations
Initialize: q*←0q^* \leftarrow 0 , p*←0p^* \leftarrow 0
for j=1j = 1 to nn
    if B(cj)≤−RTln⁡(q*ε−p*)B(c_j) \leq -RT \ln(q^* \varepsilon - p^*)
         q*←q*+exp⁡(−ComputeMinEnergy(cj)/RT)q^* \leftarrow q^* + \exp(-\text{ComputeMinEnergy}(c_j)/RT)
    else
         p*←p*+exp⁡(−B(cj)/RT)p^* \leftarrow p^* + \exp(-B(c_j)/RT)
Return q*q^*

Figure 12.3 Intramutation pruning, Constant-factor speed-up. Here q*q^* is the running approximation to the partition function, and p*p^* is an upper bound on the partition function of the pruned conformations. The function B(⋅)B(\cdot) computes a lower energy bound for the given conformation. The function ComputeMinEnergy(⋅)\text{ComputeMinEnergy}(\cdot) returns the energy of the energy-minimized conformation as computed using steepest-descent minimization and an implementation of the AMBER energy function. Later work used more sophisticated energy functions [13, 2]. At the end, q*q^* represents an ε\varepsilon -approximation to the true partition function qq such that q≥q*≥(1−ε)qq \geq q^* \geq (1 - \varepsilon)q .

Initialize: n←n \leftarrow Number of rotameric conformations; q*←0q^* \leftarrow 0
while ( n>0n > 0 )
     c←c \leftarrow GetNextAStarConf()
    if B(c)≤−RT(ln⁡(q*ρ−kexp⁡(−E0/RT))−ln⁡n)B(c) \leq -RT (\ln(q^* \rho - k \exp(-E_0/RT)) - \ln n)
         q*←q*+exp⁡(−ComputeMinEnergy(c)/RT)q^* \leftarrow q^* + \exp(-\text{ComputeMinEnergy}(c)/RT)
         n←n−1n \leftarrow n - 1
    else Return q*q^*
if q*ρ≥kexp⁡(−E0/RT)q^* \rho \geq k \exp(-E_0/RT)
    Return q*q^*

Figure 12.4 Efficient partition function computation with energy minimization using the A* search. minDEE/A*\text{minDEE}/\text{A*} provides a combinatorial-factor speed-up. q*q^* is the running approximation to the partition function. The function B(⋅)B(\cdot) computes the energy lower bound for the given conformation [13]. The function ComputeMinEnergy(⋅)\text{ComputeMinEnergy}(\cdot) returns a conformation’s energy after energy minimization. The function GetNextAStarConf()\text{GetNextAStarConf}() returns the next conformation from the A* search. Define ρ=ε1−ε\rho = \frac{\varepsilon}{1-\varepsilon} . p*p^* is the partition function computed over the set PP of conformations pruned by minDEE\text{minDEE} , so that p*≤kexp⁡(−E0/RT)p^* \leq k \exp(-E_0/RT) , where |P|=k|P| = k . E0E_0 is the minimum lower energy bound among all conformations containing at least one pruned rotamer. Upon completion, q*q^* represents an ε\varepsilon -approximation to the true partition function qq , such that q≥q*≥(1−ε)qq \geq q^* \geq (1 - \varepsilon)q . Simplified version of figure 4 from [13].

The application of the minDEE criterion [13] for each rotamer iri_r requires that the corresponding minimum energy terms are accessed. Hence, we can piggyback the computation of a lower bound BirB_{i_r} on the energy of all conformations that contain a pruned rotamer iri_r . Let E0E_0 be the minimum lower energy bound among all conformations containing at least one pruned rotamer,

E0=minir∈SBir,E_0 = \min_{i_r \in S} B_{i_r}, where SS is the set of rotamers pruned by minDEE. E0E_0 can be precomputed during the minDEE stage and prior to the A*A^* search. Let p*p^* be the partition function computed over the set PP of conformations pruned by minDEE, so that p*≤kexp⁡(−E0/RT)p^* \leq k \exp(-E_0/RT) , where |P|=k|P| = k . We can then guarantee an ε\varepsilon -approximation to the full partition function qq using the minDEE/ A*/K*A^*/K^* algorithm in figure 12.4. Somewhat surprisingly, the algorithm can ignore a combinatorial number of conformations, and therefore provides a combinatorial-factor speed up, while still guaranteeing to compute an ε\varepsilon -approximation.

We have described intramutation pruning, namely, conditions under which a conformation could be pruned when computing a single partition function for a single mutation. What about pruning across mutations?

When using K*K^* to perform a mutation search, we can bootstrap the pruning condition for improved efficiency (by caching partition functions, we can exploit K*K^* bounds from other mutations in the same search). Similarly to the development above, pruned conformations are not energy-minimized, thereby saving time in the overall mutation search. Georgiev et al. and Lilien et al. [22, 13] show how, in a mutation search, the partition-function ε\varepsilon -approximation pruning conditions can exploit the partition functions previously computed for other, different mutation sequences evaluated earlier in that search. Therefore, we call this intermutation pruning: Georgiev et al. and Lilien et al. [22, 13] derive a lower bound on the partition function that allows us to prune more conformations earlier in the search.

In summary, four levels of approximation are used in computing K*K^* scores. (1) A rotamer library is used to model side-chain conformations. (2) Sterically disallowed rotamer-based conformations are combinatorially pruned. (3) Intra-and intermutation pruning methods are used to skip evaluation of conformations that are not required to compute ε\varepsilon -approximations to the partition function and K*K^* values. (4) In computing partition functions and K*K^* values, the algorithm starts with discrete rotamers and then performs bounded minimization. Finally, in the exposition above, and in many other protein design algorithms, the backbone is fixed. However, this restriction can be lifted, and some backbone flexibility modeled, as we discuss later in this chapter.

Energy Functions

Any pairwise energy function can be used in K*K^* . The default K*K^* energy function includes the Lazaridis-Karplus EEF1 pairwise solvation energy term [20]. A list of some energy functions used in protein design (including K*K^*) is given in table 12.1. Improvements to protein design

Table 12.1 Some energy functions used in protein design

FF a vdW b elect c H bond d dihed e bonds f angles g entropy h solv i stats j other k
Amber [4] A • • implicit l • • • • • • •
Dreidning [26] D • • • • • • • • • •
CHARMM [25] C • • implicit l • • • • • • •
Mayo [29] D • • • • • • • • • •
Baker [10] C • • • • • • • • • •
Kuhlman [11] C • • • • • • • • • •
Hellinga [19] C • • • • • • • • • •
Dunbrack [9] O • • • • • • • • • •
K*, 2005 [23] A • • implicit l • • • ensembles • • •
K*, 2009 [13] A • • implicit l • • • ensembles • • •
DEE/A* [13] A • • implicit l • • • • • • •
minDEE/A* [13] A • • implicit l • • • • • • •
BD/A* [14] A • • implicit l • • • • • • •
brDEE/A* [15] A • • implicit l • • • • • • •

aForce field parameters: A if the corresponding energy function uses the AMBER force field; C—CHARMM; D—DREIDNING; and O—other. The “•” in a column for bvan der Waals, celectrostatic, dhydrogen bonding, ehydrogen bonding, fdihedral, gbonds, hangles, ientropy, jsolvation, and kstatistical terms, signifies that the corresponding energy function has some representation for the respective energy term. The kother column contains terms that cannot be readily classified in the preceding columns. lHydrogen bonding is modeled by the charges and the vdW parameters of the force field; mInversion energies; nUrey-Bradley and improper energies; oRotamer free energies modeled by —In Pr(rol/AA, φ, ψ) and a bonus for close unlike charges; pAmino acid reference energies Eref(AA); qAA preference for core/surface from PDB; rLinear repulsive vdW; sNormalized —In Pr(rol/AA, φ, ψ); tCan easily be added; see section 12.3.

energy functions can be implemented, and in some cases they are quite helpful to improve the accuracy of the predictions. Some of these improvements try to incorporate more accurate physics; some introduce statistics from known high-resolution crystal structures; and some use statistical parameter estimation or machine learning techniques to fit the weights and parameters in the energy function terms, so that the results of the design algorithm jibe better with experimental data.

For example, one can use a rotamer probability term such as the (normalized)

−ln⁡Pr⁡(rot|AA,ϕ,ψ)(12.3)-\ln \Pr(rot|AA, \phi, \psi) \quad (12.3) score employed by Dunbrack and co-workers [9]; this is the negative natural logarithm of the probability (across a distribution of structures in a database) of a rotamer given the amino acid type and backbone dihedral angles. These probabilities can be obtained from the Richardsons’ rotamer library [23] and also from a second library they have provided that has a finer sampling. Other enhancements to energy functions can include: scaling the van der Waals (vdW) radii (which can allow for limited overpacking, and therefore compensate for the lack of backbone flexibility in fixed-backbone redesign [7]), and a distance-dependent dielectric [28].

The original K*K^* scoring function [22] used the binding energy, without an explicit term to disfavor mutations that destabilize the protein versus the unfolded state. A rigorous solution to this problem requires negative design against the unfolded state [17, 1]. In principle, Backbone-flexible DEE (the BD algorithm; see section 12.6) can model backbone flexibility for negative design against a range of backbone competitors [14]. While a precise description of the ensemble for the unfolded state can sometimes be constructed from experimental data (see chapter 7), this process is nontrivial. Hence, the selection of charged residues at buried positions is discouraged by excluding polar residues from buried positions and by constraining the amino acid composition (core, surface, and active site compatible with a particular ligand) [22]. Similarly, hydrophobic residues are excluded from surface positions to prevent aggregation [22]. Such sequence constraints are expedient, but a more general approach is desirable [17, 1]. In the newer K*K^* energy function [13, 2], the solvation term from the EEF1 model [20] implicitly remedies this problem to some extent. One can also introduce an explicit destabilization penalty, which may be necessary when introducing buried polar residues to bind more polar substrates. This may be done by penalizing the burial of polar surface area [6, 5].

Note that minDEE/A* [13] and BD (section 12.6 and [14]) can be used either for GMEC-based design or for ensemble-based design (K*K^*). An explicit empirical entropy term need not be used for K*K^* , since the K*K^* method of ensemble scoring encompasses a measure of conformational entropy through use of the partition function over ligand and side-chain conformations. However, for GMEC-based redesign such as minDEE/A* (without ensembles), the empirical, amino acid–specific entropic penalties suggested by Looger and Hellinga [18] (e.g., for Met residues) can be incorporated. An explicit amino acid reference energy term [10] is not necessary for K*K^* , since the K*K^* method of ensemble scoring divides partition functions for the bound and unbound states (which would cause the reference energies to cancel out).

Redesigning Enzymes with K*K^*

The work of Chen et al. and Lilien et al. [22, 2] constructed a structural model based on the crystal structure of GrsA-PheA (PDB id: 1AMU), which consists of 9 active site residues (D235, A236, W239, T278, I299, A301, A322, I330, C331), the 30 residues with at least one atom within 8 Å of the active site (termed the steric shell), the amino acid substrate, and the AMP cofactor. In structure 1AMU [3], and also in the K*K^* -predicted structures, residues 235D and 517K make hydrogen bonds to the amino acid backbone of the ligand, thereby stabilizing the substrate in a productive orientation for catalysis.

Flexible residues are represented by rotamers from the Richardsons’ rotamer library [23]. Rotameric-based conformations in BB , FF , and LL (eq. 12.2) that survive minDEE are enumerated in order of lower-bound energy by A*A^* , and are minimized by steepest-descent minimization using the AMBER-EEFI energy function (section 12.3) and are then combined using equations (12.1) and (12.2).

Several tests were implemented in Lilien et al. [22] to validate the algorithm. One is to find a conformation close to the crystal structure to confirm the rotamer search strategy with minimization and the scoring scheme. Another test is to simulate the biochemical activity assays of L-Phe and L-Leu against wild-type PheA and the T278M/A301G double mutation, and the results qualitatively agreed with the activity assays of Stachelhaus et al. [27]. Later, Chen et al. performed a K*K^* mutation search to redesign GrsA-PheA to bind and adenylate Leu and several other amino acids instead of Phe. Novel mutants were reported and experimentally validated [2].

In particular, Chen et al. [2] performed a computational structure-based redesign of the GrsA-PheA for a set of noncognate substrates for which the wild-type (WT) enzyme has little or virtually no specificity. Experimental validation of a set of top-ranked computationally predicted enzyme mutants showed significant improvement in the specificity for the target substrates. Chen et al. [2] further developed enhancements to the methodology for computational enzyme redesign, which resulted experimentally in significant additional improvements in the target substrate specificity. The results suggest that structure-based protein design can identify active mutants different from those selected by evolution.

Chen et al. [2] used provable K*K^* algorithms to redesign GrsA-PheA. They designed mutations to switch the substrate specificity of this enzyme from its cognate substrate phenylalanine, to leucine. The mutant with the highest activity for a noncognate substrate exhibits one-sixth of the WT enzyme:WT substrate activity. That is, the best redesigned enzymes have activity that is up to one-sixth of WT:Phe (kcat/KMk_{cat}/K_M). To do this they employed minDEE and K*K^* algorithms that not only design mutations to the active site, but also design distal mutations that significantly aid in switching the specificity. These algorithms have the possibility to compete in silico with directed evolution (an experimental technique that is often used to find distal mutations to restabilize the protein and counterbalance specificity-changing mutations made to the active site). Chen et al. [2] also redesigned the enzyme to adenylate a variety of charged substrates: Arg, Lys, Asp, and

Glu. The latter represent challenges, because the wildtype enzyme has essentially no activity for charged substrates. The designs were experimentally tested by creating the predicted mutant proteins and assaying their activity and binding.

Minimized Dead-End Elimination (minDEE)

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) (see chapter 11). 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 (“rigid-rotamer”) 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. Georgiev et al. [13] derive a 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. MinDEE is sometimes called minimization-aware dead-end elimination.

A* Search and minDEE

An additional combinatorial factor reduction in computational complexity can be achieved through the use of an A* (pronounced “A star”) search algorithm to enumerate conformations in order of increasing energy. In Leach and Lemon [21] an A* branch and bound algorithm was developed to explore a number of low-energy conformations for a single mutation sequence (i.e., a single protein). In this algorithm, traditional DEE was first used to reduce the number of side-chain conformations, and then surviving conformations were enumerated in order of conformation energy by expanding sorted nodes of a conformation tree. Georgiev et al. [13] modified the A* algorithm of [21] to compute a partition function using the ideas discussed in section 12.2.

The A* algorithm deterministically identifies the least-cost path in a tree from the root to a leaf node. When the tree is a conformation tree (figure 12.2) and the path costs encode conformation energies, the A* algorithm can be used to identify minimum-energy conformations [21]. In a conformation tree (figure 12.2), the rotamers of flexible residue ii are represented by the branches at depth ii . For example, in figure 12.2, residue A has 4 rotamers, residue B has 2 rotamers, and residue C has 3 rotamers. Internal nodes of a conformation tree represent partially-assigned conformations and each leaf node represents a fully-assigned conformation. Let EwE_w be a scalar energy threshold. The DEE/A*\text{DEE}/A^* algorithm of [21] generates all low-energy conformations within a window EwE_w of the GMEC. Georgiev et al. [13] extended this algorithm (a) for minDEE (i.e., to use minimized rotamers, figure 12.5, plate 12), and (b) to compute provable ε\varepsilon -approximations to the partition functions.

Figure 12.5 (plate 12) Energy-minimized DEE. Without energy minimization the swapping of rotamer iri_r for iti_t (panel a to panel b) leaves unchanged the conformations and self and pairwise energies of residues jj and kk . When energy minimization is allowed, the swapping of rotamer iri_r for rotamer iti_t (panel c to panel d) may cause the conformations of residues jj and kk to minimize (i.e., move) to form more energetically favorable interactions (from the faded to the solid conformations in panels c and d).

Hence, minDEE is useful not only in identifying the minimized-GMEC, but also as a filter in an ensemble-based scoring and search algorithm, called minDEE/K*\text{minDEE}/K^* , for protein redesign that exploits energy-minimized conformations. The provable and efficient minimized-DEE algorithm is applicable in protein redesign, protein-ligand binding prediction, and computer-aided drug design.

Backbone Flexibility in DEE for Protein Design

Continuous Backbone Flexibility DEE

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, traditional DEE identifies and prunes rotamer choices that are provably not part of the 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. Georgiev and Donald [14] 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 (there are also further enhancements to BD for improved pruning efficiency; see [14, 16]). The results from applying BD to redesign the β1\beta 1 domain of protein G and to switch the substrate specificity of the NRPS enzyme GrsA-PheA were compared against the results from previous fixed-backbone DEE algorithms. This showed 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 BD.

Backrub DEE

Based on stereochemical intuition, the existence of a subtle backbone motion coupled to rotamer jumps has long been suspected. Such a motion, the “backrub,” was confirmed by closely examining the electron density for side-chains modeled as alternates in very high-resolution crystal structures and inferring that the backbone must have shifted between the two conformations to maintain reasonably ideal geometry [8]. It is conservatively estimated that 3% of all residues undergo backrubs, with a large fraction occurring at the protein surface, most likely reacting to bombardment from solvent molecules. In addition to modeling dynamics, [8, 15, 26] show that backrubs can allow rotamer changes. Hence, by deduction, they can accommodate mutations to amino acid types for which no rotamers fit in the original backbone. Therefore, it is reasonable to assume that backrubs may play an evolutionary role. Such an assumption is, of course, impossible to demonstrate from single high-resolution structures and, due to coordinate error on the level of backrub shifts, is also difficult to tease out by comparing otherwise identical-in-sequence point mutant structures. However, one way to address the question is by investigating the effects of backrubs in protein design [15, 26], which is essentially a guided form of evolution that contributes to our knowledge of the determinants of protein packing and folding. Backrubs enable a provable algorithm to design proteins with low energies [15]; therefore, we can be confident that they may also contribute on an evolutionary time scale [8].

The Backrub [8] is a small but kinematically efficient side-chain-coupled local backbone motion frequently observed in atomic-resolution crystal structures of proteins. A backrub shifts the CαC^\alpha - CβC^\beta orientation of a given side-chain by rigid-body dipeptide rotation plus smaller individual rotations of the two peptides, with virtually no change in the rest of the protein. Backrubs can therefore provide a biophysically realistic model of local backbone flexibility for structure-based protein design. Georgiev et al. [15] present a combinatorial search algorithm for protein design that incorporates an automated procedure for local backbone flexibility via backrub motions. This derives a DEE-based criterion for pruning candidate rotamers that, in contrast to previous DEE algorithms, is provably accurate with backrub motions. The backrub-based DEE algorithm (“brDEE”) successfully predicts alternate side-chain conformations from ≤0.9-Å\leq 0.9\text{-}\text{\AA} resolution structures, confirming the suitability of the automated backrub procedure. Finally, the application of the algorithm to redesign two different proteins was shown to identify a large number of lower-energy conformations and mutation sequences that would have been ignored by a rigid-backbone model.

Application to Negative Design

It is intriguing to speculate how protein redesign algorithms based on K*K^* can be used for negative design. An illuminating example focuses on prospective prediction of resistance mutations. These mutations arise in protein targets to resist antimicrobial and antibiotic drugs, antivirals, and even in cancer cells to evade antineoplastic and chemotherapy agents.

Drug resistance resulting from mutations to the target is an unfortunately common phenomenon that limits the lifetime of many of the most successful drugs. In contrast to the investigation of mutations after clinical exposure, it would be powerful to be able to incorporate strategies early in the development process to predict and overcome the effects of possible resistance mutations. Frey et al. [29] describe the successful in silico prediction of resistance mutations to a novel antifolate inhibitor of Staphylococcus aureus (MRSA) dihydrofolate reductase (DHFR). This was the first prospective computational prediction of resistance mutations in a drug target, thus opening the possibility of overcoming drug resistance early in the iterative drug discovery process.

The K*K^* algorithm predicted potential resistance mutations in DHFR using positive design to maintain catalytic function and negative design to interfere with binding of a lead inhibitor [29]. Enzyme inhibition assays showed that three of the four highly ranked predicted mutants are active yet display lower affinity (18-, 9-, and 13-fold) for the inhibitor. A crystal structure of the top-ranked mutant enzyme validated the predicted conformations of the mutated residues and the structural basis of the loss of potency.

  • This study demonstrates K*K^* can do negative design. Negative design is difficult because much greater conformational flexibility must be modeled.
  • Deterministic algorithms were used to enumerate top mutants in gap-free order. All tested predictions (#1, #3, #7, and #9) were in the top 10 predictions (out of 1173 mutants and 101210^{12} conformations), and the top-ranked mutant (#1) performed best (followed by #3 and #7).
  • Except for the selection of four of the top ten mutants, there was no human intervention or manual selection; the entire design was automated.
  • Experimentally measured enzyme activities had precisely the same rankings predicted by the algorithm.
  • While the negative designs were based on a crystal structure of the DHFR:inhibitor complex, the positive designs were based on a model (structure prediction) of MRSA DHFR bound to NADPH and dihydrofolate. The success of the algorithm in designing to a model (as opposed to a crystal structure) is notable.
  • A crystal structure of the top-ranked mutant (#1) proved the algorithm’s structural predictions were highly accurate, explaining the affinity loss as predicted.

This study used the protein design algorithms discussed in this chapter (minDEE/ K*K^*), and the predictions were then tested prospectively. The ability of these provable, ensemble-based protein design algorithms to predict resistance mutations could be incorporated in a lead design strategy against any target that is susceptible to mutational resistance. The accuracy of the algorithms suggests the possibility to analogously predict future mutational resistance to other targets.

There were several extensions made to K*K^* to handle the negative design. K*K^* uses both intra-and intermutation pruning, as described earlier in this chapter [13]. The intra-and intermutation pruning algorithms ensure provably accurate K*K^* scores for the best-scoring mutants and structures. This suffices for positive design, in which good-scoring structures and mutants are of interest. However for negative design, we are interested in poorly scoring structures and mutants as well. For poorly scoring structures and mutants, the intermutation pruning algorithm described earlier does not guarantee accurate scores [13]. For this reason, some modifications were undertaken to extend the algorithm for provably accurate negative design. Specifically, either changing γ\gamma (which controls the intermutation pruning fraction) or disabling the intermutation pruning may be necessary for provably accurate negative design. Frey et al. [29] tried both ways. In practice they have found that the negative design predictions are often still adequate even with the intermutation pruning enabled. These changes to the K*K^* parameters are described in the open-source code provided with [29].

Discussion

Algorithms for determining protein structures using NMR or X-ray crystallography comprise a family of techniques for analyzing biological data and biological problems. However, this chapter described another family of algorithms and their application to synthetic biology problems such as a protein engineering. These ensemble-based scoring and search algorithms for protein design have been applied to modify the substrate specificity of an antibiotic-producing enzyme in the non-ribosomal peptide synthetase (NRPS) pathway [2], and to predict resistance mutations in MRSA DHFR [29]; The latter were confirmed with crystal structures.

Realization of novel molecular function requires the ability to alter molecular complex formation. Enzymatic function can be altered by changing enzyme-substrate interactions via modification of an enzyme’s active site. A redesigned enzyme may either perform a novel reaction on its native substrates or its native reaction on novel substrates. A number of computational approaches have been developed to address the combinatorial nature of the protein redesign problem. These approaches typically search for the GMEC among an exponential number of protein conformations. In contrast, new algorithms for protein redesign combine a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm [22, 2, 13]. In addition, efficient deterministic approximation algorithms have been obtained, capable of approximating biophysical scoring functions to arbitrary precision [2, 13]. These techniques include provable ε\varepsilon -approximation algorithms for estimating partition functions to model binding and protein flexibility.

This lecture only covers the basic ideas behind the K*K^* algorithm. Since 2005, there has been rapid progress on improved versions of the K*K^* and DEE algorithms, and the designs have been experimentally tested. For a general introduction to this line of research, see Chen et al. [2]. Recent provable algorithms include minDEE [13]; continuous backbone flexibility in DEE (BD) [14]; backrub motions in DEE (brDEE) [15]; and divide-and-conquer splitting (DACS) [16]. For K*K^* implementation, see Chen et al. and Georgiev et al. [13, 2]. For the general idea of K*K^* , also see Lilien et al. [22]. Three of these extensions and improvements—minDEE, BD, and brDEE—were discussed earlier. MinDEE/ K*K^* and BD were used to obtain novel enzyme and DHFR resistance designs that were experimentally verified [2].

The algorithms in chapters 11 and 12 are provable and complete, which allows an engineering segregation of the search procedure from the model. The input model typically includes initial protein backbone structures, a library of rigid rotamers, an energy function, and models of continuous or discrete flexibility for the backbones and rotamers. The search procedure rank-orders, gap-free, the best solutions in sequence and conformational space. We expect some of these solutions to be improved designs, but the unsuccessful designs will be useful to improve the model or the algorithm. In contrast, if a heuristic (as opposed to provable) design algorithm is used, we have no idea whether the failures arose from inadequate optimization or from flaws in the model (energy function, structure, flexibility, rotamer library, etc.). Thus, there is a danger that the failures will be used to overfit the energy function. In particular, without a provable algorithm, we do not know whether the original model can successfully discriminate the decoys, since the heuristic technique is not guaranteed to return the optimal answers for the model nor to compute a list in the order ranked by the model. If a perfectly good energy function is overfit to handle spurious predictions (artifacts of the algorithm, not of the model) then the process of improving the model has failed, and the additional experimental data will be misused to effectively “break” a good model to overfit the putative outliers. Hence, with heuristic design algorithms the operation of tuning the model to match the data can be fundamentally unsound. On the other hand, with a provable algorithm, we remove one “variable” from the experiment (the algorithm), and we know that any discrepancies between the experimental results and the algorithm’s predictions must be blamed solely on inadequacies of the model (and not the algorithm). In this manner, by using provable algorithms it is substantially more straightforward to improve the model given new experimental data, and these improvements or “tuning” are sound.

Recent work (e.g., chapters 11, 12) has extended the boundaries of what is possible with provable algorithms, in a series of end-to-end studies going from mathematics to novel algorithms to software to prospective experimental validation including binding, kinetics, stability, in vivo assays, and NMR and crystal structures. The algorithms were experimentally demonstrated to have remarkable accuracy and predictive power. Computational protein designs can only be as good as the (necessarily approximate) input model. But provable algorithms can avoid the undersampling, overfitting, and local minima that may cause heuristic algorithms to predict solutions far worse than the model. Provable algorithms guarantee that the predictions are exactly as good as the model, and as described above, this enables a powerful and principled path to improving the model based on experimental feedback.

Exercise Explain why more conformational flexibility must be modeled for negative design (as opposed to positive design). How much more conformational flexibility was modeled for negative design (versus positive design) in the study of Frey et al. [29]? Will that about be sufficient, in general? How could additional conformational flexibility be modeled?

References

  • [1] Daniel N. Bolon, Robert A. Grant, Tania A. Baker, and Robert T. Sauer. Specificity versus stability in computational protein design. Proceedings of the National Academy Sciences (U S A), 102;36(Sep 2005):12724–12729.
  • [2] C. Chen, I. Georgiev, A.C. Anderson, and B.R. Donald. Computational structure-based redesign of enzyme activity. Proceedings of the National Academy of Sciences (USA), 106;10(2009): 3764–3769.
  • [3] E. Conti, T. Stachelhaus, M. Marahiel, and P. Brick. Structural basis for the activation of phenylalanine in the non-ribosomal biosynthesis of Gramicidin S. The EMBO Journal 16 (1997):4174–4183.
  • [4] W. Cornell, P. Cieplak, C. Bayly, I. Gould, K. Merz, D. Ferguson, et al. A second generation force field for the simulation of proteins, nucleic acids and organic molecules. Journal of the American Chemical Society 117(1995):5179–5197.
  • [5] B. I. Dahiyat, D. B. Gordon, and S. L. Mayo. Automated design of the surface positions of protein helices. Protein Science 6;6(Jun 1997):1333–1337.
  • [6] B. I. Dahiyat and S. L. Mayo. Protein design automation. Protein Science 5;5(May 1996):895–903.
  • [7] B. I. Dahiyat and S. L. Mayo. Probing the role of packing specificity in protein design. Proceedings of the National Academy of Sciences (USA) 94(1997):10172–10177.
  • [8] I. W. Davis, W. B. Arendall 3rd, D. C. Richardson and P. S. Richardson. The backrub motion: how protein backbone shrugs when a side-chain dances. Structure. 2006 Feb;14(2):265–274.
  • [9] A. A. Canutescu, A. A. Shelenkov, and R. L. Dunbrack Jr. A graph-theory algorithm for rapid protein side-chain prediction. Protein Science 12(2003):2001–2014.
  • [10] B. Kuhlman and D. Baker. Native protein sequences are close to optimal for their structures. Proceedings of the National Academy of Sciences (USA) 97(2000):10383–10388.
  • [11] X. Hu and B. Kuhlman. Protein design simulations suggest that side-chain conformational entropy is not a strong determinant of amino acid environmental preferences. PROTEINS: Structure, Function, and Bioinformatics, 62(2006):739–748.
  • [12] G. D. Friedland, A. J. Linares, C. A. Smith, and T. Kortemme. A simple model of backbone flexibility improves modeling of side-chain conformational variability. Journal of Molecular Biology 380;4(2008 Jul):757–774.
  • [13] I. Georgiev, R. Lilien, and B. R. Donald. 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. Journal of Computational Chemistry 29;10(2008):1527–1542.
  • [14] I. Georgiev and B. R. Donald. Dead-end elimination with backbone flexibility. Bioinformatics 23;13(2007): i85–94. Proceedings of the International Conference on Intelligent Systems for Molecular Biology (ISMB), Vienna, Austria (2007).
  • [15] I. Georgiev, D. Keedy, J. S. Richardson, D. C. Richardson, and B. R. Donald. Algorithm for backrub motions in protein design. Bioinformatics 24;13(2008):i96–204. Proceedings of the International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada (2008).
  • [16] I. Georgiev, R. Lilien, and B. R. Donald. Improved pruning algorithms and divide-and-conquer strategies for dead-end elimination, with application to protein design. Bioinformatics, 22;14(2006):e174–183, Proceedings of the International Conference on Intelligent Systems for Molecular Biology (ISMB), Fortaleza, Brazil (2006).
  • [17] James J. Havranek and Pehr B. Harbury. Automated design of specificity in molecular recognition. Nature Structural Biology, 10;1(2003):45–52.
  • [18] L. Looger and H. Hellinga. Generalized dead-end elimination algorithms make large-scale protein side-chain structure prediction tractable: Implications for protein design and structural genomics. Journal Molecular Biology 307(2001):429–445.

[19] H. Hellinga and F. Richards. Construction of new ligand binding sites in proteins of known structure: I. Computer-aided modeling of sites with pre-defined geometry. Journal Molecular Biology 222(1991):763–785.

[20] T. Lazaridis and M. Karplus. Effective energy function for proteins in solution. PROTEINS: Structure, Function, and Genetics 35(1999):133–152.

[21] A. Leach and A. Lemon. Exploring the conformational space of protein side-chains using dead-end elimination and the A*A^* algorithm. Proteins: Structure, Function, and Bioinformatics 33(1998):227–239.

[22] R. H. Lilien, B. W. Stevens, A. C. Anderson, and B. R. Donald. A novel ensemble-based scoring and search algorithm for protein redesign and its application to modify the substrate specificity of the gramicidin synthetase a phenylalanine adenylation enzyme. Journal of Computational Biology 12;6(2005 Jul–Aug):740–761.

[23] S. Lovell, J. Word, J. Richardson, and D. Richardson. The penultimate rotamer library. Proteins: Structure, Function, and Bioinformatics 40(2000):389–408.

[24] A. D. MacKerell Jr., D. Bashford, M. Bellott, R. L. Dunbrack Jr., J. D. Evanseck, M. J. Field, et al. All-atom empirical potential for molecular modeling and dynamics studies of proteins. The Journal of Physical Chemistry B, 102(1998):3586–3616.

[25] S. L. Mayo, B. D. Olafson, and W. A. Goddard III. DREIDING: A generic force field for molecular simulations. The Journal of Physical Chemistry 94(1990):8897–8909.

[26] C. A. Smith, and T. Kortemme. Backrub-like backbone simulation recapitulates natural protein conformational variability and improves mutant side-chain prediction. Journal of Molecular Biology 380;4(2008 Jul 18):742–756.

[27] T. Stachelhaus, H. Mootz, and M. Marahiel. The specificity-conferring code of adenylation domains in nonribosomal peptide synthetases. Chemical Biology 6(1999):493–505.

[28] Eric S. Zollars, Shannon A. Marshall, and Stephen L. Mayo. Simple electrostatic model improves designed protein sequences. Protein Science 15(2006):2014–2018.

[29] Frey K, Georgiev I, Donald BR, Anderson A. Predicting resistance mutations using protein design algorithms. Proceedings of the National Academy of Sciences (PNAS) USA. 2010;107(31):13707–12.