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

摘要: Motivation: Side-chain positioning is a central component of homology modeling and protein design. In common formulation the problem, backbone fixed, side-chain conformations come from rotamer library, pairwise energy function optimized. It NP-complete to find even reasonable approximate solution this problem. We seek put hardness result into practical context. Results: present an integer linear programming (ILP) that allows us tackle large problem sizes. relax integrality constraint give polynomial-time (LP) heuristic. apply LP position side chains on native homologous backbones choose for Surprisingly, when backbones, optimal solutions using simple, biologically relevant can usually be found LP. On other hand, design often cannot solved directly; however, instances still computationally more expensive ILP procedure. While different functions also affect difficulty LP/ILP approach able solutions. Our analysis first large-scale demonstration LP-based approaches are highly effective in finding (and successive near-optimal) problem. Availability: The source code generating given file energies between rotamers available online at http://compbio.cs.princeton.edu/scplp Contact: msingh@cs.princeton.edu