Related Experiment Videos
On the complexity of protein folding
P Crescenzi1, D Goldman, C Papadimitriou
1Dipartimento di Sistemi e Informatica, Università di Firenze, Italy.
Summary
The protein folding problem in the 2D H-P model is NP-complete. This finding has significant implications for computational biology and protein structure prediction.
Area of Science:
- Computational biology
- Theoretical computer science
- Biophysics
Background:
- The protein folding problem seeks to predict a protein's three-dimensional structure from its amino acid sequence.
- The Hydrophobic-Polar (H-P) model is a simplified lattice model used to study protein folding.
- Understanding protein folding is crucial for deciphering biological function and disease mechanisms.
Purpose of the Study:
- To determine the computational complexity of the protein folding problem within the 2D H-P model.
- To establish a theoretical foundation for the difficulty of solving protein folding using this model.
Main Methods:
- Utilized techniques from computational complexity theory.
- Developed a reduction from a known NP-complete problem to the 2D H-P protein folding problem.
Main Results:
- The protein folding problem in the two-dimensional H-P model is proven to be NP-complete.
- This demonstrates that finding the optimal fold in this model is computationally intractable for large proteins.
Conclusions:
- The NP-completeness result implies that efficient algorithms for the general 2D H-P protein folding problem are unlikely to exist.
- This complexity highlights the challenges in computational protein structure prediction and suggests the need for heuristic or approximation approaches.