A Method to Identify and Analyze Biological Programs through Automated Reasoning

Combining Zhegalkin Polynomials and SAT Solving for Context-Specific Boolean Modeling of Biological Systems

Large amounts of knowledge regarding biological processes are readily available in the literature and aggregated in diverse databases. Boolean networks are powerful tools to render that knowledge into models that can mimic and simulate biological phenomena at multiple scales. Yet, when a model is required to understand or predict the behavior of a biological system in given conditions, existing information often does not completely match this context. Networks built from only prior knowledge can overlook mechanisms, lack specificity, and just partially recapitulate experimental observations. To address this limitation, context-specific data needs to be integrated. However, the brute-force identification of qualitative rules matching these data becomes infeasible as the number of candidates explodes for increasingly complex systems. Here, we used Zhegalkin polynomials to transform this identification into a binary value assignment for exponentially fewer variables, which we addressed with a state-of-the-art SAT solver. We evaluated our implemented method alongside two widely recognized tools, CellNetOptimizer and Caspo-ts, on both artificial toy models and large-scale models based on experimental data from the HPN-DREAM challenge. Our approach demonstrated benchmark-leading capabilities on networks of significant size and intricate complexity. It thus appears promising for the in silico modeling of ever more comprehensive biological systems.

The Reasoning Engine: A Satisfiability Modulo Theories-Based Framework for Reasoning About Discrete Biological Models

We present a framework called the Reasoning Engine, which implements Satisfiability Modulo Theories (SMT)-based methods within a unified computational environment to address diverse biological analysis problems. The Reasoning Engine was used to reproduce results from key scientific studies, as well as supporting new research in stem cell biology. The framework utilizes an intermediate language for encoding partially specified discrete dynamical systems, which bridges the gap between high-level domain-specific languages and low-level SMT solvers. We provide this framework as open source together with various biological case studies, illustrating the synthesis, enumeration, optimization, and reasoning over models consistent with experimental observations to reveal novel biological insights.

Automatic mechanistic inference from large families of Boolean models generated by Monte Carlo tree search

Many important processes in biology, such as signaling and gene regulation, can be described using logic models. These logic models are typically built to behaviorally emulate experimentally observed phenotypes, which are assumed to be steady states of a biological system. Most models are built by hand and therefore researchers are only able to consider one or perhaps a few potential mechanisms. We present a method to automatically synthesize Boolean logic models with a specified set of steady states. Our method, called MC-Boomer, is based on Monte Carlo Tree Search an efficient, parallel search method using reinforcement learning. Our approach enables users to constrain the model search space using prior knowledge or biochemical interaction databases, thus leading to generation of biologically plausible mechanistic hypotheses. Our approach can generate very large numbers of data-consistent models. To help develop mechanistic insight from these models, we developed analytical tools for multi-model inference and model selection. These tools reveal the key sets of interactions that govern the behavior of the models. We demonstrate that MC-Boomer works well at reconstructing randomly generated models. Then, using single time point measurements and reasonable biological constraints, our method generates hundreds of thousands of candidate models that match experimentally validated in-vivo behaviors of the Drosophila segment polarity network. Finally we outline how our multi-model analysis procedures elucidate potentially novel biological mechanisms and provide opportunities for model-driven experimental validation.

Esrrb guides naive pluripotent cells through the formative transcriptional programme

During embryonic development, naive pluripotent epiblast cells transit to a formative state. The formative epiblast cells form a polarized epithelium, exhibit distinct transcriptional and epigenetic profiles and acquire competence to differentiate into all somatic and germline lineages. However, we have limited understanding of how the transition to a formative state is molecularly controlled. Here we used murine embryonic stem cell models to show that ESRRB is both required and sufficient to activate formative genes. Genetic inactivation of Esrrb leads to illegitimate expression of mesendoderm and extra-embryonic markers, impaired formative expression and failure to self-organize in 3D. Functionally, this results in impaired ability to generate formative stem cells and primordial germ cells in the absence of Esrrb. Computational modelling and genomic analyses revealed that ESRRB occupies key formative genes in naive cells and throughout the formative state. In so doing, ESRRB kickstarts the formative transition, leading to timely and unbiased capacity for multi-lineage differentiation.

