review-article

Free access

Protein design by provable algorithms

Authors:

Mark A. Hallen,

Bruce R. DonaldAuthors Info & Claims

Communications of the ACM, Volume 62, Issue 10

Pages 76 - 84

https://doi.org/10.1145/3338124

Published: 24 September 2019 Publication History

All formats PDF

Abstract

Protein design algorithms can leverage provable guarantees of accuracy to provide new insights and unique optimized molecules.

References

[1]

Chazelle, B., Kingsford, C. and Singh, M. A semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Computing, Computational Biology Special Issue 16, 4 (2004), 380--392.

Google Scholar

[2]

Chen, C., Georgiev, I., Anderson, A. and Donald, B. Computational structure-based redesign of enzyme activity. Proc. Nat. Acad. Sci. U. S. A. 106, 10 (2009), 3764--3769.

Google Scholar

[3]

Davey, J., Damry, A., Goto, N. and Chica, R. Rational design of proteins that exchange on functional timescales. Nature Chemical Biology 13, 12 (2017), 1280.

Crossref

Google Scholar

[4]

Desmet, J., Maeyer, M., Hazes, B. and Lasters, I. The dead-end elimination theorem and its use in protein sidechain positioning. Nature 356 (1992), 539--542.

Crossref

Google Scholar

[5]

Donald, B. Algorithms in Structural Molecular Biology. MIT Press, Cambridge, MA, 2011.

Digital Library

Google Scholar

[6]

Frey, K., Georgiev, I., Donald, B. and Anderson, A. Predicting resistance mutations using protein design algorithms. Proc. Nat. Acad. Sci. U. S. A. 107, 31 (2010), 13707--13712.

Crossref

Google Scholar

[7]

Fromer, M., Yanover, C., and Linial, M. Design of multispecific protein sequences using probabilistic graphical modeling. Proteins: Structure, Function, and Bioinformatics 78, 3 (2010), 530--547.

Google Scholar

[8]

Gainza, P., Nisonoff, H. and Donald, B. Algorithms for protein design. Current Opinion in Structural Biology 39 (2016), 16--26.

Crossref

Google Scholar

[9]

Gainza, P., Roberts, K. and Donald, B. Protein design using continuous rotamers. PLoS Computational Biology 8, 1 (2012), e1002335.

Crossref

Google Scholar

[10]

Gainza, P. et al. OSPREY: Protein design with ensembles, flexibility, and provable algorithms. Methods in Enzymology 523 (2013), 87--107.

Crossref

Google Scholar

[11]

Gainza, P., Vollers, S. and Correia, B. Mining protein surfaces for binding seeds. (Aug. 2017). RosettaCon.

Google Scholar

[12]

Georgiev, I., Lilien, R. and Donald, B. 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. Computational Chemistry 29, 10 (2008), 1527--1542.

Crossref

Google Scholar

[13]

Grigoryan, G., Reinke, A. and Keating, A. Design of protein-interaction specificity affords selective bZIP-binding peptides. Nature 458, 7240 (2009), 859--864.

Crossref

Google Scholar

[14]

Grigoryan, G., Zhou, F., Lustig, S., Ceder, G., Morgan, D., and Keating, A. Ultra-fast evaluation of protein energies directly from sequence. PLoS Computational Biology 2, 6 (2006), e63.

Crossref

Google Scholar

[15]

Hallen, M. and Donald, B. 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. J. Computational Biology 23, 5 (2016), 311--321.

Crossref

Google Scholar

[16]

Hallen, M. and Donald, B. CATS (Coordinates of Atoms by Taylor Series): Protein design with backbone flexibility in all locally feasible directions. Bioinformatics 33, 14 (2017), i5--i12.

Crossref

Google Scholar

[17]

Hallen, M., Jou, J. and Donald, B. LUTE (Local Unpruned Tuple Expansion): Accurate continuously flexible protein design with general energy functions and rigid-rotamer-like efficiency. In Proceedings of the Intern. Conf. on Research in Computational Molecular Biology. Springer, 2016, 122--136.

Crossref

Google Scholar

[18]

Hallen, M., Keedy, D. and Donald, B. Dead-end elimination with perturbations (DEEPer): A provable protein design algorithm with continuous sidechain and backbone flexibility. Proteins: Structure, Function and Bioinformatics 81, 1 (2013), 18--39.

Crossref

Google Scholar

[19]

Hallen, M. et al. OSPREY 3.0: Open-source protein redesign for you, with powerful new features. J. Computational Chemistry 39, 30 (2018), 2494--2507.

Google Scholar

[20]

Jou, J., Jain, S., Georgiev, I., and Donald, B. BWM*: A Novel, Provable, Ensemble-Based Dynamic Programming Algorithm for Sparse Approximations of Computational Protein Design. Journal of Computational Biology 23, 6 (2016), 413--424.

Google Scholar

[21]

