Minimization-Aware Recursive K*: A Novel, Provable Algorithm that Accelerates Ensemble-Based Protein Design and...

Area of Science:

• Computational biology and biophysics
• Protein engineering and design
• Bioinformatics and computational methods

Background:

• Accurate protein modeling requires accounting for sidechain flexibility and conformational ensembles.
• Existing algorithms like iMinDEE-A*-K* approximate protein partition functions but struggle with conformational energy correlations.
• The inability to exploit the correlation between similar conformations and similar energies limits the efficiency of current protein design tools.

Purpose of the Study:

• To introduce a novel algorithm, Minimization-Aware Recursive K* (MARK*), that addresses the limitations of previous protein design methods.
• To improve the efficiency and accuracy of approximating protein partition functions and energy landscapes.
• To enable new analyses of protein conformational changes and binding events.

Main Methods:

• Development of Minimization-Aware Enumeration and Recursive K* concepts.
• Integration of these concepts into the MARK* algorithm.
• Comparison of MARK* against iMinDEE-A*-K* using the Branch and Bound over K* (BBK*) algorithm on 200 design problems.
• Application of MARK* to analyze the energy landscape changes of an HIV-1 capsid protein.

Main Results:

• MARK* enumerates and minimizes significantly fewer conformations compared to the state-of-the-art.
• MARK* achieves up to two orders of magnitude faster performance than iMinDEE-A*-K*.
• MARK* provably approximates protein energy landscapes, a capability not previously achieved.
• Analysis of HIV-1 capsid protein reveals changes in conformational entropy upon binding.

Conclusions:

• MARK* represents a significant advancement in protein design algorithms, offering substantial speedups and improved accuracy.
• The algorithm's ability to approximate energy landscapes opens new avenues for understanding protein behavior.
• MARK* enhances existing protein design workflows and provides novel analytical capabilities for molecular interactions.