Abstract

Abstract

Abstract

Network biology is a powerful framework for studying the structure, function, and dynamics of biological systems, offering insights into the balance between health and disease states. The field is seeing rapid progress in all of its aspects: data availability, network synthesis, network analytics, and impactful applications in medicine and drug development. We review the most recent and significant results in network biomedicine, with a focus on the latest data, analytics, software resources, and applications in medicine. We also discuss what in our view are the likely directions of impactful development over the next few years.

Abstract

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n, for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Omega(n) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O(log n) and O(root n) that accept non-regular languages. Several open problems and directions for further developments are finally discussed.

Abstract

BACKGROUND: Formalin-fixed, paraffin-embedded (FFPE) tissue slides are routinely used in cancer diagnosis, clinical decision-making, and stored in biobanks, but their utilization in Raman spectroscopy-based studies has been limited due to the background coming from embedding media.METHODS: Spontaneous Raman spectroscopy was used for molecular fingerprinting of FFPE tissue from 46 patient samples with known methylation subtypes. Spectra were used to construct tumor/non-tumor, IDH1WT/IDH1mut, and methylation-subtype classifiers. Support vector machine and random forest were used to identify the most discriminatory Raman frequencies. Stimulated Raman spectroscopy was used to validate the frequencies identified. Mass spectrometry of glioma cell lines and TCGA were used to validate the biological findings.RESULTS: Here we develop APOLLO (rAman-based PathOLogy of maLignant glioma) - a computational workflow that predicts different subtypes of glioma from spontaneous Raman spectra of FFPE tissue slides. Our novel APOLLO platform distinguishes tumors from nontumor tissue and identifies novel Raman peaks corresponding to DNA and proteins that are more intense in the tumor. APOLLO differentiates isocitrate dehydrogenase 1 mutant (IDH1mut) from wildtype (IDH1WT) tumors and identifies cholesterol ester levels to be highly abundant in IDHmut glioma. Moreover, APOLLO achieves high discriminative power between finer, clinically relevant glioma methylation subtypes, distinguishing between the CpG island hypermethylated phenotype (G-CIMP)-high and G-CIMP-low molecular phenotypes within the IDH1mut types.CONCLUSIONS: Our results demonstrate the potential of label-free Raman spectroscopy to classify glioma subtypes from FFPE slides and to extract meaningful biological information thus opening the door for future applications on these archived tissues in other cancers.

Abstract

We continue here the theoretical study initiated approximately twenty years ago on the possibility of using living cells for computing. In this paper, we reconsider the formal operations inspired by the intramolecular DNA rearrangements in the evolution of the macronucleus from the micronucleus in a group of ciliates. After introducing the concept of a valid string, we propose an efficient algorithm for checking this property for a given string. Then we investigate which of the considered operations preserve the property of a string to be valid. We also show that just one of the operations can be simulated by a finite transducer. The important problem regarding the order of applying the operations is then investigated showing that one operation can commute with the other two. Finally, we introduce the iterated variants and investigate a few properties. A sort of a normal form for the gene assembly in ciliates is obtained. The paper ends by a short discussion about open problems and further directions of research.

Abstract

Abstract

Abstract

We introduce an accepting splicing system based on a type of splicing, multiple splicing, which has never considered so far for accepting systems. This type of splicing differs from the usual operation in that several (not necessarily distinct) rules can be applied simultaneously to the same string. We first consider accepting multiple splicing systems where the number of splicing sites is a predefined constant. We prove that this model is computationally complete, if the constant is 2, by simulating a 2-tag system. Moreover, we show that the simulation is time-complexity preserving, and discuss also the descriptional complexity of the accepting splicing system given by our construction. We then consider the accepting multiple splicing systems where the number of sites has either an upper bound or a lower bound. The computational power of these systems is also investigated. We finally discuss some open problems. (C) 2022 The Author(s). Published by Elsevier B.V. on behalf of King Saud University.

Abstract