Boolean network sketches: a unifying framework for logical model inference

MOTIVATION

The problem of model inference is of fundamental importance to systems biology. Logical models (e.g. Boolean networks; BNs) represent a computationally attractive approach capable of handling large biological networks. The models are typically inferred from experimental data. However, even with a substantial amount of experimental data supported by some prior knowledge, existing inference methods often focus on a small sample of admissible candidate models only.

RESULTS

We propose Boolean network sketches as a new formal instrument for the inference of Boolean networks. A sketch integrates (typically partial) knowledge about the network's topology and the update logic (obtained through, e.g. a biological knowledge base or a literature search), as well as further assumptions about the properties of the network's transitions (e.g. the form of its attractor landscape), and additional restrictions on the model dynamics given by the measured experimental data. Our new BNs inference algorithm starts with an 'initial' sketch, which is extended by adding restrictions representing experimental data to a 'data-informed' sketch and subsequently computes all BNs consistent with the data-informed sketch. Our algorithm is based on a symbolic representation and coloured model-checking. Our approach is unique in its ability to cover a broad spectrum of knowledge and efficiently produce a compact representation of all inferred BNs. We evaluate the method on a non-trivial collection of real-world and simulated data.

AVAILABILITY AND IMPLEMENTATION

All software and data are freely available as a reproducible artefact at https://doi.org/10.5281/zenodo.7688740.

Langley M, Fisher CL, Aguilar-Hidalgo D, Shukla S, Yachie-Kinoshita A, Hughes M, M. McNagny K, Zandstra PW. IQCELL: A platform for predicting the effect of gene perturbations on developmental trajectories using single-cell RNA-seq data

The increasing availability of single-cell RNA-sequencing (scRNA-seq) data from various developmental systems provides the opportunity to infer gene regulatory networks (GRNs) directly from data. Herein we describe IQCELL, a platform to infer, simulate, and study executable logical GRNs directly from scRNA-seq data. Such executable GRNs allow simulation of fundamental hypotheses governing developmental programs and help accelerate the design of strategies to control stem cell fate. We first describe the architecture of IQCELL. Next, we apply IQCELL to scRNA-seq datasets from early mouse T-cell and red blood cell development, and show that the platform can infer overall over 74% of causal gene interactions previously reported from decades of research. We will also show that dynamic simulations of the generated GRN qualitatively recapitulate the effects of known gene perturbations. Finally, we implement an IQCELL gene selection pipeline that allows us to identify candidate genes, without prior knowledge. We demonstrate that GRN simulations based on the inferred set yield results similar to the original curated lists. In summary, the IQCELL platform offers a versatile tool to infer, simulate, and study executable GRNs in dynamic biological systems.

Dynamical properties and path dependence in a gene-network model of cell differentiation

In this work, we explore the properties of a control mechanism exerted on random Boolean networks that takes inspiration from the methylation mechanisms in cell differentiation and consists in progressively freezing (i.e. clamping to 0) some nodes of the network. We study the main dynamical properties of this mechanism both theoretically and in simulation. In particular, we show that when applied to random Boolean networks, it makes it possible to attain dynamics and path dependence typical of biological cells undergoing differentiation.

TaBooN Boolean Network Synthesis Based on Tabu Search

Recent developments in Omics-technologies revolutionized the investigation of biology by producing molecular data in multiple dimensions and scale. This breakthrough in biology raises the crucial issue of their interpretation based on modelling. In this undertaking, network provides a suitable framework for modelling the interactions between molecules. Basically a Biological network is composed of nodes referring to the components such as genes or proteins, and the edges/arcs formalizing interactions between them. The evolution of the interactions is then modelled by the definition of a dynamical system. Among the different categories of network, the Boolean network offers a reliable qualitative framework for the modelling. Automatically synthesizing a Boolean network from experimental data therefore remains a necessary but challenging issue. In this study, we present Taboon, an original work-flow for synthesizing Boolean Networks from biological data. The methodology uses the data in the form of boolean profiles for inferring all the potential local formula inference. They combine to form the model space from which the most truthful model with regards to biological knowledge and experiments must be found. In the TaBooN work-flow the selection of the fittest model is achieved by a Tabu-search algorithm. TaBooN is an automated method for Boolean Network inference from.

