# Mathematical Programming for Side-chain Positioning

Linear programming (LP), integer linear programming (ILP), and semidefinite
programming (SDP) are effective methods for solving
fixed-backbone homology modeling and
protein design problems.

## Papers

C. L. Kingsford, B. Chazelle,
M. Singh.
*
Solving and analyzing side-chain
positioning problems using linear and integer programming*.
Bioinformatics 2005 21(7):1028-1039. (Advance access publication
11/16/2004.) Local copy of paper here.

B. Chazelle, C. L. Kingsford, M. Singh. *
A Semidefinite Programming Approach to Side-Chain Positioning with New Rounding
Strategies*. INFORMS Journal on Computing, Vol. 16, No. 4, 380-392.
Special Issue in Computational Molecular Biology/Bioinformatics, 2004. (Prelim.
version in Proc. ACM FCRC'2003, Principles of Computing and Knowledge: Paris
Kanellakis Memorial Workshop (2003), 86-94.)

B. Chazelle, C. Kingsford, M. Singh. *The
Inapproximability of Side-Chain Positioning*. Unpublished note that
describes the inapproximability result of the above paper more fully.

## Code to use LP and ILP for SCP

To use LP or ILP you need an LP or ILP solver. CPLEX is a commercial package
that solves both types of problems. There are other free and commercial solvers
that can attack LP and/or ILP problems.

It is also convenient to use a modeling language to specify the input
to the solver. Ampl is the package we used.

- Ampl code for the linear programs
and integer linear programs.
- How to use Ampl, CPLEX, and the above code
to solve side-chain positioning problems.
- Datasets used in the Bioinformatics paper
(basic energy function).

If you use the above code, please cite
C. L. Kingsford, B. Chazelle, M. Singh. Solving and analyzing side-chain
positioning problems using linear and integer programming.
* Bioinformatics* (2005) 21: 1028–1036.

If you do not have Ampl and CPLEX, you might try out the NEOS Server for Optimization. It
currently has several LP solvers and one ILP solver that take Ampl input. (We
have not extensively tested the approach with these solvers, however.)

visitors since July 27, 2004. (Counter may not work in the Safari browser.)

Last modified November 17, 2004.