Search

Boolean networks are a well-established formalism for modelling biological systems. An important aspect of analysing a Boolean network is to identify all its attractors. This becomes challenging for large Boolean networks due to the infamous state-space explosion problem. In this paper, we propose a new strongly connected component (SCC) based decomposition method for attractor detection in large synchronous Boolean networks and prove its correctness. Experimental results show that our proposed method is significantly better in terms of performance when compared to existing methods in the literature.

As a well-established computational framework, probabilistic Boolean networks (PBNs) are widely used for modelling, simulation, and analysis of biological systems. To analyze the steady-state dynamics of PBNs is of crucial importance to explore the characteristics of biological systems. However, the analysis of large PBNs, which often arise in systems biology, is prone to the infamous state-space explosion problem. Therefore, the employment of statistical methods often remains the only feasible solution. We present ${\mathsf{ASSA-PBN}}$ , a software toolbox for modelling, simulation, and analysis of PBNs. ${\mathsf{ASSA-PBN}}$ provides efficient statistical methods with three parallel techniques to speed up the computation of steady-state probabilities. Moreover, particle swarm optimisation (PSO) and differential evolution (DE) are implemented for the estimation of PBN parameters. Additionally, we implement in-depth analyses of PBNs, including long-run influence analysis, long-run sensitivity analysis, computation of one-parameter profile likelihoods, and the visualization of one-parameter profile likelihoods. A PBN model of apoptosis is used as a case study to illustrate the main functionalities of ${\mathsf{ASSA-PBN}}$ and to demonstrate the capabilities of ${\mathsf{ASSA-PBN}}$ to effectively analyse biological systems modelled as PBNs.

Quantitative models may exhibit sophisticated behaviour that includes having multiple steady states, bistability, limit cycles, and period-doubling bifurcation. Such behaviour is typically driven by the numerical dynamics of the model, where the values of various numerical parameters play the crucial role. We introduce in this paper natural correspondents of these concepts to reaction systems modelling, a framework based on elementary set theoretical, forbidding/enforcing-based mechanisms. We construct several reaction systems models exhibiting these properties.

Computation of steady-state probabilities is an important aspect of analysing biological systems modelled as probabilistic Boolean networks (PBNs). For small PBNs, efficient numerical methods to compute steady-state probabilities of PBNs exist, based on the Markov chain state-transition matrix. However, for large PBNs, numerical methods suffer from the state-space explosion problem since the state-space size is exponential in the number of nodes in a PBN. In fact, the use of statistical methods and Monte Carlo methods remain the only feasible approach to address the problem for large PBNs. Such methods usually rely on long simulations of a PBN. Since slow simulation can impede the analysis, the efficiency of the simulation procedure becomes critical. Intuitively, parallelising the simulation process is the ideal way to accelerate the computation. Recent developments of general purpose graphics processing units (GPUs) provide possibilities to massively parallelise the simulation process. In this work, we propose a trajectory-level parallelisation framework to accelerate the computation of steady-state probabilities in large PBNs with the use of GPUs. To maximise the computation efficiency on a GPU, we develop a dynamical data arrangement mechanism for handling different size PBNs with a GPU. Specially, we propose a reorder-and-split method to handle both large and dense PBNs. Besides, we develop a specific way of storing predictor functions of a PBN and the state of the PBN in the GPU memory. Moreover, we introduce a strongly connected component (SCC)-based network reduction technique to further accelerate the computation speed. Experimental results show that our GPU-based parallelisation gains approximately a 600-fold speedup for a real-life PBN compared to the state-of-the-art sequential method.

Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.

Probabilistic Boolean networks (PBNs) is a well-established computational framework for modelling biological systems. The steady-state dynamics of PBNs is of crucial importance in the study of such systems. However, for large PBNs, which often arise in systems biology, obtaining the steady-state distribution poses a significant challenge. In this paper, we revive the two-state Markov chain approach to solve this problem. This paper contributes in three aspects. First, we identify a problem of generating biased results with the approach and we propose a few heuristics to avoid such a pitfall. Secondly, we conduct an extensive experimental comparison of the extended two-state Markov chain approach and another approach based on the Skart method. We analyse the results with machine learning techniques and we show that statistically the two-state Markov chain approach has a better performance. Finally, we demonstrate the potential of the extended two-state Markov chain approach on a case study of a large PBN model of apoptosis in hepatocytes.

