nach oben

2006 | Buch

Kapitel lesen Erstes Kapitel lesen

Applications of Membrane Computing

herausgegeben von: Gabriel Ciobanu, Gheorghe Păun, Mario J. Pérez-Jiménez

Verlag: Springer Berlin Heidelberg

Buchreihe : Natural Computing Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Membrane computing is a branch of natural computing which investigates computing models abstracted from the structure and functioning of living cells and from their interactions in tissues or higher-order biological structures. The models considered, called membrane systems (P systems), are parallel, distributed computing models, processing multisets of symbols in cell-like compartmental architectures. In many applications membrane systems have considerable advantages – among these are their inherently discrete nature, parallelism, transparency, scalability and nondeterminism.

In dedicated chapters, leading experts explain most of the applications of membrane computing reported so far, in biology, computer science, computer graphics and linguistics. The book also contains detailed reviews of the software tools used to simulate P systems.

Inhaltsverzeichnis

Frontmatter

Introduction to Membrane Computing

Chapter 1. Introduction to Membrane Computing

Abstract

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.

Gheorghe Păun

Bio-applications

Chapter 2. P System Models for Mechanosensitive Channels

Abstract

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.

Ioan I. Ardelean, Daniela Besozzi, Max H. Garzon, Giancarlo Mauri, Sujoy Roy

Chapter 3. P Systems for Biological Dynamics

Abstract

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.

Luca Bianco, Federico Fontana, Giuditta Franco, Vincenzo Manca

Chapter 4. Modeling Respiration in Bacteria and Respiration/Photosynthesis Interaction in Cyanobacteria Using a P System Simulator

Abstract

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].

Matteo Cavaliere, Ioan I. Ardelean

Chapter 5. Modeling Cell-Mediated Immunity by Means of P Systems

Abstract

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.

Gabriel Ciobanu

Chapter 6. A Membrane Computing Model of Photosynthesis

Abstract

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.

Taishin Yasunobu Nishida

Chapter 7. Modeling p53 Signaling Pathways by Using Multiset Processing

Abstract

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.

Yasuhiro Suzuki, Hiroshi Tanaka

Computer Science Applications

Chapter 8. Static Sorting P Systems

Abstract

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.

Artiom Alhazov, Dragoş Sburlan

Chapter 9. Membrane-Based Devices Used in Computer Graphics

Abstract

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.

Alexandros Georgiou, Marian Gheorghe, Francesco Bernardini

Chapter 10. An Analysis of a Public Key Protocol with Membranes

Abstract

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.

Olivier Michel, Florent Jacquemard

Chapter 11. Membrane Algorithms: Approximate Algorithms for NP-Complete Optimization Problems

Abstract

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.

Taishin Yasunobu Nishida

Chapter 12. Computationally Hard Problems Addressed Through P Systems

Abstract

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.

Mario J. Pérez-Jiménez, Alvaro Romero-Jiménez, Fernando Sancho-Caparrini

Applications to Linguistics

Chapter 13. Linguistic Membrane Systems and Applications

Abstract

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.

Gemma Bel Enguix, Maria Dolores Jiménez López

Chapter 14. Parsing with P Automata

Abstract

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.

Radu Gramatovici, Gemma Bel Enguix

Membrane Software

Chapter 15. Available Membrane Computing Software

Abstract

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.

Miguel Angel Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez

Backmatter

Titel: Applications of Membrane Computing
herausgegeben von: Gabriel Ciobanu
Gheorghe Păun
Mario J. Pérez-Jiménez
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-29937-0
Print ISBN: 978-3-540-25017-3
DOI: https://doi.org/10.1007/3-540-29937-8