The current paper estimated the physico-chemical properties of water in the Danube Delta (Romania), based on Sentinel 2 remote sensing data. Eleven sites from the Danube Delta were sampled in spring and autumn for three years (2018-2020) and 21 water physico-chemical parameters were measured in laboratory. Several families of machine learning algorithms, translated into hundreds of models with different parameterizations for each machine learning algorithm, based on remote sensing data input from Sentinel 2 spectral bands, were employed to find the best models that predicted the values measured in laboratory. This was a novel approach, reflected in the types of selected models that minimised the values of performance metrics for the tested parameters. For alkalinity, calcium, chloride, carbon dioxide, hardness, potassium, sodium, ammonium, dissolved oxygen, sulphates, and suspended matter the results were promising, with an overall percentage bias of the estimates of +/- 10% from the observed values. For copper, magnesium, nitrites, nitrates, turbidity and zinc the estimates were fairly accurate, with percentage biases in the interval +/- 10% - 20%, whereas for detergents, led, and phosphates the percentage bias was higher than 20%. Overall, the results of the current study showed fairly good estimates between remote sensing based estimates and laboratory measured values for most water physico-chemical parameters.

Abstract

Membrane computing or P-systems is a subfield of natural computing, which models living systems with mathematical tools. In classical membrane-computing, cells or organs are surrounded by a simple membrane and computational events take place in either side of the membrane. We have developed a new conceptual tool to better fit P-systems to higher-order organisms, which rely on the actual membrane structure of the cell and on the biochemical reactions (rules), which take place on the membrane of different organs in our body. To demonstrate the power of this new concept, we modeled the process of maintaining normoglycemia in healthy individuals as well as in type-I and type-II diabetes patients. The main challenge was to prioritize the insulin-producing P-cells over other organs, i.e., once glucose has entered the body, it must first enter specifically into pancreatic P-cells in order to release the hormone Insulin. However, using classical membrane computing, we could not implement this hierarchy. Therefore, we chose to utilize the membrane actual physiology and add its properties to the current definitions of membrane computing. In particular, we use enzymes and protein-transporters (as well as channels) to apply algebraic rules. In addition, we show that the defined systems are universal, by simulating register machines. Thus, allowing deterministic manner operations in a non-deterministic system by giving membrane-specific rules. To our gratification, we succeeded to adequately describe the process of glucose homeostasis in health and disease while bringing the science of membrane-computing closer to the natural world. (C) 2022 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.

Abstract

To better understand the potential of drug repurposing in COVID-19, we analyzed control strategies over essential host factors for SARS-CoV-2 infection. We constructed comprehensive directed protein-protein interaction (PPI) networks integrating the top-ranked host factors, the drug target proteins and directed PPI data. We analyzed the networks to identify drug targets and combinations thereof that offer efficient control over the host factors. We validated our findings against clinical studies data and bioinformatics studies. Our method offers a new insight into the molecular details of the disease and into potentially new therapy targets for it. Our approach for drug repurposing is significant beyond COVID-19 and may be applied also to other diseases.

Abstract

Abstract

Abstract

We partially answer an open question on small computational devices: how many neurons are needed by a spiking neural P system with communication on request (SNQ P Systems) to achieve universality? We provide an answer in the case when the SNQ P System uses at least 5 types of spikes. Our work shows that 6 neurons are enough to achieve universality as number generators, number accepters and function computation device. We achieve this result by using only two neuron to simulate the instructions labels and one type of spike to emulate a register. (C) 2020 Elsevier B.V. All rights reserved.

Abstract

Current advances in computational modelling and simulation have led to the inclusion of computer scientists as partners in the process of engineering of new nanomaterials and nanodevices. This trend is now, more than ever, visible in the field of deoxyribonucleic acid (DNA)-based nanotechnology, as DNA's intrinsic principle of self-assembly has been proven to be highly algorithmic and programmable. As a raw material, DNA is a rather unremarkable fabric. However, as a way to achieve patterns, dynamic behavior, or nano-shape reconstruction, DNA has been proven to be one of the most functional nanomaterials. It would thus be of great potential to pair up DNA's highly functional assembly characteristics with the mechanic properties of other well-known bio-nanomaterials, such as graphene, cellulos, or fibroin. In the current study, we perform projections regarding the structural properties of a fibril mesh (or filter) for which assembly would be guided by the controlled aggregation of DNA scaffold subunits. The formation of such a 2D fibril mesh structure is ensured by the mechanistic assembly properties borrowed from the DNA assembly apparatus. For generating inexpensive pre-experimental assessments regarding the efficiency of various assembly strategies, we introduced in this study a computational model for the simulation of fibril mesh assembly dynamical systems. Our approach was based on providing solutions towards two main circumstances. First, we created a functional computational model that is restrictive enough to be able to numerically simulate the controlled aggregation of up to 1000s of elementary fibril elements yet rich enough to provide actionable insides on the structural characteristics for the generated assembly. Second, we used the provided numerical model in order to generate projections regarding effective ways of manipulating one of the the key structural properties of such generated filters, namely the average size of the openings (gaps) within these meshes, also known as the filter's aperture. This work is a continuation of Amarioarei et al., 2018, where a preliminary version of this research was discussed.