Boolean networks is a well-established formalism for modelling biological systems. An important challenge for analysing a Boolean network is to identify all its attractors. This becomes challenging for large Boolean networks due to the well-known state-space explosion problem. In this paper, we propose a new SCC-based decomposition method for attractor detection in large synchronous Boolean networks. Experimental results show that our proposed method is significantly better in terms of performance when compared to existing methods in the literature.

Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An~important challenge in Boolean networks is to exhaustively find attractors, which represent steady states of a~biological network. In this paper, we propose a~new approach to improve the efficiency of BDD-based attractor detection. Our approach includes a~monolithic algorithm for small networks, an~enumerative strategy to deal with large networks, a~method to accelerate attractor detection based on an~analysis of the network structure, and two heuristics on ordering BDD variables. We demonstrate the performance of our approach on a~number of examples and on a~realistic model of apoptosis in hepatocytes. We compare it with one existing technique in the literature.

Probabilistic Boolean networks (PBNs) is a widely used computational framework for modelling biological systems. The steady-state dynamics of PBNs is of special interest in the analysis of biological machinery. However, obtaining the steady-state distributions for such systems poses a significant challenge due to the state space explosion problem which arises in the case of large PBNs. The only viable way is to use statistical methods. In the literature, the two-state Markov chain approach and the Skart method have been proposed for the analysis of large PBNs. However, the sample size required by both methods is often huge in the case of large PBNs and generating them is expensive in terms of computation time. Parallelising the sample generation is an ideal way to solve this issue. In this paper, we consider combining the Gelman & Rubin method with either the two-state Markov chain approach or the Skart method for parallelisation. The first method can be used to run multiple independent Markov chains in parallel and to control their convergence to the steady-state while the other two methods can be used to determine the sample size required for computing the steady-state probability of states of interest. Experimental results show that our proposed combinations can reduce time cost of computing stead-state probabilities of large PBNs significantly.

Proteus spp. strains are some of the most important pathogens associated with complicated urinary tract infections and bacteremia affecting patients with immunodeficiency and long-term urinary catheterization. For epidemiological purposes, various molecular typing methods have been developed for this pathogen. However, these methods are labor intensive and time consuming. We evaluated a new method of differentiation between strains. A collection of Proteus spp. strains was analyzed by attenuated total reflectance Fourier transform infrared (ATR FT-IR) spectroscopy in the mid-infrared region. ATR FT-IR spectroscopy used in conjunction with a diamond ATR accessory directly produced the biochemical profile of the surface chemistry of bacteria. We conclude that a combination of ATR FT-IR spectroscopy and mathematical modeling provides a fast and reliable alternative for discrimination between Proteus isolates, contributing to epidemiological research.

Computation of steady-state probabilities is an important aspect of analysing biological systems modelled as probabilistic Boolean networks (PBNs). For small PBNs, efficient numerical methods can be successfully applied to perform the computation with the use of Markov chain state transition matrix underlying the studied networks. However, for large PBNs, numerical methods suffer from the state-space explosion problem since the state-space size is exponential in the number of nodes in a PBN. In fact, the use of statistical methods and Monte Carlo methods remain the only feasible approach to address the problem for large PBNs. Such methods usually rely on long simulations of a PBN. Since slow simulation can impede the analysis, the efficiency of the simulation procedure becomes critical. Intuitively, parallelising the simulation process can be an ideal way to accelerate the computation. Recent developments of general purpose graphics processing units (GPUs) provide possibilities to massively parallelise the simulation process. In this work, we propose a trajectory-level parallelisation framework to accelerate the computation of steady-state probabilities in large PBNs with the use of GPUs. To maximise the computation efficiency on a GPU, we develop a dynamical data arrangement mechanism for handling different size PBNs with a GPU, and a specific way of storing predictor functions of a PBN and the state of the PBN in the GPU memory. Experimental results show that our GPU-based parallelisation gains a speedup of approximately 400 times for a real-life PBN.

As an important mathematical modelling framework, probabilistic Boolean networks (PBNs) are widely used for modelling and analysing biological systems. PBNs are suited for modelling large biological systems, which more and more often arise in systems biology. However, the large system size poses a significant challenge to the analysis of PBNs, in particular, to the crucial analysis of their steady-state behaviour. Numerical methods for performing steady-state analyses suffer from the state-space explosion problem, which makes the utilisation of statistical methods the only viable approach. However, such methods require long simulations of PBNs, rendering the simulation speed a crucial efficiency factor. For large PBNs and high estimation precision requirements, a slow simulation speed becomes an obstacle. In this paper, we propose a structure-based method for fast simulation of PBNs. This method first performs a network reduction operation and then divides nodes into groups for parallel simulation. Experimental results show that our method can lead to an approximately 10 times speedup for computing steady-state probabilities of a real-life biological network.