Computational Stem Cell Biology: Open Questions and Guiding Principles

Computational biology is enabling an explosive growth in our understanding of stem cells and our ability to use them for disease modeling, regenerative medicine, and drug discovery. We discuss four topics that exemplify applications of computation to stem cell biology: cell typing, lineage tracing, trajectory inference, and regulatory networks. We use these examples to articulate principles that have guided computational biology broadly and call for renewed attention to these principles as computation becomes increasingly important in stem cell biology. We also discuss important challenges for this field with the hope that it will inspire more to join this exciting area.

Formal Analysis of Network Motifs Links Structure to Function in Biological Programs

A recurring set of small sub-networks have been identified as the building blocks of biological networks across diverse organisms. These network motifs are associated with certain dynamic behaviors and define key modules that are important for understanding complex biological programs. Besides studying the properties of motifs in isolation, current algorithms typically evaluate the occurrence frequency of a specific motif in a given biological network compared to that in random networks of similar structure. However, it remains challenging to relate the structure of motifs to the observed and expected behavior of the larger, more complex network they are contained within. This problem is compounded as even the precise structure of most biological networks remains largely unknown. Previously, we developed a formal reasoning approach enabling the synthesis of biological networks capable of reproducing some experimentally observed behavior. Here, we extend this approach to allow reasoning over the requirement for specific network motifs as a way of explaining how these behaviors arise. We illustrate the approach by analyzing the motifs involved in sign-sensitive delay and pulse generation. We demonstrate the scalability and biological relevance of the approach by studying the previously defined networks governing myeloid differentiation, the yeast cell cycle, and naïve pluripotency in mouse embryonic stem cells, revealing the requirement for certain motifs in these systems.

Robust network inference using response logic

Motivation

A major challenge in molecular and cellular biology is to map out the regulatory networks of cells. As regulatory interactions can typically not be directly observed experimentally, various computational methods have been proposed to disentangling direct and indirect effects. Most of these rely on assumptions that are rarely met or cannot be adapted to a given context.

Results

We present a network inference method that is based on a simple response logic with minimal presumptions. It requires that we can experimentally observe whether or not some of the system’s components respond to perturbations of some other components, and then identifies the directed networks that most accurately account for the observed propagation of the signal. To cope with the intractable number of possible networks, we developed a logic programming approach that can infer networks of hundreds of nodes, while being robust to noisy, heterogeneous or missing data. This allows to directly integrate prior network knowledge and additional constraints such as sparsity. We systematically benchmark our method on KEGG pathways, and show that it outperforms existing approaches in DREAM3 and DREAM4 challenges. Applied to a novel perturbation dataset on PI3K and MAPK pathways in isogenic models of a colon cancer cell line, it generates plausible network hypotheses that explain distinct sensitivities toward various targeted inhibitors due to different PI3K mutants.

Availability and implementation

A Python/Answer Set Programming implementation can be accessed at github.com/GrossTor/response-logic. Data and analysis scripts are available at github.com/GrossTor/response-logic-projects.

Supplementary information

Supplementary data are available at Bioinformatics online.

Automated inference of gene regulatory networks using explicit regulatory modules

