Fundamenta Informaticae - Volume 171, issue 1-4

Authors: Ferretti, Claudio | Leporati, Alberto | Manzoni, Luca | Porreca, Antonio E.

Article Type: Research Article

Abstract: Reaction systems are a computational model inspired by the bio-chemical reactions that happen inside biological cells. They have been and currently are studied for their many nice theoretical properties. They are also a useful modeling tool for biochemical systems, but in order to be able to employ them effectively in the field the presence of efficient and widely available simulators is essential. Here we explore three different algorithms and implementations of the simulation, comparing them to the current state of the art. We also show that we can obtain performances comparable to GPU-based simulations on real-world systems by using a …carefully tuned CPU-based simulator. Show more

Keywords: Reaction Systems, Simulation of Biochemical Systems

DOI: 10.3233/FI-2020-1878

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 175-188, 2020

Authors: Formenti, Enrico | Perrot, Kévin

Article Type: Research Article

Abstract: Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the computational complexity of the prediction problem, namely, the complexity of knowing, given a finite configuration c and a cell x in c , if cell x will eventually become unstable. This is an attempt to formalize the intuitive notion of “behavioral complexity” that one easily observes in simulations. However, despite many efforts and nice results, the original question remains open: how hard is it to predict the two-dimensional sandpile model …of Bak, Tang and Wiesenfeld? Show more

DOI: 10.3233/FI-2020-1879

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 189-219, 2020

Authors: Gianola, Alessandro | Kasangian, Stefano | Manicardi, Desiree | Sabadini, Nicoletta | Schiavio, Filippo | Tini, Simone

Article Type: Research Article

Abstract: In this paper, we recall the basic features of the CospanSpan(Graph) algebra for the compositional description of reconfigurable hierarchical networks. In particular, we focus on compositionality and on the possibility of describing the interactions among physical/biological systems, using a parallel with communication operation not considered in the usual Kleene’s algebra. As a novel application, we give a complete compositional description in Span(Graph) of a simplified version of the heart system.

Keywords: Automata, Categories, Composition, Biological Systems

DOI: 10.3233/FI-2020-1880

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 221-237, 2020

Authors: Jalonen, Joonatan | Kari, Jarkko

Article Type: Research Article

Abstract: Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) expansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption …of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018. Show more

Keywords: cellular automata, expansivity, pseudo-orbit tracing property

DOI: 10.3233/FI-2020-1881

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 239-259, 2020

Authors: Kleijn, Jetty | Koutny, Maciej | Mikulski, Łukasz

Article Type: Research Article

Abstract: Reaction systems were introduced in order to provide an abstract model for the study of the biochemical processes that take place in the living cell. Processes of this kind are the result of the interactions between reactions and may be influenced by the environment. Thus, reaction systems can be considered as a model of (interactive) computation. In previous works, various equivalences defined directly on reaction systems and processes had been proposed and compared. These equivalences were all based on functional equivalence that compares a system’s behaviour at every stage of its execution. In this paper, in contrast, we investigate enabling …equivalence which focuses on the system behaviour only in specific stages of its evolution, namely those where all of its reactions are active. We discuss the effect of such an approach and, in particular, its relationship to a transition system representation of the system’s behaviour. Show more

Keywords: Reaction system, living cell, model of computation, functional equivalence, interactive process, context-independent process, transition system, enabling equivalence

DOI: 10.3233/FI-2020-1882

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 261-277, 2020

Authors: Maspero, Davide | Damiani, Chiara | Antoniotti, Marco | Graudenzi, Alex | Di Filippo, Marzia | Vanoni, Marco | Caravagna, Giulio | Colombo, Riccardo | Ramazzotti, Daniele | Pescini, Dario

Article Type: Research Article

Abstract: The metabolic processes related to the synthesis of the molecules needed for a new round of cell division underlie the complex behaviour of cell populations in multi-cellular systems, such as tissues and organs, whereas their deregulation can lead to pathological states, such as cancer. Even within genetically homogeneous populations, complex dynamics, such as population oscillations or the emergence of specific metabolic and/or proliferative patterns, may arise, and this aspect is highly amplified in systems characterized by extreme heterogeneity. To investigate the conditions and mechanisms that link metabolic processes to cell population dynamics, we here employ a previously introduced multi-scale …model of multi-cellular system, named FBCA (Flux Balance Analysis with Cellular Automata), which couples biomass accumulation, simulated via Flux Balance Analysis of a metabolic network, with the simulation of population and spatial dynamics via Cellular Potts Models. In this work, we investigate the influence that different modes of nutrients diffusion within the system may have on the emerging behaviour of cell populations. In our model, metabolic communication among cells is allowed by letting secreted metabolites to diffuse over the lattice, in addition to diffusion of nutrients from given sources. The inclusion of the diffusion processes in the model proved its effectiveness in characterizing plausible biological scenarios. Show more

