A semidefinite programming approach to side chain positioning with new rounding strategies

A semidefinite programming approach to side chain positioning with new rounding strategies

0.00 Avg rating0 Votes
Article ID: iaor2007230
Country: United States
Volume: 16
Issue: 4
Start Page Number: 380
End Page Number: 392
Publication Date: Sep 2004
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: programming (semidefinite), Protein design
Abstract:

Side chain positioning is an important subproblem of the general protein-structure-prediction problem, with applications in homology modeling and protein design. The side chain positioning problem takes a fixed backbone and a protein sequence and predicts the lowest energy conformation of the protein's side chains on this backbone. We study a widely used version of the problem where the side chain positioning procedure uses a rotamer library and an energy function that can be expressed as a sum of pairwise terms. The problem is NP-complete; we show that it cannot even be approximated. In practice, it is tackled by a variety of general search techniques and specialized heuristics. Here, we propose formulating the side chain positioning problem as an instance of semidefinite programming (SDP). We introduce two novel rounding schemes and provide theoretical justification for their effectiveness under various conditions. We apply our method on simulated data, as well as on the computational redesign of two naturally occurring protein cores, and show that our SDP approach generally finds good solutions. Beyond the context of side chain positioning, our very general rounding schemes should be applicable elsewhere.

Reviews

Required fields are marked *. Your email address will not be published.