Heuristics, optimizations, and parallelism for protein structure prediction in CLP(FD)

ABSTRACT

The paper describes a constraint-based solution to the protein folding problem on face-centered cubic lattices---a biologically meaningful approximation of the general protein folding problem. The paper improves the results presented in [15] and introduces new ideas for improving efficiency: (i) proper reorganization of the constraint structure; (ii) development of novel, both general and problem-specific, heuristics; (iii) exploitation of parallelism. Globally, we obtain a speed up in the order of 60 w.r.t. [15]. We show how these results can be employed to solve the folding problem for large proteins containing subsequences whose conformation is already known.

REFERENCES

• 1: R. Agarwala et al. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. J. of Computational Biology, pages 275--296, 1997.
• 2: K. R. Apt. Principles of constraint programming. Cambridge University press, 2003.
• 3: Rolf Backofen, The Protein Structure Prediction Problem: A Constraint Optimization Approach using a New Lower Bound, Constraints, v.6 n.2-3, p.223-255, June 2001
• 4: Rolf Backofen , Sebastian Will, Fast, Constraint-Based Threading of HP-Sequences to Hydrophobic Cores, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.494-508, November 26-December 01, 2001
• 5: R. Backofen and S. Will. A Constraint-Based Approach to Structure Prediction for Simplified Protein Models that Outperforms Other Existing Methods. ICLP, 2003, Springer Verlag.
• 6: H. M. Berman et al. The protein data bank. Nucleic Acids Research, 28:235--242, 2000. http://www.rcsb.org/pdb/.
• 7: M. Berrera, H. Molinari, and F. Fogolari. Amino acid empirical contact energy definitions for fold recognition in the space of contact maps. BMC Bioinformatics, 4(8), 2003.
• 8: R. Bonneau and D. Baker. Ab initio protein structure prediction: progress and prospects. Annu. Rev. Biophys. Biomol. Struct., 30:173--89, 2001.
• 9: B. R. Brooks et al. Charmm: A program for macromolecular energy minimization and dynamics calculations. J. Comput. Chem., 4:187--217, 1983.
• 10: Mats Carlsson , Greger Ottosson , Björn Carlson, An Open-Ended Finite Domain Constraint Solver, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.191-206, September 03-05, 1997
• 11: A. M. Cheadle et al. ECLiPSe: An Introduction. Technical Report IC-Parc 03--1, IC-Parc, 2003.
• 12: D. Clark, J. Shirazi, and C. Rawlings. Protein topology prediction through constraint-based search and the evaluation of topological folding rules. Protein Engineering, 4:752--760, 1991.
• 13: P. Clote and R. Backofen. Computational Molecular Biology: An Introduction. John Wiley & Sons, 2001.
• 14: Pierluigi Crescenzi , Deborah Goldman , Christos Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis, On the complexity of protein folding (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.597-603, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276875]
• 15: A. Dal Palù, A. Dovier, and F. Fogolari. Constraint logic programming approach to protein structure prediction. BMC Bioinformatics, 5(186), 2004.
• 16: A. Dal Palù, A. Dovier, and F. Fogolari. Protein folding in CLP(FD) with empirical contact energies. In Recent Advances in Constraints, Springer Verlag, 2004.
• 17: F. Fogolari et al. Modeling of polypeptide chains as C-α chains, C-α chains with C-β, and C-α chains with ellipsoidal lateral chains. Biophysical Journal, 70:1183--1197, 1996.
• 18: S. Forman. Torsion Angle Selection and Emergent Non-local Secondary Structure in Protein Structure Prediction. PhD thesis, U. of Iowa, 2001.
• 19: Gopal Gupta , Enrico Pontelli , Khayri A.M. Ali , Mats Carlsson , Manuel V. Hermenegildo, Parallel execution of prolog programs: a survey, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.4, p.472-602, July 2001 [doi>10.1145/504083.504085]
• 20: W. Hart and S. Israil. Fast protein folding in the hydrophobic-hytrophilic model within three-eighths of optimal. J. of Computational Biology, pages 53--96, 1996.
• 21: S. Miyazawa and R. L. Jernigan. Residue-residue potentials with a favorable contact pair term and an unfavorable high packing density term, for simulation and threading. J. of Molecular Biology, 256(3):623--644, 1996.
• 22: Alantha Newman, A new algorithm for protein folding in the HP model, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.876-884, January 06-08, 2002, San Francisco, California
• 23: Committee on Mathematical Challenges from Computational Chemistry. National Research Council, 1995.
• 24: D. Qiu, P. Shenkin, F. Hollinger, and W. Still. The gb/sa continuum model for solvation. A fast analytical method for the calculation of approximate born radii. J. Phys. Chem., 101:3005--3014, 1997.
• 25: G. Raghunathan and R. L. Jernigan. Ideal architecture of residue packing and its observation in protein structures. Protein Science, 6:2072--2083, 1997.
• 26: B. Rost and C. Sander. Prediction of protein secondary structure at better than 70% accuracy. J. Mol. Biol., 232:584--599, 1993.
• 27: K. Simons et al. Ab initio protein structure prediction of CASP III targets using ROSETTA. Proteins 1999, 3:171--176.
• 28: Jeffrey Skolnick , Andrzej Kolinski, Computational studies of protein folding, Computing in Science and Engineering, v.3 n.5, p.40-50, September/October 2001 [doi>10.1109/MCISE.2001.947107]
• 29: J. Skolnick and A. Kolinski. Reduced models of proteins and their applications. Polymer, 45:511--524, 2004.
• 30: Swedish Institute for Computer Science. Sicstus Prolog. http://www.sics.se/sicstus/.
• 31: L. Toma and S. Toma. Folding simulation of protein models on the structure-based cubo-octahedral lattice with contact interactions algorithm. Protein Science, 8:196--202, 1999.
• 32: M.L.G. William and D. Harvey. Limited discrepancy search. IJCAI, pages 607--615, Morgan Kaufmann, 1995.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms, Experimentation

Keywords:
bioinformatics, constraint logic programming, parallelism