Residue contact prediction is an important component of protein structure prediction and it is used to predict contacts between residue pairs which are far apart in the primary sequence of a protein but proximal in their three dimensional structure. This method can be particularly useful in first principles based approaches where no database information is used for the secondary and tertiary structure prediction. These residue contacts are highly useful in guiding the search and help a structure prediction algorithm identify better quality structures. 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]. Recently, an integer-linear programming based framework was proposed to predict hydrophobic contacts in alpha-helical proteins [6].

In this presentation, a novel optimization based method framework is introduced to predict contacts in beta, alpha+beta and alpha/beta proteins. In this method, a Calpha-Calpha distance dependent force field [7] is used to assign contact energy for a particular contact based on the identity of the amino acids [8]. This problem has been formulated as an 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 and topologies for alpha, beta, alpha+beta and alpha/beta proteins. 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. This model also offers the flexibility of incorporating additional constraints where a user can add unique and problem specific constraints to the model. The presented method was tested on few test proteins and produced an average accuracy of ~60%.

[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, Towards Accurate Residue-Residue Hydrophobic Contact Prediction for Alpha-Helical Proteins Via Integer Linear Optimization , Proteins, Submitted.

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

[8] Rajgaria, R., and Floudas, C.A., 2008, In Preparation.