# Biomolecular and Biocellular Computing

**Solving NP-Complete Problems with Networks of Evolutionary Processors.**Juan Castellanos, Carlos Martín-Vide, Victor Mitrana, José M. Sempere. In**6th International Work-conference on Artificial and Natural Neural Networks, IWANN 2001**(Granada,Spain). J. Mira, A. Prieto (Eds.) LNCS Vol. 2084 Part I, pp 621-628. Springer-Verlag, 2001.

**[PDF]****Networks of evolutionary processors.**Juan Castellanos, Carlos Martín-Vide, Victor Mitrana, José M. Sempere.**Acta Informatica**39, 517-529. 2003

**[PDF]****Filter Position in Networks of Evolutionary Processors Does Not Matter: A Direct Proof.**P. Bottoni, A. Labella, F. Manea, V. Mitrana, José M. Sempere. In**15th International Meeting on DNA Computing and Molecular Programming (DNA 15)**(Fayetteville, Arkansas USA). R. Deaton, A. Suyama (Eds.), LNCS Vol. 5877, pp 1-11. Springer, 2009.

**[PDF]****Networks of Evolutionary Picture Processors with Filtered Connections.**P. Bottoni, A. Labella, F. Manea, V. Mitrana, José M. Sempere. In**8th International Conference on Unconventional Computing (UC 9)**(Ponta Delgada, Azores Portugal). C.S. Calude, J.F.G.d. Costa, N. Dershowitz, E. Freire, G. Rozenberg (Eds.), LNCS Vol. 5715, pp 70-84. Springer, 2009.

**[PDF]****Recognizing membrane structures with tree automata.**José M. Sempere, Damián López. In**3rd Brainstorming Week on Membrane Computing, BWMC 2005**(Sevilla, Spain). M.A. Gutiérrez-Naranjo, A. Riscos-Núñez, F.J. Romero-Campero, D. Sburlan (Eds.), pp. 305-316. Fénix Editora, 2005.

**[PDF]****Editing Distances between Membrane Structures.**Damián López, José M. Sempere. In**6th International Workshop on Membrane Computing, WMC 2005**(Vienna, Austria). R. Freund, Gh. Paun, G. Rozenberg, A. Salomaa (Eds.), LNCS Vol. 3850, pp 326-341. Springer. 2006.

**[PDF]****Identifying P Rules from Membrane Structures with an Error-Correcting Approach.**José M. Sempere, D. López. In**7th International Workshop on Membrane Computing, WMC 2006**(Leiden, The Netherlands). H.J. Hoogeboom, Gh. Paun, G. Rozenberg, A. Salomaa (Eds.), LNCS Vol. 4361, pp 507-520. Springer, 2006.

**[PDF]****Characterizing Membrane Structures through Multiset Tree Automata.**José M. Sempere, D. López. In**8th International Workshop on Membrane Computing (WMC 2007)**(Thessaloniki, Greece). G. Eleftherakis, P. Kefalas, Gh. Paun, G. Rozenberg, A. Salomaa (Eds.), LNCS Vol. 4860, pp 428-437. Springer, 2007.

**[PDF]****On Two Families of Multiset Tree Automata.**José M. Sempere, D. López. In**Fifth Brainstorming Week on Membrane Computing, BWMC 2007**(Sevilla, Spain). M.A. Gutiérrez-Naranjo, Gh. Paun, A. Romero-Jiménez, A. Riscos-Núñez (Eds), pp 315-324. Fénix Editora. 2007.

**[PDF]****Translating Multiset Tree Automata into P systems.**José M. Sempere. In**9th Workshop on Membrane Computing (WMC 9)**(Edinburgh, Scotland). D. W. Corne, P. Frisco, Gh. Paun, G. Rozenberg, A. Salomaa (Eds.), LNCS Vol. 5391, pp 394-402. Springer, 2008.

