Applications of Membrane Computing

This is a comprehensive (and friendly) introduction to membrane computing (MC), meant to offer both computer scientists and non-computer scientists an up-to-date overview of the field. That is why the set of notions introduced here is rather large, but the presentation is informal, without proofs and with rigorous definitions given only for the basic types of P systems — symbol object P systems with multiset rewriting rules, systems with symport/antiport rules, systems with string objects, tissue-like P systems, and neural-like P systems. Besides a list of (biologically inspired or mathematically motivated) ingredients/features which can be used in systems of these types, we also mention a series of results, as well as a series of research trends and topics.

The activity of mechanosensitive channels of large conductance (MscL for short) in cellular membranes is modeled within the framework of P systems. These channels are gated by changes in the pressure exerted against the membrane, which may be due to natural environmental conditions (e.g., rain falling) or to a suction applied by artificial patch clamping. In correspondence to these distinct situations, we present two models for the description of MscL activation and functioning. We present simulations

in silico

of one model and show the emergent behavior of fundamental quantitites. Finally, we discuss several topics for further extensions and development of these models.

P systems have clear structural analogies with the cell. However, certain difficulties arise when one attempts to represent a biomolecular process using these systems. This chapter suggests some ways to overcome such difficulties and to provide P systems with further functionalities aimed at increasing their versatility in the modeling of biomolecular processes. Concepts from state transition dynamics are taken to put P systems in a general analysis framework for dynamical discrete systems. An explicit notion of environment is proposed to provide P systems with a regulatory and constraining agent, as real biomolecular processes must deal with. The chapter focuses on a new rewriting strategy inspired by biochemistry, in which reactivities play a central role in driving the rules as happens during biochemical reactions. Tests on an algorithm implementing rewriting with reactivities, realized on a simulator called

Psim

, show the capability of this algorithm to express several processes with precision, particularly those presenting oscillatory phenomena. Finally, an analysis of the process of leukocyte recruitment is also performed using

Psim

.

We present a probabilistic simulator of P systems that implements the evolution-communication model proposed in [

8

] enriched with some probabilistic parameters inspired by cell biology. After describing the software and its working, we compare the mathematical model with the biological reality of the cell. Then, we present some biological applications showing how one can use this software to simulate simple but interesting biological phenomena, related to respiration in

Escherichia coli

and the interaction between respiration and photosynthesis in cyanobacteria. The present chapter is an extension of the work presented in [

5

].

The immune system represents the natural defense of an organism. It comprises a network of cells, molecules, and organs whose primary tasks are to defend the organism from pathogens, and to maintain its integrity. Since our knowledge of the immune system is still incomplete, formal modeling can help provide a better understanding of its underlying principles and organization. In this chapter we provide a brief introduction to the biology of the immune system, recalling several approaches used in the modeling of the immune system, and then describe a model based on P systems. Starting from a variant of P systems called client-server P systems, we use an abstract simulator as a useful intermediate step from a formal theory suitable for theoretical results to a software implementation of a molecular network. Finally, our approach leads to novel software able to provide new insights into the interactions influencing T cell behavior with the use of statistical correlations of the software experiments’ results.

A model of light reactions taking place in photosynthesis is constructed using a variant of P systems. Behaviors of the model under various combinations of parameters are tested on a computer. Computer simulations show that the model explains in a good way many phenomena of photosynthesis, including photoinhibition mechanisms. A dynamical system using differential equations for photosynthesis is compared with the P system model. The comparison makes it clear that P systems are much better tools for dealing with biological phenomena than models based on differential equations.

We present an approach to modeling and simulating the protein p53 signaling pathways by means of a particular class of P systems, called ARMS (Abstract Rewriting Systems on Multisets). The results of the computer simulations are presented; they agree with the biological observations.

This chapter deals with the application of P systems to sorting problems. Traditional studies of sorting assume constant time for comparing two numbers and compute the time complexity with respect to the number of components of a vector to be sorted. Here, we assume the number of components to be a fixed number

k

, and study various algorithms based on different models of P systems and their time complexities with respect to the maximal number or to the sum of the numbers. Massively parallel computations that can be realized within the framework of P systems may lead to major improvements in solving the classical integer sorting problems. Despite this important characteristic, we will see that, depending on the model used, the massive parallelism feature cannot be always used, and so some results will have complexities “comparable” with the classical integer sorting algorithms. Still, computing a word (ordered) from a multiset (unordered) can be a goal not only for computer science, but also, e.g., for biosynthesis (separating mixed objects according to some characteristics). Here, we will move from ranking algorithms that, starting with numbers represented as multisets, produce symbols in an order, to effective sorting algorithms.

A model of plant growing based on some variants of P systems is considered. The model (very close to L systems-based approaches) represents a further step toward a more modular way to specify biological systems. A specification language and a tool supporting the model are also presented together with some simple examples. A key operation introduced in this context is rule rewriting — there are rules which rewrite the right hand sides of other rules. Because of the importance of this operation for our approach, we also briefly investigate it from a theoretical point of view in the Annex.

We develop an analysis of the Needham-Schroeder public key protocol in the framework of membrane computing. This analysis is used to validate the protocol and exhibits, as expected, a well known logical attack. The novelty of our approach is to use multiset rewriting in a nest of membranes. The use of membranes enables us to make airtight the conditions for detecting an attack. The approach has been validated by developing a full implementation for several versions of the analysis.

A new type of approximate algorithm for optimization problems, called the membrane algorithm, is proposed. A membrane algorithm consists of several regions separated by means of membranes; in each region we place a few tentative solutions of the optimization problem and a subalgorithm. The subalgorithms improve the tentative solutions simultaneously. The best and worst solutions in a region are sent to adjacent inner and outer regions, respectively. By repeating this process, a good solution will appear in the innermost region. The algorithm terminates if a termination condition is satisfied. A simple condition is the number of iterations, while a little more sophisticated condition becomes true if the good solution is not changed during a predetermined number of iterations. Computer experiments show that the membrane algorithms solve the traveling salesman problem better than the simulated annealing algorithm.

In this chapter we present a general framework to provide efficient solutions to decision problems through families of cell-like membrane systems constructed in a semi-uniform way (associating with

each instance

of the problem one P system solving it) or a uniform way (all instances of a decision problem having the same

size

are processed by the same system). We also show a brief compendium of efficient semi-uniform and uniform solutions to hard problems in these systems, and we explicitly describe some of these solutions.

We introduce a general model for linguistics based on P systems, called linguistic P systems (LPSs). Several applications of LPSs to linguistic issues are suggested. Two variants of LPSs are developed: conversational P systems (CPSs) and dynamic meaning P systems (DMPSs). The former type of systems are used to provide a membrane computing approach to the analysis of conversational acts, while the latter type offer a bio-inspired framework for dealing with semantics.

P automata are membrane systems that work as accepting devices. In this chapter, two parsing methods using P automata are presented. The first method uses P automata with active membranes for parsing natural language sentences into dependency trees. The second method uses a variant of P automata with evolution and communication rules for parsing Marcus contextual languages.

The simulation of a P system with current computers is a quite complex task. P systems are intrinsically nondeterministic computational devices and therefore their computation trees are difficult to store and handle with computers with one processor (or a bounded number of processors). Nevertheless, there exists a first generation of simulators which can be successfully used for pedagogical purposes and as assistant tools for researchers. This chapter summarizes some of these simulators, presenting the state of the art of the available software for simulating (different variants of) cell-like membrane systems.