Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Complexity of protein folding

A S Fraenkel1

  • 1Department of Mathematics, University of Pennsylvania, Philadelphia 19104-6395.

Bulletin of Mathematical Biology
|November 1, 1993
PubMed
Summary

Protein folding, crucial for biological function, is computationally very difficult. Mathematical models show that finding a protein's lowest energy state, its native conformation, is an NP-hard problem, suggesting significant computational challenges.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Proof that sequences of A,C,G, and T can be assembled to produce chains of ultimate length avoiding repetitions everywhere.

Progress in nucleic acid research and molecular biologyยท1966
See all related articles

Area of Science:

  • Computational Biology
  • Biophysics
  • Biochemistry

Background:

  • Proteins fold into specific three-dimensional structures essential for their function.
  • The native state of a protein is generally considered its lowest free energy conformation.
  • Predicting this native state is a fundamental challenge in molecular biology.

Purpose of the Study:

  • To analyze the computational complexity of protein folding.
  • To determine if modeling protein folding as a free energy minimization problem is computationally tractable.
  • To explore the implications of the folding problem's complexity.

Main Methods:

  • Development of two- and three-dimensional mathematical models for protein folding.
  • Analysis of these models using computational complexity theory.
  • Classification of the protein folding problem within computational complexity classes.

Main Results:

  • The mathematical models for protein folding as a free energy minimization problem were shown to be NP-hard.
  • This classification places protein folding among computationally difficult problems.
  • The study highlights the inherent computational intractability for certain aspects of protein folding.

Conclusions:

  • The computational difficulty of predicting protein native states is formally demonstrated.
  • This NP-hard nature suggests limitations for exact solutions in large-scale protein folding predictions.
  • The findings have implications for computational approaches and algorithm development in structural biology.

Related Experiment Videos