Abstract

This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed.

Abstract

Subterranean streams represent unique heterotrophic ecosystems, usually supported by organic matter imported from the surface. Traditionally, the biological communities from subterranean streams were characterized as simple associations, with low diversity and species abundance, comprising mostly aquatic invertebrates connected by few trophic links compared with those of the surface. However, these features have not yet been described in the wider context of fluxes of energy and nutrients through food webs along a gradual switch from autotrophy (dominated by photosynthesis) towards heterotrophy (dominated by detritus) following the surface-subterranean continuum. Combining the most recent predictions of Ecological Stoichiometry and the Metabolic Theory of Ecology, this article provides a theoretical framework aiming to explain the patterns observed along the surface-subterranean continuum in streams. It is predicted that the main factors constraining the structure and functioning of communities and food webs are the decline in the quantity and diversity of basal resources along this gradient, along with nutrients availability in water that affects food quality. With increasing availability of dissolved nutrients in water, sinking-cave streams are hypothesized to fluctuate between being N and/ or P co-limited to C-limited. Combined, the quantity, quality, and diversity of basal resources regulate subterranean aquatic communities through bottom-up mechanisms, reflected in a decreased flux of macronutrients through food webs. The consequences of these bottom-up effects are decreased abundance, biomass, secondary production, consumption rate, and mean body size of communities, together with potential increases in the elemental imbalance for macronutrients, omnivory, trophic position, and niche width and overlap among aquatic consumers along the surface-subterranean continuum. The bottom-up effects induce changes in the topology of stream food webs, which become shorter, with lower trophic diversity at the base of the network, but increased connectance along this environmental gradient.

Abstract

Many experiments cannot feasibly be conducted as factorials. Simulations using synthetically generated data are viable alternatives to such factorial experiments. The main objective of the present research is to develop a methodology and platform to synthetically generate spatially explicit forest ecosystems represented by points with a predefined spatial pattern. Using algorithms with polynomial complexity and parameters that control the number of clusters, the degree of clusterization, and the proportion of nonrandom trees, we show that spatially explicit forest ecosystems can be generated time efficiently, which enables large factorial simulations. The proposed method was tested on 1200 synthetically generated forest stands, each of 25 ha, using 10 spatial indices: Clark-Evans aggregation index; Ripley's K; Besag's L; Morisita's dispersion index; Greig-Smith index; the size dominance index of Hui; index of nonrandomness of Pielou; directional index and mean directional index of Corral-Rivas; and size differentiation index of Von Gadow. The size of individual trees was randomly generated aiming at variograms such as real forests. We obtained forest stands with the expected spatial arrangement and distribution of sizes in less than 1 h. To ensure replicability of the study, we have provided free, fully functional software that executes the stated tasks.

Abstract

Subterranean streams represent unique heterotrophic ecosystems, usually supported by organic matter imported from the surface. Traditionally, the biological communities from subterranean streams were characterized as simple associations, with low diversity and species abundance, comprising mostly aquatic invertebrates connected by few trophic links compared with those of the surface. However, these features have not yet been described in the wider context of fluxes of energy and nutrients through food webs along a gradual switch from autotrophy (dominated by photosynthesis) towards heterotrophy (dominated by detritus) following the surface–subterranean continuum. Combining the most recent predictions of Ecological Stoichiometry and the Metabolic Theory of Ecology, this article provides a theoretical framework aiming to explain the patterns observed along the surface–subterranean continuum in streams. It is predicted that the main factors constraining the structure and functioning of communities and food webs are the decline in the quantity and diversity of basal resources along this gradient, along with nutrients availability in water that affects food quality. With increasing availability of dissolved nutrients in water, sinking-cave streams are hypothesized to fluctuate between being N and/ or P co-limited to C-limited. Combined, the quantity, quality, and diversity of basal resources regulate subterranean aquatic communities through bottom–up mechanisms, reflected in a decreased flux of macronutrients through food webs. The consequences of these bottom–up effects are decreased abundance, biomass, secondary production, consumption rate, and mean body size of communities, together with potential increases in the elemental imbalance for macronutrients, omnivory, trophic position, and niche width and overlap among aquatic consumers along the surface–subterranean continuum. The bottom–up effects induce changes in the topology of stream food webs, which become shorter, with lower trophic diversity at the base of the network, but increased connectance along this environmental gradient. © 2021, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

