Efficient parameter search for qualitative models of regulatory networks using symbolic model checking

Optimal Robust Search for Parameter Values of Qualitative Models of Gene Regulatory Networks

Computational and mathematical models are a must for the in silico analysis or design of Gene Regulatory Networks (GRN)as they offer a theoretical context to deeply address biological regulation. We have proposed a framework where models of network dynamics are expressed through a class of nonlinear and temporal multiscale Ordinary Differential Equations (ODE). To find out models that disclose network structures underlying an observed or desired network behavior, and parameter values that enable the candidate models to reproduce such behavior, we follow a reasoning cycle that alternates procedures for model selection and parameter refinement. Plausible network models are first selected via qualitative simulation, and next their parameters are given quantitative values such that the ODE model solution reproduces the specified behavior. This paper gives algorithms to tackle the parameter refinement problem formulated as an optimization problem. We search, within the parameter space symbolically expressed, for the largest hypersphere whose points correspond to parameter values such that the ODE solution gives an instance of the given qualitative trajectory. Our approach overcomes the limitation of a previously proposed stochastic approach, namely computational load and very reduced scalability. Its applicability and effectiveness are demonstrated through two benchmark synthetic networks with different complexity.

Qualitative Modeling, Analysis and Control of Synthetic Regulatory Circuits

Qualitative modeling approaches are promising and still underexploited tools for the analysis and design of synthetic circuits. They can make predictions of circuit behavior in the absence of precise, quantitative information. Moreover, they provide direct insight into the relation between the feedback structure and the dynamical properties of a network. We review qualitative modeling approaches by focusing on two specific formalisms, Boolean networks and piecewise-linear differential equations, and illustrate their application by means of three well-known synthetic circuits. We describe various methods for the analysis of state transition graphs, discrete representations of the network dynamics that are generated in both modeling frameworks. We also briefly present the problem of controlling synthetic circuits, an emerging topic that could profit from the capacity of qualitative modeling approaches to rapidly scan a space of design alternatives.

Symbolic Coloured SCC Decomposition

Problems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph’s strongly connected components, which is challenging at this scale.

We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(p\cdot n\cdot \log n)$$\end{document}O(p·n·logn) symbolic steps, where p is the number of colours and n the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{48}$$\end{document}248) coloured graphs produced by models appearing in systems biology.

Multi-parameter exploration of dynamics of regulatory networks

Over the last twenty years advances in systems biology have changed our views on microbial communities and promise to revolutionize treatment of human diseases. In almost all scientific breakthroughs since time of Newton, mathematical modeling has played a prominent role. Regulatory networks emerged as preferred descriptors of how abundances of molecular species depend on each other. However, the central question on how cellular phenotypes emerge from dynamics of these network remains elusive. The principal reason is that differential equation models in the field of biology (while so successful in areas of physics and physical chemistry), do not arise from first principles, and these models suffer from lack of proper parameterization. In response to these challenges, discrete time models based on Boolean networks have been developed. In this review, we discuss an emerging modeling paradigm that combines ideas from differential equations and Boolean models, and has been developed independently within dynamical systems and computer science communities. The result is an approach that can associate a range of potential dynamical behaviors to a network, arrange the descriptors of the dynamics in a searchable database, and allows for multi-parameter exploration of the dynamics akin to bifurcation theory. Since this approach is computationally accessible for moderately sized networks, it allows, perhaps for the first time, to rationally compare different network topologies based on their dynamics.

Bio-ModelChecker: Using Bounded Constraint Satisfaction to Seamlessly Integrate Observed Behavior With Prior Knowledge of Biological Networks

