[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Application of local rules and cellular automata in representing protein translation and enhancing protein folding approximation

  • Regular Paper
  • Published:
Progress in Artificial Intelligence Aims and scope Submit manuscript

Abstract

It is self-evident that the coarse-grained view of transcription and protein translation is a result of certain computations. Although there is no single definition of the term “computation,” protein translation can be implemented over mathematical models of computers. Protein folding, however, is a combinatorial problem; it is still unknown whether a fast, accurate, and optimal folding algorithm exists. The discovery of near-optimal folds depends on approximation algorithms and heuristic searches. The hydrophobic–hydrophilic (HP) model is a simplified representation of some of the realities of protein structure. Despite the simplified representation, the folding problem in the HP model was proven to be NP-complete. We use simple and local rules to model translation and folding of proteins. Local rules imply that at a certain level of abstraction an entity can move from a state to another based on its state and information collected from its neighborhood. Also, the rules are simple in a sense that they do not require complicated computation. We use one-dimensional cellular automata to describe translation of mRNA into protein. Cellular automata are discrete models of computation that use local interactions to produce a global behavior of some sort. We will also discuss how local rules can improve approximation algorithms of protein folding and give an example of a CA that accept a certain family of strings to achieve half H–H contacts.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abu Dalhoum, L.A., Madain, A., Hiary, H.: Digital image scrambling based on elementary cellular automata. Multimed. Tools Appl. 75(24), 17019–17034 (2016). https://doi.org/10.1007/s11042-015-2972-z

    Article  Google Scholar 

  2. Aleksic, Z.: Artificial life: growing complex systems. In: Bossomaier, T.R.J., Green, D.G. (eds.) Complex Systems, pp. 91–126. Cambridge University Press, Cambridge (2000). (Cambridge Books Online)

    Chapter  Google Scholar 

  3. Anfinsen, C.B.: Principles that govern the folding of protein chains. Science 181(4096), 223–230 (1973)

    Article  Google Scholar 

  4. Berger, B., Leighton, T.: Protein folding in the hydrophobic–hydrophilic (HP) is NP-complete. In: Proceedings of the Second Annual International Conference on Computational Molecular Biology, RECOMB ’98, pp. 30–39. ACM, New York (1998)

  5. Bokovi, B., Brest, J.: Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic-polar model and cubic lattice. Appl. Soft Comput. 45(Supplement C), 61–70 (2016)

    Google Scholar 

  6. Burks, C., Farmer, D.: Towards modeling DNA sequences as automata. Phys. D 10(1–2), 157–167 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cook, M.: Universality in elementary cellular automata. Complex Syst. 15, 1–40 (2004)

    MathSciNet  MATH  Google Scholar 

  8. Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding (abstract). In: Proceedings of the Second Annual International Conference on Computational Molecular Biology, RECOMB ’98, pp. 61–62. ACM, New York (1998)

  9. Crick, F.: On protein synthesis. Symp. Soc. Exp. Biol. 12, 138–163 (1958)

    Google Scholar 

  10. Crick, F.: Central dogma of molecular biology. Nature 227(5258), 561–563 (1970)

    Article  Google Scholar 

  11. de Sales, J.A., Martins, M.L., Stariolo, D.A.: Cellular automata model for gene networks. Phys. Rev. E 55, 3262–3270 (1997)

    Article  Google Scholar 

  12. Diao, Y., Ma, D., Wen, Z., Yin, J., Xiang, J., Li, M.: Using pseudo amino acid composition to predict transmembrane regions in protein: cellular automata and lempel-ziv complexity. Amino Acids 34(1), 111–117 (2008)

    Article  Google Scholar 

  13. Dill, K.A.: Theory for the folding and stability of globular proteins. Biochemistry 24(6), 1501–1509 (1985)

    Article  Google Scholar 

  14. Dill, K.A., Bromberg, S., Yue, K., Chan, H.S., Ftebig, K.M., Yee, D.P., Thomas, P.D.: Principles of protein folding a perspective from simple exact models. Protein Sci. 4(4), 561–602 (1995)

    Article  Google Scholar 

  15. Drabo, H.K.: Formalization of transcription and translation processes by Turing machines. Master’s thesis, Morgan State University (2015)

  16. Gardner, M.: Mathematical games: the fantastic combinations of John Conway’s new solitaire game “life”. Sci. Am. 223, 120–123 (1970)

    Article  Google Scholar 

  17. Gianni, S., Jemth, P.: Protein folding: vexing debates on a fundamental problem. Biophys. Chem. 212, 17–21 (2016)

    Article  Google Scholar 

  18. Gibson, M., Mjolsness, E.: Computational modeling of genetic and biochemical networks, vol. 8, chap. In: Bower, J. M., Bolouri, H. (eds.) Modeling the Activity of Single Genes, pp. 3–48. MIT Press, Cambridge MA (2001)

  19. Günther, F., Möbius, A., Schreiber, M.: Structure optimisation by thermal cycling for the hydrophobic-polar lattice model of protein folding. Eur. Phys. J. Spec. Top. 226(4), 639–649 (2017)

    Article  Google Scholar 

  20. Haralick, R.M., Shanmugam, K., Dinstein, I.: Textural features for image classification. IEEE Trans. Syst. Man Cybern. 3(6), 610–621 (1973)

    Article  Google Scholar 

  21. Hart, W.E., Istrail, S.: Fast protein folding in the hydrophobichydrophilic model within three-eighths of optimal. J. Comput. Biol. 3(1), 53–96 (1996)

    Article  Google Scholar 

  22. Hu, M.K.: Visual pattern recognition by moment invariants. IRE Trans. Inf. Theory 8(2), 179–187 (1962)

    Article  MATH  Google Scholar 

  23. Kaushik, A.C., Sahi, S.: Biological complexity: ant colony meta-heuristic optimization algorithm for protein folding. Neural Comput. Appl. 28(11), 3385–3391 (2017)

    Article  Google Scholar 

  24. Kier, L.B., Seybold, P.G., Cheng, C.K.: Cellular Automata, pp. 9–38. Springer, Dordrecht (2005)

    Google Scholar 

  25. Koehl, P.: Protein Structure Classification, pp. 1–55. Wiley, New York (2006)

    Google Scholar 

  26. 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)

    Article  Google Scholar 

  27. Levinthal, C.: How to fold graciously. In: Debrunnder, J.T.P., Munck, E. (eds.) Mossbauer Spectroscopy in Biological Systems: Proceedings of a Meeting Held at Allerton House, Monticello, Ill, pp. 22–24. University of Illinois Press (1969)

  28. Llanes, A., Vélez, C., Sánchez, A.M., Pérez-Sánchez, H., Cecilia, J.M.: Parallel Ant Colony Optimization for the HP Protein Folding Problem, pp. 615–626. Springer, New York (2016)

    Google Scholar 

  29. Lopes, H.S., Bitello, R.: A differential evolution approach for protein folding using a lattice model. J. Comput. Sci. Technol. 22(6), 904–908 (2007)

    Article  Google Scholar 

  30. Lopes, H.S.: Evolutionary algorithms for the protein folding problem: A review and current trends. In: Smolinski, T.G., Milanova, M.G., Hassanien, A.E. (eds.) Computational intelligence in biomedicine and bioinformatics. Studies in computational intelligence, vol. 151, pp. 297–315. Springer, Berlin, Heidelberg (2008)

  31. Madain, A., Abu Dalhoum, A.L., Hiary, H., Ortega, A., Alfonseca, M.: Audio scrambling technique based on cellular automata. Multimed. Tools Appl. 71(3), 1803–1822 (2014)

    Article  Google Scholar 

  32. Madain, A., Abu Dalhoum, A.L., Sleit, A.: Computational modeling of proteins based on cellular automata. Int. J. Adv. Comput. Sci. Appl. 7(7), 491–498 (2016)

    Google Scholar 

  33. Madain, A., Abu Dalhoum, A.L., Sleit, A.: Potentials and challenges of building computational models of proteins based on cellular automata. Int. J. Comput. Sci. Inf. Secur. 14(9), 1–6 (2016)

    Google Scholar 

  34. Madain, A., Abu Dalhoum, A.L., Sleit, A.: Protein folding in the two-dimensional hydrophobic polar model based on cellular automata and local rules. Int. J. Comput. Sci. Netw. Secur. 16(9), 48–54 (2016)

    Google Scholar 

  35. Mauri, G., Pavesi, G.: Approximation algorithms for string folding problems. In: Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, TCS ’00, pp. 45–58. Springer, London (2000)

  36. Mizas, C., Sirakoulis, G., Mardiris, V., Karafyllidis, I., Glykos, N., Sandaltzopoulos, R.: Reconstruction of DNA sequences using genetic algorithms and cellular automata: Towards mutation prediction? Biosystems 92(1), 61–68 (2008)

    Article  Google Scholar 

  37. Newman, A.: A new algorithm for protein folding in the HP model. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pp. 876–884. Society for Industrial and Applied Mathematics, Philadelphia (2002)

  38. Nishio, H.: How does the neighborhood affect the global behavior of cellular automata? In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) Cellular Automata. Lecture Notes in Computer Science, vol. 4173, pp. 122–130. Springer, Berlin (2006)

    Chapter  Google Scholar 

  39. Paterson, M., Przytycka, T.: On the complexity of string folding. Discrete Appl. Math. 71(1), 217–230 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  40. Santos, J., Villot, P., Dieguez, M.: Cellular automata for modeling protein folding using the hp model. In: Evolutionary Computation (CEC), 2013 IEEE Congress, pp. 1586–1593 (2013)

  41. Santos, J., Villot, P., Diéguez, M.: Emergent protein folding modeled with evolved neural cellular automata using the 3d HP model. J. Comput. Biol. 21(11), 823–845 (2014)

    Article  Google Scholar 

  42. Sarkar, P.: A brief history of cellular automata. ACM Comput. Surv. 32(1), 80–107 (2000)

    Article  Google Scholar 

  43. Sirakoulis, G., Karafyllidis, I., Mizas, C., Mardiris, V., Thanailakis, A., Tsalides, P.: A cellular automaton model for the study of dna sequence evolution. Comput. Biol. Med. 33(5), 439–453 (2003)

    Article  Google Scholar 

  44. Takata, D., Isokawa, T., Matsui, N., Peper, F.: Modeling chemical reactions in protein synthesis by a Brownian cellular automaton. In: 2013 First International Symposium on Computing and Networking, pp. 527–532 (2013)

  45. Unger, R., Moult, J.: Genetic algorithms for protein folding simulations. J. Mol. Biol. 231(1), 75–81 (1993)

    Article  Google Scholar 

  46. Wang, S., Wu, L., Huo, Y., Wu, X., Wang, H., Zhang, Y.: Predict Two-Dimensional Protein Folding Based on Hydrophobic-Polar Lattice Model and Chaotic Clonal Genetic Algorithm, pp. 10–17. Springer, New York (2016)

    Google Scholar 

  47. Wooley, J.C., Lin., H.S.: Computational modeling and simulation as enablers for biological discovery. In: Catalyzing Inquiry at the Interface of Computing and Biology, pp. 117–202. National Academies Press (US), Washington (2005)

  48. Xiao, X., Ling, W.: Using cellular automata images to predict protein structural classes. In: Bioinformatics and Biomedical Engineering, 2007. ICBBE 2007. The 1st International Conference, pp. 346–349 (2007)

  49. Xiao, X., Shao, S., Ding, Y., Huang, Z., Chou, K.C.: Using cellular automata images and pseudo amino acid composition to predict protein subcellular location. Amino Acids 30(1), 49–54 (2006)

    Article  Google Scholar 

  50. Xiao, X., Wang, P., Chou, K.C.: GPCR-CA: a cellular automaton image approach for predicting g-protein-coupled receptor functional classes. J. Comput. Chem. 30(9), 1414–1423 (2008)

    Article  Google Scholar 

  51. Xiao, X., Wang, P., Chou, K.C.: Predicting protein structural classes with pseudo amino acid composition: an approach using geometric moments of cellular automaton image. J. Theor. Biol. 254(3), 691–696 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank Dr. Khair Eddin Sabri, Dr. Loai Alnemer, and Dr. Rawan Ghnemat for their suggestions and comments that greatly improved the content of this manuscript.

Author information

Authors and Affiliations

  1. Department of Computer Science, King Abdulla II School for Information Technology, The University of Jordan, Amman, 11942, Jordan

    Alia Madain, Abdel Latif Abu Dalhoum & Azzam Sleit

Authors
  1. Alia Madain
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abdel Latif Abu Dalhoum
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Azzam Sleit
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alia Madain.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Madain, A., Abu Dalhoum, A.L. & Sleit, A. Application of local rules and cellular automata in representing protein translation and enhancing protein folding approximation. Prog Artif Intell 7, 225–235 (2018). https://doi.org/10.1007/s13748-018-0146-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13748-018-0146-8

Keywords

Search

Navigation