{ "cells": [ { "cell_type": "markdown", "id": "ac1b5e30", "metadata": { "latex_maketitle": { "corrAuthor": "Loïc Paulev", "corrEmail": "loic.pauleve@labri.fr", "firstAuthorLast": "Paulevé", "runningTitle": "Reprogramming of Most Permissive Boolean networks with BoNesis" } }, "source": [ "# Marker and source-marker reprogramming of Most Permissive Boolean networks and ensembles with BoNesis\n", "\n", "Loïc Paulevé\n", "> Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France\n", "\n", "#### Abstract\n", "> Boolean networks (BNs) are discrete dynamical systems with applications to the modeling of cellular behaviors. In this paper, we demonstrate how the software BoNesis can be employed to exhaustively identify combinations of perturbations which enforce properties on their fixed points and attractors. We consider marker properties, which specify that some components are fixed to a specific value.\n", "> We study 4 variants of the marker reprogramming problem: the reprogramming of fixed points, of minimal trap spaces, and of fixed points and minimal trap spaces reachable from a given initial configuration with the most permissive update mode. The perturbations consist of fixing a set of components to a fixed value. They can destroy and create new attractors.\n", "> In each case, we give an upper bound on their theoretical computational complexity, and give an implementation of the resolution using the BoNesis Python framework.\n", "> Finally, we lift the reprogramming problems to ensembles of BNs, as supported by *BoNesis*, bringing insight on possible and universal reprogramming strategies.\n", "> This paper can be executed and modified interactively.\n", "\n", "**Keywords**: Discrete dynamical systems, Control, Minimal trap spaces, Attractors, Reachability" ] }, { "cell_type": "markdown", "id": "8ddd4775", "metadata": {}, "source": [ "# Introduction\n", "\n", "Boolean networks (BNs) are formal discrete dynamical systems with pertinent applications for modeling cellular differentiation and fate decision processes (Saez-Rodriguez et al., 2009; Cohen et al., 2015; Schwab et al., 2021; Zañudo et al., 2021; Montagud et al., 2022). In these applications, BNs aim at capturing the stable behaviors (attractors) and the transient dynamics (trajectories) of the cell. From this perspective, BNs offer a formal framework for predicting perturbations that destabilize the system and drive it towards a desired new stable behavior. BN *control* or BN *reprogramming*, in reference to cellular reprogramming which aims at converting cell types, is thus receiving a lot of interest from the computational systems biology community (Zañudo et al., 2015; Yang et al., 2018; Biane et al., 2018; Mandon et al., 2019; Cifuentes Fontanals et al., 2020; Su and Pang, 2020; Rozum et al., 2021).\n", "\n", "The reprogramming of BNs led to a range of methods and tools addressing different instantiations of this problem: with different type of perturbations (instantaneous, temporary, permanent), different temporal modalities (one-step, sequential), different scopes (global reprogramming or from a given initial condition), different restrictions on the target attractor (fixed points only, attractors of the original \"wild-type\" BN). On top of that, the *update mode* of the BN, which determines how the trajectories are computed, can play an important role on the predictions." ] }, { "cell_type": "markdown", "id": "069f30c2", "metadata": {}, "source": [ "In this paper, we address the BN reprogramming with the Most Permissive (MP) update mode, where attractors are the minimal trap spaces of the BN (Paulevé et al., 2020). The problems we tackle are related to *marker* reprogramming: the desired target attractors are specified by a set of markers, associating a subset of nodes of the network to fixed values (e.g., $A=1,C=0$). After reprogramming, all the configurations in all (reachable) attractors must be compatible with these markers. Importantly, the target attractors are not necessarily attractors of the original (wild-type) BN: the reprogramming can destroy and create new attractors. In particular, if there is no attractor in the original model matching with the marker, the reprogramming will identify perturbations that will create such an attractor and ensure its reachability. This is a substantial difference with many of the methods in the literature. Moreover, the approach we present here can return *all* the possible solutions, possibly up to a given maximum number of perturbations to apply, and possibly avoiding *uncontrollable* nodes.\n", "\n", "We address the following BN reprogramming problems in the scope of the MP update mode:\n", "\n", "* *P1*: Marker reprogramming of fixed points: after reprogramming, all the fixed points of the BN match with the given markers; optionally, we can also ensure that at least one fixed point exists.\n", "* *P2*: Source-marker reprogramming of fixed points: after reprogramming, all the fixed points that are *reachable from the given initial configuration* match with the given markers.\n", "* *P3*: Marker reprogramming of attractors: after reprogramming, all the configurations of all the MP attractors (the minimal trap spaces) of the BN match with the given markers.\n", "* *P4*: Source-marker reprogramming of attractors: after reprogramming, all the configurations of all the attractors that are *reachable from the given initial configuration* match with the given markers.\n", "\n", "MP fixed points match with the fixed points of the global Boolean map of the BN and are thus identical to the fixed points of the (a)synchronous update modes. MP attractors match with so-called *minimal trap spaces* of the BN, which are the smallest sub-hypercubes closed by the Boolean map. Problem *P1* has been already addressed in the literature, notably by Biane et al. (2018) with the *ActoNet* method and by Moon et al. (2022a), based on bilevel integer programming. To our knowledge, none of the other problems have been addressed completely in the literature.\n", "\n", "The software *BoNesis* ([github.com/bnediction/bonesis](https://github.com/bnediction/bonesis)) provides a generic environment for the automated construction of BNs with MP update mode from specified structural and dynamical properties. The properties are translated into a logic satisfiability problem, expressed in Answer-Set Programming (ASP). Initially, *BoNesis* has been designed for performing BN synthesis (Chevalier et al., 2019): solutions of the logic model correspond to BNs that possess the specified structural and dynamical properties. Leveraging this generic declarative specification of properties, *BoNesis* is a versatile tool for reasoning on BNs in general, with the MP update mode: besides synthesis, it can be used to do model checking, identify fixed points and attractors in ensemble of BNs, and identifying reprogramming strategies.\n", "\n", "In this paper, we show how the software *BoNesis* can be employed to solve P1, P2, P3, and P4 in the scope of *locally-monotone* BNs, where each local function is *[unate](https://en.wikipedia.org/wiki/Unate_function)*, i.e., where each local function never depends on both positively and negatively from a same component. Locally-monotone BNs cover all the models where it assumed that a node cannot be both an activator and inhibitor of a same other node, which is a common assumption when modeling biological system.\n", "\n", "*BoNesis* enables reasoning on *ensembles* of BNs: one of its basic input is the domain of BNs to consider. This domain could be reduced to a singleton BN: in that case, the reasoning is similar to standard model checking and reprogramming. In general, the domain is specified from an influence graph, possibly with additional constraints on the underlying logical functions. For BN synthesis, this domain is used to delimit symbolically the set of candidate models: *BoNesis* will output the subset of them that verify the desired dynamical properties. We show how problems P1 to P4 can be partly lifted to ensembles of BNs using this approach." ] }, { "cell_type": "markdown", "id": "a9fd4555", "metadata": {}, "source": [ "The paper is structured as follows. The *Methods* section gives the necessary background on BNs and MP update mode and formulation of elementary dynamical properties as satisfaction problems, as well as main principles of the *BoNesis* environment. The *Results* section details how the different reprogramming problems P1-P4 can be addressed using *BoNesis* and shows some experiments to assess their scalability. Finally, the *Discussion* section sketches possible extensions of the addressed problems and underlines current challenges for their resolution.\n", "\n", "This paper is *executable*: it contains snippets of Python code employing *BoNesis* to demonstrate its usage on small examples, including command line usage. Instructions for its execution are given at the beginning of the *Results* section.\n", "It can be visualized online at [nbviewer.org/github/bnediction/reprogramming-with-bonesis/blob/release/paper.ipynb](https://nbviewer.org/github/bnediction/reprogramming-with-bonesis/blob/release/paper.ipynb) and interactively executed either online at [mybinder.org/v2/gh/bnediction/reprogramming-with-bonesis/release](https://mybinder.org/v2/gh/bnediction/reprogramming-with-bonesis/release) using [mybinder](https://mybinder.org/) online free service, or locally, following instructions given later in this paper." ] }, { "cell_type": "markdown", "id": "72e6a624", "metadata": {}, "source": [ "# Methods\n", "\n", "## Boolean networks and the Most Permissive update mode\n", "\n", "### Basic definitions\n", "A Boolean network (BN) of dimension $n$ is specified by a function $f: \\mathbb B^n\\to\\mathbb B^n$ where $\\mathbb B = \\{0,1\\}$ is the Boolean domain. For $i\\in \\{1,\\cdots,n\\}$, $f_i:\\mathbb B^n\\to\\mathbb B$ is referred to as the *local function* of the *component* $i$.\n", "The Boolean vectors $x\\in\\mathbb B^n$ are called *configurations*, where for any $i\\in\\{1,\\cdots,n\\}$, $x_i$ denotes the *state* of component $i$ in the configuration $x$.\n", "\n", "A BN $f$ is *locally monotone* whenever every of its local functions are *unate*: for each $i\\in\\{1,\\cdots,n\\}$, there exists an ordering of components $\\preceq^i\\in \\{\\leq, \\geq\\}^n$ such that $\\forall x,y\\in \\mathbb B^n$, $(x_1\\preceq^i_1 y_1 \\wedge \\cdots \\land x_n\\preceq^i_n y_n) \\implies f_i(x) \\leq f_i(y)$. Intuitively, a BN is locally monotone whenever each of its local function can be expressed in propositional logic such that each variable appears either never or always with the same sign. For instance $f_1(x) = x_1\\vee (\\neg x_3 \\wedge x_2)$ is unate, whereas $f_1(x) = x_2 \\oplus x_3 = (x_2\\wedge\\neg x_3)\\vee (\\neg x_2\\wedge x_3)$ is not unate.\n", "\n", "*Example.* The BN $f$ of dimension $3$ with $f_1(x)=\\neg x_2$, $f_2(x)=\\neg x_1$, and $f_3(x) = \\neg x_1\\wedge x_2$ is locally monotone; and an instance of application is $f(000)=110$.\n", "\n", "Locally monotone BNs should not be confused with *monotone* BNs where a component appears in *all* local functions with the same sign. Monotone BNs are a particular case of locally-monotone BNs.\n", "\n", "### Update modes\n", "\n", "Given a BN $f$ and a configuration $x$, the *update mode* specifies how to compute the next configuration. There is a vast zoo of update modes (Paulevé and Sené, 2022), but traditionally, two modes are usually considered in biological modeling: the *synchronous* (or parallel) deterministic mode, where the next configuration is given by its application to $f$ ($x$ is succeeded by $f(x)$), and the *fully asynchronous* (often denoted only asynchronous) where the next configuration results from the application of only one local function, chosen non-deterministically.\n", "\n", "However, (a)synchronous update modes do not lead to a complete qualitative abstraction of quantitative systems and preclude the prediction of trajectories that are actually feasible when considering time scales or concentration scales. The *Most Permissive* (MP) (Paulevé et al., 2020; Paulevé and Sené, 2021) is a recently-introduced update mode which brings the formal guarantee to capture any trajectory that is feasible by any quantitative system compatible with the Boolean network (see (Paulevé et al., 2020) for details).\n", "The main idea behind the MP update mode is to systematically consider a potential delay when a component changes state, and consider any additional transitions that could occur if the changing component is in an intermediate state. It can be modeled as additional *dynamic* states \"increase\" ($\\nearrow$) and \"decrease\" ($\\searrow$): when a component can be activated, it will first go through the \"increase\" state where it can be interpreted as either 0 or 1 by the other components, until eventually reaching the Boolean 1 state; and symmetrically for deactivation.\n", "A formal definition of MP dynamics is given later in this section.\n", "\n", "### Perturbations\n", "\n", "In this paper we will consider BN *perturbations* that modify the local functions of some components so they become a constant function. Perturbations model mutations, where a gene is silenced or constitutively activated. Mathematically, a perturbation is a map associating a set of components to a Boolean value, for instance, $P = \\{ 2 \\mapsto 0, 4 \\mapsto 1\\}$. Given a perturbation $P$, the *perturbed BN* $f/P$ is given by, for each component $i\\in \\{1,\\ldots,n\\}$:\n", "$$\n", "(f/P)_i(x) = \\begin{cases}\n", "b & \\text{ if }i \\mapsto b \\in P\\\\\n", "f_i(x) & \\text{otherwise.}\n", "\\end{cases}\n", "$$" ] }, { "cell_type": "markdown", "id": "34a6a4c1", "metadata": {}, "source": [ "## Quantified Boolean expressions and computational complexity\n", "\n", "A Boolean expression is a logic formula composed of Boolean variables and propositional logic operators (negation $\\neg$, conjunction $\\wedge$, disjunction $\\vee$, implication $\\implies$, equivalence $\\equiv$, exclusive disjunction $\\oplus$).\n", "Given variables $x_1,\\cdots,x_m$, a *quantified* Boolean expression is of the form $Q_1 x_1 \\cdots Q_n x_m \\phi(x_1, \\cdots, x_m)$ where $Q_1, \\cdots, Q_m$ can be the existential $\\exists$ or universal $\\forall$ quantifier, and $\\phi(x_1,\\cdots,x_m)$ a quantifier-free Boolean expression composed of variables $x_1, \\cdots, x_m$.\n", "For instance, consider the quantified Boolean expression \"$\\exists x_1\\exists x_2 \\forall x_3\\, (x_3 \\wedge x_1) \\vee (\\neg x_3 \\wedge \\neg x_2)$\". This expression is satisfiable: fix $x_1=1$ and $x_2=0$, then the Boolean expression becomes equivalent to $x_3 \\vee \\neg x_3$ which is true for all assignments of $x_3$.\n", "\n", "Deciding whether such an expression is true (satisfiable) is a fundamental problem in computer science. The complexity of this problem actually depends on the alternation of quantifiers. Thus, in the following we will classify the quantified Boolean expressions by their sequence of quantifiers $Q_1\\cdots Q_m$ but ignoring repetitions: an $\\exists\\exists\\forall\\forall\\forall\\exists\\exists\\forall$-expression has the same decision complexity as an $\\exists\\forall\\exists\\forall$-expression.\n", "\n", "Computational complexity (Papadimitriou, 1993) is a fundamental theory of computer science to classify decision problems: a (decision) problem is in class C whenever there exists an algorithm of worst-case complexity C, C referring to either a time or space complexity. For instance, the class PTIME gathers all the problems that can be decided in time polynomial with the size of the input (e.g., the length of the Boolean expression).\n", "\n", "The decision of satisfiability of $\\exists$-expressions is the infamous (Boolean) SAT(isfiability) problem, which is NP-complete: it can be solved by a non-deterministic polynomial time algorithm, and it is among the hardest problems in this class: any problem in NP can be (efficiently) transformed into a SAT problem. In practice, our computers being deterministic, the resolution of the SAT problems employs algorithms running in worst-case time and space exponential with the number of variables in the Boolean expression. However, modern SAT solvers can approach expressions with thousands to millions of variables.\n", "\n", "The decision of satisfiability of $\\forall$-expressions can be seen as a complementary problem to $\\exists$-expression: $\\forall X~\\phi(X)$ is satisfiable if and only if $\\exists X~\\neg\\phi(X)$ is not satisfiable: it is a *co*NP-complete problem. It is not known whether coNP = NP.\n", "\n", "Then, the alternation of quantifiers makes the problem climbing into the so-called polynomial hierarchy[^1]. $\\exists\\ldots$-expressions are $\\Sigma_k^{\\mathrm P}$-complete problems, where $k$ is the number of alternating quantifiers (starting with $\\exists$), while $\\forall\\ldots$-expressions are $\\Pi_k^{\\mathrm P}$-complete\n", "($\\Sigma_1^{\\mathrm P}$=NP and $\\Pi_1^{\\mathrm P}$=coNP). It is not known yet whether all these complexity classes are equal, but in practice, algorithms of resolution scale rapidly down with their height in the polynomial hierarchy. Each of these complexity classes are included in PSPACE, the class of problems solvable in polynomial space. PSPACE-complete problems, such as the verification of properties of asynchronous BNs, are known to be difficult to tackle in practice (currently limited to a couple of hundreds of variables in the case of BNs).\n", "\n", "The reader should keep in mind that the length of the expression is a crucial parameter for the decision complexity. When variables have a finite domain, one can rewrite quantified Boolean expression in a universal-free one. However, the length of the obtained expression will be exponentially larger.\n", "\n", "In the rest of the paper, for the sake of simplicity, we will not fully detail the size of the quantified Boolean expression we derive, and are expected to be of length linear or polynomial with the size of the BN.\n", "\n", "[^1]: See [en.wikipedia.org/wiki/Polynomial_hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy)" ] }, { "cell_type": "markdown", "id": "0c27e700", "metadata": {}, "source": [ "## Elementary dynamical properties and their complexity\n", "\n", "We present the formal aspects of the MP dynamics that are employed in the rest of the paper, i.e., related to attractors and the reachability of attractors. The proofs and full MP definition and properties can be found in (Paulevé et al., 2020).\n", "\n", "### Sub-hypercubes and trap spaces\n", "\n", "A sub-hypercube specifies for each dimension of the BN if it is either fixed to a Boolean value, or free: it can be characterized by a vector $h\\in \\{0,1,*\\}^n$. Its *vertices* are denoted by $c(h) = \\{ x\\in \\mathbb B^n\\mid h_i\\neq *\\implies x_i=h_i\\}$. For instance, $h=0**$ is a sub-hypercube of dimension 3, with $c(h) = \\{000, 001, 010, 011\\}$.\n", "\n", "A sub-hypercube $h$ is a *trap space* whenever for each of its vertices $x\\in c(h)$, $f(x)$ is also one of its vertices ($h$ is closed by $f$). In particular, the (sub-)hypercube $\\mathbf *_n$ is always a trap space.\n", "\n", "A sub-hypercube $h$ is *smaller* than a sub-hypercube $h'$, denoted by $h \\preceq h'$ whenever $c(h)\\subseteq c(h')$. Equivalently, this means that each non-free component of $h'$ is fixed to the same value in $h$: $h \\preceq h' \\iff \\forall i\\in \\{1,\\ldots,n\\}, h'_i\\neq *\\implies h_i=h'_i$.\n", "\n", "\n", "### MP attractors are minimal trap spaces\n", "\n", "The attractors of MP dynamics are the *minimal trap spaces* of the Boolean function $f$ (Paulevé et al., 2020), i.e., the trap spaces which do not include strictly smaller trap spaces.\n", "Thus, we denote MP attractors by sub-hypercubes, i.e., an MP attractor $A$ is a vector in $\\{0,1,*\\}^n$.\n", "Therefore, a component with a $*$ value in an MP attractor $A$ indicates that the component that can always oscillate between 0 and 1 in the (cyclic) attractor.\n", "\n", "The computational complexity of decision problems related to minimal trap spaces has been extensively addressed in (Moon et al., 2022b) with different representations of Boolean networks.\n", "For the case of local functions represented with propositional logic, as we consider here, deciding whether a sub-hypercube is a trap space is coNP-complete problem, whereas deciding whether it is a *minimal* trap space is a coNPcoNP-complete problem, i.e., equivalent to the decision of satisfiability of $\\forall\\exists$ expressions.\n", "In the case of *locally-monotone* BNs, deciding whether a sub-hypercube is a trap space is in PTIME, whereas deciding whether it is a minimal trap spaces is a coNP-complete problem, i.e., equivalent to the decision of satisfiability of $\\forall$-expressions.\n", "\n", "\n", "### MP reachability of attractors\n", "\n", "Given a configuration $x$ and an MP attractor $A\\in \\{0,1,*\\}^n$, there is an MP trajectory from $x$ to any configuration $y\\in A$ if and only if $A$ is smaller than the smallest trap space *containing* $x$. We write $\\operatorname{reach}(x,y)$ the existence of such a trajectory.\n", "\n", "Let us denote by $\\operatorname{TS}(x) \\in \\{0,1,*\\}^n$ the smallest trap space containing $x$. The computation of $h=\\operatorname{TS}(x)$ can be performed from $x$ by iteratively freeing the components necessarily to fulfill the closeness property. Here is a sketch of algorithm, where `SAT(h, f[i] = -x[i])` is true if and only if there exists a configuration $y\\in c(h)$ such that $f_i(y)=\\neg x_i$:\n", "```\n", "Algorithm TS(x: configuration)\n", "Returns sub-hypercube h\n", "--\n", "h := x\n", "repeat\n", " changed := false\n", " for i in 1..n:\n", " if h[i] != * and SAT(h, f[i] = -x[i]):\n", " h[i] := *\n", " changed := true\n", "while changed\n", "```\n", "In the worst case, this algorithm makes a quadratic number of calls to the `SAT` problem.\n", "Therefore, the decision of MP reachability of attractors is in PTIMENP in general[^2], and PTIME in the locally-monotone case.\n", "\n", "Note that the general MP reachability property is not addressed here, but its overall complexity is identical. With (a)synchronous update modes, it is a PSPACE-complete problem.\n", "\n", "[^2]: this problem is actually in NP when allowing a number of variables quadratic with $n$\n", "\n", "### Belonging to an MP attractor\n", "\n", "In the following, we will consider the problem of deciding whether a given configuration $x$ belongs to an MP attractor of $f$. We write $\\operatorname{IN-ATTRACTOR}(x)$ such a property. This can be verified in two steps: (1) compute the smallest trap spaces containing $x$, noted $\\operatorname{TS}(x)$, and (2) verify whether $\\operatorname{TS}(x)$ is a minimal trap space. This later property is true if and only if for any vertex $y$ of $\\operatorname{TS}(x)$, the minimal trap space containing $y$ is equal to $\\operatorname{TS}(x)$:\n", "$$\n", "\\operatorname{IN-ATTRACTOR}(x) \\equiv \\forall y \\in c(\\operatorname{TS}(x)), \\operatorname{TS}(y) = \\operatorname{TS}(x) \\enspace.\n", "$$\n", "\n", "Finally, given a set of perturbations $P$, we write $\\operatorname{TS}_P(x)$ for the small trap space of perturbed BN $(f/P)$ containing $x$, and $\\operatorname{IN-ATTRACTOR}_P(x)$ the property of $x$ belonging to an attractor of the perturbed BN $(f/P)$." ] }, { "cell_type": "markdown", "id": "6b76fef3", "metadata": {}, "source": [ "## BoNesis\n", "\n", "*BoNesis* ([github.com/bnediction/bonesis](https://github.com/bnediction/bonesis)) is a Python library which has been primarily designed for identifying BNs satisfying user-given dynamical properties among a given domain of BNs and with the MP update mode.\n", "It takes as input (1) a domain of BNs $\\mathbb F$, and (2) a set of Boolean dynamical properties $\\phi$, and can enumerate the BNs $f \\in \\mathbb F$ such that $f\\models \\phi$, i.e., $f$ verifies the properties $\\phi$.\n", "\n", "Currently, the domain of BNs $\\mathbb F$ can be one of the following:\n", "\n", "- A singleton locally-monotone BN $\\mathbb F=\\{f\\}$. In that case, *BoNesis* can be employed as a model checker to verify that $f$ has the specified dynamical properties. In this paper, this is the main setting we will consider, in order to predict perturbations to reprogram the attractors of $f$.\n", "- An explicit ensemble of locally-monotone BNs $\\mathbb F=\\{ f^1,\\cdots, f^m \\}$.\n", "- Any locally-monotone BN matching with a given *influence graph* $\\mathcal G$: $\\mathbb F = \\{ f\\mid G(f)\\subseteq \\mathcal G\\}$. An influence graph is a signed digraph between components, i.e., of the form $(\\{1,\\cdots,n\\},V)$ with $V\\subseteq \\{1,\\cdots,n\\}\\times \\{+1,-1\\}\\times \\{1,\\cdots n\\}$. The influence graph of a BN $f$, denoted by $G(f)$ has an edge $i\\xrightarrow{s} j$ if and only there exists a configuration $x\\in\\mathbb B^n$ such that $f_j(x_1, \\ldots, x_{i-1}, 1, x_{i+1},\\ldots, x_n) - f_j(x_1, \\ldots, x_{i-1}, 0, x_{i+1},\\ldots, x_n) = s$.\n", "- Any locally-monotone BN matching with a partially-defined BN following the AEON framework (Beneš et al., 2021).\n", "\n", "*BoNesis* offers a Python programming interface to declare the dynamical properties over BNs, including reachability, fixed points and trap spaces. *BoNesis* relies on Answer-Set Programming (ASP) and the ASP solver [*clingo*](https://potassco.org/clingo) for the enumeration of solutions. ASP is a declarative logic programming framework for expressing combinatorial decision problems and enumerate their solutions, possibly with optimizations. ASP can be employed for efficiently solving $\\exists$- and $\\exists\\forall$-expressions, thus having an expressiveness higher than classical SAT.\n", "\n", "We emphasize that *BoNesis* is currently restricted to locally-monotone BNs only for which efficient logical encoding of domains of models are possible. Whereas it is a common assumption when modeling of biological systems (a node cannot be both an activator and inhibitor of a same other node), non-monotone BNs are also employed, and cannot be addressed with the current implementation.\n", "\n", "The usage of *BoNesis* Python programming interface and command line will be explained along with the code snippets provided in the next sections." ] }, { "cell_type": "markdown", "id": "6aba3e2a", "metadata": {}, "source": [ "# Results\n", "\n", "We show how the general declarative approach of *BoNesis* can be instantiated to compute the complete solutions to the P1, P2, P3, and P4 reprogramming problems on BNs, and also extend the reasoning to ensembles of BNs.\n", "Importantly, note that *BoNesis* currently supports only locally-monotone BNs.\n", "\n", "This is an *executable paper* which demonstrates the use of *BoNesis* for the reprogramming of BNs. The corresponding notebook can be downloaded from [nbviewer.org/github/bnediction/reprogramming-with-bonesis/blob/release/paper.ipynb](https://nbviewer.org/github/bnediction/reprogramming-with-bonesis/blob/release/paper.ipynb). Its execution requires the [Jupyter notebook](https://jupyter.org/) system, [Python](https://python.org), and the Python package `bonesis` to be installed, see [github.com/bnediction/bonesis](https://github.com/bnediction/bonesis) for instructions.\n", "Alternatively, the notebook can be executed within the CoLoMoTo Docker distribution (Naldi et al., 2018), using the Docker image `colomoto/colomoto-docker:2023-03-01`, which can be launched as follows:\n", "```\n", "pip install colomoto-docker\n", "colomoto-docker -V 2023-03-01\n", "```\n", "then open [http://127.0.0.1:8888](http://127.0.0.1:8888) and upload the notebook from the Jupyter interface.\n", "See [github.com/bnediction/reprogramming-with-bonesis](https://github.com/bnediction/reprogramming-with-bonesis) for further help." ] }, { "cell_type": "code", "execution_count": 1, "id": "ddac3ea7", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:16.455369Z", "iopub.status.busy": "2022-07-22T16:22:16.454368Z", "iopub.status.idle": "2022-07-22T16:22:17.085218Z", "shell.execute_reply": "2022-07-22T16:22:17.084827Z" } }, "outputs": [], "source": [ "#!pip install --user bonesis # uncomment to install bonesis\n", "import bonesis" ] }, { "cell_type": "code", "execution_count": 2, "id": "d64c32e6", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.087270Z", "iopub.status.busy": "2022-07-22T16:22:17.087163Z", "iopub.status.idle": "2022-07-22T16:22:17.089324Z", "shell.execute_reply": "2022-07-22T16:22:17.089067Z" } }, "outputs": [], "source": [ "from colomoto_jupyter import tabulate # for display\n", "import pandas as pd # for display\n", "import mpbn # for analyzing individual Boolean networks with MP update mode\n", "from colomoto.minibn import BooleanNetwork" ] }, { "cell_type": "markdown", "id": "47ec547a", "metadata": {}, "source": [ "Alternatively, the computation of reprogramming perturbations from single Boolean networks can be performed using the command line program`bonesis-reprogramming`, provided alongside the `bonesis` Python package. We detail its usage in each case." ] }, { "cell_type": "markdown", "id": "eed44f65", "metadata": {}, "source": [ "## Marker reprogramming of Boolean networks\n", "\n", "We first consider the reprogramming of a single BN $f$ of dimension $n$. In the framework of *BoNesis*, this means the domain of BNs is the singleton $\\mathbb F = \\{ f \\}$.\n", "\n", "A marker $M$ is a map associating a subset of components of $f$ to a Boolean value. For instance, $M = \\{ 1\\mapsto 0, 3\\mapsto 1\\}$ is the marker where component $1$ is $0$ and component $3$ is $1$. We denote by $dom(M)$ the domain of the map $M$, i.e., in our example $dom(M) = \\{ 1, 3\\}$.\n", "Given a configuration $x\\in \\mathbb B^n$, we say $x$ matches with a marker $M$, denoted by $x\\models M$, if and only if $\\forall i\\in dom(M), x_i=M(i)$.\n", "Given a set of configurations $A\\subseteq \\mathbb B^n$, we say $A$ matches with a marker $M$ if and only if each of its configurations match with $M$ ($\\forall x\\in A, x\\models M$).\n", "Given $k\\in\\mathbb N$, we denote by $\\mathbb M^{\\leq k}$ the sets of maps associating at most $k$ components among $\\{1, \\cdots, n\\}$ to a Boolean value. \n", "\n", "The objective of marker-reprogramming is to identify perturbations so that all the fixed points/attractors of the perturbed $f$ match with the marker $M$. The source-marker reprogramming then focuses on the fixed points/attractors reachable from a given initial configuration only, thus potentially requiring fewer perturbations.\n", "\n", "\n", "A very important aspect of marker reprogramming is that it accounts for the creation and deletion of attractors due to the perturbation. Thus, in general, the attractors of the reprogrammed BN are different from the attractors of the input (wild-type) BN.\n", "\n", "In this section, we tackle the following instantiations of the reprogramming problem:\n", "\n", "1. Marker reprogramming of fixed points (*P1*);\n", "2. Source-marker reprogramming of fixed points (*P2*);\n", "3. Marker reprogramming of attractors (*P3*);\n", "4. Source-marker reprogramming of attractors (*P4*).\n", "\n", "In each case, we briefly study the complexity of the associated decision problem (existence of a perturbation given the desired reprogramming property), and give the Python and command line recipe to identify the perturbations with *BoNesis*.\n", "The following table summarizes the results, with the complexity in the locally-monotone case and command line usage:\n", "\n", "| Problem | Complexity | Command line |\n", "|:---:|:---|:---|\n", "| P1 | $\\exists\\forall$ | `[base] --fixpoints`\n", "| P2 | $\\exists\\forall$ | `[base] --fixpoints --reachable-from z`\n", "| P3 | $\\exists\\forall\\exists$ | `[base]`\n", "| P4 | $\\exists\\forall\\exists$ | `[base] --reachable-from z`\n", "\n", "where `[base]` is the command line `bonesis-reprogramming model.bnet M k`, with `model.bnet` the path to a file in [BooleanNet format](http://colomoto.org/biolqm/doc/format-bnet.html), `M` specifies the marker as a JSON map, `k` is the maximum number of simultaneous perturbations, and `z` is the initial configuration as a JSON map.\n", "For instance,\n", "```bash\n", "bonesis-reprogramming model.bnet '{\"A\": 0, \"C\": 1}' 3 \\\n", " --reachable-from '{\"A\":1, \"B\":0, \"C\":0,\"D\":0}'\n", "```" ] }, { "cell_type": "markdown", "id": "9b467bfe", "metadata": {}, "source": [ "### Marker-reprogramming of fixed points (P1)\n", "\n", "We identify the perturbations $P$ of at most $k$ components so that all the fixed points of $f/P$ match with the given marker $M$. The associated decision problem can be expressed as the following $\\exists\\forall$-expression, hence being at most in $\\Sigma_2^{\\mathrm P}$:\n", "\n", "\\begin{equation}\n", "\\exists P\\in \\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, (f/P)(x) = x \\Rightarrow x\\models M\n", "\\end{equation}\n", "\n", "\"There exists a perturbation being a map of at most $k$ components to a Boolean value, such that for all configurations $x\\in\\mathbb B^n$, if $x$ is a fixed point of the perturbed BN $(f/P)$, then $x$ matches with the marker $M$\".\n", "\n", "Remark that any BN having no fixed point verify the above equation with an empty perturbation. Thus, in practice, one may also expect that the perturbed BN possesses at least one fixed point:\n", "\n", "\\begin{equation}\n", "\\exists P\\in \\mathbb M^{\\leq k}, \\exists y\\in\\mathbb B^n, (f/P)(y) = y, \\forall x\\in\\mathbb B^n, (f/P)(x) = x \\Rightarrow x\\models M\\enspace.\n", "\\end{equation}\n", "\n", "With the *BoNesis* Python interface, this reprogramming property can be declared as follows, where `f` is a BN, `M` the marker (specified as Python dictionary associating a subset of components to a Boolean value), and `k` the maximum number of components that can be perturbed (at most $n$):" ] }, { "cell_type": "code", "execution_count": 3, "id": "c25bc153", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.090877Z", "iopub.status.busy": "2022-07-22T16:22:17.090779Z", "iopub.status.idle": "2022-07-22T16:22:17.093488Z", "shell.execute_reply": "2022-07-22T16:22:17.093233Z" } }, "outputs": [], "source": [ "def marker_reprogramming_fixpoints(f: BooleanNetwork, \n", " M: dict[str,bool],\n", " k: int, ensure_exists:bool=True):\n", " # f: Boolean network; M: marker; k: maximum number of components to perturb\n", " bo = bonesis.BoNesis(f)\n", " P = bo.Some(max_size=k) # perturbations to identify\n", " with bo.mutant(P):\n", " # impose that all the fixed points of the perturbed BN match with M\n", " bo.all_fixpoints(bo.obs(M))\n", " if ensure_exists:\n", " # impose the existence of at least one fixed point matching with M\n", " bo.fixed(~bo.obs(M)) \n", " return P.assignments()" ] }, { "cell_type": "markdown", "id": "f2d74273", "metadata": {}, "source": [ "The line `bo = bonesis.BoNesis(f)` instantiates a *BoNesis* object `bo` with the domain `f`. In this section, we assume that `f` is a single Boolean network. It can be either the path to a BooleanNet file, a `minibn` object, for instance as returned by the `biolqm.to_minibn` function for importing models from various formats, or a Python dictionary, associating components to a Boolean function. Examples are given below.\n", "Then, the line `P = bo.Some(max_size=k)` declares a variable that will consist of a map associating at most `k` components to a Boolean value (the perturbation to be identified).\n", "The instruction `with bo.mutant(P)` opens a context where dynamical properties will be verified against the BN `f` with the perturbation `P` applied.\n", "Within this mutant context, we declare with `bo.all_fixpoints(bo.obs(M))` that each fixed point of the perturbed model matches with `M`. Moreover, whenever `ensure_exists` is true, the constraint `bo.fixed(~bo.obs(M))` imposes that the configuration associated with `M` (`~bo.obs(M)`) is a fixed point.\n", "Finally, `P.assignments()` returns an iterator over all the possible assignments of `P` that fulfill the above dynamical properties.\n", "\n", "The corresponding command line is of the form\n", "```bash\n", "bonesis-reprogramming model.bnet M k --fixpoints\n", "```\n", "where `model.bnet` is a BN encoded in BooleanNet format, `M` specifies the marker as a JSON map, and `k` is the maximum number of perturbations.\n", "The existence of at least one fixed point can be lifted with the option `--allow-no-fixpoint`." ] }, { "cell_type": "markdown", "id": "e0563d16", "metadata": {}, "source": [ "*Example.* We illustrate the marker-reprogramming of fixed points on a small toy BN example, which has no fixed point. In the following, we use `colomoto.minibn.BooleanNetwork` to define this BN." ] }, { "cell_type": "code", "execution_count": 4, "id": "28a2730d", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.098278Z", "iopub.status.busy": "2022-07-22T16:22:17.098155Z", "iopub.status.idle": "2022-07-22T16:22:17.101174Z", "shell.execute_reply": "2022-07-22T16:22:17.100841Z" } }, "outputs": [ { "data": { "text/plain": [ "A <- B\n", "B <- !A\n", "C <- !A&B" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = BooleanNetwork({\n", " \"A\": \"B\",\n", " \"B\": \"!A\",\n", " \"C\": \"!A & B\"\n", "})\n", "f" ] }, { "cell_type": "markdown", "id": "72c806cd", "metadata": {}, "source": [ "This example BN has two components in negative feedback: they will oscillate forever. The state of the third component `C` is then determined by the state of the oscillating components. The following command returns its influence graph:" ] }, { "cell_type": "code", "execution_count": 5, "id": "383db273", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.102675Z", "iopub.status.busy": "2022-07-22T16:22:17.102546Z", "iopub.status.idle": "2022-07-22T16:22:17.262315Z", "shell.execute_reply": "2022-07-22T16:22:17.260458Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Influence graph of the example BN for P1" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "-\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "-\n", "\n", "\n", "\n", "B->A\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "+\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.influence_graph()" ] }, { "cell_type": "markdown", "id": "15e3ca01", "metadata": {}, "source": [ "With the (fully) asynchronous update mode, the system has a single attractor, consisting of all the configurations of the network." ] }, { "cell_type": "code", "execution_count": 6, "id": "245c991a", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.270649Z", "iopub.status.busy": "2022-07-22T16:22:17.270108Z", "iopub.status.idle": "2022-07-22T16:22:17.377138Z", "shell.execute_reply": "2022-07-22T16:22:17.376363Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Fully-asynchronous dynamics of the example BN for P1" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "000\n", "\n", "000\n", "\n", "\n", "\n", "010\n", "\n", "010\n", "\n", "\n", "\n", "000->010\n", "\n", "\n", "\n", "\n", "\n", "110\n", "\n", "110\n", "\n", "\n", "\n", "010->110\n", "\n", "\n", "\n", "\n", "\n", "011\n", "\n", "011\n", "\n", "\n", "\n", "010->011\n", "\n", "\n", "\n", "\n", "\n", "100\n", "\n", "100\n", "\n", "\n", "\n", "100->000\n", "\n", "\n", "\n", "\n", "\n", "110->100\n", "\n", "\n", "\n", "\n", "\n", "111\n", "\n", "111\n", "\n", "\n", "\n", "011->111\n", "\n", "\n", "\n", "\n", "\n", "111->110\n", "\n", "\n", "\n", "\n", "\n", "101\n", "\n", "101\n", "\n", "\n", "\n", "111->101\n", "\n", "\n", "\n", "\n", "\n", "101->100\n", "\n", "\n", "\n", "\n", "\n", "001\n", "\n", "001\n", "\n", "\n", "\n", "101->001\n", "\n", "\n", "\n", "\n", "\n", "001->000\n", "\n", "\n", "\n", "\n", "\n", "001->011\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f.dynamics(\"asynchronous\")" ] }, { "cell_type": "markdown", "id": "401051a5", "metadata": {}, "source": [ "Recall that the fixed points are identical in asynchronous and MP. We use [`mpbn`](https://github.com/bnediction/mpbn) to analyze the dynamical properties with the MP update mode:" ] }, { "cell_type": "code", "execution_count": 7, "id": "bae873f6", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.380366Z", "iopub.status.busy": "2022-07-22T16:22:17.380159Z", "iopub.status.idle": "2022-07-22T16:22:17.390002Z", "shell.execute_reply": "2022-07-22T16:22:17.389381Z" } }, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mf = mpbn.MPBooleanNetwork(f)\n", "list(mf.fixedpoints())" ] }, { "cell_type": "code", "execution_count": 8, "id": "76fbc814", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.393089Z", "iopub.status.busy": "2022-07-22T16:22:17.392901Z", "iopub.status.idle": "2022-07-22T16:22:17.400545Z", "shell.execute_reply": "2022-07-22T16:22:17.399870Z" } }, "outputs": [ { "data": { "text/plain": [ "[{'A': '*', 'B': '*', 'C': '*'}]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(mf.attractors())" ] }, { "cell_type": "markdown", "id": "58f061fd", "metadata": {}, "source": [ "Indeed, the network has no fixed points, and its attractor is the full hypercube of dimension 3.\n", "\n", "Using the `marker_reprogramming_fixpoints` snippet defined above, we identify all perturbations of at most 2 components which ensure that (1) all the fixed points have `C` active, and (2) at least one fixed point exists:" ] }, { "cell_type": "code", "execution_count": 9, "id": "36c7e093", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.403441Z", "iopub.status.busy": "2022-07-22T16:22:17.403175Z", "iopub.status.idle": "2022-07-22T16:22:17.417699Z", "shell.execute_reply": "2022-07-22T16:22:17.417175Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'A': 0}, {'C': 1, 'B': 0}, {'A': 1, 'C': 1}, {'B': 1, 'C': 1}]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(f, {\"C\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "1070b5f1", "metadata": {}, "source": [ "Indeed, fixing `A` to 0 breaks the negative feedback, and make `B` converge to 1. There, `C` converges to state 1.\n", "Then, remark that fixing `C` to 1 is not enough to fulfill the property, as `A` and `B` still oscillate. Thus, one of these 2 must be fixed as well, to any value. The solution `{'A': 0, 'C': 1}` is not returned as `{'A': 0}` is sufficient to acquire the desired dynamical property.\n", "\n", "In our *BoNesis* code snippet defined above, by default we ensure that the perturbed BN possesses at least one fixed point. When relaxing this constraint, we obtain that the empty perturbation is the (unique) minimal solution, as `f` has no fixed point." ] }, { "cell_type": "code", "execution_count": 10, "id": "9f07db28", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.420202Z", "iopub.status.busy": "2022-07-22T16:22:17.420028Z", "iopub.status.idle": "2022-07-22T16:22:17.428844Z", "shell.execute_reply": "2022-07-22T16:22:17.428425Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{}]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(f, {\"C\": 1}, 2, ensure_exists=False))" ] }, { "cell_type": "markdown", "id": "98d0be69", "metadata": {}, "source": [ "In the following, we demonstrate how to perform the same computation with the command line. By default, the reprogramming of fixed points adds the constraint that at least one fixed point must exist." ] }, { "cell_type": "code", "execution_count": 11, "id": "16678aed", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.430775Z", "iopub.status.busy": "2022-07-22T16:22:17.430657Z", "iopub.status.idle": "2022-07-22T16:22:17.796099Z", "shell.execute_reply": "2022-07-22T16:22:17.794337Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A, B\r\n", "B, !A\r\n", "C, !A&B\r\n" ] } ], "source": [ "with open(\"example1.bnet\", \"w\") as fp:\n", " fp.write(f.source())\n", "%cat example1.bnet" ] }, { "cell_type": "code", "execution_count": 12, "id": "1f391cba", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:17.805014Z", "iopub.status.busy": "2022-07-22T16:22:17.804359Z", "iopub.status.idle": "2022-07-22T16:22:18.732896Z", "shell.execute_reply": "2022-07-22T16:22:18.730889Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'A': 0}\r\n", "{'C': 1, 'B': 0}\r\n", "{'A': 1, 'C': 1}\r\n", "{'B': 1, 'C': 1}\r\n" ] } ], "source": [ "!bonesis-reprogramming example1.bnet '{\"C\": 1}' 2 --fixpoints" ] }, { "cell_type": "markdown", "id": "b983d13f", "metadata": {}, "source": [ "Adding the option `--allow-no-fixpoint` would return an empty perturbation as unique minimal solution." ] }, { "cell_type": "markdown", "id": "1ae86105", "metadata": {}, "source": [ "### Source-marker reprogramming of fixed points (P2)\n", "\n", "Given an initial configuration $z$, we identify the perturbations $P$ of at most $k$ components so that all the fixed points of $f/P$ that are reachable from $z$ in $f/P$ match with the given marker $M$.\n", "The associated decision problem can be expressed as the following $\\exists\\forall$-expression, hence being at most in $\\Sigma_2^{\\mathrm P}$:\n", "\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, ((f/P)(x)=x \\wedge \\operatorname{reach}_P(z,x))\\implies x\\models M\n", "\\end{equation}\n", "\n", "\"There exists a perturbation $P$ such that for any configuration $x\\in\\mathbb B^n$,\n", "if $x$ is a fixed point of the perturbed BN $(f/P)$, and $x$ is reachable from $z$ in $(f/P)$, then $x$ must match with $M$\".\n", "\n", "As explained in the Method section, the reachability property boils down to computing the smallest trap space containing $z$: if it contains the fixed point $x$, then $x$ is reachable from $z$ with the MP update mode.\n", "\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, ((f/P)(x)=x \\wedge \n", "x\\in\\operatorname{TS}_P(z))\\implies x\\models M\\enspace.\n", "\\end{equation}\n", "\n", "As with the previous case, in practice we may also want that there exists at least one fixed point reachable from $z$.\n", "\n", "With the *BoNesis* Python interface, this reprogramming property is declared as follows, where `f` is a BN, `z` the initial configuration (Python dictionary), `M` the marker, and `k` the maximum number of components that can be perturbed (at most $n$):" ] }, { "cell_type": "code", "execution_count": 13, "id": "dc459f94", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.741733Z", "iopub.status.busy": "2022-07-22T16:22:18.741149Z", "iopub.status.idle": "2022-07-22T16:22:18.754340Z", "shell.execute_reply": "2022-07-22T16:22:18.752590Z" } }, "outputs": [], "source": [ "def source_marker_reprogramming_fixpoints(f: BooleanNetwork,\n", " z: dict[str,bool],\n", " M: dict[str,bool],\n", " k: int):\n", " # f: Boolean network; z: initial configuration;\n", " # M: marker; k: maximum number of components to perturb\n", " bo = bonesis.BoNesis(f)\n", " P = bo.Some(max_size=k) # perturbation to identify\n", " with bo.mutant(P):\n", " # all the fixed points reachable from z match with M\n", " ~bo.obs(z) >> \"fixpoints\" ^ {bo.obs(M)}\n", " # at least one fixed point matching with M is reachable from z\n", " ~bo.obs(z) >= bo.fixed(~bo.obs(M))\n", " return P.assignments()" ] }, { "cell_type": "markdown", "id": "8a2b4423", "metadata": {}, "source": [ "Compared to the previous code snippet, this function relies on specific operators to restrict the properties to the fixed point reachable from `z`.\n", "The instruction `~bo.obs(z)` refers to a specific configuration matching with `z`;\n", "`~bo.obs(z) >> \"fixpoints\" ^ {bo.obs(M)}` specifies that all the fixed points reachable from such configuration have to match with at least one configuration given in the set `{bo.obs(M)}`, i.e., `M` in this case.\n", "This property is satisfied whenever no fixed point are reachable. Thus, the next line ensures that at least one fixed point is reachable from the configuration associated with `z`: `bo.fixed(~bo.obs(M))` refers to one configuration which is a fixed point (in the perturbed BN), and which matches with `M`. Then, the binary operator `>=` declares the existence of a trajectory from its left to its right configuration.\n", "\n", "Notice that with this formulation, in the case whenever `z` is only partially defined (some components are not associated to a Boolean value), a perturbation is returned as long as there exists at least one fully-defined configuration matching with $z$ which fulfil the specified dynamical properties.\n", "\n", "The corresponding command line is of the form\n", "```bash\n", "bonesis-reprogramming model.bnet M k --fixpoints --reachable-from z\n", "```\n", "where `model.bnet` is a BN encoded in BooleanNet format, `M` specifies the marker as a JSON map, `k` is the maximum number of perturbations, and `z` is the initial configuration as a JSON map.\n", "The existence of at least one fixed point can be lifted with the option `--allow-no-fixpoint`." ] }, { "cell_type": "markdown", "id": "19d4102f", "metadata": {}, "source": [ "*Example.* Let us consider the following toy BN with two positive feedback cycles:" ] }, { "cell_type": "code", "execution_count": 14, "id": "4204531d", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.761930Z", "iopub.status.busy": "2022-07-22T16:22:18.761397Z", "iopub.status.idle": "2022-07-22T16:22:18.806400Z", "shell.execute_reply": "2022-07-22T16:22:18.805948Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Influence graph of the example BN for P2" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "+\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->A\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "+\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "C->D\n", "\n", "\n", "-\n", "\n", "\n", "\n", "D->C\n", "\n", "\n", "-\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = BooleanNetwork({\n", " \"A\": \"B\",\n", " \"B\": \"A\",\n", " \"C\": \"!D & (A|B)\",\n", " \"D\": \"!C\"\n", "})\n", "f.influence_graph()" ] }, { "cell_type": "markdown", "id": "f9f82c6c", "metadata": {}, "source": [ "This BN has 3 fixed points, 2 of which are reachable from the configuration where `A` and `B` are active, and `C` and `D` inactive:" ] }, { "cell_type": "code", "execution_count": 15, "id": "535121b6", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.808350Z", "iopub.status.busy": "2022-07-22T16:22:18.808234Z", "iopub.status.idle": "2022-07-22T16:22:18.833849Z", "shell.execute_reply": "2022-07-22T16:22:18.833331Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Fully-asynchronous dynamics of the example BN for P2 from the configuration $1100$" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1100\n", "\n", "1100\n", "\n", "\n", "\n", "1110\n", "\n", "1110\n", "\n", "\n", "\n", "1100->1110\n", "\n", "\n", "\n", "\n", "\n", "1101\n", "\n", "1101\n", "\n", "\n", "\n", "1100->1101\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z = {\"A\": 1, \"B\": 1, \"C\": 0, \"D\": 0}\n", "f.dynamics(\"asynchronous\", init=z)" ] }, { "cell_type": "code", "execution_count": 16, "id": "2d492a49", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.835736Z", "iopub.status.busy": "2022-07-22T16:22:18.835572Z", "iopub.status.idle": "2022-07-22T16:22:18.842360Z", "shell.execute_reply": "2022-07-22T16:22:18.841940Z" } }, "outputs": [ { "data": { "text/plain": [ "[{'A': 0, 'B': 0, 'C': 0, 'D': 1},\n", " {'A': 1, 'B': 1, 'C': 0, 'D': 1},\n", " {'A': 1, 'B': 1, 'C': 1, 'D': 0}]" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(mpbn.MPBooleanNetwork(f).fixedpoints())" ] }, { "cell_type": "code", "execution_count": 17, "id": "4a7de3b3", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.844013Z", "iopub.status.busy": "2022-07-22T16:22:18.843885Z", "iopub.status.idle": "2022-07-22T16:22:18.849894Z", "shell.execute_reply": "2022-07-22T16:22:18.849609Z" } }, "outputs": [ { "data": { "text/plain": [ "[{'A': 1, 'B': 1, 'C': 1, 'D': 0}, {'A': 1, 'B': 1, 'C': 0, 'D': 1}]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(mpbn.MPBooleanNetwork(f).fixedpoints(reachable_from=z))" ] }, { "cell_type": "markdown", "id": "528a7364", "metadata": {}, "source": [ "Let us compare the results of the global marker-reprogramming of fixed points (P1) with the source-marker reprogramming of fixed points (P2), the objective being to have fixed points having `C` active.\n", "In the first case, putting aside the perturbation of `C`, this necessitates to act on either `A` or `B` to prevent the existence of the fixed points where `A`, `B` and `C` are inactive:" ] }, { "cell_type": "code", "execution_count": 18, "id": "5bdbd976", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.851544Z", "iopub.status.busy": "2022-07-22T16:22:18.851405Z", "iopub.status.idle": "2022-07-22T16:22:18.860579Z", "shell.execute_reply": "2022-07-22T16:22:18.860299Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'A': 1, 'D': 0}, {'B': 1, 'D': 0}, {'C': 1}]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(f, {\"C\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "365ebe6e", "metadata": {}, "source": [ "Considering only the fixed points reachable from the configuration `z`, there is no need to act on `A` or `B`:" ] }, { "cell_type": "code", "execution_count": 19, "id": "ca3b3cb6", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.862304Z", "iopub.status.busy": "2022-07-22T16:22:18.862161Z", "iopub.status.idle": "2022-07-22T16:22:18.871908Z", "shell.execute_reply": "2022-07-22T16:22:18.871546Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'D': 0}, {'C': 1}]" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(source_marker_reprogramming_fixpoints(f, z, {\"C\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "f5135f2d", "metadata": {}, "source": [ "The command line program `bonesis-reprogramming` can perform P2 by specifying the `--rechable-from` option giving the initial configuration in JSON format:" ] }, { "cell_type": "code", "execution_count": 20, "id": "d759f129", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.873539Z", "iopub.status.busy": "2022-07-22T16:22:18.873401Z", "iopub.status.idle": "2022-07-22T16:22:18.875679Z", "shell.execute_reply": "2022-07-22T16:22:18.875407Z" } }, "outputs": [], "source": [ "with open(\"example2.bnet\", \"w\") as fp:\n", " fp.write(f.source())" ] }, { "cell_type": "code", "execution_count": 21, "id": "73de5aad", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:18.877162Z", "iopub.status.busy": "2022-07-22T16:22:18.877034Z", "iopub.status.idle": "2022-07-22T16:22:19.755334Z", "shell.execute_reply": "2022-07-22T16:22:19.753227Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'D': 0}\r\n", "{'C': 1}\r\n" ] } ], "source": [ "!bonesis-reprogramming example2.bnet '{\"C\": 1}' 2 --fixpoints \\\n", " --reachable-from '{\"A\": 1, \"B\": 1, \"C\": 0, \"D\": 0}'" ] }, { "cell_type": "markdown", "id": "bfa5bc2c", "metadata": {}, "source": [ "### Marker reprogramming of attractors (P3)\n", "\n", "We identify the perturbations $P$ of at most $k$ components so that the configurations of the all the attractors of $f/P$ match with the given marker $M$ (i.e., in each attractor, the specified markers cannot oscillate).\n", "The associated decision problem can be expressed as follows:\n", "\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, \\operatorname{IN-ATTRACTOR}_P(x) \\implies x\\models M\n", "\\end{equation}\n", "\n", "(\"There exists a perturbation $P$ of at most $k$ components, such that for all configurations $x$, if $x$ belongs to an attractor of the perturbed BN $f/P$, then $x$ matches with the specified markers $M$\")\n", "\n", "By restricting the range of the universal part of the equation to the configurations which do not match with the marker $M$, we obtain:\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n: x\\not\\models M, \\neg\\operatorname{IN-ATTRACTOR}_P(x)\n", "\\end{equation}\n", "\n", "The $\\operatorname{IN-ATTRACTOR}$ property being itself a quantified Boolean expression, we obtain the following $\\exists\\forall\\exists$-expression:\n", "\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n: x\\not\\models M, \\exists y\\in\\mathbb B^n,\n", " y\\in \\operatorname{TS}_P(x), \\operatorname{TS}_P(y) \\neq \\operatorname{TS}_P(x)\n", "\\end{equation}\n", "\n", "The problem of satisfiability of this quantified Boolean expression is beyond the expressiveness power of ASP which is limited to $\\exists\\forall$-expressions.\n", "Nevertheless, we can approach this problem by its complementary: the existence of perturbations of size $k$ such that at least one configuration belonging to an attractor does *not* match with the marker $M$.\n", "This complementary problem can be expressed with this following expression\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\exists x\\in\\mathbb B^n,x\\not\\models M \\wedge \\operatorname{IN-ATTRACTOR}_P(x)\n", "\\end{equation}\n", "which is an $\\exists\\forall$-expression:\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\exists x\\in\\mathbb B^n, x\\not\\models M\\wedge \\forall y\\in\\mathbb B^n, y\\in \\operatorname{TS}_P(x) \\implies \\operatorname{TS}_P(y) \\neq \\operatorname{TS}_P(x)\n", "\\enspace.\n", "\\end{equation}\n", "\n", "Because the domain of candidate perturbations $\\mathbb M^{\\leq k}$ is finite, one can first resolve the complementary problem, giving all bad perturbations, and returns its complement.\n", "\n", "Notice that this approach is highly combinatorics, and is likely limited to identifying perturbations of small size. However, to our knowledge, this is the first implemented method which addresses the complement reprogramming of MP attractors, i.e., of the minimal trap spaces of the BN.\n", "\n", "With the *BoNesis* Python interface, this reprogramming property is declared as follows, where `f` is a BN, `M` the marker, and `k` the maximum number of components that can be perturbed (at most $n$):" ] }, { "cell_type": "code", "execution_count": 22, "id": "309449de", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.764409Z", "iopub.status.busy": "2022-07-22T16:22:19.763701Z", "iopub.status.idle": "2022-07-22T16:22:19.775581Z", "shell.execute_reply": "2022-07-22T16:22:19.773736Z" } }, "outputs": [], "source": [ "def marker_reprogramming(f: BooleanNetwork,\n", " M: dict[str,bool],\n", " k: int):\n", " bo = bonesis.BoNesis(f)\n", " coP = bo.Some(max_size=k)\n", " with bo.mutant(coP):\n", " x = bo.cfg()\n", " bo.in_attractor(x)\n", " x != bo.obs(M)\n", " return coP.complementary_assignments()" ] }, { "cell_type": "markdown", "id": "5860db18", "metadata": {}, "source": [ "The idea of the above code snippet is to declare the property of being a bad perturbation (`coP`). In the context of this perturbation, we declare with `x=bo.cfg()` a configuration. Then, `bo.in_attractor(x)` imposes that `x` belongs to an attractor (minimal trap space) of the perturbed BN; and the `x != bo.obs(M)` instruction adds the constraint that `x` must not match with `M`.\n", "\n", "The `.complementary_assignments()` method performs the computation of the complement of solutions. It solves the above problem with perturbation sizes ranging from 0 to `k`, and returns complement minimal perturbations only.\n", "\n", "The corresponding command line is of the form\n", "```bash\n", "bonesis-reprogramming model.bnet M k\n", "```\n", "where `model.bnet` is a BN encoded in BooleanNet format, `M` specifies the marker as a JSON map, `k` is the maximum number of perturbations." ] }, { "cell_type": "markdown", "id": "d07855e1", "metadata": {}, "source": [ "*Example.* Let us consider the following BN:" ] }, { "cell_type": "code", "execution_count": 23, "id": "fcfed413", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.783380Z", "iopub.status.busy": "2022-07-22T16:22:19.782738Z", "iopub.status.idle": "2022-07-22T16:22:19.831852Z", "shell.execute_reply": "2022-07-22T16:22:19.831401Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Influence graph of the example BN for P3" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "-\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->A\n", "\n", "\n", "-\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "-\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "C->D\n", "\n", "\n", "+\n", "\n", "\n", "\n", "E\n", "\n", "E\n", "\n", "\n", "\n", "C->E\n", "\n", "\n", "-\n", "\n", "\n", "\n", "D->C\n", "\n", "\n", "-\n", "\n", "\n", "\n", "E->D\n", "\n", "\n", "+\n", "\n", "\n", "\n", "E->E\n", "\n", "\n", "-\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = mpbn.MPBooleanNetwork({\n", " \"A\": \"!B\",\n", " \"B\": \"!A\",\n", " \"C\": \"A & !B & !D\",\n", " \"D\": \"C | E\",\n", " \"E\": \"!C & !E\",\n", "})\n", "f.influence_graph()" ] }, { "cell_type": "markdown", "id": "1574f08c", "metadata": {}, "source": [ "Essentially, `A` and `B` always stabilize to opposite states. Whenever `A` is active (and `B` inactive) then `C` will oscillate, otherwise it stabilizes to 0. In each case `D` and `E` oscillate.\n", "This lead to the following MP attractors:" ] }, { "cell_type": "code", "execution_count": 24, "id": "091253f1", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.833875Z", "iopub.status.busy": "2022-07-22T16:22:19.833751Z", "iopub.status.idle": "2022-07-22T16:22:19.849488Z", "shell.execute_reply": "2022-07-22T16:22:19.849119Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABCDE
0010**
110***
\n", "
" ], "text/plain": [ " A B C D E\n", "0 0 1 0 * *\n", "1 1 0 * * *" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tabulate(list(f.attractors()))" ] }, { "cell_type": "markdown", "id": "f51cc569", "metadata": {}, "source": [ "Let us say that our objective is to reprogram the BN such that all the attractors of the component `C` fixed to 1.\n", "The reprogramming of fixed points (P1) gives the following solutions:" ] }, { "cell_type": "code", "execution_count": 25, "id": "ad91c340", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.851375Z", "iopub.status.busy": "2022-07-22T16:22:19.851259Z", "iopub.status.idle": "2022-07-22T16:22:19.860962Z", "shell.execute_reply": "2022-07-22T16:22:19.860587Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'D': 0}, {'C': 1}]" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(f, {\"C\": 1}, 3))" ] }, { "cell_type": "markdown", "id": "a5564cb7", "metadata": {}, "source": [ "Putting aside the trivial solution of perturbing `C`, let us analyze the BN perturbed with the `D` forced to 0:" ] }, { "cell_type": "code", "execution_count": 26, "id": "df834f4f", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.862800Z", "iopub.status.busy": "2022-07-22T16:22:19.862683Z", "iopub.status.idle": "2022-07-22T16:22:19.872324Z", "shell.execute_reply": "2022-07-22T16:22:19.871977Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABCDE
10100*
010100
\n", "
" ], "text/plain": [ " A B C D E\n", "1 0 1 0 0 *\n", "0 1 0 1 0 0" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pf = f.copy()\n", "pf[\"D\"] = 0\n", "tabulate(pf.attractors())" ] }, { "cell_type": "markdown", "id": "41fd5c72", "metadata": {}, "source": [ "The (only) fixed point of the network indeed has `C` active. However, it possesses another (cyclic) attractor, where `C` is inactive.\n", "This example points out that focusing on fixed point reprogramming may lead to predicting perturbations which are not sufficient to ensure that all the attractors show the desired marker.\n", "\n", "The complete attractor reprogramming returns that the perturbation of `D` must be coupled with a perturbation of `A` or `B`, in this case to destroy the cyclic attractor." ] }, { "cell_type": "code", "execution_count": 27, "id": "dac28185", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.874038Z", "iopub.status.busy": "2022-07-22T16:22:19.873927Z", "iopub.status.idle": "2022-07-22T16:22:19.904381Z", "shell.execute_reply": "2022-07-22T16:22:19.904033Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'C': 1}, {'D': 0, 'B': 0}, {'D': 0, 'A': 1}]" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming(f, {\"C\": 1}, 3))" ] }, { "cell_type": "markdown", "id": "eca324ad", "metadata": {}, "source": [ "The same results can be obtained using the command line as follows." ] }, { "cell_type": "code", "execution_count": 28, "id": "a7150b98", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.906165Z", "iopub.status.busy": "2022-07-22T16:22:19.906053Z", "iopub.status.idle": "2022-07-22T16:22:19.908543Z", "shell.execute_reply": "2022-07-22T16:22:19.908211Z" } }, "outputs": [], "source": [ "with open(\"example3.bnet\", \"w\") as fp:\n", " fp.write(f.source())" ] }, { "cell_type": "code", "execution_count": 29, "id": "92991d0c", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:19.910131Z", "iopub.status.busy": "2022-07-22T16:22:19.910027Z", "iopub.status.idle": "2022-07-22T16:22:20.807156Z", "shell.execute_reply": "2022-07-22T16:22:20.804998Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'C': 1}\r\n", "{'D': 0, 'B': 0}\r\n", "{'D': 0, 'A': 1}\r\n" ] } ], "source": [ "!bonesis-reprogramming example3.bnet '{\"C\": 1}' 3" ] }, { "cell_type": "markdown", "id": "94c328ff", "metadata": {}, "source": [ "In other cases, the reprogramming of attractors may also lead to fewer required perturbations than focusing on fixed points, provided we enforce the existence of at least one fixed point. This can be illustrated with the following example:" ] }, { "cell_type": "code", "execution_count": 30, "id": "0996b71c", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.815844Z", "iopub.status.busy": "2022-07-22T16:22:20.815290Z", "iopub.status.idle": "2022-07-22T16:22:20.904649Z", "shell.execute_reply": "2022-07-22T16:22:20.903718Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Influence graph of the example BN $g$ for P3" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "+\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->A\n", "\n", "\n", "-\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "+\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "C->D\n", "\n", "\n", "+\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = mpbn.MPBooleanNetwork({\n", " \"A\": \"!B\",\n", " \"B\": \"A\",\n", " \"C\": \"A & B\",\n", " \"D\": \"C\"\n", "})\n", "g.influence_graph()" ] }, { "cell_type": "markdown", "id": "7f106c56", "metadata": {}, "source": [ "Unperturbed, this network has a single cyclic attractor, as `A` and `B` are in a sustained oscillation." ] }, { "cell_type": "code", "execution_count": 31, "id": "ac5322ad", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.908501Z", "iopub.status.busy": "2022-07-22T16:22:20.908182Z", "iopub.status.idle": "2022-07-22T16:22:20.927954Z", "shell.execute_reply": "2022-07-22T16:22:20.927176Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABCD
0****
\n", "
" ], "text/plain": [ " A B C D\n", "0 * * * *" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tabulate(g.attractors())" ] }, { "cell_type": "markdown", "id": "67785d75", "metadata": {}, "source": [ "Enforcing that all attractors have `D` fixed to 1 can be achieved either by perturbing `A`, or by perturbing only `C`, letting `A` and `B` oscillate." ] }, { "cell_type": "code", "execution_count": 32, "id": "a1d7d335", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.931188Z", "iopub.status.busy": "2022-07-22T16:22:20.930959Z", "iopub.status.idle": "2022-07-22T16:22:20.954864Z", "shell.execute_reply": "2022-07-22T16:22:20.954396Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'A': 1}, {'C': 1}, {'D': 1}]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming(g, {\"D\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "e72d9a6c", "metadata": {}, "source": [ "However, besides the forced activation of `A`, ensuring that all and at least one fixed point have `D` active always requires perturbing at least two components." ] }, { "cell_type": "code", "execution_count": 33, "id": "93efa422", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.957023Z", "iopub.status.busy": "2022-07-22T16:22:20.956876Z", "iopub.status.idle": "2022-07-22T16:22:20.967548Z", "shell.execute_reply": "2022-07-22T16:22:20.967186Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'A': 1},\n", " {'D': 1, 'A': 0},\n", " {'D': 1, 'B': 0},\n", " {'B': 1, 'D': 1},\n", " {'C': 1, 'A': 0},\n", " {'C': 1, 'B': 0},\n", " {'B': 1, 'C': 1}]" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(g, {\"D\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "353935be", "metadata": {}, "source": [ "### Soure-marker reprograming of attractors (P4)\n", "\n", "Given an initial configuration $z$, we identify the perturbations $P$ of at most $k$ components so that the configurations of the all the attractors of $f/P$ that are reachable from $z$ match with the given marker $M$ (i.e., in each reachable attractor, the specified markers cannot oscillate).\n", "Thus, P4 is the same problem as P3, except that we focus only on attractors reachable from $z$, therefore potentially requiring fewer perturbations.\n", "\n", "The associated decision problem can be expressed as follows:\n", "\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, x\\models M \\vee x\\notin\\bar\\rho^{f/P}_{\\mathrm{mp}}(z) \\vee \\neg\\operatorname{IN-ATTRACTOR}_P(x)\n", "\\end{equation}\n", "\n", "(\"There exists a perturbation $P$ of at most $k$ components, such that for all configurations $x$, either $x$ matches with the marker $M$, or $x$ does not belong to an attractor, or $x$ is not reachable from $z$\").\n", "\n", "By integrating the definition of the $\\operatorname{IN-ATTRACTOR}$ property, we obtain the following $\\exists\\forall\\exists$-expression:\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\forall x\\in\\mathbb B^n, x\\models M \\vee x\\notin\\bar\\rho^{f/P}_{\\mathrm{mp}}(z) \\vee \\exists y\\in\\mathbb B^n,\n", " y\\in \\operatorname{TS}_P(x), \\operatorname{TS}_P(y) \\neq \\operatorname{TS}_P(x)\n", "\\end{equation}\n", "\n", "The resolution of the problem can be approached in a very similar way to P3, i.e., by solving its complement. The equation is almost the same, with the addition that $x$ must be reachable from $z$, leading to the $\\exists\\forall$-expression:\n", "\\begin{equation}\n", "\\exists P\\in\\mathbb M^{\\leq k}, \\exists x\\in\\mathbb B^n, x\\in\\operatorname{TS}_P(z) \\wedge x\\not\\models M\\wedge \\forall y\\in\\mathbb B^n, y\\in \\operatorname{TS}_P(x) \\implies \\operatorname{TS}_P(y) \\neq \\operatorname{TS}_P(x)\n", "\\enspace.\n", "\\end{equation}\n", "\n", "With the *BoNesis* Python interface, this reprogramming property is declared as follows, where `f` is a BN, `z` the initial configuration, `M` the marker, and `k` the maximum number of components that can be perturbed (at most $n$):" ] }, { "cell_type": "code", "execution_count": 34, "id": "e4a9d0a6", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.969281Z", "iopub.status.busy": "2022-07-22T16:22:20.969164Z", "iopub.status.idle": "2022-07-22T16:22:20.972175Z", "shell.execute_reply": "2022-07-22T16:22:20.971819Z" } }, "outputs": [], "source": [ "def source_marker_reprogramming(f: BooleanNetwork,\n", " z: dict[str,bool],\n", " M: dict[str,bool],\n", " k: int):\n", " bo = bonesis.BoNesis(f)\n", " coP = bo.Some(max_size=k)\n", " with bo.mutant(coP):\n", " x = bo.cfg()\n", " bo.in_attractor(x)\n", " x != bo.obs(M)\n", " ~bo.obs(z) >= x\n", " return coP.complementary_assignments()" ] }, { "cell_type": "markdown", "id": "68dc4aca", "metadata": {}, "source": [ "The above code snippet is very similar to the previous `marker_reprogramming`, with the addition of the `~bo.obs(z) >= x` instruction which declares that `x`, a configuration which belongs to an attractor of the perturbed BN and which does not match with `M`, is reachable from `z`." ] }, { "cell_type": "markdown", "id": "5f5f5628", "metadata": {}, "source": [ "The corresponding command line is of the form\n", "```bash\n", "bonesis-reprogramming model.bnet M k --reachable-from z\n", "```\n", "where `model.bnet` is a BN encoded in BooleanNet format, `M` specifies the marker as a JSON map, `k` is the maximum number of perturbations, and `z` is the initial configuration as a JSON map." ] }, { "cell_type": "markdown", "id": "a9814a44", "metadata": {}, "source": [ "*Example.* Let us consider again the BN `f` analyzed in the previous section. By focusing only on attractors reachable from the configuration where `A` is fixed to 1 and other nodes to 0, the reprogramming required to make all attractors have `C` fixed to 1 consists only of fixing `D` to 0. Note that in the specific example, the reprogramming of reachable fixed point would give an equivalent result." ] }, { "cell_type": "code", "execution_count": 35, "id": "1e08a04e", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:20.973735Z", "iopub.status.busy": "2022-07-22T16:22:20.973631Z", "iopub.status.idle": "2022-07-22T16:22:21.006849Z", "shell.execute_reply": "2022-07-22T16:22:21.006494Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'D': 0}, {'C': 1}]" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z = f.zero()\n", "z[\"A\"] = 1\n", "list(source_marker_reprogramming(f, z, {\"C\": 1}, 3))" ] }, { "cell_type": "markdown", "id": "a8107dfb", "metadata": {}, "source": [ "The same results can be obtained using the command line as follows." ] }, { "cell_type": "code", "execution_count": 36, "id": "235ee249", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:21.008533Z", "iopub.status.busy": "2022-07-22T16:22:21.008422Z", "iopub.status.idle": "2022-07-22T16:22:21.905373Z", "shell.execute_reply": "2022-07-22T16:22:21.903326Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'D': 0}\r\n", "{'C': 1}\r\n" ] } ], "source": [ "!bonesis-reprogramming example3.bnet '{\"C\": 1}' 3 \\\n", " --reachable-from '{\"A\": 1, \"B\": 0, \"C\": 0, \"D\": 0}'" ] }, { "cell_type": "markdown", "id": "d273bf21", "metadata": {}, "source": [ "## Reprogramming of ensembles of Boolean networks\n", "\n", "In the previous section, the reprogramming was performed on a single BN, by giving to *BoNesis* the singleton domain of BNs to consider. As described in the Method section, *BoNesis* can reason on ensembles of BNs, either specified explicitly, or implicitly by an influence graph.\n", "The functions defined above can then be directly applied to such ensembles of BNs. In this section, we briefly discuss how the resulting reprogramming solutions should then be interpreted with respect to these ensembles.\n", "\n", "Given a domain of BNs $\\mathbb F$, *BoNesis* returns a solution whenever at least one BN of this domain satisfies the given properties. Intuitively, this means that the logic satisfiability problem is of the form $\\exists f\\in \\mathbb F, \\Phi(f)$.\n", "As detailed in (Chevalier et al., 2019) in the scope of locally-monotone BNs, the size of the \"$f\\in\\mathbb F$\" formula is, in general, exponential (binomial coefficient) with the in-degree of nodes in the influence graph. This complexity is due to the maximum number of clauses a Boolean function can have. Our encoding in *BoNesis* allows specifying an upper bound to this number, which enables tackling very large scale instances although giving access only to a subset of $\\mathbb F$. The encoding of $\\mathbb F$ in *BoNesis* also supports enforcing a canonic representation of BNs in order to offer a non-redundant enumeration of the BNs, at the price of a quadratic size of the formula. However, in our case, as we are only interested in enumerating the perturbations, the canonic form of BNs is not needed.\n", "\n", "In the case of our implementation of marker reprogramming of fixed points (P1 and P2), the expression becomes of the form:\n", "$$\\exists f\\in\\mathbb F, \\exists P\\in\\mathbb M^{\\leq k}, \\cdots$$\n", "Therefore, a perturbation $P$ is returned as soon as it is a reprogramming solution for *at least one* BN of the input domain: $P$ may not work on every BN in $\\mathbb F$, but at least one.\n", "\n", "In the case of our implementation of marker reprogramming of attractors (P3 and P4), because we tackle the complementary problem, the expression becomes of the form:\n", "$$\\exists f\\in\\mathbb F, \\exists coP\\in\\mathbb M^{\\leq k}, \\cdots$$\n", "Therefore, a *bad* perturbation $coP$ is returned as soon as it is a bad perturbation for at least one BN of the input domain. By taking the complement of these perturbations (in $\\mathbb M^{\\leq k}$), we obtain that the returned perturbations are reprogramming solutions *for all* the BNs in $\\mathbb F$." ] }, { "cell_type": "markdown", "id": "e4754ea2", "metadata": {}, "source": [ "Let us illustrate the ensemble reprogramming with the following example.\n", "First, let us define an influence graph to delimit the domain of admissible BNs:" ] }, { "cell_type": "code", "execution_count": 37, "id": "ba05ce55", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:21.914336Z", "iopub.status.busy": "2022-07-22T16:22:21.913771Z", "iopub.status.idle": "2022-07-22T16:22:21.968068Z", "shell.execute_reply": "2022-07-22T16:22:21.967515Z" }, "nbconvert_latex": { "nbconvert.figure.caption": "Influence graph delimiting the ensembles of BNs in the example" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# computing graph layout...\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "C->B\n", "\n", "\n", "+\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "C->D\n", "\n", "\n", "+\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "-\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "A->C\n", "\n", "\n", "+\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dom = bonesis.InfluenceGraph([\n", " (\"C\", \"B\", {\"sign\": 1}),\n", " (\"A\", \"C\", {\"sign\": 1}),\n", " (\"B\", \"C\", {\"sign\": -1}),\n", " (\"C\", \"D\", {\"sign\": 1}),\n", "], exact=True, canonic=False) # we disable canonic encoding\n", "dom" ] }, { "cell_type": "markdown", "id": "3fb6f089", "metadata": {}, "source": [ "This domain encloses all the BNs having exactly (`exact=True`) the specified influence graph, 4 distinct BNs in this case:" ] }, { "cell_type": "code", "execution_count": 38, "id": "7c79cd76", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:21.970346Z", "iopub.status.busy": "2022-07-22T16:22:21.970212Z", "iopub.status.idle": "2022-07-22T16:22:21.985228Z", "shell.execute_reply": "2022-07-22T16:22:21.984771Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABCD
01CA|!BC
10CA|!BC
20CA&!BC
31CA&!BC
\n", "
" ], "text/plain": [ " A B C D\n", "0 1 C A|!B C\n", "1 0 C A|!B C\n", "2 0 C A&!B C\n", "3 1 C A&!B C" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dom.canonic = True # we set canonic encoding for enumerating BNs\n", "F = list(bonesis.BoNesis(dom).boolean_networks())\n", "dom.canonic = False\n", "pd.DataFrame(F)" ] }, { "cell_type": "markdown", "id": "fc3bcea7", "metadata": {}, "source": [ "Let us explore the attractors of each individual BNs:" ] }, { "cell_type": "code", "execution_count": 39, "id": "b0b6a143", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:21.987347Z", "iopub.status.busy": "2022-07-22T16:22:21.987222Z", "iopub.status.idle": "2022-07-22T16:22:21.996500Z", "shell.execute_reply": "2022-07-22T16:22:21.996038Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Attractors of BN 0: [{'A': 1, 'B': 1, 'C': 1, 'D': 1}]\n", "Attractors of BN 1: [{'A': 0, 'B': '*', 'C': '*', 'D': '*'}]\n", "Attractors of BN 2: [{'A': 0, 'B': 0, 'C': 0, 'D': 0}]\n", "Attractors of BN 3: [{'A': 1, 'B': '*', 'C': '*', 'D': '*'}]\n" ] } ], "source": [ "for i, f in enumerate(F):\n", " print(f\"Attractors of BN {i}:\", list(f.attractors()))" ] }, { "cell_type": "markdown", "id": "0bc82b28", "metadata": {}, "source": [ "In this example, we focus on reprogramming the attractors so that the component `D` is fixed to 1.\n", "\n", "On the one hand, when reprogramming fixed points only, because one BN already verifies this property, the empty perturbation is a solution:" ] }, { "cell_type": "code", "execution_count": 40, "id": "d4f108bd", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:21.998446Z", "iopub.status.busy": "2022-07-22T16:22:21.998325Z", "iopub.status.idle": "2022-07-22T16:22:22.009519Z", "shell.execute_reply": "2022-07-22T16:22:22.009092Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{}]" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming_fixpoints(dom, {\"D\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "7faa9fca", "metadata": {}, "source": [ "On the other hand, the reprogramming of attractors returns solution that work on every BN:" ] }, { "cell_type": "code", "execution_count": 41, "id": "f27f1fb9", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:22.011352Z", "iopub.status.busy": "2022-07-22T16:22:22.011210Z", "iopub.status.idle": "2022-07-22T16:22:22.033821Z", "shell.execute_reply": "2022-07-22T16:22:22.033534Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'C': 1}, {'D': 1}, {'B': 0, 'A': 1}]" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(marker_reprogramming(dom, {\"D\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "0b7e67a2", "metadata": {}, "source": [ "Indeed, fixed `C` to 1, ensures in each case that `D` is fixed to 1." ] }, { "cell_type": "markdown", "id": "f1645388", "metadata": {}, "source": [ "The computation of universal solutions for the reprogramming of fixed points can be tackled by following a similar encoding than the reprogramming of attractors, i.e., by identifying perturbations which do not fulfill the property for at least one BN in the domain (the complement results in perturbations working for all the BNs):" ] }, { "cell_type": "code", "execution_count": 42, "id": "123323eb", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:22.035571Z", "iopub.status.busy": "2022-07-22T16:22:22.035466Z", "iopub.status.idle": "2022-07-22T16:22:22.038423Z", "shell.execute_reply": "2022-07-22T16:22:22.038024Z" } }, "outputs": [], "source": [ "def universal_marker_reprogramming_fixpoints(f: BooleanNetwork,\n", " M: dict[str,bool],\n", " k: int):\n", " bo = bonesis.BoNesis(f)\n", " coP = bo.Some(max_size=k)\n", " with bo.mutant(coP):\n", " x = bo.cfg()\n", " bo.fixed(x) # x is a fixed point\n", " x != bo.obs(M) # x does not match with M\n", " return coP.complementary_assignments()" ] }, { "cell_type": "code", "execution_count": 43, "id": "1fd7255f", "metadata": { "execution": { "iopub.execute_input": "2022-07-22T16:22:22.039903Z", "iopub.status.busy": "2022-07-22T16:22:22.039806Z", "iopub.status.idle": "2022-07-22T16:22:22.058038Z", "shell.execute_reply": "2022-07-22T16:22:22.057620Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n", "Grounding...done in 0.0s\n" ] }, { "data": { "text/plain": [ "[{'C': 1}, {'A': 1}, {'D': 1}]" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(universal_marker_reprogramming_fixpoints(dom, {\"D\": 1}, 2))" ] }, { "cell_type": "markdown", "id": "8512629d", "metadata": {}, "source": [ "Note that in this implementation, we do not ensure the existence of a fixed point after reprogramming. This is why the perturbation fixing only `A` to 1 is considered as a solution in our example:" ] }, { "cell_type": "code", "execution_count": 44, "id": "bcc7f7ec", "metadata": { "execution": { "iopub.execute_input": "2023-01-20T15:23:23.771237Z", "iopub.status.busy": "2023-01-20T15:23:23.771035Z", "iopub.status.idle": "2023-01-20T15:23:23.780442Z", "shell.execute_reply": "2023-01-20T15:23:23.779812Z" }, "nbconvert.display": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Attractors of BN 0 after fixing A to 1: [{'A': 1, 'B': 1, 'C': 1, 'D': 1}]\n", "Attractors of BN 1 after fixing A to 1: [{'A': 1, 'B': 1, 'C': 1, 'D': 1}]\n", "Attractors of BN 2 after fixing A to 1: [{'A': 1, 'B': '*', 'C': '*', 'D': '*'}]\n", "Attractors of BN 3 after fixing A to 1: [{'A': 1, 'B': '*', 'C': '*', 'D': '*'}]\n" ] } ], "source": [ "for i, f in enumerate(F):\n", " f[\"A\"] = 1\n", " print(f\"Attractors of BN {i} after fixing A to 1:\", list(f.attractors()))" ] }, { "cell_type": "markdown", "id": "7d370342", "metadata": {}, "source": [ "As BNs 2 and 3 have no fixed point, they fulfill the criteria \"all the fixed points match with marker `M`\"." ] }, { "cell_type": "markdown", "id": "03121088", "metadata": {}, "source": [ "## Scalability\n", "\n", "In order to evaluate the scalability on realistic BNs, we use the benchmark constituted by Moon et al. (2022a) to evaluate the reprogramming of fixed points (P1). Their benchmark gathers 10 locally-monotone BNs and 1 non-monotone one, that BoNesis cannot address. The dimension of the 10 BNs are respectively 14, 17, 18, 20, 28, 32, 53, 59, 66, and 75. For each of these models, a target marker for reprogramming has been defined from the corresponding published studies. Moreover, a subset of nodes has been declared as uncontrollable to avoid trivial solutions.\n", "We used this benchmark to evaluate the scalability of the P1 and P3 implementation we propose in this paper.\n", "\n", "For these 10 models, we applied the P1 and P3 reprogramming for different maximum number of simultaneous perturbations (denoted $k$ in the previous sections), up to $k=6$. In each case, we measured the time for the first solution, for listing up to 100 solutions, and for listing all the solutions, with a timeout of 10 minutes. The experiments have been performed on an Intel(R) Xeon(R) processor at 3.3Ghz with 16BG of RAM.\\\n", "In the case of P1, with $k=6$, it took around 1s to get at least one solution for each of the 10 models; up to 100 solutions have been listed in the same timing, except for one model which took 8s. The full listing of solutions of 3 of the larger models have timed out, the rest necessitating between 1 and 18s. With $k=4$, *BoNesis* was able to list all the solutions for all models (up to 5min for one of the larger model).\\\n", "In the case of P3, with $k\\geq 4$, 3 of the 10 models could not find a single solution in the given time limit; for most of the other models, a first solution was found in around 1s, a couple of models took around 1-2min. The enumeration of the first 100 solutions took a similar time with $k=4$, but timed out with $k=6$ for all but the 4 smallest models. With $k\\leq 2$, *BoNesis* has found all the solutions to P3 for all the 10 models in a few seconds maximum.\n", "\n", "These experiments testify of the difference of complexity between P1 and P3, and more precisely on the resolution approach taken for P3: the computation of the complementary sets of solutions becomes rapidly intractable for large combinations of perturbation. Indeed, in practice, there are many bad perturbations, thus their enumeration, which is necessary to compute their complement, is an important bottleneck.\n", "\n", "Evaluating the scalability of P2 and P4 would require defining initial configurations which are meaningful for the different models, which are not available in the selected benchmark. Nevertheless, because the source constraint does not change the complexity classes, we can conjecture that their scalability should be comparable to P1 and P3 respectively.\n", "Moreover, having benchmarks at larger scale would be insightful, but none of them are available to the best of our knowledge. It should be noted *BoNesis* has been applied to do BN synthesis for models with 1,000 nodes (Chevalier et al., 2019), suggesting a potential applicability of *BoNesis* for the reprogramming of large BNs.\n", "\n", "As stressed in the introduction, there exists only tools addressing P1 to compare with. The experiments of Moon et al. (2022a) show that their bilevel integer programming-based method systematically outperforms the ASP implementation of pyActoNet (Biane et al., 2018). On the same benchmark, *BoNesis* performed either similarly or in shorter time, albeit limited to locally-monotone BNs only." ] }, { "cell_type": "markdown", "id": "6018355c", "metadata": {}, "source": [ "# Discussion\n", "\n", "In this paper, we demonstrated how the *BoNesis* Python library can be employed to fully characterize permanent perturbations which guarantee that all the fixed points or all minimal trap spaces of the perturbed BN have a subset of components fixed to desired values (marker).\n", "We focused on reprogramming for achieving elementary dynamical properties, that are the fixed points or attractors, optionally reachable from a given configuration.\n", "Nevertheless, the snippets shown in this paper can be extended to account for more complex or specific dynamical properties after mutation, e.g., existence of additional trajectories, considering multiple initial configurations.\n", "\n", "It should be noted that the candidate combinations of perturbations are computed solely based on the Boolean dynamics, and do not account for experimental feasibility, e.g., in the scope of models of biological systems.\n", "Future work may consider optimization or prioritization of perturbations based on such extra information.\n", "Currently, *BoNesis* enables specifying uncontrollable components which must not be perturbed (`exclude` option for the `Some` object, or `--exclude` for the command line, taking a list of components which should be excluded from the candidate perturbations).\n", "\n", "We considered for problems, referred to as P1, P2, P3, P4, where P1-P2 relate to the reprogramming of fixed points, and P3-P4 to the reprogramming of MP attractors (i.e., minimal trap spaces).\n", "The computational complexity of P1-P2 allows an efficient implementation using Answer-Set Programming (ASP), whereas the one of P3-P4 necessitate working around complementary solution to fit into the expressiveness of ASP, limiting their scalability. Future work may explore alternative implementations using different logic frameworks.\n", "\n", "The identified perturbations may destroy and create new fixed points and attractors for the BN. This is a significant difference with most of the methods developed in the literature where many focus on the control towards attractors of the unperturbed BNs only. Whereas the problem P1 which has been already addressed with different methods, we are not aware of any other approach tackling P2, P3, and P4.\n", "\n", "Besides the four reprogramming problems tackled in this paper, an additional variant would be the marker-reprogramming of fixed points which also ensures the absence of cyclic attractors. Note that its complexity is equivalent to the one of P3/P4, i.e., it can be expressed as a $\\exists\\forall\\exists$-expression. This problem may be relevant for modeling cases where cyclic attractors do not make sense. The programming interface of *BoNesis* do not permit an efficient encoding of this problem at the moment.\n", "\n", "This paper focused on permanent perturbations, i.e., enforcing the value of one or several components constantly over time, independently of the state of the system.\n", "*Sequential* reprogramming (Mandon et al., 2017,Pardo et al., 2021) consists in applying sets of perturbations at different time. This can lead to reducing the overall number of component to perturb, by taking advantage of the natural transient dynamics of the system.\n", "Sequential reprogramming brings the BN reprogramming settings closer to classical control theory, as the\n", "control can depend both on time and state of the system.\n", "Having fixed a number of steps, say $m$, the reprogramming problems consists in identifying $m$ sets of perturbations which will be applied in sequence, and their application may be restricted to attractors only\n", "(Mandon et al., 2019).\n", "Interestingly in that case, having fixed the number of reprogramming steps, the computational complexity remains identical to the one-step reprogramming with locally-monotone BNs, due to the PTIME complexity of the reachability.\n", "For instance, the 2-steps reprogramming of BNs along fixed points only with the MP update mode can be expressed as the following $\\exists\\forall$-expression, as P1:\n", "\n", "$$\\exists P,Q\\in\\mathbb M^{\\leq k}, \\forall x,y\\in\\mathbb B^n,\n", " f_P(x) = x \\Rightarrow\n", " \\operatorname{reach}_Q(x,y) \\Rightarrow\n", " f_Q(y) = y \\Rightarrow y\\models M$$\n", "\n", "\"There exist two sets of perturbations $P$ and $Q$, such that for any configuration $x$ and any configuration $y$, if $x$ is a fixed point of under the perturbation $P$, then if $y$ is reachable from $x$ under the perturbation $Q$, then if $y$ is a fixed point under the perturbation $Q$, then it must match with the marker $M$\".\n", "The more general 2-steps reprogramming along attractors can be expressed as follows:\n", "\n", "$$\\exists P,Q\\in\\mathbb M^{\\leq k}, \\forall x,y\\in\\mathbb B^n,\n", "\\operatorname{IN-ATTRACTOR}_P(x) \\Rightarrow\n", " \\operatorname{reach}_Q(x,y) \\Rightarrow\n", " \\operatorname{IN-ATTRACTOR}_Q(y) \\Rightarrow y \\models M$$\n", "Accounting for $\\operatorname{IN-ATTRACTOR}$, this leads to an $\\exists\\forall\\exists$-expression, as for the single-step reprogramming.\n", "Future work may then investigate the encoding of sequential reprogramming with *BoNesis*.\n", "\n", "Finally, we demonstrated how *BoNesis* can be employed to reason on the reprogramming of BNs, leading to either solutions that work for at least one BN of the ensemble, or working on each of them (universal reprogramming). We believe that reasoning on ensemble of models is a promising direction to address the robustness of predictions in the scope of applications in systems biology." ] }, { "cell_type": "markdown", "id": "da37e4d0", "metadata": {}, "source": [ "### Acknowledgements\n", "\n", "The author would like to thank Kyungduk Moon and Kangbok Lee for stimulating discussions and for providing the model and configuration files for the benchmarks of Moon et al. (2022a).\n", "\n", "### Software and data availability\n", "\n", "The software *BoNesis* is available at [github.com/bnediction/bonesis](https://github.com/bnediction/bonesis). The code of this paper uses version 0.4.93 (archived at [doi:10.5281/zenodo.7657487](https://doi.org/10.5281/zenodo.7657487)).\n", "The notebook, models, and instructions for reproducing the results are available at [github.com/bnediction/reprogramming-with-bonesis](https://github.com/bnediction/reprogramming-with-bonesis) (archived at [doi:10.5281/zenodo.7733095](https://doi.org/10.5281/zenodo.7733095)).\n", "\n", "### Funding\n", "\n", "This work has been supported by the French Agence Nationale pour la Recherche (ANR) in the scope of the\n", "project [BNeDiction](https://bnediction.github.io) (grant number ANR-20-CE45-0001).\n", "\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.1" } }, "nbformat": 4, "nbformat_minor": 5 }