Most protein design algorithms search over discrete conformations and an energy function that is residue-pairwise, that is, a sum of terms that depend on the sequence and conformation of at most two residues. Although modeling of continuous flexibility and of non-residue-pairwise energies significantly increases the accuracy of protein design, previous methods to model these phenomena add a significant asymptotic cost to design calculations. We now remove this cost by modeling continuous flexibility and non-residue-pairwise energies in a form suitable for direct input to highly efficient, discrete combinatorial optimization algorithms such as DEE/A* or branch-width minimization. Our novel algorithm performs a local unpruned tuple expansion (LUTE), which can efficiently represent both continuous flexibility and general, possibly nonpairwise energy functions to an arbitrary level of accuracy using a discrete energy matrix. We show using 47 design calculation test cases that LUTE provides a dramatic speedup in both single-state and multistate continuously flexible designs.
Get full access to this article
View all access options for this article.
References
1.
ChazelleB., KingsfordC., and SinghM.2004. A semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Comput. Comput. Biol. Spec. Issue, 16, 380–392.
2.
ChenC.-Y., GeorgievI., AndersonA.C., et al.2009. Computational structure-based redesign of enzyme activity. Proc. Natl. Acad. Sci. U.S.A., 106, 3764–3769.
3.
ČížekJ.2009. On the use of the cluster expansion and the technique of diagrams in calculations of correlation effects in atoms and molecules, 35–90. In Correlation Effects in Atoms and Molecules, volume 14 of Advances in Chemical Physics. John Wiley and Sons, Hoboken, NJ.
4.
DesmetJ., de MaeyerM., HazesB., et al.1992. The dead-end elimination theorem and its use in protein side-chain positioning. Nature, 356, 539–542.
5.
DonaldB.R.2011. Algorithms in Structural Molecular Biology. MIT Press, Cambridge, MA.
6.
FlockeN., and BartlettR.J.2004. A natural linear-scaling coupled-cluster method. J. Chem. Phys., 121, 10935–10944.
7.
FloudasC.A., KlepeisJ.L., and PardalosP.M.1999. Global optimization approaches in protein folding and peptide docking, 141–172. In Mathematical Support for Molecular Biology, volume 47 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Hoboken, NJ.
8.
FreyK.M., GeorgievI., DonaldB.R., et al.2010. Predicting resistance mutations using protein design algorithms. Proc. Natl. Acad. Sci. U.S.A., 107, 13707–13712.
9.
GainzaP., RobertsK., and DonaldB.R.2012. Protein design using continuous rotamers. PLoS Comput. Biol. 8, e1002335.
10.
GainzaP., RobertsK.E., GeorgievI., et al.2013. OSPREY: Protein design with ensembles, flexibility, and provable algorithms. Methods Enzymol. 523, 87–107.
11.
GeorgievI., AcharyaP., SchmidtS., et al.2012. Design of epitope-specific probes for sera analysis and antibody isolation. Retrovirology, 9, P50.
12.
GeorgievI., and DonaldB.R.2007. Dead-end elimination with backbone flexibility. Bioinformatics, 23, i185–i194.
13.
GeorgievI., LilienR.H., and DonaldB.R.2008. 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. J. Comput. Chem., 29, 1527–1542.
14.
GeorgievI., RobertsK.E., GainzaP., et al.2009. OSPREY (Open Source Protein Redesign for You) user manual, 94 pages. Available at: www.cs.duke.edu/donaldlab/software.php Updated 2015.
15.
GeorgievI.S., RudicellR.S., SaundersK.O., et al.2014. Antibodies VRC01 and 10E8 neutralize HIV-1 with high breadth and potency even with Ig-framework regions substantially reverted to germline. J. Immunol., 192, 1100–1106.
16.
GorczynskiM.J., GrembeckaJ., ZhouY., et al.2007. Allosteric inhibition of the protein-protein interaction between the leukemia-associated proteins Runx1 and CBFβ. Chem. Biol., 14, 1186–1197.
17.
GordonD.B., and MayoS.L.1998. Radical performance enhancements for combinatorial optimization algorithms based on the dead-end elimination theorem. J. Comput. Chem., 19, 1505–1514.
18.
GrigoryanG., ReinkeA.W., and KeatingA.E.2009. Design of protein-interaction specificity affords selective bZIP-binding peptides. Nature, 458, 859–864.
19.
GrigoryanG., ZhouF., LustigS.R., et al.2006. Ultra-fast evaluation of protein energies directly from sequence. PLoS Comput. Biol. 2, e63.
20.
HallenM.A., and DonaldB.R.2015. COMETS (Constrained Optimization of Multistate Energies by Tree Search): A provable and efficient algorithm to optimize binding affinity and specificity with respect to sequence, 122–135. In Research in Computational Molecular Biology, volume 9029 of Lecture Notes in Computer Science. Springer International Publishing, Berlin.
21.
HallenM.A., GainzaP., and DonaldB.R.2015. A compact representation of continuous energy surfaces for more efficient protein design. J. Chem. Theory Comput., 11, 2292–2306.
22.
HallenM.A., KeedyD.A., and DonaldB.R.2013. Dead-end elimination with perturbations (DEEPer): A provable protein design algorithm with continuous sidechain and backbone flexibility. Proteins, 81, 18–39.
23.
HartP.E., NilssonN.J., and RaphaelB.1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 4, 100–107.
24.
JaninJ., WodakS., LevittM., et al.1978. Conformation of amino acid side-chains in proteins. J. Mol. Biol., 125, 357–386.
25.
JouJ.D., JainS., GeorgievI., et al.2015. BWM*: A novel, provable, ensemble-based dynamic programming algorithm for sparse approximations of computational protein design. J. Comput. Biol., 23:413–424.
26.
KaranicolasJ., and KuhlmanB.2009. Computational design of affinity and specificity at protein-protein interfaces. Curr. Opin. Struct. Biol., 19, 458–463.
27.
KingsfordC.L., ChazelleB., and SinghM.2005. Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics, 21, 1028–1039.
28.
KuhlmanB., and BakerD.2000. Native protein sequences are close to optimal for their structures. Proc. Natl. Acad. Sci. U.S.A., 97, 10383–10388.
29.
LazaridisT., and KarplusM.1999. Effective energy function for proteins in solution. Proteins, 35, 133–152.
30.
LeachA.R., and LemonA.P.1998. Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm. Proteins, 33, 227–239.
31.
Leaver-FayA., JacakR., StrangesP.B., et al.2011. A generic program for multistate protein design. PLoS One, 6, e20937.
32.
LeeC., and LevittM.1991. Accurate prediction of the stability and activity effects of site-directed mutagenesis on a protein core. Nature, 352, 448–451.
33.
LilienR.H., StevensB.W., AndersonA.C., et al.2005. 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. J. Comput. Biol., 12, 740–761.
34.
LuCoreS.D., LitmanJ.M., PowersK.T., et al.2015. Dead-end elimination with a polarizable force field repacks PCNA structures. Biophys. J., 109, 816–826.
35.
NichollsA., and HonigB.1991. A rapid finite difference algorithm, utilizing successive over-relaxation to solve the Poisson-Boltzmann equation. J. Comput. Chem., 12, 435–445.
36.
NocedalJ., and WrightS.J.2006. Numerical Optimization, 2nd ed. Springer-Verlag, Berlin.
37.
PierceN.A., and WinfreeE.2002. Protein design is NP-hard. Protein Eng. 15, 779–782.
38.
RobertsK.E., CushingP.R., BoisguerinP., et al.2012. Computational design of a PDZ domain peptide inhibitor that rescues CFTR activity. PLoS Comput.Biol., 8, e1002477.
39.
RobertsK.E., GainzaP., HallenM.A., et al.2015. Fast gap-free enumeration of conformations and sequences for protein design. Proteins, 83, 1859–1877.
40.
RochiaW., SridharanS., NichollsA., et al.2002. Rapid grid-based construction of the molecular surface and the use of induced surface charge to calculate reaction field energies: Applications to the molecular systems and geometric objects. J. Comput. Chem., 23, 128–137.
41.
RosenzweigA.C., HuffmanD.L., HouM.Y., et al.1999. Crystal structure of the Atx1 metallochaperone protein at 1.02 A resolution. Structure, 7, 605–617.
42.
RudicellR.S., KwonY.D., KoS.-Y., et al.2014. Enhanced potency of a broadly neutralizing HIV-1 antibody in vitro improves protection against lentiviral infection in vivo. J. Virol., 88, 12669–12682.
43.
SimonciniD., AlloucheD., de GivryS., et al.2015. Guaranteed discrete energy optimization on large design problems. J. Chem. Theory Comput., 11, 5980–5989.
44.
SitkoffD., SharpK.A., and HonigB.1994. Accurate calculation of hydration free energies using macroscopic solvent models. J. Phys. Chem., 98, 1978–1988.
45.
StevensB.W., LilienR.H., GeorgievI., et al.2006. Redesigning the PheA domain of gramicidin synthetase leads to a new understanding of the enzyme's mechanism and selectivity. Biochemistry, 45, 15495–15504.
46.
TanX., Calderón-VillalobosL.I.A., SharonM., et al.2007. Mechanism of auxin perception by the TIR1 ubiquitin ligase. Nature, 446, 640–645.
47.
TraoréS., AlloucheD., AndréI., et al.2013. A new framework for computational protein design through cost function network optimization. Bioinformatics, 29, 2129–2136.
48.
TraoréS., RobertsK.E., AlloucheD., et al.2016. Fast search algorithms for computational protein design. J. Comput. Chem. 37, 1048–1058.
49.
VizcarraC.L., ZhangN., MarshallS.A., et al.2008. An improved pairwise decomposable finite-difference Poisson-Boltzmann method for computational protein design. J. Comput. Chem., 29, 1153–1162.
50.
XuJ., and BergerB.2006. Fast and accurate algorithms for protein side-chain packing. J. ACM, 53, 533–557.
51.
YanoverC., FromerM., and ShifmanJ.M.2007. Dead-end elimination for multistate protein design. J. Comput. Chem., 28, 2122–2129.
52.
ZhangD.W., and ZhangJ.Z.H.2003. Molecular fractionation with conjugate caps for full quantum mechanical calculation of protein-molecule interaction energy. J. Chem. Phys., 119, 3599–3605.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