The in silico study and reverse engineering of regulatory networks has gained in recognition as an insightful tool for the qualitative study of biological mechanisms that underlie a broad range of complex illness. In the creation of reliable network models, the integration of prior mechanistic knowledge with experimentally observed behavior is hampered by the disparate nature and widespread sparsity of such measurements. The former challenges conventional regression-based parameter fitting while the latter leads to large sets of highly variable network models that are equally compliant with the data. In this paper, we propose a bounded Constraint Satisfaction (CS) based model checking framework for parameter set identification that readily accommodates partial records and the exponential complexity of this problem. We introduce specific criteria to describe the biological plausibility of competing multi-valued regulatory networks that satisfy all the constraints and formulate model identification as a multi-objective optimization problem. Optimization is directed at maximizing structural parsimony of the regulatory network by mitigating excessive control action selectivity while also favoring increased state transition efficiency and robustness of the network's dynamic response. The framework's scalability, computational time and validity is demonstrated on several well-established and well-studied biological networks.

Reconstructing cancer drug response networks using multitask learning

BACKGROUND

Translating in vitro results to clinical tests is a major challenge in systems biology. Here we present a new Multi-Task learning framework which integrates thousands of cell line expression experiments to reconstruct drug specific response networks in cancer.

RESULTS

The reconstructed networks correctly identify several shared key proteins and pathways while simultaneously highlighting many cell type specific proteins. We used top proteins from each drug network to predict survival for patients prescribed the drug.

CONCLUSIONS

Predictions based on proteins from the in-vitro derived networks significantly outperformed predictions based on known cancer genes indicating that Multi-Task learning can indeed identify accurate drug response networks.

Logical model specification aided by model-checking techniques: application to the mammalian cell cycle regulation

MOTIVATION

Understanding the temporal behaviour of biological regulatory networks requires the integration of molecular information into a formal model. However, the analysis of model dynamics faces a combinatorial explosion as the number of regulatory components and interactions increases.

RESULTS

We use model-checking techniques to verify sophisticated dynamical properties resulting from the model regulatory structure in the absence of kinetic assumption. We demonstrate the power of this approach by analysing a logical model of the molecular network controlling mammalian cell cycle. This approach enables a systematic analysis of model properties, the delineation of model limitations, and the assessment of various refinements and extensions based on recent experimental observations. The resulting logical model accounts for the main irreversible transitions between cell cycle phases, the sequential activation of cyclins, and the inhibitory role of Skp2, and further emphasizes the multifunctional role for the cell cycle inhibitor Rb.

AVAILABILITY AND IMPLEMENTATION

