Optimization Techniques for Protein Structure Prediction

Given the primary sequence of a protein, can we predict its three-dimensional structure by computational methods? This is one of the most important and difficult problems in computational molecular biology and has tremendous implications for many applications such as drug design.

This talk will present efficient algorithms to solve two key problems of protein structure prediction: protein threading by linear programming and protein side-chain packing via tree-decomposition. The linear programming approach can empirically solve the protein threading problem within polynomial-time, although this problem is NP-hard in theory. The tree-decomposition algorithm not only runs very efficiently in practice, but also yields a polynomial-time approximation scheme for some typical cases.

Two protein structure prediction programs, RAPTOR for threading and TreePack for side-chain packing, have been developed based on the abovementioned algorithms. RAPTOR ranks first among all the programs of its category in CASP5, 3rd in CASP6 and 2nd in CASP8, the most recognized competition in the community of protein structure prediction. Without losing any prediction accuracy, TreePack runs up to 90 times faster than SCWRL, a widely-used side-chain packing program. TreePack can also solve some instances that SCWRL fails. Both programs have demonstrated success in real-world structure prediction and functional annotations.