Is protein folding problem really a NP-complete one? First investigations

Area of Science:

• Computational Biology
• Biophysics
• Bioinformatics

Background:

• Determining protein 3D conformation is crucial for understanding protein function and molecular interactions.
• Protein folding is generally believed to result in conformations that minimize free energy.
• Predicting protein 3D structure from amino acid sequences is an NP-complete problem, necessitating computational models and artificial intelligence.

Purpose of the Study:

• To investigate the accuracy of low-resolution models (2D HP square and 3D HP cubic) in predicting protein backbone structure by minimizing free energy.
• To analyze the self-avoiding walk (SAW) requirement used in NP-completeness proofs and prediction programs.
• To compare these computational SAW requirements with actual biological constraints in protein folding.

Main Methods:

• Analysis of NP-completeness proofs for protein folding.
• Examination of low-resolution lattice models (2D HP square, 3D HP cubic) used in protein structure prediction.
• Comparison of theoretical self-avoiding walk (SAW) constraints with biological reality.

Main Results:

• The self-avoiding walk (SAW) requirement used in NP-completeness proofs differs from that used in prediction programs.
• Both computational SAW requirements are distinct from the actual biological constraints governing protein folding.
• Current in silico prediction methods may consider conformations that are not biologically feasible.

Conclusions:

• The discrepancy between computational and biological self-avoiding walk (SAW) requirements can impact the accuracy of protein 3D structure predictions.
• Further research is needed to refine computational models to better align with biological realities for more precise protein folding predictions.
• This work highlights potential limitations in current bioinformatics tools for protein structure determination.