Variable Neighborhood Search with Cost Function Networks To Solve Large Computational Protein Design Problems.

Area of Science:

• Computational biology
• Protein engineering
• Bioinformatics

Background:

• Computational protein design (CPD) seeks amino acid sequences for specific protein structures and functions.
• Effective CPD relies on rotamer libraries, energy functions, and search algorithms.
• Variable Neighborhood Search (VNS) offers a robust framework for optimizing energy calculations.

Purpose of the Study:

• To introduce and evaluate a novel CPD heuristic algorithm based on VNS.
• To assess the performance of the VNS heuristic against established methods like Monte Carlo (MC).
• To demonstrate the efficacy of VNS for complex protein redesign challenges.

Main Methods:

• Development of a VNS-based CPD heuristic algorithm.
• Gradual expansion of the explored solution space using a probabilistic heuristic.
• Testing the algorithm on 99 fixed-backbone protein designs from SH2, SH3, and PDZ families.
• Comparison with Monte Carlo, replica-exchange MC, and steepest-descent minimization.

Main Results:

• The VNS heuristic outperformed MC and steepest-descent methods in most cases.
• VNS achieved equal or lower best energies for protein designs.
• For complete protein redesign, VNS yielded solutions 2.5 to 11.2 kcal/mol lower in energy.
• The VNS algorithm is implemented in the toulbar2 software.

Conclusions:

• The proposed VNS heuristic is a powerful and efficient tool for computational protein design.
• VNS provides superior performance, especially for large-scale and complex protein redesign problems.
• This approach has significant potential to advance the field of protein engineering.