The original and revised mammalian cell cycle models are available in the model repository associated with the public modelling software GINsim (http://ginsim.org/node/189).

CONTACT

thieffry@ens.fr

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Automated parameter estimation for biological models using Bayesian statistical model checking

Background

Probabilistic models have gained widespread acceptance in the systems biology community as a useful way to represent complex biological systems. Such models are developed using existing knowledge of the structure and dynamics of the system, experimental observations, and inferences drawn from statistical analysis of empirical data. A key bottleneck in building such models is that some system variables cannot be measured experimentally. These variables are incorporated into the model as numerical parameters. Determining values of these parameters that justify existing experiments and provide reliable predictions when model simulations are performed is a key research problem.

Domain experts usually estimate the values of these parameters by fitting the model to experimental data. Model fitting is usually expressed as an optimization problem that requires minimizing a cost-function which measures some notion of distance between the model and the data. This optimization problem is often solved by combining local and global search methods that tend to perform well for the specific application domain. When some prior information about parameters is available, methods such as Bayesian inference are commonly used for parameter learning. Choosing the appropriate parameter search technique requires detailed domain knowledge and insight into the underlying system.

Results

Using an agent-based model of the dynamics of acute inflammation, we demonstrate a novel parameter estimation algorithm by discovering the amount and schedule of doses of bacterial lipopolysaccharide that guarantee a set of observed clinical outcomes with high probability. We synthesized values of twenty-eight unknown parameters such that the parameterized model instantiated with these parameter values satisfies four specifications describing the dynamic behavior of the model.

Conclusions

We have developed a new algorithmic technique for discovering parameters in complex stochastic models of biological systems given behavioral specifications written in a formal mathematical logic. Our algorithm uses Bayesian model checking, sequential hypothesis testing, and stochastic optimization to automatically synthesize parameters of probabilistic biological models.

De novo reconstruction of gene regulatory networks from time series data, an approach based on formal methods

Reverse engineering of gene regulatory relationships from genomics data is a crucial task to dissect the complex underlying regulatory mechanism occurring in a cell. From a computational point of view the reconstruction of gene regulatory networks is an undetermined problem as the large number of possible solutions is typically high in contrast to the number of available independent data points. Many possible solutions can fit the available data, explaining the data equally well, but only one of them can be the biologically true solution. Several strategies have been proposed in literature to reduce the search space and/or extend the amount of independent information. In this paper we propose a novel algorithm based on formal methods, mathematically rigorous techniques widely adopted in engineering to specify and verify complex software and hardware systems. Starting with a formal specification of gene regulatory hypotheses we are able to mathematically prove whether a time course experiment belongs or not to the formal specification, determining in fact whether a gene regulation exists or not. The method is able to detect both direction and sign (inhibition/activation) of regulations whereas most of literature methods are limited to undirected and/or unsigned relationships. We empirically evaluated the approach on experimental and synthetic datasets in terms of precision and recall. In most cases we observed high levels of accuracy outperforming the current state of art, despite the computational cost increases exponentially with the size of the network. We made available the tool implementing the algorithm at the following url: http://www.bioinformatics.unisannio.it.

An efficient method of exploring simulation models by assimilating literature and biological observational data

Recently, several biological simulation models of, e.g., gene regulatory networks and metabolic pathways, have been constructed based on existing knowledge of biomolecular reactions, e.g., DNA-protein and protein-protein interactions. However, since these do not always contain all necessary molecules and reactions, their simulation results can be inconsistent with observational data. Therefore, improvements in such simulation models are urgently required. A previously reported method created multiple candidate simulation models by partially modifying existing models. However, this approach was computationally costly and could not handle a large number of candidates that are required to find models whose simulation results are highly consistent with the data. In order to overcome the problem, we focused on the fact that the qualitative dynamics of simulation models are highly similar if they share a certain amount of regulatory structures. This indicates that better fitting candidates tend to share the basic regulatory structure of the best fitting candidate, which can best predict the data among candidates. Thus, instead of evaluating all candidates, we propose an efficient explorative method that can selectively and sequentially evaluate candidates based on the similarity of their regulatory structures. Furthermore, in estimating the parameter values of a candidate, e.g., synthesis and degradation rates of mRNA, for the data, those of the previously evaluated candidates can be utilized. The method is applied here to the pharmacogenomic pathways for corticosteroids in rats, using time-series microarray expression data. In the performance test, we succeeded in obtaining more than 80% of consistent solutions within 15% of the computational time as compared to the comprehensive evaluation. Then, we applied this approach to 142 literature-recorded simulation models of corticosteroid-induced genes, and consequently selected 134 newly constructed better models. The method described here was found to be capable of efficiently exploring candidate simulation models and obtaining better models within a short span of time. Furthermore, the results suggest that there may be room for improvement in literature recorded pathways and that they can be systematically updated using biological observational data.

STL-based analysis of TRAIL-induced apoptosis challenges the notion of type I/type II cell line classification

Extrinsic apoptosis is a programmed cell death triggered by external ligands, such as the TNF-related apoptosis inducing ligand (TRAIL). Depending on the cell line, the specific molecular mechanisms leading to cell death may significantly differ. Precise characterization of these differences is crucial for understanding and exploiting extrinsic apoptosis. Cells show distinct behaviors on several aspects of apoptosis, including (i) the relative order of caspases activation, (ii) the necessity of mitochondria outer membrane permeabilization (MOMP) for effector caspase activation, and (iii) the survival of cell lines overexpressing Bcl2. These differences are attributed to the activation of one of two pathways, leading to classification of cell lines into two groups: type I and type II. In this work we challenge this type I/type II cell line classification. We encode the three aforementioned distinguishing behaviors in a formal language, called signal temporal logic (STL), and use it to extensively test the validity of a previously-proposed model of TRAIL-induced apoptosis with respect to experimental observations made on different cell lines. After having solved a few inconsistencies using STL-guided parameter search, we show that these three criteria do not define consistent cell line classifications in type I or type II, and suggest mutants that are predicted to exhibit ambivalent behaviors. In particular, this finding sheds light on the role of a feedback loop between caspases, and reconciliates two apparently-conflicting views regarding the importance of either upstream or downstream processes for cell-type determination. More generally, our work suggests that these three distinguishing behaviors should be merely considered as type I/II features rather than cell-type defining criteria. On the methodological side, this work illustrates the biological relevance of STL-diagrams, STL population data, and STL-guided parameter search implemented in the tool Breach. Such tools are well-adapted to the ever-increasing availability of heterogeneous knowledge on complex signal transduction pathways.

Apoptosis, a major form of programmed cell death, plays a crucial role in shaping organs during development and controls homeostasis and tissue integrity throughout life. Defective apoptosis is often involved in cancer development and progression. Current understanding of externally triggered apoptosis is that death results from the activation of one out of two parallel signal transduction pathways. This leads to a classification of cell lines in two main types: type I and II. In the context of chemotherapy, understanding the cell-line-specific molecular mechanisms of apoptosis is important since this could guide drug usage. Biologists investigate the details of signal transduction pathways often at the single cell level and construct models to assess their current understanding. However, no systematic approach is employed to check the consistency of model predictions and experimental observations on various cell lines. Here we propose to use a formal specification language to encode the observed properties and a systematic approach to test whether model predictions are consistent with expected properties. Such property-guided model development and model revision approaches should guarantee an optimal use of the often heterogeneous experimental data.

Qualitative reasoning for biological network inference from systematic perturbation experiments

The systematic perturbation of the components of a biological system has been proven among the most informative experimental setups for the identification of causal relations between the components. In this paper, we present Systematic Perturbation-Qualitative Reasoning (SPQR), a novel Qualitative Reasoning approach to automate the interpretation of the results of systematic perturbation experiments. Our method is based on a qualitative abstraction of the experimental data: for each perturbation experiment, measured values of the observed variables are modeled as lower, equal or higher than the measurements in the wild type condition, when no perturbation is applied. The algorithm exploits a set of IF-THEN rules to infer causal relations between the variables, analyzing the patterns of propagation of the perturbation signals through the biological network, and is specifically designed to minimize the rate of false positives among the inferred relations. Tested on both simulated and real perturbation data, SPQR indeed exhibits a significantly higher precision than the state of the art.

Time series dependent analysis of unparametrized Thomas networks

This paper is concerned with the analysis of labeled Thomas networks using discrete time series. It focuses on refining the given edge labels and on assessing the data quality. The results are aimed at being exploitable for experimental design and include the prediction of new activatory or inhibitory effects of given interactions and yet unobserved oscillations of specific components in between specific sampling intervals. On the formal side, we generalize the concept of edge labels and introduce a discrete time series interpretation. This interpretation features two original concepts: 1) Incomplete measurements are admissible, and 2) it allows qualitative assumptions about the changes in gene expression by means of monotonicity. On the computational side, we provide a Python script, erda.py, that automates the suggested workflow by model checking and constraint satisfaction. We illustrate the workflow by investigating the yeast network IRMA.

On parameter synthesis by parallel model checking

An important problem in current computational systems biology is to analyze models of biological systems dynamics under parameter uncertainty. This paper presents a novel algorithm for parameter synthesis based on parallel model checking. The algorithm is conceptually universal with respect to the modeling approach employed. We introduce the algorithm, show its scalability, and examine its applicability on several biological models.