Last modified November 17, 2004.
Linear programming (LP), integer linear programming (ILP), and semidefinite programming (SDP) are effective methods for solving fixed-backbone homology modeling and protein design problems.
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.
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.
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.