Search

Gene regulatory networks represent the interactions among genes regulating the activation of specific cell functionalities. They have been successfully modelled using Boolean networks, where a set of Boolean variables model the activation state of each gene, and Boolean functions model positive and negative influences among genes. Moreover, when the effect of such influences is additive, threshold Boolean networks, in which Boolean functions are replaced by simpler threshold functions, turned out to be particularly effective. In this paper we propose a systematic translation of threshold Boolean networks into Ehrenfeucht and Rozenberg's reaction systems. Our translation produces a non redundant set of reactions, each using a minimal set of objects. This translation allows us to simulate the behaviour of a general threshold Boolean network by simply executing the (closed) reaction system we obtain, and to investigate causality relations among genes by applying tools available for reaction systems. We implemented our translation in an open-source tool and applied it in two case studies: the gene regulation network of segment polarity in Drosophila melanogaster and the one controlling the differentiation of Th cells in the immune system. In both case studies, we investigate causalities among genes in the reaction system obtained from the translation by applying a tool for the computation of formula based predictors. In the context of the second case study, we show that also Boolean networks with non-additive influences and modelling genes with multiple expression levels can be dealt with by our approach.

In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

Gene regulatory networks represent the interactions among genes regulating the activation of specific cell functionalities and they have been successfully modeled using threshold Boolean networks. In this paper we propose a systematic translation of threshold Boolean networks into reaction systems. Our translation produces a non redundant set of rules with a minimal number of objects. This translation allows us to simulate the behavior of a Boolean network simply by executing the (closed) reaction system we obtain. This can be very useful for investigating the role of different genes simply by “playing” with the rules. We developed a tool able to systematically translate a threshold Boolean network into a reaction system. We use our tool to translate two well known Boolean networks modelling biological systems: the yeast-cell cycle and the SOS response in Escherichia coli. The resulting reaction systems can be used for investigating dynamic causalities among genes.

Gene Regulatory Networks (GRNs) represent the interactions among genes regulating the activation of specific cell functionalities, such as reception of (chemical) signals or reaction to environmental changes. Studying and understanding these processes is crucial: they are the fundamental mechanism at the basis of cell functioning, and many diseases are based on perturbations or malfunctioning of some gene regulation activities. In this paper, we provide an overview on computational approaches to GRN modelling and analysis. We start from the biological and quantitative modelling background notions, recalling differential equations and the Gillespie’s algorithm. Then, we describe more in depth qualitative approaches such as Boolean networks and some computer science formalisms, including Petri nets, P systems and reaction systems. Our aim is to introduce the reader to the problem of GRN modelling and to guide her/him along the path that goes from classical quantitative methods, through qualitative methods based on Boolean network, up to some of the most relevant qualitative computational methods to understand the advantages and limitations of the different approaches.

Reaction systems are a qualitative formalism for modeling systems of biochemical reactions characterized by the non-permanency of the elements: molecules disappear if not produced by any enabled reaction. Reaction systems execute in an environment that provides new molecules at each step. Brijder, Ehrenfeucht and Rozemberg introduced the idea of predictors. A predictor of a molecule s, for a given n, is the set of molecules to be observed in the environment in order to determine whether s is produced or not by the system at step n. We introduced the notion of formula based predictor, that is a propositional logic formula that precisely characterizes environments that lead to the production of s after n steps. In this paper we revise the notion of formula based predictor by defining a specialized version that assumes the environment to provide molecules according to what expressed by a temporal logic formula. As an application, we use specialized formula based predictors to give theoretical grounds to previously obtained results on a model of gene regulation.

In reaction systems, preimages and n-th ancestors are sets of reactants leading to the production of a target set of products in either one or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality n-th ancestors, computing their size, or counting them, are intractable. In this paper we propose a characterization of n-th ancestors as a Boolean formula, and we define an operator able to compute such a formula in polynomial time. Our formula can be exploited to solve all preimage and ancestors problems and, therefore, it can be directly used to study their complexity. In particular, we focus on two problems: (i) deciding whether a preimage/n-th ancestor exists (ii) finding a preimage/n-th ancestor of minimal size. Our approach naturally leads to the definition of classes of systems for which such problems can be solved in polynomial time.

Reaction systems are a qualitative formalism for the modelling of systems of biochemical reactions. In their original formulation, a reaction system executes in an environment (or context) that can supply it with new objects at each evolution step. The context drives the behaviour of a reaction system: it can provide different inputs to the system that can lead to different behaviours. In order to more faithfully deal with open systems, in this paper we propose a more powerful notion of context having not only the capability to provide objects, but also to absorb (or remove) objects at each evolution step. For such reaction systems with generalized context we investigate properties of dynamic causality by revising the previously proposed concept of formula based predictor. A formula based predictor is a Boolean formula characterising all contexts that lead to the production of a certain object after a given number of steps. In this paper, we revise the theory of formula based predictors in order to deal with reaction systems executed in a context of the new kind. As applications, we show an example of interaction between biochemical pathways and a reaction system modelling cell metabolism and respiration.

In this paper we investigate dynamic causalities in membrane systems by proposing the concept of “predictor”, originally defined in the context of the reaction systems by Brijder, Ehrenfeucht and Rozenberg. The goal is to characterise sufficient and necessary conditions for the presence of a multiset of molecules of interest in the configuration of a P system at a given evolution step (independently from the non-deterministic choices taken). These conditions can be used to study causal relationships between molecules and, therefore, to predict some aspects of future development of multiset rewriting systems. To achieve this goal, we introduce the new concept of “multiset pattern” representing a logical formula on multisets. A sufficient predictor can be expressed as a pattern characterising initial multisets that will surely evolve, after the given number of evolution steps, into a multiset containing the molecules of interest. On the other hand, a necessary predictor models initial multisets that may evolve after the given number of evolution steps, into a multiset containing the molecules of interest. Necessary predictors can be used to characterise initial multisets that will surely not evolve (in the required number of steps) into a multiset that contains such molecules. We inductively define operators able to compute these predictors. The patterns obtained from our operators are sound (sufficient or necessary) predictors, but, in general, they are not complete.

We describe two extensions of P systems for the modelling of populations and ecosystems. They are the Minimal Probabilistic P systems (MPP systems) and the Attributed Probabilistic P systems (APP systems). We describe also two case studies in which the two formalisms have been applied to the study of real ecological systems. The first case study deals with the causes of the stability of European hybrid populations of water frogs. The second case study deals with social interactions and the establishment of dominance hierarchies in primates.

In this paper we investigate dynamic causalities in membrane systems by proposing the concept of “predictor”, originally defined in the context of Ehrenfeucht and Rozemberg’s reaction systems. The goal is to characterize sufficient conditions for the presence of a molecule of interest in the configuration of a P system after a given number of evolution steps (independently from the non-deterministic choices taken). Such conditions can be used to study causal relationships between molecules. To achieve our goal, we introduce the new concept of “multiset pattern” representing a logical formula on multisets. A predictor can be expressed as a pattern characterizing the initial multisets that will surely lead (sufficient condition) to the presence of the molecule of interest after the given number of evolution steps. We define also an operator that computes such a predictor.