Solving and analyzing side-chain positioning problems using linear and integer programming

Area of Science:

• Computational Biology
• Structural Bioinformatics
• Protein Engineering

Background:

• Side-chain positioning is crucial for homology modeling and protein design.
• Optimizing side-chain conformations with fixed backbones is computationally challenging (NP-complete).

Purpose of the Study:

• To provide a practical context for the computational hardness of side-chain positioning.
• To develop and evaluate efficient computational methods for this problem.

Main Methods:

• Formulation of side-chain positioning using integer linear programming (ILP).
• Development of a linear programming (LP) heuristic by relaxing the ILP integrality constraint.
• Application of LP and ILP to side-chain positioning on native/homologous backbones and protein design.

Main Results:

• LP efficiently finds optimal side-chain positions for native and homologous backbones with simple energy functions.
• The LP heuristic is often insufficient for the protein design problem.
• ILP successfully solves complex protein design instances, even for large datasets.
• LP/ILP approaches demonstrate high effectiveness in finding optimal and near-optimal solutions across various energy functions.

Conclusions:

• LP-based methods are highly effective for optimizing side-chain positioning in protein modeling.
• ILP provides a robust solution for challenging protein design problems.
• This study offers the first large-scale validation of LP/ILP for side-chain positioning.