Catálogo de publicaciones - libros

Among the many events that occur in the life of biological organisms there are multitudes of specific chemical transformations that provide the cell with usable energy and molecules needed to form its structure and coordinate its activities. These biochemical reactions, as well as all other cellular processes, are governed by basic principles of chemistry and physics. A significant factor that determines whether or not reactions could take place is the entropy (it measures the randomness of the system). This measure depends on various factors. In an abstract framework, all these factors, which describe the way molecules interact, can be expressed by means of a computable multi-valued function that, depending on the current state of the system, establishes the possible ways of the evolution of the system. Inspired by these facts, we introduce and study several bio-mimetic computational rewriting systems that use discrete components (i.e., finite alphabets, finite set(s) of rewriting rules, etc.) and perform their computational steps in a non-deterministic manner and in a degree of rewriting parallelism that depends on the current state of the system, both specified by a given multi-valued function. Furthermore, we describe systems which produce the same output independently of the values taken by the considered functions.

We continue the investigation of P colonies, a class of abstract computing devices composed of very simple agents (computational tools), acting and evolving in a shared environment. We show that if P colonies are initialized by placing a number of copies of a certain object in the environment, then they can generate any recursively enumerable set of numbers with a bounded number of cells, each cell containing a bounded number of programs (of bounded length), for constant bounds.

We examine the class of languages over countably infinite alphabets characterized by a class of restricted and simplified P automata variants, which we call P finite automata, and show that these classes possess several properties which make them perfect candidates for being the natural extension of the notion of finite automata and that of regular languages to infinite alphabets. To this aim, we also show that P finite automata are equivalent to a restricted variant of register machines, providing a more conventional automata theoretical characterization of the same infinite alphabet language class.

This paper proposes a model in terms of metabolic P graphs of a few important processes occurring during the biological phase where the choice is made to begin again mitosis or to arrest it. The cellular processes during this phase turn out to be especially interesting in the case of DNA damage, which triggers a specific destruction of Cdc25A phosphatase. It has important implications to understand the role of cell cycle checkpoints and the mechanism(s) guiding the proliferation of UV-resistant tumored cells. The formalism of metabolic P graphs highlights the relevant information of the biological network dynamics, and the individuation of few parameters rules the basic mechanisms of Cdc25A degradation, involving a couple of important mitotic oscillators.

Two models of conformon-P systems, one restricted in the number of input conformons and the other restricted in the number of input membranes, are proved to induce infinite hierarchies.

The described systems do not work under the requirement of maximal parallelism and perform deterministic simulations of restricted counter machines.

The way how cell signals are generated, encoded, transferred, modified, and utilized is essential for understanding information processing inside living organisms. The tremendously growing biological knowledge about proteins and their interactions draws a more and more detailed image of a complex functional network. Considering signalling networks as computing devices, the detection of structural principles, especially modularization into subunits and interfaces between them, can help to seize ideas for their description and analysis. Algebraic models like P systems prove to be appropriate to this. We utilize string-objects to carry information about protein binding domains and their ligands. Embedding these string-objects into a deterministic graph structured P system with dynamical behavior, we introduce a model that can describe cell signalling pathways on a submolecular level. Beyond questions of formal languages, the model facilitates tracing the evolutionary development from single protein components towards functional interacting networks. We exemplify the model by means of the yeast pheromone pathway.

A -output spiking neural P system (SNP) with output neurons, , ⋯, , generates a tuple (, ⋯, ) of positive integers if, starting from the initial configuration, there is a sequence of steps such that during the computation, each generates exactly two spikes   (the times the pair   are generated may be different for different output neurons) and the time interval between the first and the second is . After the output neurons have generated their pairs of spikes, the system eventually halts. Another model, called -train SNP, has only one output neuron. It generates a -tuple (, ⋯, ) if, starting from the initial configuration, the output neuron generates the spike train ⋯ with exactly +1 ’s such that the interval between the and the +1 is , and the system eventually halts. We assume, without loss of generality, that each neuron in the SNP is either bounded or unbounded. (Bounded here means that there is a fixed constant such that at any time during the computation, the number of spikes in the neuron is at most . Otherwise, the neuron is unbounded.) It is known that 1-output SNPs (= 1-train SNPs) are universal, i.e., they generate exactly the recursively enumerable sets over . Here, we show the following:

1. For ≥1, a set  ⊆  is semilinear if and only if it can be generated by a -output SNP, where every unbounded neuron satisfies the property that once it starts “spiking” it will no longer receive future spikes (but can continue spiking). This result also holds for -train SNP.

2. The set = {(,2) |  ≥1} (which is semilinear) cannot be generated by any 2-output bounded SNP (i.e., SNP all of whose neurons are bounded). Thus, for ≥2, there are semilinear sets over that cannot be generated by -output bounded SNPs. This contrasts a known result that 1-output bounded SNPs generate all semilinear sets over .

3. For ≥2, -output bounded SNPs are computationally more powerful than -train bounded SNPs. (They are identical when =1.)

4. For ≥1, -output bounded SNPs and -train bounded SNPs can be characterized by certain classes of nondeterministic finite automata with strictly monotonic counters.

is an NP–hard optimization problem that arises in a natural way when one considers computations in which the amount of energy provided with the input values is preserved during the computation. In this paper we propose a polynomial time membrane algorithm that computes approximate solutions to the instances of , and we study its behavior on (almost) uniformly randomly chosen instances. Moreover, we compare the (estimated) coefficient of approximation of this algorithm with the ones obtained from several other polynomial time heuristics. The result of this comparison indicates the superiority of the membrane algorithm with respect to many other traditional approximation techniques.

We consider symport/antiport P systems using the time as the support for the output of a computation. We describe and study the properties of “timed symport/antiport systems”, showing that this new model of membrane systems based on time has more power/flexibility, and thus allows us to improve previous universality results. We were able to improve or match the best results concerning the symport/antiport systems which consider the output as originally defined as the number of molecules found in a pre-defined elementary membrane in the halting configuration of the system.

This paper presents the use of P systems and -calculus to model interacting molecular entities and how they are translated into a probabilistic and symbolic model checker called PRISM.