Skip Navigation



Bioinformatics Advance Access published online on November 16, 2004
Bioinformatics, doi:10.1093/bioinformatics/bti144
Bioinformatics © Oxford University Press 2004; all rights reserved
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow All Versions of this Article:
21/7/1028    most recent
bti144v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Kingsford, C. L.
Right arrow Articles by Singh, M.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Kingsford, C. L.
Right arrow Articles by Singh, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Received August 1, 2004
Revised October 10, 2004
Accepted November 8, 2004

Article

Solving and analyzing side-chain positioning problems using linear and integer programming

Carleton L. Kingsford 1, Bernard Chazelle 2, and Mona Singh 1*

1 Department of Computer Science and Lewis-Sigler Institute for Integrative Genomics, Princeton University
2 Department of Computer Science, Princeton University

* To whom correspondence should be addressed.
Mona Singh, E-mail: msingh{at}cs.princeton.edu


  Abstract

Motivation: Side-chain positioning is a central component of homology modeling and protein design. In a common formulation of the problem, the backbone is fixed, side-chain conformations come from a rotamer library, and a pairwise energy function is optimized. It is NP-complete to find even a reasonable approximate solution to this problem. We seek to put this hardness result into practical context.

Results: We present an integer linear programming (ILP) formulation of side-chain positioning that allows us to tackle large problem sizes. We relax the integrality constraint to give a polynomial-time linear programming (LP) heuristic. We apply LP to position side chains on native and homologous backbones and to choose side chains for protein design. Surprisingly, when positioning side chains on native and homologous backbones, optimal solutions using a simple, biologically relevant energy function can usually be found using LP. On the other hand, the design problem often cannot be solved using LP directly; however, optimal solutions for large instances can still be found using the computationally more expensive ILP procedure. While different energy functions also affect the difficulty of the problem, the LP/ILP approach is able to find optimal solutions. Our analysis is the first large-scale demonstration that LP-based approaches are highly effective in finding optimal (and near-optimal) solutions for the side-chain positioning problem.

Availability: The source code for generating the ILP given a file of pairwise energies between rotamers is available online at http://compbio.cs.princeton.edu/scplp.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
E. Mashiach, D. Schneidman-Duhovny, N. Andrusier, R. Nussinov, and H. J. Wolfson
FireDock: a web server for fast interaction refinement in molecular docking
Nucleic Acids Res., July 1, 2008; 36(suppl_2): W229 - W232.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
R. E. Smith, S. C. Lovell, D. F. Burke, R. W. Montalvao, and T. L. Blundell
Andante: reducing side-chain rotamer search space during comparative modeling using environment-specific substitution probabilities
Bioinformatics, May 1, 2007; 23(9): 1099 - 1105.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
W. Xie and N. V. Sahinidis
Residue-rotamer-reduction algorithm for the protein side-chain conformation problem
Bioinformatics, January 15, 2006; 22(2): 188 - 194.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.