Gene regulatory networks are a popular tool for modelling important biological phenomena, such as cell differentiation or oncogenesis. Efficient identification of the causal connections between genes, their products and regulating transcription factors, is key to understanding how defects in their function may trigger diseases. Modelling approaches should keep up with the ever more detailed descriptions of the biological phenomena at play, as provided by new experimental findings and technical improvements. In recent years, we have seen great improvements in mapping of specific binding sites of many transcription factors to distinct regulatory regions. Recent gene regulatory network models use binding measurements; but usually only to define gene-to-gene interactions, ignoring regulatory module structure. Moreover, current huge amount of transcriptomic data, and exploration of all possible cis-regulatory arrangements which can lead to the same transcriptomic response, makes manual model building both tedious and time-consuming. In our paper, we propose a method to specify possible regulatory connections in a given Boolean network, based on transcription factor binding evidence. This is implemented by an algorithm which expands a regular Boolean network model into a "cis-regulatory" Boolean network model. This expanded model explicitly defines regulatory regions as additional nodes in the network, and adds new, valuable biological insights to the system dynamics. The expanded model can automatically be compared with expression data. And, for each node, a regulatory function, consistent with the experimental data, can be found. The resulting models are usually more constrained (by biologically-motivated metadata), and can then be inspected in in silico simulations. The fully automated method for model identification has been implemented in Python, and the expansion algorithm in R. The method resorts to the Z3 Satisfiability Modulo Theories (SMT) solver, and is similar to the RE:IN application (Yordanov et al., 2016). It is available on https://github.com/regulomics/expansion-network.

Synthesizing and tuning stochastic chemical reaction networks with specified behaviours

Methods from stochastic dynamical systems theory have been instrumental in understanding the behaviours of chemical reaction networks (CRNs) arising in natural systems. However, considerably less attention has been given to the inverse problem of synthesizing CRNs with a specified behaviour, which is important for the forward engineering of biological systems. Here, we present a method for generating discrete-state stochastic CRNs from functional specifications, which combines synthesis of reactions using satisfiability modulo theories and parameter optimization using Markov chain Monte Carlo. First, we identify candidate CRNs that have the possibility to produce correct computations for a given finite set of inputs. We then optimize the parameters of each CRN, using a combination of stochastic search techniques applied to the chemical master equation, to improve the probability of correct behaviour and rule out spurious solutions. In addition, we use techniques from continuous-time Markov chain theory to analyse the expected termination time for each CRN. We illustrate our approach by synthesizing CRNs for probabilistically computing majority, maximum and division, producing both known and previously unknown networks, including a novel CRN for probabilistically computing the maximum of two species. In future, synthesis techniques such as these could be used to automate the design of engineered biological circuits and chemical systems.

Stem cell bioengineering: building from stem cell biology

New fundamental discoveries in stem cell biology have yielded potentially transformative regenerative therapeutics. However, widespread implementation of stem-cell-derived therapeutics remains sporadic. Barriers that impede the development of these therapeutics can be linked to our incomplete understanding of how the regulatory networks that encode stem cell fate govern the development of the complex tissues and organs that are ultimately required for restorative function. Bioengineering tools, strategies and design principles represent core components of the stem cell bioengineering toolbox. Applied to the different layers of complexity present in stem-cell-derived systems - from gene regulatory networks in single stem cells to the systemic interactions of stem-cell-derived organs and tissues - stem cell bioengineering can address existing challenges and advance regenerative medicine and cellular therapies.

Dynamic modeling and network approaches for omics time course data: overview of computational approaches and applications

Inferring networks and dynamics of genes, proteins, cells and other biological entities from high-throughput biological omics data is a central and challenging issue in computational and systems biology. This is essential for understanding the complexity of human health, disease susceptibility and pathogenesis for Predictive, Preventive, Personalized and Participatory (P4) system and precision medicine. The delineation of the possible interactions of all genes/proteins in a genome/proteome is a task for which conventional experimental techniques are ill suited. Urgently needed are rapid and inexpensive computational and statistical methods that can identify interacting candidate disease genes or drug targets out of thousands that can be further investigated or validated by experimentations. Moreover, identifying biological dynamic systems, and simultaneously estimating the important kinetic structural and functional parameters, which may not be experimentally accessible could be important directions for drug-disease-gene network studies. In this article, we present an overview and comparison of recent developments of dynamic modeling and network approaches for time-course omics data, and their applications to various biological systems, health conditions and disease statuses. Moreover, various data reduction and analytical schemes ranging from mathematical to computational to statistical methods are compared including their merits, drawbacks and limitations. The most recent software, associated web resources and other potentials for the compared methods are also presented and discussed in detail.

