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

Bernard Chazelle, Carl Kingsford, Mona Singh

Research output: Contribution to journalArticlepeer-review

71 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)380-392
Number of pages13
JournalINFORMS Journal on Computing
Issue number4
StatePublished - 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


  • Computational biology
  • Semidefinite programming
  • Side chain positioning


Dive into the research topics of 'A semidefinite programming approach to side chain positioning with new rounding strategies'. Together they form a unique fingerprint.

Cite this