Abstract

We define and investigate a complexity measure defined for extended finite automata over groups (EFA). Roughly, an EFA is a finite automaton augmented with a register storing an element of a group, initially the identity element. When a transition is performed, not only the state, but the register contents are updated. A word is accepted if, after reading completely the word, the automaton reached a final state, and the register returned to the identity element. The group memory complexity of an EFA over a group is a function from N to N which associates with each n the value 0, if there is no word of length n accepted by the automaton, or the minimal integer c such that for every word x of length n accepted by the automaton, there is a computation on x such that the number of transitions labeled by non-neutral element of the group used in that computation is at most c. We prove that a language is regular if and only if it is accepted by an EFA with a finite group memory complexity. In particular, any EFA over a group such that all its finitely generated subgroups are finite accepts a regular language. We then provide examples of EFA over some groups that accept non-regular languages and have a sublinear group memory complexity, namely a function in O(root n) or O(log n). There are non-regular languages such that any EFA over some group that accepts that language has a group memory complexity in Omega(n). (C) 2020 Elsevier Inc. All rights reserved.

Abstract

In a recent paper, using one of the algorithmic assembly formalisms of DNA nanotechnology, we proved that one tile can self-assemble length n structures and n x n squares, which are basic shapes in the study of DNA origami. This new result within a classic Tile Assembly Model (TAM) would not have been possible without the following programming topics: how can we simulate one-dimensional staged self-assembly using the signal-passing TAM, and how can we program staged self-assembly using the available software? We provide probabilistic approaches for investigating the assembly of tile-based one-dimensional structures. We obtain a probabilistic proof of Han's hook length formula in Enumerative Combinatorics. We identify algebraic and combinatorial structures underlying these algorithmic and information theory results.

Abstract

We investigate the spiking neural P systems with communication on request (SNQ P systems) that are devices in the area of neural like P systems abstracting the way in which neurons work and process information. Here we discuss the SNQ P systems using the rule application strategy as defined by Linqiang Pan and collaborators and we are able to improve their result of universality of such systems using two types of spikes. In the current work, we prove that only one type of spikes is sufficient for reaching the computational power of Turing Machines for these devices, bringing closer to implementation such a device. The result holds both in maximum parallel manner application of the rules as well as the maximum-sequentiality application of rules.

Abstract

Since its introduction in the early 2000s, DNA origami had a big impact on the development of nanotechnology by gathering numerous applications. During this time, many tools were designed and used to generate arbitrary shapes capable of self-assembly which make this technique more approachable. In this paper, we have created the map of Romania at nanoscale dimensions by using a new open-source software - PERDIX. For this purpose, we used a scaffold strand with a length of 6959 nucleotides and 162 staple strands with a variable length ranging between 20 and 63 nucleotides. All the computational tools that were used in this experiment are open-source and user-friendly.

Abstract

We describe two new discrete symmetries of the inviscid Burgers (or Riemann–Hopf) equation ut+uux=0. We derived both of them using a local, formal approach of Hopf algebraic renormalization, a tool recently used in algorithmic computations. We prove that one of them is a Lie point transformation. Symmetries generate new exact solutions from the known solutions and provide useful frames of reference in the study of shock wave formation. © 2020 The Author(s)

Abstract

Abstract

We define a variant of accepting splicing system that can be used as a problem solver. A condition for halting the computation on a given input as well as a condition for making a decision as soon as the computation has stopped is considered. An algorithm based on this accepting splicing system that solves a well-known NP-complete problem, namely the 3-colorability problem is presented. We discuss an efficient solution in terms of running time and additional resources (axioms, supplementary symbols, number of splicing rules. More precisely, for a given graph with n vertices and m edges, our solution runs in O (nm) time, and needs O (mn(2)) other resources. Two variants of this algorithm of a reduced time complexity at an exponential increase of the other resources are finally discussed.

Abstract

An intriguing problem in computer science is the formal description of dynamics in cell populations. We propose here a multi-agent-based model that could be used in this respect. The model proposed in this paper consists of biological entities (cells) as agents and a biochemical environment. Both are represented by multisets of symbols. The environment evolution is regulated by multiset Lindenmayer rules depending on the current state of all agents, while the evolution of each agent, which depends on the environment current state, is defined by means of multiset patterns. We discuss some algorithmic problems related to the dynamics of the proposed multi-agent model: infinite and stationary evolution, environment, and agent reachability.

Abstract

We continue the investigation of three operations on words and languages with motivations coming from DNA biochemistry, namely unbounded and bounded hairpin completion and hairpin lengthening. We first show that each of these operations can be used for replacing the third step, the most laborious one, of the solution to the CNF-SAT reported in [28]. As not all the bounded/unbounded hairpin completion or lengthening of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying once either the bounded or unbounded hairpin completion, or lengthening. A similar approach is then started for the iterated variants of the three operations. A few open problems are finally discussed.

Abstract

We give examples of 2-parameter bounded quadratic dynamical systems with 3 finite singularities, which have at least 4 limit cycles around a singularity (in the (4,0)-configuration)-the first example of this type - and in a (3,1)-configuration. The paper mentions the Nanobiotechnological origins of these experimentally discovered systems with interesting properties.

Abstract

We give examples of 2-parameter bounded quadratic dynamical systems with 3 finite singularities, which have at least 4 limit cycles around a singularity (in the (4,0)-configuration) - the first example of this type - and in a (3,1)-configuration. The paper mentions the Nanobiotechnological origins of these experimentally discovered systems with interesting properties. © 2019 University of Kragujevac, Faculty of Science. All rights reserved.

Abstract

Numerical P systems (for short, NP systems) are distributed and parallel computing models inspired from the structure of living cells and economics. Enzymatic numerical P systems (for short, ENP systems) are a variant of NP systems, which have been successfully applied in designing and implementing controllers for mobile robots. Since ENP systems were proved to be Turing universal, there has been much work to simplify the universal systems, where the complexity parameters considered are the number of membranes, the degrees of polynomial production functions or the number of variables used in the systems. Yet the number of enzymatic variables, which is essential for ENP systems to reach universality, has not been investigated. Here we consider the problem of searching for the smallest number of enzymatic variables needed for universal ENP systems. We prove that for ENP systems as number acceptors working in the all-parallel or one-parallel mode, one enzymatic variable is sufficient to reach universality; while for the one-parallel ENP systems as number generators, two enzymatic variables are sufficient. to reach universality. These results improve the best known results that the numbers of enzymatic variables are 13 and 52 for the all-parallel and one-parallel systems, respectively.

Abstract

In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation.

Abstract

Abstract

Spiking neural P systems are a class of third generation neural networks belonging to the framework of membrane computing. Spiking neural P systems with communication on request (SNQ P systems) are a type of spiking neural P system where the spikes are requested from neighboring neurons. SNQ P systems have previously been proved to be universal (computationally equivalent to Turing machines) when two types of spikes are considered. This paper studies a simplified version of SNQ P systems, i.e. SNQ P systems with one type of spike. It is proved that one type of spike is enough to guarantee the Turing universality of SNQ P systems. Theoretical results are shown in the cases of the SNQ P system used in both generating and accepting modes. Furthermore, the influence of the number of unbounded neurons (the number of spikes in a neuron is not bounded) on the computation power of SNQ P systems with one type of spike is investigated. It is found that SNQ P systems functioning as number generating devices with one type of spike and four unbounded neurons are Turing universal.

Abstract

Abstract

Abstract

Abstract

This paper presents the latest trends and approaches used for constructing nanoscale structures of 2D objects through DNA folding based on the DNA origami technology developed by Rothemund. The Rothemund method has been used in the construction of various shapes, such as the development of the nanoscale structure for the United States map. Following the steps of Rothemund's technique, we simulate the construction of the Romanian map nanoscale 2D structure, embedding the number 100 into it.

Abstract

The TAM (Model Tile Assembly Model) is a mathematical paradigm for modeling DNA self-assembling according to various given shapes, using DNA-tiles (rectangular shape) with sticky ends on each of the four edges that bound together on various shapes desired by the researcher. Although there are various models in the literature, the focus in this manuscript is on a rule based model, specifically the authors present an overview of the one-dimensional hierarchical self-assembly model of DNA tiles. The authors also present the evolution of number of tiles in partial assemblies, the average assembly size and of the number of partial assemblies of sizes 2 through 10 over the total running time. All simulations were run using the NFSim simulator on a preset period of time.

Abstract

Abstract

this paper we present an improvement of the Segment Based Contours (SBC) method by implementing a higher order of finite difference schemes in the partial differential equation used in our mathematical model. Two methods are presented: one is a 4th order method and the other a 8th order method. The 4th order method could be applied to segment both the cDNA microarray images and the Affymetrix GeneChips, while the 8th order method could only be applied to processing the cDNA microarray images, due to the limitation of the current image resolution. Additionally, we provide both the mathematical derivations for the partial. differential equations (their 4th or 8th order approximations) as well as the validation trough simulations of the microarray images by using real images as seeds for the Nykter's 2006 methodology. We conclude by showing that both the 4th order method as well as the 8th order one are superior to the SBC and the widely used GOGAC method implemented in the Affymetrix standard processing package for microarrays. (C) 2017 Elsevier B.V. All rights reserved.

Abstract

In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. We prove that NPSP of size 4 can accept all languages in NP in polynomial time. All these results can be obtained with NPSPs with valuations in the set {-1, 0, 1} as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of these simulations.

Abstract

We refine the modeling in the P systems area of the way bacteria transmit genetic information in bacterial colonies, specifically the conjugation process. We study this new model from the computational power perspective using methods and ideas in the area; we are able to prove the universality of these systems. We show that systems working in a homogeneous manner and using only 75 species of objects in the regions and 13 species of on-membrane objects are enough for reaching universality. The system starts in a initial state with only few (nine) bacteria needed and the bacteria from this system are homogeneous, all have the same rules.

Abstract

We extend to spiking neural P systems a notion investigated in the standard membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by marking it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language. In all proofs we try to keep the size of used systems (number of neurons, of rules in each neuron, of spikes consumed or removed by rules) as small as possible. (C) 2016 Elsevier B.V. All rights reserved.

Abstract

Spiking neural P systems with rules on synapses (RSSN P systems, for short) are a class of distributed and parallel computation models inspired by the way in which neurons process and communicate information with each other by means of spikes, where neurons only contain spikes and the evolution rules are on synapses. RSSN P systems have been proved to be Turing universal, using the strategy that restricts all the applied rules to consume the same number of spikes from the given neuron, termed as equal spikes consumption strategy. In this work, in order to avoid imposing the equal spikes consumption restriction on the application of rules, a new strategy for rule application, termed as sum spikes consumption strategy, is considered in RSSN P systems, where a maximal set of enabled rules from synapses starting from the same neuron is nondeterministically chosen to be applied, in the sense that no further synapse can use any of its rules, and the sum of these numbers of spikes that all the applied rules consume is removed from the neuron. In this way, the proposed strategy avoids checking whether all the applied rules consume the same number of spikes from the given neuron. The computation power of RSSN P systems working in the proposed strategy is investigated, and it is proved that such systems characterize the semilinear sets of natural numbers, i.e., such systems are not universal. Furthermore, RSSN P systems with weighted synapses working in the proposed strategy are proved to be Turing universal. These results show that the weight on synapses is a powerful ingredient of RSSN P systems in terms of the computation power, which makes RSSN P systems working in sum spikes consumption strategy become universal from non-universality.

Abstract

This paper conducts an examination of log files originating from High Performance Computing (HPC) applications with known reliability problems. The results of this study further the maturation and adoption of meaningful metrics representing HPC system and application failure characteristics. Quantifiable metrics representing the reliability of HPC applications are foundational for building an application resilience methodology critical in the realization of exascale supercomputing. In this examination, statistical inequality methods originating from the study of economics are applied to health and status information contained in HPC application log files. The main result is the derivation of a new failure index metric for HPC a normalized representation of parallel application volatility and/or resiliency to complement existing reliability metrics such as mean time between failure (MTBF), which aims for a better presentation of HPC application resilience. This paper provides an introduction to a Failure Index (FI) for HPC reliability and takes the reader through a use-case wherein the H is used to expose various run-time fluctuations in the failure rate of applications running on a collection of HPC platforms. (C) 2016 Elsevier Inc. All rights reserved.

Abstract

Sustainable river basin management depends on knowledge, skills and education. The DANCERS project set out to identify feasible options for achieving education for sustainable water management across the Danube river basin, and its integration with broader education and economic development. The study traced the historic, regulatory and educational landscape of water management in the basin, contrasting it with the complex political decision-making, data-heavy decision support, learning-centred collaboration, and information-based participation that are all inherent components of Integrated Water Resource Management (IWRM). While there is a wide range of educational opportunities and mobility schemes available to individuals, there is no coherent network related to training in water management and sustainable development in the study region. Progress in addressing the multi-layered environmental challenges within the basin requires further aligning of economic, environmental and educational policies, advancing the EU Bologna Process across the region, and the development of dedicated training programmes that combine technical and relational skills. The DANCERS project identified key short and medium term needs for education and research to support progressive adoption of sustainable development, and the necessary dialogue across the public and private sectors to align policies. These include the development of new education networks for masters and PhD programmes, including joint programmes; improved access to technical training and life-long learning programmes for skills development; developing formalized and certified competency structures and associated accreditation of institutions where such skilled individuals work; and developing a co-ordinated research infrastructure and pan-basin programme for research for water management and sustainable development 2015 Elsevier B.V. All rights reserved.

Abstract

In this work we describe a new segmentation technique for the Affymetrix microarray images. We prove that our method can offer better predictions on the gene levels as opposed to the standard Affymetrix segmentation implemented in the Affymetrix GeneChip Operating Software (GCOS). To check the accuracy and show the benefits of the new segmentation method we use a previously implemented methodology to simulate microarray images with realistic features. Using such an artificial image provides us with the actual levels for each spot and each gene investigated in the microarray. Using this information we then proceed to segment the same image twice (with GCOS and our new method). The two segmentations will produce two sets of gene levels that are then compared to the known gene levels (known since the moment of generating the artificial image). Using this methodology we are able to show statistically (using 50 replicates of the same steps of generating the image, segmenting, comparing the results) that in some cases our new method greatly outperforms the GCOS implemented segmentation method, while in the rest of the cases performs in similar fashion. (C) 2015 Elsevier B.V. All rights reserved.

Abstract

Abstract

Abstract

Abstract

Abstract

Abstract

The ideas expressed in this work pertain to biochemical modeling. We explore our technique, the Nondeterministic Waiting Time algorithm, for modeling molecular signaling cascades. The algorithm is presented with pseudocode along with an explanation of its implementation. We discuss several important extensions including: (i) a heap with special maintenance functions for sorting reaction waiting times, (ii) a nondeterminstic component for handling reaction competition, and (iii) a memory enhancement allowing slower reactions to compete with faster reactions. Several example systems are provided for comparisons between modeling with systems of ordinary differential equations, the Gillespie Algorithm, and our Nondeterministic Waiting Time Algorithm. Our algorithm has a unique ability to exhibit behavior similar to the solutions to systems of ordinary differential equations for certain models and parameter choices, but it also has the nondeterministic component which yields results similar stochastic methods (e.g., the Gillespie Algorithm). There are several extensions for the current work discussed at the end of the chapter.

Abstract

The paper studies algorithmic properties of operations with membrane proteins modeled within the framework of membrane systems (also called P systems). Membrane systems are biologically inspired models of parallel and distributed computing based on the information processing in cells and cellular membranes. We show that the computational potential of P systems with proteins on membranes is equivalent to that of parallel computing models as the alternating Turing machine or the PRAM. These abstract machines characterize by their polynomial time-bounded computations the class PSPACE, and simultaneously they serve as idealized models of real parallel machines. Therefore, this and other related results suggest the existence of a homology between the potential of silicon and biological parallel information processing. (C) 2013 Elsevier B.V. All rights reserved.

Abstract

Abstract

In this paper we consider sequential SNP systems where the sequentiality of the system is induced by the max-spike: the neuron with the maximum number of spikes out of the neurons that can spike at one step will fire. This corresponds to a global view of the whole network that makes the system sequential. We continue the study in the direction of max-spike and show that systems with 132 neurons are universal. This improves a recent result in the area. © 2012 Springer-Verlag.

Abstract

A systematic use of the Monte Carlo method appeared since the early days of electronic computing and since then it is more present in different scientific research fields. Therefore, many techniques were developed based on this method and one of them is called sequential importance sampling. This technique is an adaptation of the Monte Carlo method that can be used to better extract samples form the domain using an importance weight function.

Abstract

We provide the description for the nondeterministic waiting time (NWT) algorithm, a biochemical modeling approach based on the membrane systems paradigm of computation. The technique provides a unique (different to Gillespie's algorithm or ODE modeling) perspective on the biochemical evolution of the cell. That is, depending on the reactions and molecular multiplicities of a given model, our simulator is capable of producing results comparable to the alternative techniques-continuous and deterministic or discrete and stochastic. Some results for sample models are given, illustrating the differences between the NWT algorithm, the Gillespie algorithm, and the solutions to systems of ordinary differential equations. We have previously used this simulation technique to address issues surrounding Fas-induced apoptosis in cancerous cells and so-called latent HIV-infected cells.

Abstract

The paper is a survey of the recent model of P systems with proteins on membranes introduced by Paun and Popa in 2006. This model can be viewed as an extension of the highly successful paper of (Paun and Paun 2002) describing P systems based on symport/antiport. The previous model represented an important change of direction from strings to objects in the area of P systems. The main drawback of the model from 2002 was the massive parallelism that is not seen in real life. The 2006 model was a step in controlling the parallelism the same way it is done in nature in symporters and antiporters: these processes take place through protein channels embedded at the level of the membrane which can only be used by a molecule at a time, thus yielding a sequentiality with respect to the number of such proteins embedded in the membrane.

Abstract

P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins. © 2010 Springer-Verlag.

Abstract

We present the Nondeterministic Waiting Time algorithm. Our technique for the simulation of biochemical reaction networks has the ability to mimic the Gillespie Algorithm for some networks and solutions to ordinary differential equations for other networks, depending on the rules of the system, the kinetic rates and numbers of molecules. We provide a full description of the algorithm as well as specifics on its implementation. Some results for two well-knownmodels are reported. We have used the algorithm to explore Fas-mediated apoptosis models in cancerous and HIV-1 infected T cells.

Abstract

We show that the absolute worst case time complexity for Hopcroft's minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires O(n log n) steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft's method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu. Published by Elsevier B.V.

Abstract

We consider the properties of spiking neural P (SNP) systems that work in a sequential manner. These SNP systems are a class of computing devices recently introduced as a bridge between spiking neural nets and membrane computing. The general sequentiality of these systems was considered previously; now we focus on the sequentiality, induced by the spike number: at each step, the neuron with the maximum (or minimum) number of spikes among the neurons that are active (can spike) will fire. This strategy corresponds to a global view of the whole network that makes the system sequential. We study the properties of this type of a restriction (i.e. considering the case of sequentiality induced by the function maximum defined on numbers of spikes as well as the case of the sequentiality induced by the function minimum similarly defined on numbers of spikes). Several universality results are obtained for the cases of maximum and minimum induced sequentiality. (C) 2009 Elsevier B.V. All rights reserved.

Abstract

We consider the absolute worst case time complexity for Hopcroft's minimization algorithm applied to unary languages (or a modification of this algorithm for cover automata minimization). We show that in this setting the worst case is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. We refine a previous result by showing that the Berstel/Carton example reported before is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also when considering the setting of cover automata and an algorithm based on the Hopcroft's method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list is desirable for the case of unary languages in the setting of deterministic finite automata.

Abstract

Computer modeling of molecular signalling cascades can provide useful insight into the underlying complexities of biological systems. We present a refined approach for the discrete modeling of protein interaction within the environment of a single cell. The technique we offer utilizes the Membrane Systems paradigm which, due to its hierarchical structure, lends itself readily to mimic the behavior of cells. Since our approach terministic ordinary differential equations techniques. We argue that our approach may outperform ordinary differential equations when modeling systems with relatively low numbers of molecules - a frequent occurrence in cellular signaling cascades. Refinements over our previous modeling efforts include the addition of nondeterminism for handling reaction competition over limited reactants, increased efficiency in the storing and storing of reaction waiting times, and modifications of the model reactions. Results of our discrete simulation of the type I and type II Fas-mediated apoptotic signaling cascade are illustrated and compared with two approaches: one based on ordinary differential equations and another based on the well-known Gillespie algorithm.

Abstract

Membrane computing is a branch of natural computing which abstracts computing models from the structure and the functioning of the living cell. The main ingredients of membrane systems, called P systems, are (i) the membrane structure, which consists of a hierarchical arrangements of membranes which delimit compartments where (ii) multisets of symbols, called objects, evolve according to (iii) sets of rules which are localised and associated with compartments. By using the rules in a nondeterministic/deterministic maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from one membrane to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. Membrane systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology gives way to a practical bio-realization. In this paper we survey some interesting and fundamental complexity issues such as universality vs. nonuniversality, determinism vs. nondeterminism, membrane and alphabet size hierarchies, characterizations of context-sensitive languages and other language classes and various notions of parallelism.

Abstract

We consider once again the membrane systems with proteins on membranes. This model is bridging the membrane systems and brane calculi areas together, thus it is interesting to study it in more depth. We improve previous results in the area and also define a new variant of these systems based on time as the output of the computation. The new model allows (due to its flexibility) even stronger improvements with respect to the number of proteins needed to perform the computation.