Methods and compositions utilizing hybrid exact rotamer optimization algorithms for protein design

The present invention relates to an apparatus and method for quantitative protein design and optimization. In particular, the invention describes the use of Hybrid Exact Rotamer Optimization algorithms in protein design.

EXAMPLES 
 Example 1 
 Use of Split DEE for Protein Design To demonstrate the increased power of split DEE over standard Goldstein DEE, the present study presents results for the three challenging design problems described in Table I. Each of the cases involves a different protein region, and each of these design problems is currently under computational and experimental study in the lab of one of the authors (S.L.M.). All methods described herein are exact in the sense that, when they do converge successfully, the same GMEC conformation is identified, regardless of the convergence path and elimination criteria employed. Case 1 represents the design of 18 residues ( 5 , 14 , 21 , 27 , 29 , 31 , 37 , 38 , 39 , 41 , 72 , 74 , 80 , 82 , 84 , 92 , 96 , 98 ) in the core of plastocyanin (PDB code 2 pcy). Case 2 involves the design of all ten nonglycine core residues ( 3 , 5 , 7 , 20 , 26 , 30 , 34 , 39 , 52 , 54 ) and nine boundary residues ( 1 , 12 , 23 , 33 , 37 , 43 , 45 , 50 , 56 ) of the &bgr;1 domain of Protein G (PDB code 1 pga). Case 3 represents the design of 14 surface residues ( 4 , 6 , 8 , 13 , 15 , 17 , 42 , 44 , 46 , 48 , 49 , 51 , 53 , 55 ) on the &bgr;-sheet of Protein G. For these designs, core residue identities are selected from among the amino acids A, V, L, I, F, Y, and W, whereas surface residue identities are selected from among A, N, Q, S, T, H, D, E, K, and R. Boundary residues are allowed to have amino acid identities from the union of these sets. For side-chain placement calculations, dead-end elimination algorithms are capable of determining the GMEC conformation for several hundred residues using well-resolved rotamer libraries. The number of rotamers per position is substantially higher for protein design calculations, because the conformational space contains rotamers for multiple amino acid identities for each position in the design. As a result, the computational efficiency and robustness of DEE are put to a much more challenging test and the number of positions that can be designed simultaneously is closer to a few dozen. The exact number is context dependent, because, for example, it is easier to eliminate rotamers in the core than on the surface due to the disparity in the strength of the interactions. Typically, successful DEE calculations are characterized by a period of rapid elimination followed by a plateau and then a second period of rapid elimination leading to the GMEC conformation. The plateau occurs as the singles elimination criteria become less effective and more time is consumed searching for dead-ending pairs using doubles calculations. Unification of rotamers at multiple positions expands a portion of the conformational space and helps lead to new eliminations, but at the cost of temporarily increasing the number of rotamers in the calculation. This in turn aggravates the higher order dependence of the DEE complexity bounds on n, the number of rotamers at each position. To prevent the calculation from overrunning the available physical memory on the machine, a hard limit is placed on the maximum allowable number of rotamers. If the singles elimination criteria are unsuccessful in eliminating enough rotamers after each round of unification, the combinatorial buildup of superrotamers will eventually encounter this cutoff and the calculation will be forced to terminate. More powerful DEE criteria help to delay the onset of this buildup, thus allowing the simultaneous design of larger numbers of residues. When comparing the computational efficiency of split DEE to standard Goldstein DEE, it is not possible to determine a speed-up factor that is relatively constant across all calculations. For easy design problems with few positions, both methods will converge rapidly in about the same amount of time; the extra cost per cycle in the split approach is balanced by the increased elimination power of the method. As the difficulty of the design problem increases, the speed-up provided by the split approach also increases, until, for some number of design positions, the standard DEE approach fails to converge and the speedup effectively becomes infinite. Eventually, for sufficiently large design calculations, the split approach will also fail to converge. Timing results for the three benchmark design cases are provided in Table II with corresponding convergence histories shown in FIGS. 12 A- 12 C. For the core design of case 1 (see FIG. 12A ), split (s&equals;1) and split (s&equals;2 mb ) DEE converge to the GMEC conformation in under 12 minutes. By contrast, Goldstein (T&equals;1) DEE reaches a plateau with 4.5×10 11 conformations remaining, and is eventually forced to terminate after 418 minutes when combinatorial buildup via unification causes the maximum allowable number of rotamers (np max &equals;10 4 ) to be surpassed. For the core/boundary design of case 2 (see FIG. 12B ), the standard Goldstein (T&equals;1) DEE algorithm plateaus at 1.1×10 13 conformations before terminating due to combinatorial buildup (np max &equals;104) after 1793 minutes. By contrast, split (s&equals;1) DEE converges to the GMEC conformation in 234 minutes and split (s&equals;2 mb ) DEE converges slightly faster in 219 minutes. For the surface design of case 3 , the rotamers interact weakly relative to interactions in the core and boundary. Using the same maximum allowable number of rotamers as before (np max &equals;10 4 ), split (s&equals;2 mb ) DEE converge successfully in 2167 minutes whereas both Goldstein (T&equals;1) and split (s&equals;1) DEE quickly overrun the maximum rotamer limit (not shown). To observe a longer convergence path for these two algorithms, the maximum rotamer limit was increased (np max &equals;2×10 4 ) and the results are shown in FIG. 11C . Using Goldstein (T&equals;D 1) DEE, a plateau is reached at 9.3×10 18 conformations and the calculation terminates due to rotamer buildup after 3006 minutes. Using split (s&equals;D 1) DEE, the number of conformations is reduced to 6.4×10 11 before the calculation is terminated after 5480 minutes. Convergence to the GMEC conformation is achieved only with split (s&equals;2 mb ) DEE, requiring 1939 minutes. For the hardest problems, which involve weak interactions between surface residues, the more powerful (s&equals;2 mb ) criterion can lead to substantial improvements in the overall performance of the algorithm, even relative to split (s&equals;1) DEE. Conformational splitting criteria significantly increase the power of dead-end elimination algorithms for the purposes of sequence selection in computational protein design. For challenging design calculations, the two splitting methods (s&equals;D 1) and (s&equals;2 mb ) dramatically increase the efficiency of DEE relative to existing state-of-the-art methods based on Goldstein (T&equals;1) singles elimination. Although the two split DEE methods perform similarly for the design of core and boundary residues, the more powerful split (s&equals;2 mb ) algorithm can provide significant advantages for calculations involving weakly interacting surface residues. 
 Example 2 
 The HERO Algorithm Using a rotameric description of conformational space, the Side Chain Placement Problem of Homology Modeling (Desmet, J., et al., (1992) Nature, 365:539) and the Sequence Selection Problem of Protein Design (Dahiyat, B. I., and Mayo, S L. (1996) Prot. Sci., 5:895) can both be described as the following combinatorial optimization problem: Choose the single rotamer for each residue position that minimizes the sum of the pairwise interaction energies between rotamers at all positions. The problem may also be recast as the Flight Pricing Problem: For a set of cities each containing multiple airports, choose the airport for each city that minimizes the cost of visiting every city from every other city. and as The Belief Network Problem (Pearl, J. (1988) “Probabilistic Reasoning in Intelligent Systems”, Morgan-Kauffman): For a graph with nodes representing conditional probabilities and edges representing dependencies between these probabilities, determine the values at the nodes that maximize the sum of these conditional probabilities. and the Spin Glass Problem (Mezard, G., et al., (1987), “Spin Glass Theory and Beyond”, World Scientific): For a graph with nodes representing spin states and edges representing coupling between spin states at neighboring nodes, find the set of spins that correspond to the lowest energy ground state of the system. The common mathematical structure in all of these problems is that the system is defined by a set of candidate solutions at each of a number of nodes. Each candidate solution is described in terms of a self-energy (possibly zero) and a set of pairwise interaction energies (possibly zero) with candidate solutions at other nodes. The goal is to find a list of unique candidate solutions (one for each node) that produces the global optimum of a specified quantity which is based on these self-and pairwise energies. The HERO algorithm is an exact search algorithm for solving any problem with this structure. The HERO Algorithm At convergence, this algorithm identifies the single rotamer at each position that belongs to the global minimum energy conformation. The following cycle is repeated until the global minimum energy conformation (GMEC) is identified by eliminating all but one rotamer at each position: 1) Iterative simple Goldstein singles DEE (T&equals;1) until no further eliminations; 2) Iterative simple split singles DEE (s&equals;1) until no further eliminations; 3) Split single DEE (s>1) with or without magic bullet metric once for each rotamer; 4) Apply singles bounding criteria to eliminate rotamers whose bounding energy E bound is greater than E low , the lowest known energy of a valid conformation obtained from the Monte Carlo searches; 5) Alternate sequentially between the following, applying one during each cycle: a) Magic bullet DEE Goldstein doubles calculation (T&equals;1) to flag dead ending pairs; b) Monte Carlo search to find a low energy of a valid conformation E low ; c) Apply doubles bounding criteria to flag pairs whose bounding energy E bound is greater than E low ; d) Goldstein DEE doubles calculation (T&equals;1) to flag dead ending pairs; and, e) Unification of any uniquely defined positions, followed by unification of the two residues with the highest fraction of dead ending pairs, followed by restoration of all flags for the new super-residues; 6) return to 1. A sample calculation comparing the performance of HERO to the previous state-of-the-art DEE algorithm is shown in FIG. 8 . The initial number of conformations is 8.4×10 39 and DEE (s &equals;2 mb ) fails to reduce the number of conformations below 1.0×10 20 after more than 6000 minutes, while HERO converges to the unique minimum conformation in 167 minutes.