**[PDF]**-
**Formal languages arising from gene repeated duplication.**P. Leupold, V. Mitrana, J. Sempere.**Aspects of Molecular Computing.**LNCS Vol. 2950, pp 297-308. N. Jonoska, Gh. Paun, G. Rozenberg (Eds.) Springer Verlag, 2004.

**[PDF]** **Some Remarks on Superposition Based on Watson-Crick-like Complementarity.**F. Manea, V. Mitrana, José M. Sempere. In**13th International Conference on Developments in Language Theory, DLT 2009**(Stuttgart, Germany). V. Diekert, D. Nowotka (Eds.), LNCS Vol. 5583, pp 372-383. Springer, 2008.

**[PDF]****A Representation Theorem for Languages accepted by Watson-Crick Finite Automata.**José M. Sempere.**Bulletin of the EATCS**83 pp. 187-191. 2004

**[PDF]****On Local Testability in Watson-Crick Finite Automata.**José M. Sempere. In**International Workshop on Automata for Cellular and Molecular Computing (ACMC07)**(Budapest, Hungary). Gy. Vaszil (Ed.), pp 120-128. MTA SZTAKI. 2007.

**[PDF]****Exploring regular reversibility in Watson-Crick finite automata.**José M. Sempere. In**13th International Symposium on Artificial Life and Robotics (AROB 2008)**(Beppu, Japan). M. Sugisaka, H. Tanaka (Eds.), pp 505-509. ISAROB, 2008.

**[PDF]****Sticker Expressions.**José M. Sempere. In**14th International Meeting on DNA Computing (DNA 14)**(Prague, Czech Republic). A. Goel, F.C. Simmel, P. Sosik (Eds.), pp 200-201. 2008.

**[PDF]**

**Natural Computing**is a research area which aims to develop new computing paradigms inspired by nature processes. Mainly, the source of inspirations comes from physics (i.e.

*quantum computing*) or biology. Our approach to biomolecular and biocellular computing can be establisehd in the following topics:

__Networks of Bio-inspired processors__The

**Networks of Biologically inspired Processors (NBP)**are universal models of computation based on the interconnection of simple processing units over strings which encode the information. The communication between processors is made through predefined filters which can be placed in the processors (input and output filters) or in the connections. The processors in turn make predefined operations over strings. The output of the model is collected in a predefined processor and the model can be defined to accept an input (i.e. as decision problem solvers) or generate a language. Recently, the approach to optimization problem solvers is under study.

The first model in this direction was proposed by Mitrana

*et al.*in the so called

**Networks of Evolutionary Processors (NEP)**. Here the processors only carry out evolutionary operations over strings inspired by nucleotide mutation during evolution (deletion, insertion and substitution). The model was first proposed as an efficient parallel way to solve NP-complete problems

In addition, we have proved that the location of the filters (inside the processors or attached to the connections) does not affect the computational power of the model

We have study the effect of filtered connections when the original NEP model works with picture data instead of strings. The model is renamed as

**Networks of Evolutionary Picture Processors (NEPP)**

Another model which has been proposed in this framework is the

**Network of Splicing Processors (NSP)**proposed by Manea

*et al.*. Here, the operation over strings is inspired by the DNA splicing process which can be defined as a DNA recombination process.

__Membrane computing (P systems)__Membrane Computing (or P systems) is a fruitful research area founded by Gheorghe Paun in 1998 in a seminal work. The universal model of computation that he proposed is inspired by the (chemical and physical) processes which happens in the living cell by using specific regions which communicate through physical membranes.

Our interest here is comprehensive. We have explored the topology of the membrane structures that P systems can generate along computation sequences. To approach this research we have proposed a

**Multiset Tree Automaton**as a computational model to recognize membrane structures as unordered trees

__Bioinspired operations and computation models__The definition of new string operations in the framework of formal language theory is our research interest. Here, we have studied and developed new operations inspired by DNA recombination such as

**superposition**and

**duplication**.

In addition, we have explored new features in DNA computing models such as the

**Watson-Crick Finite Automata**and their related regular-like expressions.