P Systems Simulating Bacterial Conjugation : Universality and Properties

• Autorzy: Păun A. , Rodríguez-Patón A.

Identyfikatory

DOI

10.3233/FI-2017-1532

• Języki publikacji: EN

Abstrakty

EN

We refine the modeling in the P systems area of the way bacteria transmit genetic information in bacterial colonies, specifically the conjugation process. We study this new model from the computational power perspective using methods and ideas in the area; we are able to prove the universality of these systems. We show that systems working in a homogeneous manner and using only 75 species of objects in the regions and 13 species of "on-membrane" objects are enough for reaching universality. The system starts in a initial state with only few (nine) bacteria needed and the "bacteria" from this system are homogeneous, all have the same rules.

Słowa kluczowe

EN

bacterial conjugation; P systems; small universal machines; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 1/2
• Strony: 87--103
• Opis fizyczny: Bibliogr. 46 poz., rys.

Twórcy

autor

Păun A.

• Department of Computer Science, Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei nr.14, sector 1, C.P. 010014, Bucuresti, Romania
• Bioinformatics Department, National Institute of Research and Development for Biological Sciences, Splaiul Independenttei, Bucuresti, Romania

autor

Rodríguez-Patón A.

• Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte, 28660, Madrid, Spain

Bibliografia

• [1] Aman B, Ciobanu G. Modelling and verification of weighted spiking neural systems. Theoretical Computer Science, 2016;623:92–102. doi:10.1016/j.tcs.2015.11.005.
• [2] Aman B, Ciobanu G. Verification of membrane systems with delays via Petri nets with delays. Theoretical Computer Science, 2015;598:87–101. doi:10.1016/j.tcs.2015.03.051.
• [3] Aman B, Ciobanu G. Properties of enhanced mobile membranes via coloured Petri nets. Inf. Process. Lett., 2012;112(6):243–248. URL https://doi.org/10.1016/j.ipl.2011.12.003.
• [4] Angluin D, Aspnes J, Diamadi Z, Fischer MJ, and Peralta R. Computation in networks of passively mobile finite-state sensors, Distributed computing, 2006;18(4):235–253. doi:10.1007/s00446-005-0138-3.
• [5] Ardelean I, Cavaliere M, Sburlan D. Computing using signals: From cells to P systems, Soft computing 2005;9(9):631–639. doi:10.1007/s00500-004-0392-5.
• [6] Bernardini F, Gheorgue M. Cell communication in tissue P systems and cell division in population P Systems. Fénix Editora, 2004;9(9):74–91. doi:10.1007/s00500-004-0393-4.
• [7] Ciobanu G, Pinna GM. Catalytic and communicating Petri nets are Turing complete. Inf. Comput., 2014;239(C):55–70. doi:10.1016/j.ic.2014.08.008.
• [8] Ciobanu G. General patterns of interaction in stochastic fusion. Natural Computing, 2013;12(3):429–439. doi:10.1007/s11047-012-9346-5.
• [9] Ciobanu G, Krishna SN. Enhanced Mobile Membranes: Computability Results. Theory Comput. Syst., 2011;48(3):715–729. doi:10.1007/s00224-010-9256-9.
• [10] Ciobanu G, Aman B. On the relationship between membranes and ambients. Biosystems, 2008;91(3):515–530. URL http://doi.org/10.1016/j.biosystems.2007.01.006.
• [11] Ciobanu G, Pan L, Paun Gh, Pérez-Jiménez MJ. P systems with minimal parallelism. Theoretical Computer Science, 2007;378(1):117–130. URL https://doi.org/10.1016/j.tcs.2007.03.044.
• [12] Colson L, Jonoska N, Margenstern M. λ P systems and typed λ-calculus, International Workshop on Membrane Computing, Springer Berlin Heidelberg, 2004, pp. 1–18.
• [13] Csuhaj-Varju E, Verlan S. On generalized communicating P systems with minimal interaction rules, Theoretical Computer Science, 2011;412(1):124–135. URL https://doi.org/10.1016/j.tcs.2010.08. 020.
• [14] Liu F, Heiner M. Modeling membrane systems using colored stochastic Petri nets. Natural Computing, 2013;12(4):617–629. doi:10.1007/s11047-013-9367-8.
• [15] Freund R, Păun Gh, Pérez-Jiménez MJ. Tissue P systems with channel states, Theoretical Computer Science, 2005;330(1):101–116. URL https://doi.org/10.1016/j.tcs.2004.09.013.
• [16] Garcia Antonio P. A first approach to individual-based modeling of the bacterial conjugation dynamics. Polytechnical university of Madrid, 2011.
• [17] Heiner M, Herajy M, Liu F, Rohr C, Schwarick M. Snoopy-a unifying Petri net tool, Application and Theory of Petri Nets, Springer, 2012, pp. 398–407. doi:10.1007/978-3-642-31131-4_22.
• [18] Ibarra OH, Păun A, Rodriguez-Paton A. Sequential SNP systems based on min/max spike number, Theoretical Computer Science, 2009;410(30-32):2982–2991. URL https://doi.org/10.1016/j.tcs.2009.03.004.
• [19] Ibarra OH, Păun A, Rodríguez-Patón A. Sequentiality Induced by Spike Number in SNP Systems, Proceedings of DNA Computing conference 2008, also LNCS, Volume 5347, 2008, pp. 179–190. doi:10.1007/978-3-642-03076-5 15.
• [20] Ionescu M, Păun Gh, Yokomori T. Spiking neural P systems. Fundamenta Informaticae, 2006;71(2-3):279–308. URL http://dl.acm.org/citation.cfm?id=1227505.1227513.
• [21] Jensen K, Kristensen LM, Wells L. Coloured Petri nets and CPN tools for modelling and validation of concurrent systems, International Journal on Software Tools for Technology Transfer, 2007;9(3-4):213–254. doi:10.1007/s10009-007-0038-x.
• [22] Korec I. Small universal register machines, Theoretical Computer Science, 1996;168(2):267–301. doi:10.1016/S0304-3975(96)00080-1.
• [23] Maass W. Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 2002;8(1):32–36.
• [24] Maass W, Bishop C, eds. Pulsed Neural Networks, MIT Press, Cambridge, 1999. ISBN-0262133504. 102 A.
• [25] Martin-Vide C, Păun Gh, Pazos J, Rodriguez-Paton A. Tissue P systems, Theoretical Computer Science, 2003;296(2):295–326. URL https://doi.org/10.1016/S0304-3975(02)00659-X.
• [26] Minsky M. Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. ISBN-13: 978-0131655638.
• [27] Neary T. On the computational complexity of spiking neural P systems, Natural Computing, 2010;9(4):831–851. doi:10.1007/s11047-010-9213-1.
• [28] Păun A, Păun Gh. Small universal spiking neural P systems, BioSystems, 2007;90(1):48–60. URL SmalluniversalspikingneuralPsystems.
• [29] Păun A, Popa B. P Systems with Proteins on Membranes. Fundamenta Informaticae, 2006;72(4):467–483. URL http://dl.acm.org/citation.cfm?id=2369344.2369347.
• [30] Păun A, Popa B. P Systems with Proteins on Membranes and Membrane Division, Proc. 10th DLT Conf., Santa Barbara, USA, 2006, LNCS 4036, Springer, Berlin, 2006, pp. 292–303. doi:10.1007/11779148 27.
• [31] Păun A, Rodriguez-Paton A. Universal Pseudo-Homogenous P Systems Simulating Bacterial Conjugation, In M. Gheorghe, I. Petre, M.J. Prez-Jimnez, G. Rozenberg, A. Salomaa (Eds.) Multidisciplinary creativity, Spandugino, Bucharest, 2015, pp. 129–140.
• [32] Păun Gh. Computing with membranes, Journal of Computer and System Sciences, 2000;61(1):108–143. URL https://doi.org/10.1006/jcss.1999.1693.
• [33] Păun Gh. Membrane Computing – An Introduction. Springer-Verlag, Berlin, 2002. ISBN-3540436014.
• [34] Păun Gh. M.J. Pérez-Jiménez, G. Rozenberg: Spike trains in spiking neural P systems, International Journal of Foundations of Computer Science, 2006;17(4):975–1002. URL http://dx.doi.org/10.1142/S0129054106004212.
• [35] Păun Gh, Pérez-Jiménez MJ, Riscos-Núñez A. Tissue P Systems with Cell Division. Int. J. Comput. Commun., 2008;3(3):295–303. A preliminary version in Proc. 2nd BWMC 2004. URL http://dx.doi.org/10.15837/ijccc.2008.3.2397.
• [36] Pan L, Ishdorj TO. P systems with active membranes and separation rules. Journal of Universal Computer Science, 2004;10(5):630–649. doi:10.3217/jucs-010-05-0630.
• [37] Quinonez I, Panche S, Gomez J. Bacterial conjugation simulation using hexagonal cellular automaton, In 7th IEEE Colombian Computing Congress (CCC), 2012 , pp. 1–6. doi: 10.1109/ColombianCC. 2012.6398014.
• [38] Rozenberg G, Salomaa A, eds.: Handbook of Formal Languages, 3 volumes. Springer-Verlag, Berlin, 1997. ISBN-3-540-60649-1.
• [39] Schroeppel R. A two counter machine cannot calculate 2N , Technical Report AIM- 257, A. I. Laboratory, Massachusetts Institute of Technology, Cambridge, MA, May 1972, 1–31, available at ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-257.pdf (viewed Oct. 14, 2015).
• [40] Soloveichik D, Seelig G, Winfree E. DNA as a universal substrate for chemical kinetics, Proceedings of the National Academy of Sciences, 2010;107(12):5393–5398. doi:10.1007/978-3-642-03076-5_6.
• [41] Spicher A, Verlan S. Generalized communicating P systems working in fair sequential model, arXiv preprint arXiv:1108.3432, 2011.
• [42] Xue J, Liu X. Lattice based communication P systems with applications in cluster analysis. Soft Computing, 2014;18(7):1425–1440. doi:10.1007/s00500-013-1155-y.
• [43] Zhang X, Zeng X, and Pan L. Smaller universal spiking neural P systems, Fundamenta Informaticae, 2008;87(1):117–136. URL http://dl.acm.org/citation.cfm?id=1487713.14877219.
• [44] Zhang X, Jiang Y, and Pan L. Small Universal Spiking Neural P Systems with Exhaustive Use of Rule, Journal of Computational and Theoretical Nanoscience, 2010;7(5):890–899. URL https://doi.org/10.1166/jctn.2010.1436.
• [45] The P Systems Web Page: http://ppage.psystems.eu12 March 2017.
• [46] The PLASWIRES PF7 project: http://www.upm.es/observatorio/vi/index.jsp?pageac=proyectos/ficha.jsp\&idp=12181 12 March 2017.