Keywords: Multi-scale modeling, Cellular Potts Model, Flux Balance Analysis, Diffusion, Cancer development

DOI: 10.3233/FI-2020-1883

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 279-295, 2020

Authors: Orellana-Martín, David | Valencia-Cabrera, Luis | Riscos-Núñez, Agustín | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Biological membranes play an active role in the evolution of cells over time. In the framework of Membrane Computing, P systems with active membranes capture this idea, and the possibility to increase the number of membranes during a computation. Classically, it has been considered, by using division rules, inspired in the mitosis process. Initially, the membranes in these models are supposed to have an electrical polarization (positive, negative or neutral) and the semantics is minimalist , in the sense that rules are applied in parallel, but in one transition step, each membrane can be the subject of at most one …rule of types communication, dissolution or division. This paper focuses on polarizationless P systems with active membranes in which membrane creation rules are considered instead of membrane division rules as a mechanism to construct an exponential workspace, expressed both in terms of number of objects and membranes, in linear time. Moreover, the minimalist semantics is considered and some complexity results are provided in this framework, allowing to tackle the P versus NP problem from a new perspective. An original frontier of the efficiency in this context is unveiled in this paper: allowing membrane creation rules to be applicable in any membrane of the system, instead of restricting them to only elementary membranes, yields a significant boost on the computational power. More precisely, only problems in P can be efficiently solved in the restricted case, while in the non-restricted case an efficient and uniform solution to a PSPACE -complete problem is provided. Show more

DOI: 10.3233/FI-2020-1884

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 297-311, 2020

Authors: Pan, Linqiang | Song, Bosheng

Article Type: Research Article

Abstract: P systems are a class of parallel computational models inspired by the structure and functioning of living cells, where all the evolution rules used in a system are initially set up and keep unchanged during a computation. In this work, inspired by the fact that chemical reactions in a cell can be affected by both the contents of the cell and the environmental conditions, we introduce a variant of P systems, called P systems with rule production and removal (abbreviated as RPR P systems), where rules in a system are dynamically changed during a computation, that is, at any computation …step new rules can be produced and some existing rules can be removed. The computational power of RPR P systems and catalytic RPR P systems is investigated. Specifically, it is proved that catalytic RPR P systems with one catalyst and one membrane are Turing universal; for purely catalytic RPR P systems, one membrane and two catalysts are enough for reaching Turing universality. Moreover, a uniform solution to the SAT problem is provided by using RPR P systems with membrane division. It is known that standard catalytic P systems with one catalyst and one membrane are not Turing universal. These results imply that rule production and removal is a powerful feature for the computational power of P systems. Show more

Keywords: Bio-inspired Computing, Membrane Computing, Catalytic P System, Universality, SAT Problem

DOI: 10.3233/FI-2020-1885

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 313-329, 2020

Authors: Petre, Luigia | Sanwal, Usman | Shah, Gohar | Panchal, Charmi | Tyagi, Dwitiya | Petre, Ion

Article Type: Research Article

Abstract: How robust is a healthcare system? How does a patient navigate the system and what is the cost (e.g., number of medical services required or number of times the medical provider had to be changed to get access to the required medical services) incurred from the first symptoms to getting cured? How will it fare in the wake to a sudden epidemic or a disaster? How are all of these affected by administrative decisions such as allocating/diminishing resources in various areas or centralising services? These are the questions motivating our study on a formal prototype model for a healthcare system. …We propose that a healthcare system can be understood as a distributed system with independent nodes (healthcare providers) computing according to their own resources and constraints, with tasks (patient needs) being allocated between the nodes. The questions about the healthcare system become in this context questions about resource availability and distribution between the nodes. We construct in this paper an Event-B model capturing the basic functionality of a simplified healthcare system: patients with different types of medical needs being allocated to suitable medical providers, and navigating between different providers for their turn for multi-step treatments. Show more

