P systems with proteins on membranes characterize PSPACE. (English) Zbl 1293.68175
Summary: The paper studies algorithmic properties of operations with membrane proteins modeled within the framework of membrane systems (also called P systems). Membrane systems are biologically inspired models of parallel and distributed computing based on the information processing in cells and cellular membranes. We show that the computational potential of P systems with proteins on membranes is equivalent to that of parallel computing models as the alternating Turing machine or the PRAM. These abstract machines characterize by their polynomial time-bounded computations the class PSPACE, and simultaneously they serve as idealized models of real parallel machines. Therefore, this and other related results suggest the existence of a homology between the potential of silicon and biological parallel information processing.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 92D20 | Protein sequences, DNA sequences |
References:
| [1] | Alberts, B.; Johnson, A.; Lewis, J.; Raff, M.; Roberts, K.; Walter, P., Molecular Biology of the Cell (2002), Garland Science: Garland Science New York |
| [2] | Alhazov, A.; Martín-Vide, C.; Pan, L., Solving a PSPACE-complete problem by P systems with restricted active membranes, Fund. Inform., 58, 2, 67-77 (2003) · Zbl 1085.68048 |
| [3] | Beaver, D., A universal molecular computer, (Lipton, R. J.; Baum, E., DNA Based Computers. DNA Based Computers, DIMACS, vol. 27 (1995), American Mathematical Society), 29-36 |
| [4] | Brijder, R.; Cavaliere, M.; Riscos-Núñez, A.; Rozenberg, G.; Sburlan, D., Membrane systems with proteins embedded in membranes, Theoret. Comput. Sci., 404, 1-2, 26-39 (2008) · Zbl 1151.68012 |
| [5] | Cardelli, L., Brane calculi — interactions of biological membranes, (Computational Methods in Systems Biology. Computational Methods in Systems Biology, Lecture Notes in Computer Science, vol. 3082 (2005), Springer-Verlag: Springer-Verlag Berlin), 257-280 · Zbl 1088.68657 |
| [6] | Ciobanu, G.; Pan, L.; Păun, G.; Pérez-Jiménez, M. J., P systems with minimal parallelism, Theoret. Comput. Sci., 378, 1, 117-130 (2007) · Zbl 1118.68066 |
| [7] | Csuhaj-Varjú, E.; Vaszil, G., (Mem)brane automata, Theoret. Comput. Sci., 404, 1-2, 52-60 (2008) · Zbl 1151.68015 |
| [8] | Dantsin, E.; Wolpert, A., A robust dna computation model that captures PSPACE, Int. J. Found. Comput. Sci., 14, 5, 933-951 (2003) · Zbl 1101.68575 |
| [9] | Freund, R.; Oswald, M., Tissue P systems and (mem)brane systems with mate and drip operations working on strings, Electron. Notes Theor. Comput. Sci., 171, 2, 105-115 (2007) · Zbl 1277.68075 |
| [10] | Frisco, P., Computing with cells, (Advances in Membrane Computing (2009), Oxford University Press: Oxford University Press Oxford) · Zbl 1248.68012 |
| [11] | Ibarra, O. H., On the computational complexity of membrane systems, Theoret. Comput. Sci., 320, 1, 89-109 (2004) · Zbl 1068.68060 |
| [12] | Krishna, S., On the computational power of flip-flop proteins on membranes, (Cooper, S. B.; Löwe, B.; Sorbi, A., CiE 2007. CiE 2007, Lecture Notes in Computer Science, vol. 4497 (2007), Springer-Verlag: Springer-Verlag Berlin), 695-704 · Zbl 1151.68417 |
| [13] | Krishna, S., Membrane computing with transport and embedded proteins, Theoret. Comput. Sci., 410, 45, 355-375 (2009) · Zbl 1158.68010 |
| [14] | Manea, F.; Margenstern, M.; Mitrana, V.; Pérez-Jiménez, M. J., A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors, Theory Comput. Syst., 46, 2, 174-192 (2010) · Zbl 1209.68264 |
| [15] | Mazza, T.; Cavaliere, M., Cell cycle and tumor growth in membrane systems with peripheral proteins, Electron. Notes Theor. Comput. Sci., 227, 127-141 (2009) · Zbl 1348.92048 |
| [16] | (Păun, G.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing (2010), Oxford University Press: Oxford University Press Oxford) · Zbl 1237.68001 |
| [17] | Pérez-Jiménez, M., A computational complexity theory in membrane computing, (Păun, G.; etal., Membrane Computing, 10th International Workshop, WMC 2009. Membrane Computing, 10th International Workshop, WMC 2009, Lecture Notes in Computer Science, vol. 5957 (2010), Springer: Springer Berlin), 125-148 · Zbl 1273.68185 |
| [18] | Pérez-Jiménez, M.; Romero-Jiménez, A.; Sancho-Caparrini, F., A polynomial complexity class in P systems using membrane division, J. Autom. Lang. Comb., 11, 4, 423-434 (2006) · Zbl 1145.68426 |
| [19] | Păun, A.; Popa, B., P systems with proteins on membranes, Fund. Inform., 72, 4, 467-483 (2006) · Zbl 1099.68031 |
| [20] | Păun, A.; Popa, B., P systems with proteins on membranes and membrane division, (Ibarra, O.; Dang, Z., DLT 2006. DLT 2006, Lecture Notes in Computer Science, vol. 4036 (2006), Springer-Verlag: Springer-Verlag Berlin), 292-303 · Zbl 1227.68027 |
| [21] | Păun, A.; Păun, G., The power of communication: P systems with symport/antiport, New Gener. Comput., 20, 3, 295-306 (2002) · Zbl 1024.68037 |
| [22] | Păun, G., P systems with active membranes: attacking NP complete problems, J. Autom. Lang. Comb., 6, 1, 75-90 (2001) · Zbl 0970.68066 |
| [23] | Păun, A.; Rodríguez-Patón, A., On flip-flop membrane systems with proteins, (Eleftherakis, G.; etal., WMC8 2007. WMC8 2007, Lecture Notes in Computer Science, vol. 4860 (2007), Springer-Verlag: Springer-Verlag Berlin), 414-427 · Zbl 1137.68402 |
| [24] | Pudlák, P., Complexity theory and genetics: the computational power of crossing-over, Inform. and Comput., 171, 201-223 (2001) · Zbl 1005.68066 |
| [25] | Sosík, P., The computational power of cell division in P systems: Beating down parallel computers?, Nat. Comput., 2, 3, 287-298 (2003) · Zbl 1048.68044 |
| [26] | Sosík, P.; Rodríguez-Patón, A., Membrane computing and complexity theory: a characterization of PSPACE, J. Comput. System Sci., 73, 1, 137-152 (2007) · Zbl 1178.68260 |
| [27] | Stevens, T.; Arkin, I., Do more complex organisms have a greater proportion of membrane proteins in their genomes?, Proteins, 39, 417-420 (2000) |
| [28] | van Emde Boas, P., Machine models and simulations, (van Leeuwen, J., Handbook of Theoretical Computer Science. Vol. A (1990), Elsevier: Elsevier Amsterdam), 1-66 · Zbl 0900.68265 |
| [29] | Wallin, E.; Heijne, G. V., Genome-wide analysis of integral membrane proteins from eubacterial, archaean, and eukaryotic organisms, Protein Science, 7, 4, 1029-1038 (1998) |
| [31] | Wu, C.; Yates, J., The application of mass spectrometry to membrane proteomics, Nature Biotechnol., 21, 262-267 (2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
