A Novel Branch-and-Bound Algorithm for the Protein Folding Problem in the 3D HP Model

Area of Science:

• Bioinformatics
• Biophysical Chemistry
• Computational Biology

Background:

• The protein folding problem (PFP) is a fundamental challenge in understanding protein structure and function.
• The hydrophobic-polar (HP) model is a simplified lattice model widely used to study protein folding dynamics.
• The 3D lattice HP model for PFP is NP-complete, necessitating efficient algorithms for near-optimal solutions.

Purpose of the Study:

• To develop a novel algorithm for solving the protein folding problem within the 3D lattice HP model.
• To improve the efficiency and accuracy of finding optimal protein energy structures.

Main Methods:

• Implementation of a branch-and-bound algorithm tailored for the 3D lattice HP model.
• Testing the algorithm on 10 48-monomer benchmark protein sequences.

Main Results:

• The proposed algorithm successfully finds the lowest energy structures for the tested benchmark sequences.
• Achieved comparable computation times to existing methods while delivering superior or equal energy results.

Conclusions:

• The branch-and-bound approach offers an effective strategy for solving the 3D lattice HP protein folding problem.
• This algorithm advances the ability to predict protein structures with higher accuracy and efficiency.