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 language | English (US) |
|---|---|
| Title of host publication | Principles of Computing and Knowledge |
| Subtitle of host publication | Paris C. Kanellakis Memorial Workshop |
| Pages | 86-94 |
| Number of pages | 9 |
| State | Published - Oct 17 2003 |
| Event | PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop - San Diego, CA, United States Duration: Jun 8 2003 → Jun 8 2003 |
Other
| Other | PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop |
|---|---|
| Country/Territory | United States |
| City | San Diego, CA |
| Period | 6/8/03 → 6/8/03 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)