DOI: 10.3233/FI-2020-1886

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 331-343, 2020

Authors: Rundo, Leonardo | Militello, Carmelo | Vitabile, Salvatore | Russo, Giorgio | Sala, Evis | Gilardi, Maria Carla

Article Type: Research Article

Abstract: Natural phenomena and mechanisms have always intrigued humans, inspiring the design of effective solutions for real-world problems. Indeed, fascinating processes occur in nature, giving rise to an ever-increasing scientific interest. In everyday life, the amount of heterogeneous biomedical data is increasing more and more thanks to the advances in image acquisition modalities and high-throughput technologies. The automated analysis of these large-scale datasets creates new compelling challenges for data-driven and model-based computational methods. The application of intelligent algorithms, which mimic natural phenomena, is emerging as an effective paradigm for tackling complex problems, by considering the unique challenges and opportunities pertaining to …biomedical images. Therefore, the principal contribution of computer science research in life sciences concerns the proper combination of diverse and heterogeneous datasets—i.e., medical imaging modalities (considering also radiomics approaches), Electronic Health Record engines, multi-omics studies, and real-time monitoring—to provide a comprehensive clinical knowledge. In this paper, the state-of-the-art of nature-inspired medical image analysis methods is surveyed, aiming at establishing a common platform for beneficial exchanges among computer scientists and clinicians. In particular, this review focuses on the main natureinspired computational techniques applied to medical image analysis tasks, namely: physical processes, bio-inspired mathematical models, Evolutionary Computation, Swarm Intelligence, and neural computation. These frameworks, tightly coupled with Clinical Decision Support Systems, can be suitably applied to every phase of the clinical workflow. We show that the proper combination of quantitative imaging and healthcare informatics enables an in-depth understanding of molecular processes that can guide towards personalised patient care. Show more

Keywords: Nature-inspired computing, artificial intelligence, medical image analysis, biomedical data integration

DOI: 10.3233/FI-2020-1887

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 345-365, 2020

Authors: Simone, Pernice | Laura, Follia | Gianfranco, Balbo | Luciano, Milanesi | Giulia, Sartini | Niccoló, Totis | Pietro, Lió | Ivan, Merelli | Francesca, Cordero | Marco, Beccuti

Article Type: Research Article

Abstract: Computational Biology is a fast-growing field that is enriched by different data-driven methodological approaches and by findings and applications in a broad range of biological areas. Fundamental to these approaches are the mathematical and computational models used to describe the different states at microscopic (for example a biochemical reaction), mesoscopic (the signalling effects at tissue level), and macroscopic levels (physiological and pathological effects) of biological processes. In this paper we address the problem of combining two powerful classes of methodologies: Flux Balance Analysis (FBA) methods which are now producing a revolution in biotechnology and medicine, and Petri Nets (PNs) which …allow system generalisation and are central to various mathematical treatments, for example Ordinary Differential Equation (ODE) specification of the biosystem under study. While the former is limited to modelling metabolic networks, i.e. does not account for intermittent dynamical signalling events, the latter is hampered by the need for a large amount of metabolic data. A first result presented in this paper is the identification of three types of cross-talks between PNs and FBA methods and their dependencies on available data. We exemplify our insights with the analysis of a pancreatic cancer model. We discuss how our reasoning framework provides a biologically and mathematically grounded decision making setting for the integration of regulatory, signalling, and metabolic networks and greatly increases model interpretability and reusability. We discuss how the parameters of PN and FBA models can be tuned and combined together so to highlight the computational effort needed to perform this task. We conclude with speculations and suggestions on this new promising research direction. Show more

Keywords: Computational biology, Petri Nets and Flux Balance Analysis

DOI: 10.3233/FI-2020-1888

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 367-392, 2020

Authors: Umeo, Hiroshi

Article Type: Research Article

Abstract: The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by Myhill and reported by Moore in 1964 to synchronize all/some parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional (1D) arrays but also for multi-dimensional arrays. In the present paper, we construct a survey on the study of FSSP algorithms, focusing on recent developments.

Keywords: Cellular automaton, Firing squad synchronization problem, FSSP

DOI: 10.3233/FI-2020-1889

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 393-419, 2020