A New Distributed Algorithm for Side-Chain Positioning in the Process of Protein Docking^*

Area of Science:

• Computational biology
• Structural bioinformatics
• Biochemistry

Background:

• Side-chain positioning (SCP) is crucial for computational protein docking.
• Existing SCP methods are often adapted from protein folding, not optimized for docking's unique structural properties.

Purpose of the Study:

• To develop a novel algorithm for side-chain positioning specifically tailored for protein docking.
• To improve the accuracy and efficiency of protein-protein interaction predictions.

Main Methods:

• Formulated side-chain positioning as a Maximum Weighted Independent Set (MWIS) problem on a constructed graph.
• Developed an approximate algorithm solving a relaxation of MWIS, followed by solution rounding.
• Implemented a fully distributed algorithm utilizing local information and message-passing.

Main Results:

• The new algorithm produced predictions close to native structures for enzyme-inhibitor complexes.
• Performance was comparable to state-of-the-art methods.
• Including rotamers from unbound protein structures significantly enhanced prediction accuracy.
• The SCP algorithm demonstrably improved overall protein docking results.

Conclusions:

• The proposed MWIS-based SCP algorithm offers a novel and effective approach for computational protein docking.
• The distributed nature of the algorithm allows for scalability on large networks.
• Optimizing side-chain positioning is critical for accurate protein docking predictions.