Automated Formal Reasoning to Uncover Molecular Programs of Self-Renewal

The Reasoning Engine for Interaction Networks (RE:IN) is a tool that was developed initially for the study of pluripotency in mouse embryonic stem cells. A set of critical factors that regulate the pluripotent state had been identified experimentally, but it was not known how these genes interacted to stabilize self-renewal or commit the cell to differentiation. The methodology encapsulated in RE:IN enabled the exploration of a space of possible network interaction models, allowing for uncertainty in whether individual interactions exist between the pluripotency factors. This concept of an "abstract" network was combined with automated reasoning that allows the user to eliminate models that are inconsistent with experimental observations. The tool generalizes beyond the study of stem cell decision-making, allowing for the study of interaction networks more broadly across biology.

A common molecular logic determines embryonic stem cell self-renewal and reprogramming

During differentiation and reprogramming, new cell identities are generated by reconfiguration of gene regulatory networks. Here, we combined automated formal reasoning with experimentation to expose the logic of network activation during induction of naïve pluripotency. We find that a Boolean network architecture defined for maintenance of naïve state embryonic stem cells (ESC) also explains transcription factor behaviour and potency during resetting from primed pluripotency. Computationally identified gene activation trajectories were experimentally substantiated at single‐cell resolution by RT–qPCR. Contingency of factor availability explains the counterintuitive observation that Klf2, which is dispensable for ESC maintenance, is required during resetting. We tested 124 predictions formulated by the dynamic network, finding a predictive accuracy of 77.4%. Finally, we show that this network explains and predicts experimental observations of somatic cell reprogramming. We conclude that a common deterministic program of gene regulation is sufficient to govern maintenance and induction of naïve pluripotency. The tools exemplified here could be broadly applied to delineate dynamic networks underlying cell fate transitions.

Kinetic models of hematopoietic differentiation

As cell and molecular biology is becoming increasingly quantitative, there is an upsurge of interest in mechanistic modeling at different levels of resolution. Such models mostly concern kinetics and include gene and protein interactions as well as cell population dynamics. The final goal of these models is to provide experimental predictions, which is now taking on. However, even without matured predictions, kinetic models serve the purpose of compressing a plurality of experimental results into something that can empower the data interpretation, and importantly, suggesting new experiments by turning "knobs" in silico. Once formulated, kinetic models can be executed in terms of molecular rate equations for concentrations or by stochastic simulations when only a limited number of copies are involved. Developmental processes, in particular those of stem and progenitor cell commitments, are not only topical but also particularly suitable for kinetic modeling due to the finite number of key genes involved in cellular decisions. Stem and progenitor cell commitment processes have been subject to intense experimental studies over the last decade with some emphasis on embryonic and hematopoietic stem cells. Gene and protein interactions governing these processes can be modeled by binary Boolean rules or by continuous-valued models with interactions set by binding strengths. Conceptual insights along with tested predictions have emerged from such kinetic models. Here we review kinetic modeling efforts applied to stem cell developmental systems with focus on hematopoiesis. We highlight the future challenges including multi-scale models integrating cell dynamical and transcriptional models. This article is categorized under: Models of Systems Properties and Processes > Mechanistic Models Developmental Biology > Stem Cell Biology and Regeneration.

A protein phosphatase network controls the temporal and spatial dynamics of differentiation commitment in human epidermis