Kingsford, C., Chazelle, B., and Singh, M. Solving and analyzing sidechain positioning problems using linear and integer programming. Bioinformatics 21, 7 (2005), 1028--1039.

Digital Library

Google Scholar

[22]

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

Crossref

Google Scholar

[23]

Lilien, R., Stevens, B., Anderson, A. and Donald, B. 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. Computational Biology 12, 6 (2005), 740--761.

Crossref

Google Scholar

[24]

LuCore, S., Litman, J., Powers, K., Gao, S., Lynn, A., Tollefson, W., Fenn, T., Washington, T. and Schnieders, M. Dead-end elimination with a polarizable force field repacks PCNA structures. Biophysical J. 109, 4 (2015), 816--826.

Crossref

Google Scholar

[25]

Ojewole, A., Jou, J., Fowler, V. and Donald, B. BBK*(Branch and Bound Over K*): A provable and efficient ensemble-based protein design algorithm to optimize stability and binding affinity over large sequence spaces. J. Computational Biology (2018). Epub ahead of print.

Google Scholar

[26]

Parker, A., Choi, Y., Griswold, K. and Bailey-Kellogg, C. Structure-guided deimmunization of therapeutic proteins. J. Computational Biology 20, 2 (2013), 152--165.

Crossref

Google Scholar

[27]

Pierce, N. and Winfree, E. Protein design is NP-hard. Protein Engineering 15, 10 (2002), 779--782.

Crossref

Google Scholar

[28]

Reeve, S., Gainza, P., Frey, K., Georgiev, I., Donald, B. and Anderson, A. Protein design algorithms predict viable resistance to an experimental antifolate. In Proceedings of the Nat. Acad. Sci. U. S. A. 112, 3 (2015), 749--754.

Crossref

Google Scholar

[29]

Roberts, K., Cushing, P., Boisguerin, P., Madden, D. and Donald, B. Computational design of a PDZ domain peptide inhibitor that rescues CFTR activity. PLoS Computational Biology 8, 4 (2012), e1002477.

Crossref

Google Scholar

[30]

Rudicell, R. et al. Enhanced potency of a broadly neutralizing HIV-1 antibody in vitro improves protection against lentiviral infection in vivo. J. Virology 88, 21 (2014), 12669--12682.

Crossref

Google Scholar

[31]

Simoncini, D., Allouche, D., Givry, S., Delmas, C., Barbe, S. and Schiex, T. Guaranteed discrete energy optimization on large protein design problems. J. Chemical Theory and Computation 11, 12 (2015), 5980--5989.

Crossref

Google Scholar

[32]

Traoré, S., Allouche, D., André, I., Givry, S., Katsirelos, G., Schiex, T. and Barbe, S. A new framework for computational protein design through cost function network optimization. Bioinformatics 29, 17 (2013), 2129--2136.

Crossref

Google Scholar

[33]

Traoré, S., Roberts, K., Allouche, D., Donald, B., André, I., Schiex, T., and Barbe, S. Fast search algorithms for computational protein design. J. Computational Chemistry 37, 12 (2016), 1048--1058.

Crossref

Google Scholar

[34]

Viricel, C., Simoncini, D., Allouche, D., Givry, S., Barbe, S. and Schiex, T. Approximate counting with deterministic guarantees for affinity computation. Modelling, Computation and Optimization in Information Systems and Management Sciences. Springer, 2015, 165--176.

Google Scholar

[35]

Vizcarra, C., Zhang, N., Marshall, S., Wingreen, N., Zeng, C. and Mayo, S. An improved pairwise decomposable finite-difference Poisson-Boltzmann method for computational protein design. J. Computational Chemistry 29, 7 (2008), 1153--1162.

Crossref

Google Scholar

[36]

Xu, J. and Berger, B. Fast and accurate algorithms for protein side-chain packing. J. ACM 53, 4 (2006), 533--557.

Digital Library

Google Scholar

[37]

Yanover, C., Fromer, M. and Shifman, J. Deadend elimination for multistate protein design. J. Computational Chemistry 28, 13 (2007), 2122--2129.

Crossref

Google Scholar

[38]

Zanghellini, A., Jiang, L., Wollacott, A., Cheng, G., Meiler, J., Althoff, E., Röthlisberger, D. and Baker, D. New algorithms and an in silico benchmark for computational enzyme design. Protein Science 15, 12 (2006), 2785--2794.

Crossref

Google Scholar

[39]

Zhou, J. and Grigoryan, G. Rapid search for tertiary fragments reveals protein sequence-structure relationships. Protein Science 24, 4 (2015), 508--524.

Crossref

Google Scholar

[40]

Zhou, Y., Xu, W., Donald, B. and Zeng, J. An efficient parallel algorithm for accelerating computational protein design. Bioinformatics 30, 12 (2014), i255--i263.

Crossref

Google Scholar

Cited By

View all

