Tissue P Systems with Protein on Cells

• Autorzy: Song B. , Pan L. , Pérez-Jiménez M. J.

Identyfikatory

DOI

10.3233/FI-2016-1324

• Języki publikacji: EN

Abstrakty

EN

Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule).

Słowa kluczowe

EN

bio-inspired computing; membrane computing; tissue P system; cell protein; cell division; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 144, nr 1
• Strony: 77--107
• Opis fizyczny: Bibliogr. 36 poz., tab.

Twórcy

autor

Song B.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Pan L.

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Pérez-Jiménez M. J.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Bibliografia

• [1] Pǎun G. Computing with membranes. Journal of Computer and System Sciences. 2000;61(1):108–143. doi:10.1006/jcss.1999.1693.
• [2] Martín-Vide C, Pazos J, Pǎun G, Rodriguez-Paton A. Tissue P systems. Theoretical Computer Science. 2003;296(2):295–326. doi:10.1016/S0304-3975(02)00659-X.
• [3] Ionescu M, Pǎun G, Yokomori T. Spiking neural P systems. Fundamenta Informaticae. 2006;71(2):279–308.
• [4] Jiang K, Pan L. Spiking neural P systems with anti-spikes working in sequential mode induced by maximum spike number. Neurocomputing. 2016;171:1674–1683.
• [5] Song T, Pan L. Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy. IEEE Transactions on NanoBioscience. 2015;14(1):38–44. doi: 10.1109/TNB.2014.2367506.
• [6] Song T, Pan L. Spiking neural P systems with rules on synapses working in maximum spiking strategy. IEEE Transactions on NanoBioscience. 2015;14(4):465–477. doi: 10.1109/TNB.2015.2402311.
• [7] Song T, Pan L, Pǎun G. Spiking neural P systems with rules on synapses. Theoretical Computer Science. 2014;529:82–95. doi:10.1016/j.tcs.2014.01.001.
• [8] Zeng X, Zhang X, Song T, Pan L. Spiking neural P systems with thresholds. Neural computation. 2014; 26(7):1340–1361. doi:10.1162/NECO a 00605.
• [9] Zhang X, Pan L, Pǎun A. On the universality of axon P systems. IEEE Transactions on Neural Networks and Learning Systems. 2015;26(11):2816–2829. doi: 10.1109/TNNLS.2015.2396940.
• [10] Pǎun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. Oxford University Press; 2010. ISBN: 0199556679, 9780199556670.
• [11] Pǎun A, Pǎun G. The power of communication: P systems with symport/antiport. New Generation Computing. 2002;20(3):295–305. doi:10.1007/BF03037362.
• [12] Alhazov A, Freund R, Leporati A, Oswald M, Zandron C. (Tissue) P systems with unit rules and energy assigned to membranes. Fundamenta Informaticae. 2006;74(4):391–408.
• [13] Alhazov A, Freund R, Oswald M. Tissue P systems with antiport rules and small numbers of symbols and cells. In: Developments in Language Theory. vol. 3572. Springer, LNCS; 2005. p. 100–111. doi:10.1007/11505877 9.
• [14] Freund R, Pǎun G, Pérez-Jiménez MJ. Tissue P systems with channel states. Theoretical Computer Science. 2005;330(1):101–116. doi:10.1016/j.tcs.2004.09.013.
• [15] Pǎun G, Pérez-Jiménez MJ, Riscos-Núñez A. Tissue P systems with cell division. International Journal of Computers, Communications and Control. 2008;3(3):295–303.
• [16] Díaz-Pernil D, Pérez-Jiménez M, Riscos-Núñez A, Romero-Jiménez A. Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology. 2008;11(3):229–241. Available from: http://www.imt.ro/romjist/Volum11/Number11_3/02-Diaz-Pernil.htm.
• [17] Díaz-Pernil D, Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A. Solving subset sum in linear time by using tissue P systems with cell division. In: Proceedings of 2th International Work-Conference on the Interplay Between Natural and Artificial Computation. Springer; 2007. p. 170–179. doi:10.1007/978-3-540-73053-8 17.
• [18] Díaz-Pernil D, Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A. A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science. 2008;404(1):76–87. doi:10.1016/j.tcs.2008.04.005.
• [19] Díaz-Pernil D, Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A. Solving the independent set problem by using tissue-like P systems with cell division. In: Proceedings of 3th International Work-Conference on the Interplay Between Natural and Artificial Computation. vol. 5601. Springer; 2009. p. 213–222. doi:10.1007/978-3-642-02264-7 23.
• [20] AlménMS, Nordström KJ, Fredriksson R, Schiöth HB. Mapping the human membrane proteome: a majority of the human membrane proteins can be classified according to function and evolutionary origin. BMC biology. 2009;7(50). doi:10.1186/1741-7007-7-50.
• [21] Alberts B, Johnson A, Lewis J, Raff M, Roberts K, Walter P. Molecular Biology of the Cell. Garland Science; 2002. ISBN- 10:0-8153-3218-1, 10:0-8153-4072-9.
• [22] Rozenberg G, Salomaa A. Handbook of Formal Languages. vol. 1–3. Springer Science & Business Media; 1997.
• [23] Minsky ML. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. 1967. ISBN-13:978-0131655638, 10:0131655639.
• [24] Pǎun A, Popa B. P systems with proteins on membranes. Fundamenta Informaticae. 2006;72(4):467–483.
• [25] Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics. 2006;11(4):423–434.
• [26] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco, LA: Freeman; 1979. ISBN:0716710447.
• [27] Christinal HA, Díaz-Pernil D, Gutiérrez-Naranjo MA, Pérez-Jiménez MJ. Tissue-like P systems without environment. In: Proceedings of the Eight Brainstorming Week on Membrane Computing, Sevilla, Spain. Citeseer; 2010. p. 53–64. Available from: http://www.gcn.us.es/8BWMC/volume/04DiazPernilEnvironment.pdf.
• [28] Song T, Macías-Ramos LF, Pan L, Pérez-Jiménez MJ. Time-free solution to SAT problem using P systems with active membranes. Theoretical Computer Science. 2014;529:61–68. doi:10.1016/j.tcs.2013.11.014.
• [29] Song B, Pan L. Computational efficiency and universality of timed P systems with active membranes. Theoretical Computer Science. 2015;567:74–86. doi: 10.1016/j.tcs.2014.10.051.
• [30] Song B, Pérez-Jiménez MJ, Pan L. Computational efficiency and universality of timed P systems with membrane creation. Soft Computing. 2015;19(11):3043–3053. doi:10.1007/s00500-015-1732-3.
• [31] Song B, Song T, Pan L. Time-free solution to SAT problem by P systems with active membranes and standard cell division rules. Natural Computing. 2015;14(4):673–681. doi: 10.1007/s11047-014-9471-4.
• [32] Song B, Song T, Pan L. A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science; doi:10.1016/j.tcs.2015.10.027.
• [33] Ciobanu G, Pan L, Pǎun G, Pérez-Jiménez MJ. P systems with minimal parallelism. Theoretical Computer Science. 2007;378(1):117–130. doi:10.1016/j.tcs.2007.03.044.
• [34] Pan L, Pǎun G, Song B. Flat maximal parallelism in P systems with promoters. Theoretical Computer Science. 2015; doi:10.1016/j.tcs.2015.10.027.
• [35] Pan L, Pérez-Jiménez MJ. Computational complexity of tissue-like P systems. Journal of Complexity. 2010;26(3):296–315. doi:10.1016/j.jco.2010.03.001.
• [36] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Campero FJ. Computational efficiency of dissolution rules in membrane systems. International Journal of ComputerMathematics. 2006;83(7):593–611. doi:10.1080/00207160601065413.