Epidermal homeostasis depends on a balance between stem cell renewal and terminal differentiation. The transition between the two cell states, termed commitment, is poorly understood. Here, we characterise commitment by integrating transcriptomic and proteomic data from disaggregated primary human keratinocytes held in suspension to induce differentiation. Cell detachment induces several protein phosphatases, five of which - DUSP6, PPTC7, PTPN1, PTPN13 and PPP3CA – promote differentiation by negatively regulating ERK MAPK and positively regulating AP1 transcription factors. Conversely, DUSP10 expression antagonises commitment. The phosphatases form a dynamic network of transient positive and negative interactions that change over time, with DUSP6 predominating at commitment. Boolean network modelling identifies a mandatory switch between two stable states (stem and differentiated) via an unstable (committed) state. Phosphatase expression is also spatially regulated in vivo and in vitro. We conclude that an auto-regulatory phosphatase network maintains epidermal homeostasis by controlling the onset and duration of commitment.

Computational dynamic approaches for temporal omics data with applications to systems medicine

Modeling and predicting biological dynamic systems and simultaneously estimating the kinetic structural and functional parameters are extremely important in systems and computational biology. This is key for understanding the complexity of the human health, drug response, disease susceptibility and pathogenesis for systems medicine. Temporal omics data used to measure the dynamic biological systems are essentials to discover complex biological interactions and clinical mechanism and causations. However, the delineation of the possible associations and causalities of genes, proteins, metabolites, cells and other biological entities from high throughput time course omics data is challenging for which conventional experimental techniques are not suited in the big omics era. In this paper, we present various recently developed dynamic trajectory and causal network approaches for temporal omics data, which are extremely useful for those researchers who want to start working in this challenging research area. Moreover, applications to various biological systems, health conditions and disease status, and examples that summarize the state-of-the art performances depending on different specific mining tasks are presented. We critically discuss the merits, drawbacks and limitations of the approaches, and the associated main challenges for the years ahead. The most recent computing tools and software to analyze specific problem type, associated platform resources, and other potentials for the dynamic trajectory and interaction methods are also presented and discussed in detail.

Environmental factors in breast cancer invasion: a mathematical modelling review

This review presents a brief overview of breast cancer, focussing on its heterogeneity and the role of mathematical modelling and simulation in teasing apart the underlying biophysical processes. Following a brief overview of the main known pathophysiological features of ductal carcinoma, attention is paid to differential equation-based models (both deterministic and stochastic), agent-based modelling, multi-scale modelling, lattice-based models and image-driven modelling. A number of vignettes are presented where these modelling approaches have elucidated novel aspects of breast cancer dynamics, and we conclude by offering some perspectives on the role mathematical modelling can play in understanding breast cancer development, invasion and treatment therapies.

Quantitative stem cell biology: the threat and the glory

Major technological innovations over the past decade have transformed our ability to extract quantitative data from biological systems at an unprecedented scale and resolution. These quantitative methods and associated large datasets should lead to an exciting new phase of discovery across many areas of biology. However, there is a clear threat: will we drown in these rivers of data? On 18th July 2016, stem cell biologists gathered in Cambridge for the 5th annual Cambridge Stem Cell Symposium to discuss 'Quantitative stem cell biology: from molecules to models'. This Meeting Review provides a summary of the data presented by each speaker, with a focus on quantitative techniques and the new biological insights that are emerging.

Automated Synthesis and Analysis of Switching Gene Regulatory Networks

Studying the gene regulatory networks (GRNs) that govern how cells change into specific cell types with unique roles throughout development is an active area of experimental research. The fate specification process can be viewed as a biological program prescribing the system dynamics, governed by a network of genetic interactions. To investigate the possibility that GRNs are not fixed but rather change their topology, for example as cells progress through commitment, we introduce the concept of Switching Gene Regulatory Networks (SGRNs) to enable the modelling and analysis of network reconfiguration. We define the synthesis problem of constructing SGRNs that are guaranteed to satisfy a set of constraints representing experimental observations of cell behaviour. We propose a solution to this problem that employs methods based upon Satisfiability Modulo Theories (SMT) solvers, and evaluate the feasibility and scalability of our approach by considering a set of synthetic benchmarks exhibiting possible biological behaviour of cell development. We outline how our approach is applied to a more realistic biological system, by considering a simplified network involved in the processes of neuron maturation and fate specification in the mammalian cortex.