## AI帮你理解科学

## AI 精读

AI抽取本论文的概要总结

微博一下：

# Computational Complexity, Protein Structure Prediction, and the Levinthal Paradox

(1994)

关键词

摘要

The task of determining the globally optimal (minimum-energy) conformation of a proteingiven its potential-energy function is widely believed to require an amount of computer time thatis exponential in the number of soft degrees of freedom in the protein. Conventional reasoning asto the exponential time complexity of this problem is fall...更多

代码：

数据：

简介

**Introduction to NP**

Completeness Theory

Before the advent of computational complexity theory, computer scientists were in the quandary of not being able to describe or characterize accurately the difficulty of several important computational problems.- One well-known example was the Traveling Salesman Problem (TSP), described in Figure 14-2.
- The central question was this: Were these problems in some way inherently difficult, or was it merely that nobody had been clever enough to discover efficient algorithms for them?.
- The maximum distance M that the salesman is allowed to travel.
- Question: Can the salesman visit each city once and return to the original city from which he departed without traveling further than the maximum distance, M?

重点内容

**Introduction to NP**

Completeness Theory

Before the advent of computational complexity theory, computer scientists were in the quandary of not being able to describe or characterize accurately the difficulty of several important computational problems- The results that we review here are related directly to questions about structure prediction (4) and indirectly to the consideration of folding rates (3), but they have little to do with the existence of unique native structures (1) and the pathway(s) by which a protein folds (2). (This is not to say that the four questions are unrelated to each other
- The proof that Polymer Structure Prediction is NP-hard suggests that exploiting the functional form of the potential energy is not enough to make the problem efficiently solvable
- The arguments that we have proposed, those based on the NP-hardness of Polymer Structure Prediction, are about the computational complexity of exploiting that information to find the configuration of globally minimal energy-in other words, the difficulty of deciding which nativelike propensities to satisfy, given that they cannot all be satisfied at once
- We examine one model from which Zwanzig et al concluded that "Levinthal's paradox becomes irrelevant to protein folding when some ofthe interactions between amino acids are taken into account" (Zwanzig et al, 1992)
- 27 Most known approximation algorithms guarantee solutions with error bounds multiplicatively related to the optimal cost, e.g., "at most 50% worse than optimal." Because absolute energies have little meaning, a useful guarantee for molecularstructure prediction would be additive, e.g., "at most 1 kcallmol worse than optimal." There is no obvious reason that additive guarantees should be more difficult to obtain than multiplicative ones, since an optimization problem does not change if its cost function f is replaced by log f

结果

- 27 Most known approximation algorithms guarantee solutions with error bounds multiplicatively related to the optimal cost, e.g., "at most 50% worse than optimal." Because absolute energies have little meaning, a useful guarantee for molecularstructure prediction would be additive, e.g., "at most 1 kcallmol worse than optimal." There is no obvious reason that additive guarantees should be more difficult to obtain than multiplicative ones, since an optimization problem does not change if its cost function f is replaced by log f.

结论

- The result that PSP is NP-hard goes a step further than previous arguments as to the intractability of protein-structure prediction.
- Useful algorithms for NP-hard problems do exist
- These include exponential-time searches (Section 4.3) and other heuristic algorithms (Section 4.4) that are "fast enough" and "correct enough" to be practical; approximation algorithms (Section 4.5); and algorithms for restricted forms of the problem (Section 4.6).
- The latter two types of algorithm might be eliminated from consideration by future theoretical results (Section 6)

基金

- This research was supported in part by grants from the National Science Foundation and the National Institutes of Health

引用论文

- Abola EE, Bernstein FC, Bryant SH, Koetzle TF, and Weng J (1987): Protein data bank. In Allen FH, Bergerhoff G, Sievers R, eds. Crystallographic DatabasesInformation Content, Software Systems, Scientific Applications, pp. 107-132. Data Commission of the International Union of Crystallography, Bonn/Cambridge/Chester
- Aho AV, Hopcroft JE, Ullman 10 (1974): The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley
- Abo AV, Hopcroft JE, Ullman JD (1982): Data Structures andAlgorithms. Reading, MA: Addison-Wesley
- Amara P, Hsu D, Straub JE (1993): Global energy minimum searches using an approximate solution of the imaginary time SchrOdinger equation. Journal of Physical Chemistry 97:6715-6721
- Anfinsen CB (1973): Principles that govern the folding of protein chains. Science 181 (4096):223-230
- Anfinsen CB, Haber E, Sela M, White FH (1961): The kinetics offormation of native ribonuclease during oxidation of the reduced polypeptide chain. Proceedings of the National Academy of Sciences, USA 47:1309-1314
- Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1992): Proof verification and hardness of approximation problems. In Thirty-Third Annual Symposium on Foundations of Computer Science (FOCS)
- Baldwin RL (1989): How does protein folding get started? Trends Biochem Sci 14:291-294
- Baraff D (1991): Coping with friction for non-penetrating rigid body simulation. Computer Graphics 25(4):31-40
- Barahona F (1982): On the computational complexity of Ising spin glass models. Journal ofPhysics A: Mathematics and General 15:3241-3253
- Berg BA, Neuhaus T (1992): Multicanonical ensemble: A new approach to simulate first-order phase transitions. Physical Review Letters 68(1):9-12
- Bernstein FC, Koetzle TF, Williams GJB, Meyer EF Jr., Brice MD, Rodgers JR, Kennard 0, Shimanouchi T, Tasumi M (1977): The protein data bank: A computerbased archival file for macromolecular structures. Journal ofMolecular Biology 112:535-542
- Bierzynski A, Kim PS, Baldwin RL (1982): A salt bridge stabilizes the helix formed by isolated C-peptide of RNAse A. Proceedings of the National Academy of Sciences, USA 79:2470-2474
- Brooks BR, Bruccoleri RE, Olafson BD, States OJ, Swaminathan S, Karplus M (1983): CHARMM: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry 4(2): 187-217
- Brown JE, Klee WA (1971): Helix-coil transition of the isolated amino terminus. Biochemistry 10(3):470-476
- Bruccoleri RE, Karplus M (1987): Prediction of the folding of short polypeptide segments by uniform conformational sampling. Biopolymers 26:137-168
- Briinger AT, Clore GM, Gronenborn AM, Karplus M (1986): Three-dimensional structure of proteins determined by molecular dynamics with interproton distance restraints: Application to crambin. Proceedings ofthe National Academy ofSciences, USA 83:3801-3805
- Bryngelson JD, Wolynes PG (1989): Intermediates and barrier crossing in a random energy model (with applications to protein folding). Journal of Physical Chemistry 93:6902-6915
- Caftisch A, Miranker A, Karplus M (1993): Multiple copy simultaneous search and construction of ligands in binding sites: Application to inhibitors of HIV-1 aspartic proteinase. Journal ofMedicinal Chemistry 36:2142-2167
- Chan HS, Dill KA (1991): Polymer principles in protein structure and stability. Annual Reviews ofBiophysics and Biophysical Chemistry 20:447-490
- Chang G, Guida WC, Still WC (1989): An internal coordinate Monte Carlo method for searching conformational space. Journal ofthe American Chemical Society 11:4379
- Cheeseman P, Kanefsky B, Taylor WM (1991): Where the really hard problems are. In Proceedings ofIJCAI '91, pp. 163-169
- Christofides N (1976): Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA
- Cook SA (1971): The complexity of theorem-proving procedures. In Proceedings ofthe Third Annual ACM Symposium on the Theory ofComputing, pp. 151-158
- Creighton TE, ed. (1992): Protein Folding. New York: WH Freeman
- Crippen GM (1975): Global optimization and polypeptide conformation. Journal of Computational Physics 18:224-231
- Crippen GM, Scheraga HA (1969): Minimization of polypeptide energy. VIII. Application of the deflation technique to a dipeptide. Proceedings of the National Academy of Sciences, USA 64:42-49
- Crippen GM, Scheraga HA (1971): Minimization ofpolypeptide energy. XI. Method of gentlest ascent. Archives ofBiochemistry and Biophysics 144:462-466
- Dandekar T, Argos P (1992): Potential of genetic algorithms in protein folding and protein engineering simulations. Protein Engineering 5(7):637-645
- Dantzig GB (1963): Linear Programming and Extensions. Princeton, NJ: Princeton University Press
- Davis L (1991): Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold
- Dunbrack RL Jr., Karplus M (1993): Backbone-dependent rotamer library for proteins: Application to side-chain prediction. Journal ofMolecular Biology 230: 543-574
- Dyson HJ, Rance M, Houghten RA, Lerner RA, Wright PE (1988a): Folding of immunogenic peptide fragments of proteins in water solution. I. Sequence requirements for the formation of a reverse tum. Journal of Molecular Biology 201(1):161-200
- Dyson HJ, Rance M, Houghten RA, Wright PE, Lerner RA (l988b): Folding of immunogenic peptide fragments of proteins in water solution. II. The nascent helix. Journal ofMolecular Biology 201(1):201-217
- Elber R, Karplus M (1987): Multiple conformational states of proteins: A molecular dynamics analysis of myoglobin. Science 235:318-321
- Epstein CJ, Goldberger RF, Anfinsen CB (1963): The genetic control of tertiary protein structure: Studies with model systems. Cold Spring Harbor Symposium on Quantitative Biology 28:439-449
- Fasman GD, ed. (1988): Prediction of Protein Structure and The Principles of Protein Conformation. New York: Plenum Press
- Finkelstein AV, Reva BA (1992): Search for the stable state of a short chain in a molecular field. Protein Engineering 5(7):617-624
- Formann M, Wagner F (1991): A packing problem with applications to lettering of maps. In Proceedings of the Seventh Annual Symposium on Computational Geometry, pp. 281-288, North Conway, NH: ACM
- Fraenkel AS (1993): Complexity of protein folding. Bulletin of Mathematical Biology 55(6):1199-1210
- Franco J, Paull M (1983): Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem. Discrete Applied Mathematics 5:77-87
- Garey MR, Johnson DS (1979): Computers and Intractability: A Guide to the Theory ofNP-Completeness. San Francisco: WH Freeman and Company
- Gibson KD, Scheraga HA (1986): Predicted conformations for the immunodominant region of the circumsporozoite protein of the human malaria parasite. Proceedings of the National Academy of Sciences, USA 83:5649-5653
- Goldberg A (1979): On the complexity of the satisfiability problem. Courant Computer Science Report 16, New York University
- Goldberg A, Purdom PW Jr., Brown CA (1982): Average time analysis of simplified Davis-Putnam procedures. Information Processing Letters 15:72-75. See also "Errata," vol. 16, 1983, p. 213
- Gordon HL, Somorjai RL (1992): Applicability ofthe method ofsmoothed functionals as a global minimizer for model polypeptides. Journal ofPhysical Chemistry 96:7116-7121
- Greengard L (1987): The Rapid Evaluation ofPotential Fields in Particle Systems. ACM Distinguished Dissertations. Cambridge, MA: MIT Press
- Greengard L, Rokhlin V (1989): On the evaluation of electrostatic interactions in molecular modeling. Chemica Scripta 29A:139-144
- Harrison SC, Durbin R (1985): Is there a single pathway for the folding of a polypeptide chain? Proceedings of the National Academy of Sciences, USA 82:40284030
- Head-Gordon T, Stillinger PH (1993): Predicting polypeptide and protein structures from amino acid sequence: Antlion method applied to melittin. Biopolymers 33(2):293-303
- Head-Gordon T, Stillinger PH, Arrecis J (1991): A strategy for finding classes of minima on a hypersurface: Implications for approaches to the protein folding problem. Proceedings of the National Academy of Sciences, USA 88:1107611080
- Jaenicke R (1987): Protein folding and protein association. Progress in Biophysics and Molecular Biology 49: 117-237
- Karplus M, Shakhnovich E (1992): Protein folding: Theoretical studies of thermodynamics and dynamics. In Creighton TE, ed., Protein Folding, chapter 4, pp. 127-196. New York: WH Freeman
- Karplus M, Weaver DL (1976): Protein-folding dynamics. Nature 260:404-406
- Karplus M, Weaver DL (1979): Diffusion-collision model for protein folding. Biopolymers 18:1421-1437
- Khachiyan LG (1979): A polynomial time algorithm in linear programming. Soviet Math DokI20:191-194
- KimPS, Baldwin RL (1990): Intermediates in the folding reactions ofsmall proteins. Annual Reviews ofBiochemistry 59:631-660
- Kirkpatrick S, Gelatt CD Jr., Vecchi MP (1983): Optimization by simulated annealing. Science 220:671-680
- Kostrowicki J, Piela L (1991): Diffusion equation method of global minimization: Performance for standard test functions. Journal of Optimization Theory and Applications 69(2):269-284
- Kostrowicki J, Piela L, Cherayil BJ, Scheraga HA (1991): Performance of the diffusion equation method in searches for optimum structures of clusters of Lennard-Jones atoms. Journal ofPhysical Chemistry 95(10):4113-4119
- Kostrowicki J, Scheraga HA (1992): Application of the diffusion equation method for global optimization to oligopeptides. Journal of Physical Chemistry 96: 7442-7449
- Ladner RE (1975): On the structure of polynomial time reducibility. Journal ofthe Association of Computing Machinery 22: 155-171
- Lee C, Subbiah S (1991): Prediction of protein side-chain conformation by packing optimization. Journal ofMolecular Biology 217:373-388
- LeGrand S, Merz K Jr. (1993): The application of the genetic algorithm to the minimization of potential energy functions. Journal of Global Optimization 3:49-66
- Levinthal C (1966): Molecular model-building by computer. Scientific American 214
- Levinthal C (1968): Are there pathways for protein folding? Journal de Chimie Physique 65(1):44-45
- Levinthal C (1969): In Mossbauer Spectroscopy in Biological Systems, pp. 2224.
- Urbana, IL: University of Illinois Press. Proceedings of a meeting held at Allerton House, Monticello, IL
- Lewis HR, Papadimitriou CH (1978): The efficiency of algorithms. Scientific American 238(1):96-109
- Lewis HR, Papadimitriou CH (1981): Elements of the Theory of Computation. Englewood Cliffs, NJ: Prentice-Hall
- Lipton M, Still WC (1988): The multiple minimum problem in molecular modeling. Tree searching internal coordinate conformational space. Journal of Computational Chemistry 9(4):343-355
- Marks J, Shieber S (1991): The computational complexity of cartographic label placement. Technical Report TR-05-91, Harvard University, Cambridge, MA
- Marqusee S, Baldwin RL (1987): Helix stablization by Gly-Lys salt bridges in short peptides of de novo design. Proceedings of the National Academy of Sciences, USA 84:8898-8902
- Metropolis N, Rosenbluth AW, Teller AH, Teller E (1953): Equation of state calculations by fast computing machines. Journal ofChemical Physics 21: 1087-1092
- Mitchell D, Selman B, Levesque H (1992): Hard and easy distributions of SAT problems. In Proceedings ofthe Tenth National Conference on Artificial Intelligence (AAAI '92) pp. 459-465. San Jose, CA: AAAl PresslMIT Press
- Momany FA, McGuire RF, Burgess AW, Scheraga HA (1975): Energy parameters in polypeptides. VII. Geometric parameters, partial atomic charges, nonbonded interactions, hydrogen bond interactions, and intrinsic torsional potentials for the naturally occurring amino acids. Journal of Physical Chemistry 79(22):23612381
- Moult J, James MNG (1986): An algorithm for determining the conformation of polypeptide segments in proteins by systematic search. PROTEINS: Structure, Function, and Genetics 1:146-163
- Moult J, Unger R (1991): An analysis of protein folding pathways. Biochemistry 30:3816-3824
- Ngo IT, Marks J (1991): Computational complexity ofa problem in molecular structure prediction. Technical Report TR-17-91, Harvard University, Cambridge, MA. Older version in which 90° angles were employed
- Ngo IT, Marks J (1992): Computational complexity of a problem in molecularstructure prediction. Protein Engineering 5(4):313-321
- Nilsson NJ (1980): Principles ofArtificial Intelligence. Palo Alto, CA: Tioga Publishing Company
- Papadimitriou CH, Steiglitz K (1982): Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall
- Papadimitriou CH, Yannakakis M (1991): Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43:425-440
- Piela L, Kostrowicki J, Scheraga HA (1989): The multiple-minima problem in the conformational analysis of molecules. Deformation of the potential energy hypersurface by the diffusion equation method. Journal of Physical Chemistry 93(8):3339-3346
- Press WH, Flannery BP, Teukolsky SA, Vetterling WT (1988): Numerical Recipes in C. The Art of Scientific Computing. Cambridge, UK: Cambridge University Press
- Ptitsyn OB (1987): Protein folding: Hypotheses and experiments. Journal ofProtein Chemistry 6:273-293
- Purisima EO, Scheraga HA (1986): An approach to the multiple-minima problem by relaxing dimensionality. Proceedings of the National Academy of Sciences, USA 83:2782-2786
- Purisima EO, Scheraga HA (1987): An approach to the multiple-minima problem in protein folding by relaxing dimensionality. Tests on enkephalin. Journal of Molecular Biology 196:697-709
- Rabin MO (1976): Probabilistic algorithms. In Traub JF, ed., Algorithms and Complexity: New Directions and Recent Results, pp. 21-39. New York: Academic Press
- Rabin MO (1980): Probabilistic algorithms for testing primality. Journal ofNumber Theory 12(1):128-138
- Reeke GN Jr. (1988): Protein folding: Computational approaches to an exponentialtime problem. In Annual Reviews of Computer Science 3:59-84; Annual Reviews, Inc.
- Robson B, Platt E, Fishleigh RV, Marsden A, Millard P (1987): Expert system for protein engineering: Its application in the study of chloroamphenicol acetyltransferase and avian pancreatic polypeptide. Journal of Molecular Graphics 5(1):8-17
- Roder H, Elove GA, Englander SW (1988): Structural characterization of folding intermediates in cytochrome c by H-exchange labelling and proton NMR. Nature 335:700-704
- Sali A, Shakhnovich EI, Karplus M (1994): Kinetics of protein folding: A lattice model study of the requirements for folding to the native state. Journal ofMolecular Biology 235:1614-1636
- Saunders M, Houk KN, Wu Y-D, Still WC, Lipton M, Chang G, Guida WC (1990): Cornformations of cycloheptadecane: A comparison of methods for conformational searching. Journal ofthe American Chemical Society 112:1419-1427
- Scheraga HA (1992): Some approaches to the multiple-minima problem in the calculation ofpolypeptide and protein structures. Internationallournal ofQuantum Chemistry 42: 1529-1536
- Schmidt KE, Lee MA (1991): Implementing the fast multipole method in three dimensions. Journal of Statistical Physics 63(5/6):1223-1235
- Shakhnovich EI, Farztdinov GM, Gutin GM, Karplus M (1991): Protein folding bottlenecks: A lattice Monte-Carlo simulation. Physical Review Letters 67(12):1665-1668
- Shakhnovich EI, Gutin AM (1989): Frozen states of a disordered globular heteropolymer. Journal ofPhysics A22(10):1647-1659
- Shalloway D (1992): Application of the renormalization group to deterministic global minimization of molecular conformation energy functions. Journal of Global Optimization 2:281-311
- Shoemaker KR, Kim PS, Brems DN, Marqusee S, York EJ, Chaiken, 1M, Stewart JM, Baldwin RL (1985): Nature of the charged group effect on the stability of the C-peptide helix. Proceedings of the National Academy of Sciences, USA 82:2349-2353
- Shoemaker KR, Kim PS, York EJ, Stewart 1M, Baldwin RL (1987): Tests of the helix dipole model for stabilization of a-helices. Nature 326:563-567
- Shubert BO (1972a): A sequential method seeking the global maximum of a function. SIAM Journal on Numerical Analysis 9(3):379-388
- Shubert BO (1972b): Sequential optimization of multimodal discrete function with bounded rate of change. Management Science 18(11):687-693
- Sikorski A, Skolnick J (1990): Dynamic Monte Carlo simulations ofglobular protein folding/unfolding pathways. II. a-helical motifs. Journal ofMolecular Biology 212:819-836
- Simon I, Glasser L, Scheraga HA (1991): Calculation of protein conformation as an assembly of stable overlapping segments: Application to bovine pancre-
- atic trypsin inhibitor. Proceedings of the National Academy of Sciences, USA 88:3661-3665
- Summers NL, Karplus M (1990): Modeling of globular proteins: A distance-based data search procedure for the construction of insertion-deletion regions and pro reversible non-pro mutations. Journal ofMolecular Biology 216(4):991-1016
- Sun S (1993): Reduced representation model of protein structure prediction: Statistical potential and genetic algorithms. Protein Science 2(5):762-785
- Tsong TY, Baldwin RL, McPhie P (1972): A sequential model of nucleationdependent protein folding: Kinetic studies of ribonuclease A. Journal of Molecular Biology 63(3):453-475
- Udgaonkar JB, Baldwin RL (1988): NMR evidence for an early framework intermediate on the folding pathway of ribonuclease A. Nature 335:694-699
- Unger R, Moult J (1993): Finding the lowest free energy conformation of a protein is a NP-hard problem: Proof and implications. Bulletin ofMathematical Biology 55(6):1183-1198 van Gunsteren WF, Berendsen HJC, Colonna F, Perahia D, Hollenberg JP, Lellouch D (1984): On searching neighbors in computer simulations of macromolecular systems. Journal of Computational Chemistry 5(3):272-279
- Vasquez M, Scheraga HA (1985): Use of buildup and energy-minimization procedures to compute low-energy structures of the backbone ofenkephalin. Biopolymers 24:1437-1447
- Wawak RJ, Wimmer MM, Scheraga HA (1992): An application of the diffusion equation method of global optimization to water clusters. Journal of Physical Chemistry 96:5138-5145
- Webster (1991): Webster's Ninth Collegiate Dictionary. Springfield, MA: MerriamWebster
- Weiner SJ, Kollman P, Nguyen D, Case DA (1986): An all-atom force field for simulations of proteins and nucleic acids. Journal of Computational Chemistry 7(2):230-252
- Wetlaufer DB (1973): Nucleation, rapid folding, and globular intrachain regions in proteins. Proceedings ofthe National Academy ofSciences, USA 70:697-701
- Zwanzig R, Szabo A, Bagchi B (1992): Levinthal's paradox. Proceedings of the National Academy ofSciences, USA 89:20-22

标签

评论

数据免责声明

页面数据均来自互联网公开来源、合作出版商和通过AI技术自动分析结果，我们不对页面数据的有效性、准确性、正确性、可靠性、完整性和及时性做出任何承诺和保证。若有疑问，可以通过电子邮件方式联系我们：report@aminer.cn