Rotamer optimization for protein design through MAP estimation and problem-size reduction.

Area of Science:

• Computational biology
• Biophysics
• Structural bioinformatics

Background:

• Finding the global minimum energy conformation (GMEC) of protein side chains is crucial for protein structure prediction and design.
• Current methods like dead-end elimination with A* search (DEE/A*) face challenges with dense residue interactions and numerous rotamers in large protein design problems.

Purpose of the Study:

• To introduce BroMAP (branch-and-bound rotamer optimization using MAP estimation), an exact solution method for protein side chain optimization.
• To develop a method that expands smaller search trees and reduces computation time compared to conventional approaches.

Main Methods:

• BroMAP utilizes branch-and-bound search combined with dead-end elimination (DEE) and approximate maximum-a-posteriori (MAP) estimation.
• It reduces problem size within nodes using DEE and lower bounds from MAP estimation.
• Lower bounds guide branching and subproblem selection for efficient discovery of strong upper bounds.

Main Results:

• BroMAP demonstrates faster performance than DEE/A* on large protein design cases.
• BroMAP successfully solved problems intractable for DEE/A* within the time limit.
• Performance was comparable to DEE/A* on cases where DEE/A* performed well.

Conclusions:

• BroMAP is highly effective for large-scale protein design problems where DEE/A* struggles.
• BroMAP can serve as a general replacement for DEE/A* in global minimum energy conformation searches.