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

Bernard Chazelle, Carl Kingsford, Mona Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationPrinciples of Computing and Knowledge
Subtitle of host publicationParis C. Kanellakis Memorial Workshop
Pages86-94
Number of pages9
StatePublished - Oct 17 2003
EventPCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop - San Diego, CA, United States
Duration: Jun 8 2003Jun 8 2003

Other

OtherPCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop
CountryUnited States
CitySan Diego, CA
Period6/8/036/8/03

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'The Side-Chain Positioning Problem: A Semidefinite Programming Formulation with New Rounding Schemes'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Kingsford, C., & Singh, M. (2003). The Side-Chain Positioning Problem: A Semidefinite Programming Formulation with New Rounding Schemes. In Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop (pp. 86-94)