Efficient Use of Semidefinite Programming for Selection of Rotamers in Protein Conformations

Determination of a protein's structure can facilitate an understanding of how the structure changes when that protein combines with other proteins or smaller molecules. In this paper we study a semidefinite programming (SDP) relaxation of the (NP-hard) side chain positioning problem presented in Chazelle et al [Chazelle B, Kingsford C, Singh M (2004) A semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Comput. 16:380-392]. We show that the Slater constraint qualification (strict feasibility) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the SDP. In fact, after applying facial reduction, we have a smaller problem that is more stable both in theory and in practice. We include cutting planes to improve the rounded SDP approximate solutions.