Abstract
Proteins are chains of simple molecules called amino acids. The three-dimensional shape of a protein and its amino acid composition define its biological function. Over millions of years, living organisms have evolved and produced a large catalog of proteins. By exploring the space of possible amino-acid sequences, protein engineering aims at similarly designing tailored proteins with specific desirable properties. In Computational Protein Design (CPD), the challenge of identifying a protein that performs a given task is defined as the combinatorial optimization problem of a complex energy function over amino acid sequences.
In this paper, we introduce the CPD problem and some of the main approaches that have been used to solve it. We then show how this problem directly reduces to Cost Function Network (CFN) and 0/1LP optimization problems. We construct different real CPD instances to evaluate CFN and 0/1LP algorithms as implemented in the toulbar2 and cplex solvers. We observe that CFN algorithms bring important speedups compared to the CPD platform osprey but also to cplex.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anfinsen, C.: Principles that govern the folding of protein chains. Science 181(4096), 223–253 (1973)
Bistarelli, S., Faltings, B., Neagu, N.: Interchangeability in Soft CSPs. In: O’Sullivan, B. (ed.) Constraint Solving and CLP. LNCS (LNAI), vol. 2627, pp. 31–46. Springer, Heidelberg (2003)
Boas, F., Harbury, P.: Potential energy functions for protein design. Current Opinion in Structural Biology 17(2), 199–204 (2007)
Case, D., Darden, T., Cheatham III, T., Simmerling, C., Wang, J., Duke, R., Luo, R., Merz, K., Pearlman, D., Crowley, M., Walker, R.C., Zhang, W., Wang, B., Hayik, S., Roitberg, A., Seabra, G., Wong, K.F., Paesani, F., Wu, X., Brozell, S., Tsui, V., Gohlke, H., Yang, L., Tan, C., Mongan, J., Hornak, V., Cui, G., Beroza, P., Mathews, D.H., Schafmeister, C., Ross, W.S., Kollman, P.A.: Amber 9. University of California, San Francisco (2006)
Cooper, M.C., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., Werner, T.: Soft arc consistency revisited. Artificial Intelligence 174, 449–478 (2010)
Cooper, M.C., de Givry, S., Schiex, T.: Optimal soft arc consistency. In: Proc. of IJCAI 2007, Hyderabad, India, pp. 68–73 (January 2007)
Cooper, M.C.: Fundamental properties of neighbourhood substitution in constraint satisfaction problems. Artificial Intelligence 90(1-2), 1–24 (1997)
Dahiyat, B., Mayo, S.: Protein design automation. Protein Science 5(5), 895–903 (1996)
Desmet, J., Maeyer, M., Hazes, B., Lasters, I.: The dead-end elimination theorem and its use in protein side-chain positioning. Nature 356(6369), 539–542 (1992)
Desmet, J., Spriet, J., Lasters, I.: Fast and accurate side-chain topology and energy refinement (FASTER) as a new method for protein structure optimization. Proteins: Structure, Function, and Bioinformatics 48(1), 31–43 (2002)
Fersht, A.: Structure and mechanism in protein science: a guide to enzyme catalysis and protein folding. WH Freemean and Co., New York (1999)
Georgiev, I., Lilien, R., Donald, B.: Improved pruning algorithms and divide-and-conquer strategies for dead-end elimination, with application to protein design. Bioinformatics 22(14), e174–e183 (2006)
Georgiev, I., Lilien, R., 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. Journal of Computational Chemistry 29(10), 1527–1542 (2008)
Goldstein, R.: Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophysical Journal 66(5), 1335–1340 (1994)
Grunwald, I., Rischka, K., Kast, S., Scheibel, T., Bargel, H.: Mimicking biopolymers on a molecular scale: nano (bio) technology based on engineered proteins. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 367(1894), 1727–1747 (2009)
Harvey, W.D., Ginsberg, M.L.: Limited discrepency search. In: Proc. of the 14th IJCAI, Montréal, Canada (1995)
Hawkins, G., Cramer, C., Truhlar, D.: Parametrized models of aqueous free energies of solvation based on pairwise descreening of solute atomic charges from a dielectric medium. The Journal of Physical Chemistry 100(51), 19824–19839 (1996)
Khare, S., Kipnis, Y., Takeuchi, R., Ashani, Y., Goldsmith, M., Song, Y., Gallaher, J., Silman, I., Leader, H., Sussman, J., et al.: Computational redesign of a mononuclear zinc metalloenzyme for organophosphate hydrolysis. Nature Chemical Biology 8(3), 294–300 (2012)
Kingsford, C., Chazelle, B., Singh, M.: Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics 21(7), 1028–1039 (2005)
Koster, A., van Hoesel, S., Kolen, A.: Solving frequency assignment problems via tree-decomposition. Tech. Rep. RM/99/011, Universiteit Maastricht, Maastricht, The Netherlands (1999)
Kuhlman, B., Baker, D.: Native protein sequences are close to optimal for their structures. Proceedings of the National Academy of Sciences 97(19), 10383 (2000)
Larrosa, J., de Givry, S., Heras, F., Zytnicki, M.: Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proc. of the 19th IJCAI, Edinburgh, Scotland, pp. 84–89 (August 2005)
Larrosa, J., Meseguer, P., Schiex, T., Verfaillie, G.: Reversible DAC and other improvements for solving max-CSP. In: Proc. of AAAI 1998, Madison, WI (July 1998)
Leach, A., Lemon, A., et al.: Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm. Proteins Structure Function and Genetics 33(2), 227–239 (1998)
Looger, L., Hellinga, H.: Generalized dead-end elimination algorithms make large-scale protein side-chain structure prediction tractable: implications for protein design and structural genomics1. Journal of Molecular Biology 307(1), 429–445 (2001)
Lovell, S., Word, J., Richardson, J., Richardson, D.: The penultimate rotamer library. Proteins: Structure, Function, and Bioinformatics 40(3), 389–408 (2000)
Nestl, B., Nebel, B., Hauer, B.: Recent progress in industrial biocatalysis. Current Opinion in Chemical Biology 15(2), 187–193 (2011)
Pabo, C.: Molecular technology: designing proteins and peptides. Nature 301, 200 (1983)
Peisajovich, S., Tawfik, D.: Protein engineers turned evolutionists. Nature Methods 4(12), 991–994 (2007)
Pierce, N., Spriet, J., Desmet, J., Mayo, S.: Conformational splitting: A more powerful criterion for dead-end elimination. Journal of Computational Chemistry 21(11), 999–1009 (2000)
Pierce, N., Winfree, E.: Protein design is NP-hard. Protein Engineering 15(10), 779–782 (2002)
Pleiss, J.: Protein design in metabolic engineering and synthetic biology. Current Opinion in Biotechnology 22(5), 611–617 (2011)
Raha, K., Wollacott, A., Italia, M., Desjarlais, J.: Prediction of amino acid sequence from structure. Protein Science 9(6), 1106–1119 (2000)
Schiex, T.: Arc Consistency for Soft Constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 411–424. Springer, Heidelberg (2000)
Swain, M.T., Kemp, G.J.L.: A CLP Approach to the Protein Side-Chain Placement Problem. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 479–493. Springer, Heidelberg (2001)
Voigt, C., Gordon, D., Mayo, S.: Trading accuracy for speed: a quantitative comparison of search algorithms in protein sequence design. Journal of Molecular Biology 299(3), 789–803 (2000)
Wallace, R.J.: Directed Arc Consistency Preprocessing. In: Meyer, M. (ed.) Constraint Processing. LNCS, vol. 923, pp. 121–137. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Allouche, D. et al. (2012). Computational Protein Design as a Cost Function Network Optimization Problem. In: Milano, M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_60
Download citation
DOI: https://doi.org/10.1007/978-3-642-33558-7_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33557-0
Online ISBN: 978-3-642-33558-7
eBook Packages: Computer ScienceComputer Science (R0)