In vitro assembly of intermediate filaments from tetrameric vimentin consists of a very rapid phase of tetramers laterally associating into unit-length filaments and a slow phase of filament elongation. We focus in this paper on a systematic quantitative investigation of two molecular models for filament assembly, recently proposed in (Kirmse et al. J. Biol. Chem. 282, 52 (2007), 18563-18572), through mathematical modeling, model fitting, and model validation. We analyze the quantitative contribution of each filament elongation strategy: with tetramers, with unit-length filaments, with longer filaments, or combinations thereof. In each case, we discuss the numerical fitting of the model with respect to one set of data, and its separate validation with respect to a second, different set of data. We introduce a high-resolution model for vimentin filament self-assembly, able to capture the detailed dynamics of filaments of arbitrary length. This provides much more predictive power for the model, in comparison to previous models where only the mean length of all filaments in the solution could be analyzed. We show how kinetic observations on low-resolution models can be extrapolated to the high-resolution model and used for lowering its complexity.

To disentangle the numerical contribution of modules to the system-level behavior of a given biomodel, one often considers knock-out mutant models, investigating the change in the model behavior when modules are systematically included and excluded from the model architecture in all possible ways. We propose in this paper a Boolean approach for extracting conclusions about the role of each module from the systematic comparison of the numerical behavior of all knock-out mutants. We associate a Boolean variable to each module, expressing when the module is included in the architecture and when it is not. We can then express the satisfiability of system-level properties of the full model, such as efficiency, or economical use of resources, in terms of a Boolean formula expressing in a compact way which model architectures, i.e., which combinations of modules, give rise to the desired property. We demonstrate this method on a recently proposed computational model for the heat shock response in eukaryotes. We describe the contribution of each of its three feedback loops towards achieving an economical and effective heat shock response.

In this presentation we consider hyperthermia, a procedure of raising the temperature above 43 °C, as a treatment modality. To this purpose, a numerical model of in vivo soft tissue ultrasound heating is proposed by extending a previously presented in vitro model. Based on the numerical simulations, a heating scheme satisfying some constraints related to potential clinical applications is established, and the resulting temperature time-course profile is composed with the temperature-dependent protein denaturation formula of a recently published mathematical model for the eukaryotic heat shock response. The obtained simulation results of the combined models are discussed in view of potential application of ultrasound soft tissue heating in clinical treatment.

Comparing alternative models for a given biochemical system is in general a very difficult problem: the models may focus on different aspects of the same system and may consist of very different species and reactions. The numerical setups of the models also play a crucial role in the quantitative comparison. When the alternative designs are submodels of a reference model, for example, knockdown mutants of a model, the problem of comparing them becomes simpler: they all have very similar, although not identical, underlying reaction networks, and the biological constraints are given by those in the reference model. In the first part of our study, we review several known methods for model decomposition and for quantitative comparison of submodels. We describe knockdown mutants, elementary flux modes, control-based decomposition, mathematically controlled comparison and its extension, local submodel comparison and a discrete approach for comparing continuous submodels. In the second part of the paper we present a new statistical method for comparing submodels, which complements the methods presented in the review. The main difference between our approach and the known methods is related to the important question of how to chose the numerical setup in which to perform the comparison. In the case of the reviewed methods, the comparison is made in the numerical context of the reference model, i.e., in each of the alternative models both the kinetics of the reactions and the initial values of all variables are chosen to be identical to those from the reference model. We propose in this paper a different approach, better suited for response networks, where each alternative model is assumed to start from its own steady state under basal conditions. We demonstrate our approach with a case study focusing on the heat shock response in eukaryotes.

The heat shock response is a primordial defense mechanism against cell stress and protein misfolding. It proceeds with the minimum number of mechanisms that any regulatory network must include, a stress-induced activation and a feedback regulation, and can thus be regarded as the archetype for a cellular regulatory process. We propose here a simple mechanistic model for the eukaryotic heat shock response, including its mathematical validation. Based on numerical predictions of the model and on its sensitivity analysis, we minimize the model by identifying the reactions with marginal contribution to the heat shock response. As the heat shock response is a very basic and conserved regulatory network, our analysis of the network provides a useful foundation for modeling strategies of more complex cellular processes.

We present ASSA-PBN, a tool for approximate steady-state analysis of large probabilistic Boolean networks (PBNs). ASSA-PBN contains a constructor, a simulator, and an analyser which can approximately compute the steady-state probabilities of PBNs. For large PBNs, such approximate analysis is the only viable way to study their long-run behaviours. Experiments show that ASSA-PBN can handle large PBNs with a few thousands of nodes.

The exposure of location information in location-based services (LBS) raises users' privacy concerns. Recent research reveals that in LBSs users concern more about the activities that they have performed than the places that they have visited. In this paper, we propose a new attack with which the adversary can accurately infer users' activities. Compared to existing attacks, our attack provides the adversary not only with the places where users perform activities but also with the information when they stay at each of these places. To achieve this objective, we propose a new model to capture users' mobility and their LBS requests in continuous time, which naturally expresses users' behaviour in LBSs.We then formally implement our attack by extending an existing framework for quantifying location privacy. Through experiments on a real-life dataset, we show the effectiveness of our new tracking attack.

The expression of genes is a fundamental process in living cells, both eukaryotic and prokaryotic. The regulation of gene expression is achieved via sophisticated networks of interactions between DNA, RNA, proteins, and small chemical compounds. The qualitative and quantitative characterisation of interactions between genes is one of the major current research targets in systems biology. In this PhD research project, we view gene regulatory networks as Markov chains, resulting from popular formalisation frameworks such as Dynamic Bayesian Networks and Probabilistic Boolean Networks. This will allow us to reason about both the structure and strength of gene interactions. Our goal is to develop new algorithms and tools, which are tailored for the modelling and analysis of gene regulatory networks, by exploring model checking techniques that have been developed and widely used in computer science. More specifically, we will combine model checking techniques with sampling and optimisation methods from the literature to derive new techniques to solve the parameter estimation problem of Markov models of gene regulatory networks.

BackgroundThere exist several computational tools which allow for the optimisation and inference of biological networks using a Boolean formalism. Nevertheless, the results from such tools yield only limited quantitative insights into the complexity of biological systems because of the inherited qualitative nature of Boolean networks.ResultsWe introduce optPBN, a Matlab-based toolbox for the optimisation of probabilistic Boolean networks (PBN) which operates under the framework of the BN/PBN toolbox. optPBN offers an easy generation of probabilistic Boolean networks from rule-based Boolean model specification and it allows for flexible measurement data integration from multiple experiments. Subsequently, optPBN generates integrated optimisation problems which can be solved by various optimisers. In term of functionalities, optPBN allows for the construction of a probabilistic Boolean network from a given set of potential constitutive Boolean networks by optimising the selection probabilities for these networks so that the resulting PBN fits experimental data. Furthermore, the optPBN pipeline can also be operated on large-scale computational platforms to solve complex optimisation problems. Apart from exemplary case studies which we correctly inferred the original network, we also successfully applied optPBN to study a large-scale Boolean model of apoptosis where it allows identifying the inverse correlation between UVB irradiation, NFκB and Caspase 3 activations, and apoptosis in primary hepatocytes quantitatively. Also, the results from optPBN help elucidating the relevancy of crosstalk interactions in the apoptotic network.SummaryThe optPBN toolbox provides a simple yet comprehensive pipeline for integrated optimisation problem generation in the PBN formalism that can readily be solved by various optimisers on local or grid-based computational platforms. optPBN can be further applied to various biological studies such as the inference of gene regulatory networks or the identification of the interaction's relevancy in signal transduction networks.

Probabilistic Boolean network (PBN) modelling is a semi-quantitative approach widely used for the study of the topology and dynamic aspects of biological systems. The combined use of rule-based representation and probability makes PBN appealing for large-scale modelling of biological networks where degrees of uncertainty need to be considered. A considerable expansion of our knowledge in the field of theoretical research on PBN can be observed over the past few years, with a focus on network inference, network intervention and control. With respect to areas of applications, PBN is mainly used for the study of gene regulatory networks though with an increasing emergence in signal transduction, metabolic, and also physiological networks. At the same time, a number of computational tools, facilitating the modelling and analysis of PBNs, are continuously developed. A concise yet comprehensive review of the state-of-the-art on PBN modelling is offered in this article, including a comparative discussion on PBN versus similar models with respect to concepts and biomedical applications. Due to their many advantages, we consider PBN to stand as a suitable modelling framework for the description and analysis of complex biological systems, ranging from molecular to physiological levels.

Comparing alternative models for a given biochemical system is in general a very difficult problem: the models may focus on different aspects of the same system and may consist of very different species and reactions. The numerical setups of the models also play a crucial role in the quantitative comparison. When the alternative designs are submodels of a reference model, e.g. knockdown mutants of a model, the problem of comparing them becomes simpler: they all have very similar, although not identical, underlying reaction networks, and the biological constraints are given by the ones in the reference model. In the first part of our study we review several known methods for model decomposition and for quantitative comparison of submodels. In the second part of the paper, we consider as a case study the eukaryotic heat shock response, an evolutionary well conserved defence mechanism against the accumulation of

Model refinement is an important aspect of the model-building process. It can be described as a procedure which, starting from an abstract model of a system, performs a number of refinement steps in result of which a more detailed model is obtained. At the same time, in order to be correct, the refinement mechanism has to be capable of preserving already proven systemic quantitative properties of the original model, e.g. model fit, stochastic semantics, etc. In this study we concentrate on the refinement in the case of self-assembly models. Self-assembly is a process in which a disordered ensemble of basic components forms an organized structure as a result of specific, local interactions among these components, without external guidance. We develop a generic formal model for this process and introduce a notion of model resolution capturing the maximum size up to which objects can be distinguished individually in the model. All bigger objects are treated homogenously in the model. We show how this self-assembly model can be systematically refined in such a way that its resolution can be increased and decreased while preserving the original model fit to experimental data, without the need for tedious, computationally expensive process of parameter refitting. We demonstrate how the introduced methodology can be applied to a previously published model: we consider the case-study of in vitro self-assembly of intermediate filaments.

International audience; The heat shock response (HSR) is a highly evolutionarily conserved defence mechanism allowing the cell to promptly react to elevated temperature conditions and other forms of stress. It has been subject to intense research for at least two main reasons. First, it is considered a promising candidate for deciphering the engineering principles underlying regulatory networks. Second, heat shock proteins (main actors of the HSR) play crucial role in many fundamental cellular processes. Therefore, profound understanding of the heat shock response would have far-reaching ramifications for the cell biology. Recently, a new deterministic model of the eukaryotic heat shock response has been proposed in the literature. It is very attractive since it consists of only the minimum number of components required by any functional regulatory network, while yet being capable of biological validation. However, it admits small molecule populations of some of the considered metabolites. In this paper a stochastic model corresponding to the deterministic one is constructed and the outcomes of these two models are confronted. The aim with this comparison is two show that, in the case of the heat shock response, the approximation of a discrete system with a continuous model is a reasonable approach. This is not always the truth, especially when the numbers of molecules of the considered species are small. By making the effort of performing and analysing 1000 stochastic simulations, we investigate the range of behaviour the stochastic model is likely to exhibit. We demonstrate that the obtained results agree well with the dynamics displayed by the continuous model, which strengthens the trust in the deterministic description. A proof of the existence and uniqueness of the stationary distribution of the Markov chain underlying the stochastic model is given. Moreover, the obtained view of the stochastic dynamics and the performed comparison to the outcome of the continuous formulation provide more insight into the dynamics of the heat shock response mechanism.

We present in this paper a novel molecular model for the gene regulatory network responsible for the eukaryotic heat shock response. Our model includes the temperature-induced protein misfolding, the chaperone activity of the heat shock proteins, and the backregulation of their gene transcription. We then build a mathematical model for it, based on ordinary differential equations. Finally, we discuss the parameter fit and the implications of the sensitivity analysis for our model.

Background A central goal of molecular biology is to understand the regulatory mechanisms of gene transcription and protein synthesis. Because of their solid basis in statistics, allowing to deal with the stochastic aspects of gene expressions and noisy measurements in a natural way, Bayesian networks appear attractive in the field of inferring gene interactions structure from microarray experiments data. However, the basic formalism has some disadvantages, e.g. it is sometimes hard to distinguish between the origin and the target of an interaction. Two kinds of microarray experiments yield data particularly rich in information regarding the direction of interactions: time series and perturbation experiments. In order to correctly handle them, the basic formalism must be modified. For example, dynamic Bayesian networks (DBN) apply to time series microarray data. To our knowledge the DBN technique has not been applied in the context of perturbation experiments. Results We extend the framework of dynamic Bayesian networks in order to incorporate perturbations. Moreover, an exact algorithm for inferring an optimal network is proposed and a discretization method specialized for time series data from perturbation experiments is introduced. We apply our procedure to realistic simulations data. The results are compared with those obtained by standard DBN learning techniques. Moreover, the advantages of using exact learning algorithm instead of heuristic methods are analyzed. Conclusion We show that the quality of inferred networks dramatically improves when using data from perturbation experiments. We also conclude that the exact algorithm should be used when it is possible, i.e. when considered set of genes is small enough.