Restricted accessResearch articleFirst published online 2016-05
comets (Constrained Optimization of Multistate Energies by Tree Search): A Provable and Efficient Protein Design Algorithm to Optimize Binding Affinity and Specificity with Respect to Sequence
Practical protein design problems require designing sequences with a combination of affinity, stability, and specificity requirements. Multistate protein design algorithms model multiple structural or binding “states” of a protein to address these requirements. comets provides a new level of versatile, efficient, and provable multistate design. It provably returns the minimum with respect to sequence of any desired linear combination of the energies of multiple protein states, subject to constraints on other linear combinations. Thus, it can target nearly any combination of affinity (to one or multiple ligands), specificity, and stability (for multiple states if needed). Empirical calculations on 52 protein design problems showed comets is far more efficient than the previous state of the art for provable multistate design (exhaustive search over sequences). comets can handle a very wide range of protein flexibility and can enumerate a gap-free list of the best constraint-satisfying sequences in order of objective function value.
Get full access to this article
View all access options for this article.
References
1.
ArnoldF.H.1998. Design by directed evolution. Acc. Chem. Res., 31, 125–131.
2.
ChenC.-Y., GeorgievI., AndersonA.C., and DonaldB.R.2009. Computational structure-based redesign of enzyme activity. Proc. Natl. Acad. Sci. USA, 106, 3764–3769.
3.
DaveyJ.A., and ChicaR.A.2012. Multistate approaches in computational protein design. Protein Sci. 21, 1241–1252.
4.
DesmetJ., de MaeyerM., HazesB., and LastersI.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.
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, Providence, RI.
7.
FreyK.M., GeorgievI., DonaldB.R., and AndersonA.C.2010. Predicting resistance mutations using protein design algorithms. Proc. Natl. Acad. Sci. USA, 107, 13707–13712.
8.
FromerM.2010. A probabilistic approach to the design of structural selectivity of proteins [Ph.D. dissertation]. Hebrew University of Jerusalem, Jerusalem.
9.
FromerM., YanoverC., HarelA., et al.2010a. SPRINT: Side-chain prediction inference toolbox for multistate protein design. Bioinformatics, 26, 2466–2467.
10.
FromerM., YanoverC., and LinialM.2010b. Design of multispecific protein sequences using probabilistic graphical modeling. Proteins Struct. Funct. Bioinform., 78, 530–547.
11.
GainzaP., RobertsK., and DonaldB.R.2012. Protein design using continuous rotamers. PLoS Comput. Biol. 8, e1002335.
12.
GainzaP., RobertsK.E., GeorgievI., et al.2013. osprey: Protein design with ensembles, flexibility, and provable algorithms. Methods Enzymol. 523, 87–107.
13.
GeorgievI., and DonaldB.R.2007. Dead-end elimination with backbone flexibility. Bioinformatics, 23, i185–i194.
14.
GeorgievI., AcharyaP., SchmidtS., et al.2012. Design of epitope-specific probes for sera analysis and antibody isolation. Retrovirology, 9, P50.
15.
GeorgievI., LilienR.H., and DonaldB.R.2006. Improved pruning algorithms and divide-and-conquer strategies for dead-end elimination, with application to protein design. Bioinformatics, 22, e174–e183.
16.
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.
17.
GeorgievI., RobertsK.E., GainzaP., et al.2009. osprey (Open Source Protein Redesign for You) User Manual. Available at: www.cs.duke.edu/donaldlab/software.php Updated, 2012. 94 pp.
18.
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.
19.
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.
20.
GrigoryanG., ReinkeA.W., and KeatingA.E.2009. Design of protein-interaction specificity affords selective bZIP-binding peptides. Nature, 458, 859–864.
21.
GrigoryanG., ZhouF., LustigS.R., et al.2006. Ultra-fast evaluation of protein energies directly from sequence. PLoS Comput. Biol. 2, e63.
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 Struct. Funct. Bioinform., 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. Cybernet., 4, 100–107.
24.
KaranicolasJ., and KuhlmanB.2009. Computational design of affinity and specificity at protein-protein interfaces. Curr. Opin. Struct. Biol., 19, 458–463.
25.
KingsfordC.L., ChazelleB., and SinghM.2005. Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics, 21, 1028–1039.
26.
KuhlmanB., and BakerD.2000. Native protein sequences are close to optimal for their structures. Proc. Natl. Acad. Sci. USA, 97, 10383–10388.
27.
LeachA.R., and LemonA.P.1998. Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm. Proteins Struct. Funct. Bioinform., 33, 227–239.
28.
Leaver-FayA., JacakR., StrangesP.B., and KuhlmanB.2011. A generic program for multistate protein design. PLoS One, 6, e20937.
29.
LeeC., and LevittM.1991. Accurate prediction of the stability and activity effects of site-directed mutagenesis on a protein core. Nature, 352, 448–451.
30.
LeechJ., PrinsJ.F., and HermansJ.1996. SMD: Visual steering of molecular dynamics for protein design. Comput. Sci. Eng., 3, 38–45.
31.
LewisS.M., WuX., PustilnikA., et al.2014. Generation of bispecific IgG antibodies by structure-based design of an orthogonal Fab interface. Nat. Biotechnol., 32, 191–198.
32.
LilienR.H., StevensB.W., AndersonA.C., and DonaldB.R.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.
33.
PierceN.A., and WinfreeE.2002. Protein design is NP-hard. Protein Eng. 15, 779–782.
34.
QiS., PangY., HuQ., et al.2010. Crystal structure of the Caenorhabditis elegans apoptosome reveals an octameric assembly of CED-4. Cell, 141, 446–457.
35.
RobertsK.E.2014. Novel computational protein design algorithms with applications to cystic fibrosis and HIV [Ph.D. dissertation]. Duke University, Durham, NC.
36.
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.
37.
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.
38.
SitkoffD., SharpK.A., and HonigB.1994. Accurate calculation of hydration free energies using macroscopic solvent models. J. Phys. Chem., 98, 1978–1988.
39.
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.
40.
YanN., ChaiJ., LeeE.S., et al.2005. Structure of the CED-4–CED-9 complex provides insights into programmed cell death in Caenorhabditis elegans. Nature, 437, 831–837.
41.
YanoverC., FromerM., and ShifmanJ.M.2007. Dead-end elimination for multistate protein design. J. Comput. Chem., 28, 2122–2129.
42.
ZhengF., YangW., KoM., et al.2008. Most efficient cocaine hydrolase designed by virtual screening of transition states. J. Am. Chem. Soc., 130, 12148–12155.
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.
