Abstract
Protein structure prediction (PSP) is a very challenging constraint optimization problem. Constraint-based local search approaches have obtained promising results in solving constraint models for PSP. However, the neighborhood exploration policies adopted in these approaches either remain exhaustive or are based on random decisions. In this paper, we propose heuristics to intelligently explore only the promising areas of the search neighborhood. On face centered cubic lattice using a realistic 20×20 energy model and standard benchmark proteins, we obtain structures with significantly lower energy and RMSD values than those obtained by the state-of-the-art algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balint, A., Fröhlich, A.: Improving stochastic local search for SAT with a new probability distribution. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 10–15. Springer, Heidelberg (2010)
Berrera, M., Molinari, H., Fogolari, F.: Amino acid empirical contact energy definitions for fold recognition in the space of contact maps. BMC Bioinformatics 4, 8 (2003)
Bornberg-Bauer, E.: Chain growth algorithms for hp-type lattice proteins. In: Proceedings of the First Annual International Conference on Computational Molecular Biology, RECOMB 1997, pp. 47–55. ACM, New York (1997)
Campeotto, F., Dal Palù, A., Dovier, A., Fioretto, F., Pontelli, E.: A filtering technique for fragment assembly- based proteins loop modeling with constraints. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 850–866. Springer, Heidelberg (2012)
Cebrián, M., Dotú, I., Van Hentenryck, P., Clote, P.: Protein structure prediction on the face centered cubic lattice by local search. In: Proceedings of the 23rd National Conference on Artificial Intelligence, AAAI 2008, vol. 1, pp. 241–246. AAAI Press (2008)
Cipra, B.: Packing challenge mastered at last. Science 281(5381), 1267 (1998)
Dotu, I., Cebrian, M., Van Hentenryck, P., Clote, P.: On lattice protein structure prediction revisited. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(6), 1620–1632 (2011)
Kapsokalivas, L., Gan, X., Albrecht, A.A., Steinhöfel, K.: Population-based local search for protein folding simulation in the MJ energy model and cubic lattices. Computational Biology and Chemistry 33(4), 283–294 (2009)
Lau, K.F., Dill, K.A.: A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules 22(10), 3986–3997 (1989)
Lesh, N., Mitzenmacher, M., Whitesides, S.: A complete and effective move set for simplified protein folding. In: Proceedings of the Seventh Annual International Conference on Research in Computational Molecular Biology, pp. 188–195. ACM, New York (2003)
Lu, H., Yang, G.: Extremal optimization for protein folding simulations on the lattice. Comput. Math. Appl. 57, 1855–1861 (2009)
Mann, M., Will, S., Backofen, R.: CPSP-tools – Exact and complete algorithms for high-throughput 3 D lattice protein studies. Bmc Bioinformatics 9(1), 230 (2008)
Mann, M., Hamra, M.A., Steinhöfel, K., Backofen, R.: Constraint-based local move definitions for lattice protein models including side chains. In: Proceedings of the Fifth Workshop on Constraint Based Methods for Bioinformatics, WCB 2009 (2009)
Miyazawa, S., Jernigan, R.L.: Estimation of effective interresidue contact energies from protein crystal structures: quasi-chemical approximation. Macromolecules 18(3), 534–552 (1985)
Newton, M.A.H., Pham, D.N., Sattar, A., Maher, M.: Kangaroo: An efficient constraint-based local search system using lazy propagation. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 645–659. Springer, Heidelberg (2011)
Palù, A.D., Dovier, A., Fogolari, F., Pontelli, E.: Exploring protein fragment assembly using CLP. In: IJCAI, pp. 2590–2595 (2011)
Palù, A.D., Dovier, A., Pontelli, E.: Heuristics, optimizations, and parallelism for protein structure prediction in CLP(FD). In: PPDP, pp. 230–241 (2005)
Palù, A.D., Dovier, A., Pontelli, E.: A constraint solver for discrete lattices, its parallelization, and application to protein structure prediction. Softw. Pract. Exper. 37, 1405–1449 (2007)
Palù, A.D., Will, S., Backofen, R., Dovier, A.: Constraint based protein structure prediction exploiting secondary structure information. In: Proceedings of Italian Conference on Computational Logic, CLIC 2004 (2004)
Pham, D.N., Thornton, J., Gretton, C., Sattar, A.: Advances in local search for satisfiability. In: Orgun, M.A., Thornton, J. (eds.) AI 2007. LNCS (LNAI), vol. 4830, pp. 213–222. Springer, Heidelberg (2007)
Rashid, M.A., Hoque, M. T., Newton, M.A.H., Pham, D.N., Sattar, A.: A new genetic algorithm for simplified protein structure prediction. In: Thielscher, M., Zhang, D. (eds.) AI 2012. LNCS, vol. 7691, pp. 107–119. Springer, Heidelberg (2012)
Rotkiewicz, P., Skolnick, J.: Fast procedure for reconstruction of full-atom protein models from reduced representations. Journal of Computational Chemistry 29(9), 1460–1465 (2008)
Shatabda, S., Newton, M.A.H., Sattar, A.: Mixed heuristic local search for protein structure prediction. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, July 14-18. AAAI Press (2013)
Shatabda, S., Newton, M., Rashid, M.A., Pham, D.N., Sattar, A.: The road not taken: retreat and diverge in local search for simplified protein structure prediction. BMC Bioinformatics 14(2), 1–9 (2013)
Steinhofel, K., Skaliotis, A., Albrecht, A.: Relating time complexity of protein folding simulation to approximations of folding time. Computer Physics Communications 176(7), 465–470 (2007)
Torres, S.R.D., Romero, D.C.B., Vasquez, L.F.N., Ardila, Y.J.P.: A novel ab-initio genetic-based approach for protein folding prediction. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO 2007, pp. 393–400. ACM, New York (2007)
Ullah, A.D., Kapsokalivas, L., Mann, M., Steinhöfel, K.: Protein folding simulation by two-stage optimization. In: Cai, Z., Li, Z., Kang, Z., Liu, Y. (eds.) ISICA 2009. CCIS, vol. 51, pp. 138–145. Springer, Heidelberg (2009)
Ullah, A.D., Steinhöfel, K.: A hybrid approach to protein folding problem integrating constraint programming with local search. BMC Bioinformatics 11(S-1), 39 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Shatabda, S., Newton, M.A.H., Sattar, A. (2013). Neighborhood Selection in Constraint-Based Local Search for Protein Structure Prediction. In: Cranefield, S., Nayak, A. (eds) AI 2013: Advances in Artificial Intelligence. AI 2013. Lecture Notes in Computer Science(), vol 8272. Springer, Cham. https://doi.org/10.1007/978-3-319-03680-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-03680-9_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03679-3
Online ISBN: 978-3-319-03680-9
eBook Packages: Computer ScienceComputer Science (R0)