The Side-Chain Positioning Problem: A Semidefinite Programming Formulation with New Rounding Schemes

Side-chain positioning is a central component of the protein structure prediction problem and has been the focus of a large body of research. The problem is NP-complete; in fact, it is even inapproximable. In practice, it is tackled by a variety of general search techniques and specialized heuristics. We investigate a new formulation of the problem as a semidefinite program. We introduce two novel rounding schemes and provide theoretical justifications for their effectiveness under various input conditions. We also present computational results on simulated data that show that our method outperforms a recently introduced linear programming approach on a wide range of inputs. Beyond the context of side-chain positioning, we are hopeful that our rounding schemes, which are very general, will be applicable elsewhere.