(538a) A New Optimization Based Approach For Protein Residue Contact Prediction

Predicting the residue contacts of a protein is an important component of protein structure prediction. It particularly plays an important role in first principles based approaches where no database information is used for the secondary and tertiary structure prediction. Residue contact prediction mainly focuses on the prediction of residue pairs which are far apart in the primary sequence of a protein but proximal in their three dimensional structure. A number of different methods have been developed to predict these non-local contacts. In a very broad sense, these techniques either use correlated mutations analysis or machine learning approach (hidden Markov models, neural networks etc.) [1-5].

We have recently developed an optimization based method to predict the residue contacts of a protein. In this model, a Cα- Cα distance dependent force field [6] is used to assign contact energy for a particular contact based on the identity of the amino acids [7]. A contact is said to occur when the predicted distance between interacting residues is more than 3 Ǻ, and less than 9 Ǻ. This problem has been formulated as a mixed integer linear programming problem where the objective function is to minimize the contact energy. A set of constraints is also included in the model to produce physically possible contacts. Apart from predicting the non-local contacts, this method can also predict the topology of a protein and disulfide bridges (if present). This formulation not only offers the advantage of finding the residue contacts corresponding to the global minima, but it can also produce a rank-ordered list of residue contacts. A rank-ordered list like this helps in finding the most frequent contacts. It is also possible to encounter cases when some of the contacts are known a priori. The proposed formulation allows the user to add such problem specific biologically relevant information in a mathematical rigorous way. This model has been tested on a test set including α, β, and α+ β protein and the preliminary results are very encouraging.

[1] Klepeis, J., and Floudas, C. A., 2003a, Prediction of Beta-Sheet Topology and Disulfide Bridges in Polypeptides. Journal of Computational Chemistry, 24: 191-208.

[2] Vicatos, S., Reddy, V. B., and Kaznessis, Y., 2005, Prediction of Distant Residue Contacts With the Use of Evolutionary Information. Proteins: Structure, Function, and Bioinformatics, 58: 935-949.

[3] Fariselli, P., Olema, O., Valencia, A., and Casadio. R, 2001, Progress in Predicting Inter-Residue Contacts of Proteins With Neural Networks and Correlated Mutations. Proteins: Structure, Function, and Genetics, 5: 157-162.

[4] Hamilton, N., Burrage, K., Ragan, M. A., and Huber, T., 2004, Protein Contact Prediction Using Patterns of Correlation. Proteins: Structure, Function, and Genetics, 56: 679-684.

[5] Cheng, J., and Baldi P., Improved Residue Contact Prediction Using Support Vector Machines and A Large Feature Set. BMC Bioinformatics, 56: 679-684.

[6] Rajgaria, R., McAllister, S. R., and Floudas, C.A., 2007, Development of A Novel High Resolution Cα- Cα Distance Dependent Force Field Using A High Quality Decoy Set. Proteins: Structure, Function, and Bioinformatics, 65: 726-742.

[7] Rajgaria, R., McAllister, S. R., and Floudas, C.A., 2007, In preparation.