Childs HGuerin NZhou PDonald B(2024) Protocol for Designing De Novo Noncanonical Peptide Binders in OSPREY Journal of Computational Biology10.1089/cmb.2024.066931:10(965-974)Online publication date: 1-Oct-2024
https://doi.org/10.1089/cmb.2024.0669
Colom MVučinić JAdolf‐Bryfogle JBowman JVerel SMoczygemba ISchiex TSimoncini DBahl C(2024)Complete combinatorial mutational enumeration of a protein functional site enables sequence‐landscape mapping and identifies highly‐mutated variants that retain activityProtein Science10.1002/pro.510933:8Online publication date: 11-Jul-2024
https://doi.org/10.1002/pro.5109
Pezeshki BMarinescu RIhler ADechter REvans RShpitser I(2023)Boosting AND/OR-based computational protein designProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625990(1662-1672)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625990
Show More Cited By

Index Terms

Protein design by provable algorithms
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
  2. Symbolic and algebraic manipulation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Specificity and affinity quantification of protein–protein interactions

Motivation: Most biological processes are mediated by the protein–protein interactions. Determination of the protein–protein structures and insight into their interactions are vital to understand the mechanisms of protein functions. Currently, ...
Design of protein-protein interactions with a novel ensemble-based scoring algorithm
RECOMB'11: Proceedings of the 15th Annual international conference on Research in computational molecular biology

Protein-protein interactions (PPIs) are vital for cell signaling, protein trafficking and localization, gene expression, and many other biological functions. Rational modification of PPI targets provides a mechanism to understand their function and ...
Epitopes based drug design for dengue virus envelope protein

Display Omitted A conserved region QHGTI in B and T cell epitopes of dengue envelope glycoprotein was predicted.A reverse pharmacophore mapping approach was used to develop phamacophore model.ChemBridge database of compounds was screen on the basis of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 62, Issue 10

October 2019

89 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/3363418

Editor:
Andrew A. Chien
Association for Computing Machinery, New York, NY

Issue’s Table of Contents

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 September 2019

Published in CACM Volume 62, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Review-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
6,380
Total Downloads

Downloads (Last 12 months)299
Downloads (Last 6 weeks)23

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Childs HGuerin NZhou PDonald B(2024) Protocol for Designing De Novo Noncanonical Peptide Binders in OSPREY Journal of Computational Biology10.1089/cmb.2024.066931:10(965-974)Online publication date: 1-Oct-2024
https://doi.org/10.1089/cmb.2024.0669
Colom MVučinić JAdolf‐Bryfogle JBowman JVerel SMoczygemba ISchiex TSimoncini DBahl C(2024)Complete combinatorial mutational enumeration of a protein functional site enables sequence‐landscape mapping and identifies highly‐mutated variants that retain activityProtein Science10.1002/pro.510933:8Online publication date: 11-Jul-2024
https://doi.org/10.1002/pro.5109
Pezeshki BMarinescu RIhler ADechter REvans RShpitser I(2023)Boosting AND/OR-based computational protein designProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625990(1662-1672)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625990
Talluri S(2022)Algorithms for protein designProtein Design and Structure10.1016/bs.apcsb.2022.01.003(1-38)Online publication date: 2022
https://doi.org/10.1016/bs.apcsb.2022.01.003
Bouchiba YRuffini MSchiex TBarbe S(2022)Computational Design of Miniprotein BindersComputational Peptide Science10.1007/978-1-0716-1855-4_17(361-382)Online publication date: 18-Mar-2022
https://doi.org/10.1007/978-1-0716-1855-4_17
El-Fakdi Ade la Rosa J(2021)Analysis of Nature-Inspired Algorithms for Long-Term Digital PreservationMathematics10.3390/math91822799:18(2279)Online publication date: 16-Sep-2021
https://doi.org/10.3390/math9182279
Defresne MBarbe SSchiex T(2021)Protein Design with Deep LearningInternational Journal of Molecular Sciences10.3390/ijms22211174122:21(11741)Online publication date: 29-Oct-2021
https://doi.org/10.3390/ijms222111741
Bouchiba YCortés JSchiex TBarbe S(2021)Molecular flexibility in computational protein design: an algorithmic perspectiveProtein Engineering, Design and Selection10.1093/protein/gzab01134Online publication date: 7-May-2021
https://doi.org/10.1093/protein/gzab011
Cheng SMa LLu HLei XShi Y(2021)Evolutionary computation for solving search-based data analytics problemsArtificial Intelligence Review10.1007/s10462-020-09882-x54:2(1321-1348)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10462-020-09882-x
Beuvin Fde Givry SSchiex TVerel SSimoncini D(2021)Iterated local search with partition crossover for computational protein designProteins: Structure, Function, and Bioinformatics10.1002/prot.2617489:11(1522-1529)Online publication date: 17-Jul-2021
https://doi.org/10.1002/prot.26174
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Specificity and affinity quantification of protein–protein interactions

Design of protein-protein interactions with a novel ensemble-based scoring algorithm

Epitopes based drug design for dengue virus envelope protein

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Digital Edition

Magazine Site

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations