Bioinformatics Advance Access originally published online on November 16, 2004
Bioinformatics 2005 21(7):1028-1039; doi:10.1093/bioinformatics/bti144
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Solving and analyzing side-chain positioning problems using linear and integer programming
Department of Computer Science and the Lewis-Sigler Institute for Integrative Genomics, Princeton University Princeton, NJ 08544, USA
*To whom correspondence should be addressed.
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 successive 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
Contact: msingh{at}cs.princeton.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Lu, A. D. Dousis, and J. Ma OPUS-Rota: A fast and accurate method for side-chain modeling Protein Sci., September 1, 2008; 17(9): 1576 - 1585. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 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]
|
|
|
|
 |
|
 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]
|
|
|
|
|
|
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]
|
|