Franck Delaplace

Philippe Dague

François Fages

Adrien Richard

Computational methods for the inference of therapeutic targets and sequences of treatment

Keywords:

le grade de docteur n'aurait jamais pu exister sans la présence de mon directeur de thèse

Titre: Méthodes d'inférence de cibles thérapeutiques et de séquences de traitement Mots clés: Réseaux booléens contrôlés -Séquence de contrôle -Médecine des réseaux Résumé: Un enjeu majeur de la médecine des réseaux est l'identification des perturbations moléculaires induites par les maladies complexes et les thérapies afin de réaliser une reprogrammation cellulaire. L'action de la reprogrammation est le résultat de l'application d'un contrôle. Dans cette thèse, nous étendons le contrôle unique des réseaux biologiques en étudiant le contrôle séquentiel des réseaux booléens. Nous présentons un nouveau cadre théorique pour l'étude formelle des séquences de contrôle. Nous considérons le contrôle par gel de noeuds. Ainsi, une variable du réseau booléen peut être fixée à la valeur 0, 1 ou décontrôlée. Nous définissons un modèle de dynamique contrôlée pour le mode de mise à jour synchrone où la modification de contrôle ne se produit que sur un état stable. Nous appelons CoFaSe le problème d'inférence consistant à trouver une séquence de contrôle modifiant la dynamique pour évoluer vers une propriété ou un état souhaité. Les réseaux auxquels sera appliqué CoFaSe auront toujours un ensemble de variables incontrôlables. Nous montrons que ce problème est PSPACE-dur. L'étude des caractéristiques dynamiques du problème CoFaSe nous a permis de constater que les propriétés dynamiques qui impliquent la nécessité d'une séquence de contrôle émergent des fonctions de mise à jour des variables incontrôlables. Nous trouvons que la longueur d'une séquence de contrôle minimale ne peut pas être supérieure à deux fois le nombre de profils des variables incontrôlables. À partir de ce résultat, nous avons construit deux algorithmes inférant des séquences de contrôle minimales sous la dynamique synchrone. Enfin, l'étude des interdépendances entre le contrôle séquentiel et la topologie du graphe d'interaction du réseau booléen nous a permis de découvrir des relations existantes entre structure et contrôle. Celles-ci mettent en évidence une borne maximale plus resserrée pour certaines topologies que celles obtenues par l'étude de la dynamique. L'étude sur la topologie met en lumière l'importance de la présence de cycles non-négatifs dans le graphe d'interaction pour l'émergence de séquences minimales de contrôle de taille supérieure ou égale à deux.

Abstract: Network controllability is a major challenge in network medicine. It consists in finding a way to rewire molecular networks to reprogram the cell fate. The reprogramming action is typically represented as the action of a control. In this thesis, we extended the single control action method by investigating the sequential control of Boolean networks. We present a theoretical framework for the formal study of control sequences.We consider freeze controls, under which the variables can only be frozen to 0, 1 or unfrozen. We define a model of controlled dynamics where the modification of the control only occurs at a stable state in the synchronous update mode. We refer to the inference problem of finding a control sequence modifying the dynamics to evolve towards a desired state or property as CoFaSe. Under this problem, a set of variables are uncontrollable. We prove that this problem is PSPACE-hard. We know from the complexity of CoFaSe that finding a minimal sequence of control by exhaustively exploring all possible control sequences is not practically tractable. By studying the dynamical properties of the CoFaSe problem, we found that the dynamical properties that imply the necessity of a sequence of control emerge from the update functions of uncontrollable variables. We found that the length of a minimal control sequence cannot be larger than twice the number of profiles of uncontrollable variables. From this result, we built two algorithms inferring minimal control sequences under synchronous dynamics. Finally, the study of the interdependencies between sequential control and the topology of the interaction graph of the Boolean network allowed us to investigate the causal relationships that exist between structure and control. Furthermore, accounting for the topological properties of the network gives additional tools for tightening the upper bounds on sequence length. This work sheds light on the key importance of non-negative cycles in the interaction graph for the emergence of minimal sequences of control of size greater than or equal to two.

-Introduction

Cell reprogramming consists in the control of molecular processes and modifying gene expression to induce a particular cell behaviour naturally or artificially. The potential outcomes of reprogramming have valuable benefits regarding the essential challenges of health: cancerous targeted therapy, complex disease aetiology, regenerative medicine, stem cells monitoring, etc. [START_REF] Loscalzo | Network medicine[END_REF]. Despite the impressive progress in cell reprogramming during the past decade, more breakthroughs are required before cellular reprogramming yields routine clinical use [START_REF] Vogel | Reprogramming cells[END_REF]. The main issues lie in the discovery of reliable ways to trigger the reprogramming process and to understand exactly how its mechanisms work. In this endeavour, the definitions of suitable theoretical frameworks and computational methods are crucial for enabling the analysis and the design of the reprogramming patterns responsible for the phenotypic switch.

Finding therapeutic targets is based on the study of molecular models of disease. These models are frameworks that define the causal relationship between disturbances at the molecular level and the diseased or healthy forms of an organism. There are two complementary approaches for studying diseases at the molecular level: empiricism and rationalism [START_REF] William | Empiricism and rationalism in medicine: can 2 competing philosophies coexist to improve the quality of medical care[END_REF][START_REF] William | Rationalism, empiricism, and evidence-based medicine: a call for a new galenic synthesis[END_REF].

The empirical method involves establishing statistical measures between sets of patients' symptoms and their molecular characteristics. The rational method relies on developing mechanistic models that theorise the functioning of an organism and explain the emergence of the symptoms of the disease via disturbances in the model. Therefore, the discovery of targeted therapies can be based on high-throughput screening, which tests, for example, the effectiveness of many molecules actions without knowing their mode of action or predicts drug effects based on biological models [START_REF] David | How were new medicines discovered?[END_REF].

Whether empirical or rational methodology, developments in precision medicine need computer science [START_REF]Toward precision medicine: building a knowledge network for biomedical research and a new taxonomy of disease[END_REF][START_REF] Hood | Systems biology and new technologies enable predictive and preventative medicine[END_REF]. The empirical methods suppose the ability to analyse considerable masses of data resulting from the progress of molecular biology. The rational methods imply the development of disease models and algorithms for obtaining the desired predictions.

In this manuscript, we focus on a rational approach based on the study of biological models. In [START_REF] Zhong | Edgetic perturbation models of human inherited disorders[END_REF], the authors relate mutations to their network effects: nonsense mutation, out-of-frame insertion or deletion and defective splicing are interpreted as node or arc deletions, whereas missense mutation and in-frame insertion or deletion can be modelled as node or arc additions. Moreover, in [START_REF] Creixell | Kinome-wide decoding of networkattacking mutations rewiring cancer signaling[END_REF], the authors classify mutations according to how they affect signalling networks and distinguish between mutations that constitutively activate or inhibit enzymes (nodes) and mutations that rewire the interactions (arcs). Similarly, [START_REF] Csermely | Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review[END_REF] interpret targeted therapies as network rewiring. The effects of mutations and drugs can, thus, be described as elementary topological actions on the network: the deletion or insertion of nodes and arcs. Cell reprogramming is then viewed as network alteration based on these topological actions. The impact of the actions on the network should be evaluated from a model of dynamics translating the topological actions into dynamical alteration of the trajectories. Accordingly, phenotypic changes are assessed at the molecular level via the measurement of the state of particular molecules called biomarkers-observable indicators of biological processes whose molecular signature variation discriminates the phenotypes [START_REF] Csermely | Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review[END_REF][START_REF] Strimbu | What are Biomarkers?[END_REF]. The signatures must be observed over a significant period of time to testify their relevance, and thus are assumed to be met concomitantly with a stability condition of the biological system. This approach is part of network medicine [START_REF] Barabási | Network medicine: a network-based approach to human disease[END_REF],which aims to address drug target discovery and the elucidation of disease mechanisms through network analysis by renewing the phenotype-genotype relationship into the association of a phenotype to some network perturbations [START_REF] Sahni | Edgotype: a fundamental link between genotype and phenotype[END_REF]. Albert-László Barabási states that biological systems contain many components that are connected in complicated relationships but are organised by simple principles. Using network theory, the organising principles can be comprehensively analysed by representing systems as complex networks. Network medicine is based on the idea that understanding the complexity of gene regulation, metabolic reactions, and protein-protein interactions, as well as using a network representation of those processes, will shed light on the causes and mechanisms of diseases.This thesis is, therefore, rooted in the field of network medicine.

We choose to use Boolean networks as a network representation for the cellular processes. Boolean networks are widely used to model biological systems in network medicine. These networks are discrete dynamics systems introduced in biology by McCulloch and Pitts [START_REF] Warren | A logical calculus of the ideas immanent in nervous activity[END_REF] as a model for the transmission of information between neurons, and by Stuart Kauffman [START_REF] Kauffman | Homeostasis and differentiation in random genetic control networks[END_REF] and Rene Thomas [START_REF] Thomas | Boolean formalization of genetic control circuits[END_REF] to model gene regulatory networks. The molecules of the system are represented as Boolean variables. By convention, the value 1 corresponds to an active or present state, and 0 to an inactive or absent state. Although Boolean networks are a rough simplification of genetic reality, as genes are not simple binary switches, they can correctly capture many expression patterns of genes [START_REF] Albert | The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in drosophila melanogaster[END_REF][START_REF] Bornholdt | Boolean network models of cellular regulation: prospects and limitations[END_REF].

Recent research in computational biology has provided novel inference methods for reprogramming a system to make its dynamics converge towards an expected fate. These works use Boolean control networks (BCNs). Its a model specifying the actions as controls on Boolean network. Various approaches have been proposed, such as stuck-at fault models and SAT-based methods [START_REF] Kent | Application of Max-SAT-based ATPG to optimal cancer therapy design[END_REF], motif-related heuristics [START_REF] Jorge | Cell fate reprogramming by control of intracellular network dynamics[END_REF], algebraic approaches [START_REF] Murrugarra | Identification of control targets in Boolean molecular network models via computational algebra[END_REF], and abductive methods [START_REF] Biane | Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery[END_REF]. These works have been validated using real biological cases showing their adequacy for drug therapy prediction. The state of art related to Boolean networks reveals that the methods are currently focused on computing a single network action modelled as a control input to reprogramme the dynamics in order to reach stable states that meet some expected properties assessed at the molecular level.

However, more complex schemes may require a control sequence. For example, in some biological cases, a sequence of mutations is observed, or a therapy involves a scheduled protocol for administering drugs. Typically, tumorigenesis results from a multi-step process governed by sequential genetic alterations. A colorectal tumour offers a paradigmatic system illustrating this sequential progression. Fearon and Vogelstein demonstrated that colorectal cancer tumorigenesis relies on a sequence of disturbances of three genes [START_REF] Fearon | A genetic model for colorectal tumorigenesis[END_REF], called the 'Vogelstein sequence'. This sequence suggests that acquiring of a cancerous phenotype requires undergoing various intermediary stages and that, if these same disturbances occur in a different order from that observed, the cell dies before developing its cancerous potential. Furthermore, in [START_REF] Lee | Sequential application of anti-cancer drugs enhances cell death by re-wiring apoptotic signaling networks[END_REF], the authors describe a systematic approach to identifying efficient drug combinations in killing cancer cells depending on changes in the order and duration of drug exposure. They found that some drug combinations (egfr inhibitor) can synergise the apoptotic response to DNA-damaging chemotherapy for a subset of triple-negative breast cancers if the drugs are administered sequentially but not simultaneously, leading to an appropriate dynamics rewiring of oncogenic signalling networks.

Therefore, the study of sequential control is a natural extension of the previous works. Investigating control sequences can, as a long-term perspective, possibly explain the causes of diseases via sequences of perturbations and help discover therapeutic regimens.

The subject of control sequence inference is vast and difficult. Related ques-tions to this problem could find their foundation in the problems related to the control of systems. We can cite, for example the control theory for linear systems, in which control system design addresses the problem of making a concrete physical system behave according to certain desired specifications by using a device called a controller [START_REF] Harry L Trentelman | Control theory for linear systems[END_REF].We can also consider the study of the robustness of the network and its boundary conditions, which offers insights into the behaviour of interacting systems and can provide important leads for finding the desired controls [START_REF] Demongeot | Phase transitions in stochastic nonlinear threshold Boolean automata networks on Z 2 : the boundary impact[END_REF][START_REF] Demongeot | Attraction basins as gauges of the robustness against boundary conditions in biological complex systems[END_REF]. In this manuscript, we only consider sequential control on Boolean networks, which is an under-researched area. The main studies on this subject are those of Mandon et al. , who researched the temporal reprogramming of Boolean networks in [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF][START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF]. Given a trajectory, they identified the appropriate states at which a control should be applied, and deduced the corresponding controls (perturbations) to reach an expected state. The authors objective was minimising the total number of perturbations, particularly regarding known one-step controls. These series of publications emphasiSe the computational complexity of sequence inference.

In this thesis, we are interested in the definition of a framework and computational methods for the inference of control sequences for Boolean networks. The problem we pose is as follows:

If not all variables are controllable, how can we find a minimal control sequence modifying the dynamics to evolve towards a desired state from an initial state if such a state is not reachable with a one-step control?

In the model of controlled dynamics that we propose, we consider the constraints of its ultimate application in biology. We impose that objectives are determined on stable states and that the modification of the control only occurs at a stable state. Studying the dynamical characteristics (Chapter 5) of this framework enabled us to bound the length of control sequences of minimal size. Furthermore, studying the causality of sequential controls from the viewpoint of the interaction graph (Chapter 7) offered key insights to reduce such bounds. This work helps reveal the key importance of non-negative cycles in the interaction graph regarding the emergence of minimal sequences of control of size greater than or equal to two. This thesis is structured as follows: In Chapter 2, we present the Boolean network model, its model of dynamics, and its interaction graph. We also recall the formalism of the Boolean control network which is a function generating Boolean networks according to control parameters. These control parameters enable us to model structural disturbances of the Boolean network interaction graph. In this manuscript, we particularly focus on the control of Boolean network nodes. More precisely on control input that freezes nodes at a specific value.

In Chapter 3, we formalise the controlled dynamics that extend the Boolean network dynamics by revealing how the system evolves through a sequence of control inputs. We explain the inference problem regarding finding a control sequence that modifies the dynamics to evolve towards a desired state or property. This problem is denoted as CoFaSe (i.e., Controlled Fate in Sequence). Finally, we prove that the inference of a control sequence satisfying CoFaSe is PSPACE-hard.

In Chapter 4, we present in greater detail the state of art regarding the control of Boolean networks. In particular, we discuss the similarities and differences to the framework proposed by Mandon et al. in [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF][START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF].

In Chapter 5, we describe the dynamical properties of the sequential inference problem. By partitioning the network variables into a set of controllable and uncontrollable variables, we obtain concrete bounds regarding the length of minimal control sequences. These upper bounds reduce the potential solution space of the inference problem.

In Chapter 6, we propose two computational approaches for inferring minimal sequences of control. The first approach always finds a minimal sequence of control if such a sequence exists. The second approach may not always find a minimal sequence of control but generally requires less computation time. In the final section of this chapter, we benchmark and discuss the performance of the two algorithms.

In Chapter 7, we study the relationship between sequential control and the topology of the interaction graph of the Boolean network. Accounting for the topological properties of the network provides additional tools for tightening the upper bounds regarding sequence length. This approach enables us to study the causal relationships between structure and control.

-Boolean control network

In this manuscript, we will formalise the Boolean network reprogramming by relying on Boolean control network. A BCN extends the Boolean network by adding Boolean controls. The reprogramming of Boolean networks leads to the modification of their dynamics. We more specifically focus on a particular class of control called the freezing control , in which a control input definitively freezes a variable state to a specific value.

In this chapter, we first recall the main definitions of Boolean networks (Section 2.1) and their interaction graph (Section 2.2). Then, we define the extension to BCNs (Section 2.3).

. Boolean network

Boolean function.

A Boolean function is defined as f : B n → B where B = {0, 1} is the Boolean domain and n is its number of arguments. Every Boolean function can be expressed as a propositional formula with n variables x 1 , . . . , x n . For example, f (x 1 , x 2 , x 3 ) = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ x 2 ) is a Boolean formula which have for variables x 1 , x 2 and x 3 .

Boolean network.

A Boolean network is a discrete dynamical system defined on a finite number of Boolean variables X = {x 1 , . . . , x n }. The network is defined by a collection of Boolean functions,

F : B n → B n , F = {x i = f i (x 1 , . . . , x n ) | 1 ≤ i ≤ n}, in which each f i is a propositional formula computing the instantiation of x i . An example of a Boolean network is presented in Figure 2.1. F =    x 1 = (x 1 ∧ ¬x 2 ) ∨ (x 1 ∧ ¬x 3 ) ∨ (¬x 1 ∧ x 2 ∧ x 3 ) x 2 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ x 2 ) x 3 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ ¬x 2 )
Legend: A Boolean network F with three variables x 1 , x 2 and x 3 .

State.

A state s belonging to the set of states S X is an interpretation assigning a Boolean value to the variables (i.e., s : X → B). The evolution of each variable x i depends on its update Boolean function f i and a state s. Table 2.1 contains the result of applying the set of Boolean functions of the Boolean network in Figure 2.1 to each state s ∈ S X .

s {x 1 ,x 2 ,x 3 } f 1 (s) f 2 (s) f 3 (s) 000 0 0 1 001 0 0 1 010 0 1 0 011 1 1 0 100 1 0 0 101 1 1 1 110 1 0 0 111 0 1 1
Legend: Application of the set of Boolean functions of the Boolean network F of Figure 2.1 to its set of states S X .

Model of dynamics.

The model of dynamics describes the evolution of states for all variables via a labelled transition system ⟨-→, M, S X ⟩, in which the states are updated according to an updating policy M ⊆ 2 X called the mode, which is a cover of X ( m∈M m = X).

f ↓X ′ defines the restriction/projection of the function to X ′ , such that f is only defined for the elements of X ′ ⊂ X.

Each transition relation (-→⊆ S X ×M ×S X ) is labelled by the set of updated variables m:

s m -→ s ′ def == s ′ = (F ↓m (s) ∪ s X\m ).
The global transition relation is defined as:

-→= m∈M m -→. A path 1 s -→ * s ′ characterises a trajectory from s to s ′ .
For example, if we consider the Boolean network of Figure 2.1 and the updating policy M = {{x 1 , x 2 }, {x 3 }}. The updating policy M means that from the state 011, it is possible to carry out one of the two following transitions:

• One transition in which the variables x 1 and x 2 are updated and the state 111 is reached.

• One transition in which the variable x 3 is updated and the state 010 is reached.

The updating policy M provides us with the following states graph: In biological modelling, various updating modes are proposed to model the numerous constraints of the abstracted system. There is no consensus regarding which updating mode for Boolean networks is the most representative of the biological reality. Thus, the choice of updating mode strongly depends on the nature of the studied problem. Indeed, each updating mode has distinct features and can have a wide range of effects on the dynamics of the Boolean network.

{x 1 x 2 } {x 1 x 2 } {x 3 } {x 1 x 2 } { x 3 } { x 1 x 2 } {x 1 x 2 }{x 3 } {x 1 x 2 }{x 3 } {x 1 x 2 }{x 3 } {x 3 } {x 3 } {x 3 } { x 1
In this manuscript, we only introduce two of the most used updating modes: the synchronous mode and the asynchronous mode. These two modes only represent a small part of the spectrum of update modes introduced in the literature. For example, the updating functions may be composed, as in block-sequential [START_REF] Robert | Discrete iterations, a metric study[END_REF] and block-parallel [START_REF] Demongeot | About block-parallel boolean networks: a position paper[END_REF] updating modes. Other updating modes may also make use of parameters that at first sight cannot be directly captured by these deterministic updates [START_REF] Paulevé | Non-deterministic updates of Boolean networks[END_REF]. Memory Boolean networks [START_REF] Goles | Attractor landscapes in boolean networks with firing memory: a theoretical study applied to genetic networks[END_REF][START_REF] Goles | On the effects of firing memory in the dynamics of conjunctive networks[END_REF] and Interval Boolean networks [START_REF] Chatain | Boolean networks: beyond generalized asynchronicity[END_REF] respectively consider delay and duration and Most Permissive Boolean networks [START_REF] Paulevé | Reconciling qualitative, abstract, and scalable modeling of biological networks[END_REF] consider thresholds in their updating functions.

In the synchronous mode, all the variables are updated during a transition (M = {X}). The synchronous update mode is deterministic since all transitions are functions. 2By contrast, in the asynchronous mode, only one variable is updated per transition (M = {{x i }} x i ∈X ). The asynchronous update mode is non-deterministic since its transitions are ordinary relations (not functions).

{ x 1 x 2 x 3 } {x 1 x 2 x 3 } {x 1 x 2 x 3 } { x 1 x 2 x 3 } { x 1 x 2 x 3 } {x 1 x 2 x 3 } {x 1 x 2 x 3 } {x 1 x 2 x 3 }
{x 1 } {x 1 } {x 3 } {x 2 } { x 3 } { x 2 } {x 1 }{x 2 }{x 3 } {x 1 }{x 2 }{x 3 } {x 1 }{x 2 }{x 3 } {x 2 } {x 2 }{x 3 } {x 1 }{x 3 } {x 1 }{x 3 } { x 1 } { x 2

}

Synchronous Asynchronous

Legend: Dynamics of the Boolean network F of Figure 2.1 under two update modes. Arcs are labelled by the sets of updated variables realizing the transitions. On the left is the dynamics of F under the synchronous update mode. On the right is the dynamics of F under the asynchronous update mode. Equilibrium. An attractor A ⊆ S X is a set of states from which only states of A are reachable and in which all states of A are reachable from any state of A.

A is an attractor if and only if:

A ̸ = ∅ ∧ ∀s ∈ A, ∀s ′ ∈ S X \ A : ¬(s -→ * s ′ ) ∧ ∀s, s ′ ∈ A : s -→ * s ′ .
A fixpoint attractor or stable state s is a particular attractor whose cardinality, denoted |A|, is equal to 1. A state s is denoted as a stable state by the following notation:

stbl F (s) def == ∀m ∈ M : s m -→ s.
A cyclic attractor is an attractor of size |A| > 1 that forms a cycle in the dynamics of the Boolean network. Note that under the synchronous update mode of a Boolean network, an attractor can only be a fixpoint or a cyclic attractor.

A basin of attraction of an attractor A is a set of states in which each of its states will always eventually reach a state of A. B is a basin of attraction of an attractor A if:

A ⊆ B ∧ ∀s ∈ B, ∃s ′ ∈ A : s -→ * s ′ ∧∀s ∈ B,∀s ′ ∈ S X : s -→ * s ′ =⇒ s ′ ∈ B.
In the left graph of Figure 2.3, the states 010, 100 and 001 are stable states. Their largest basins of attraction are, respectively, {010}, {101, 111, 011, 110, 100}, and {000, 001}.

. Boolean networks interaction graph

Interaction graph. The interaction graph of a Boolean network captures the interdependence of the network variables in the dynamics. For a Boolean network F with the set of variables X, its interaction graph is a directed graph ⟨X, ⟩, which contains the arc x i

x j if a change in x i may leads to a change in x j . Formally, an interaction is defined as follows:

x i x j def == ∃s, s ′ ∈ S X : s x i ̸ = s ′ x i ∧ s X\x i = s ′ X\x i ∧ f j (s) ̸ = f j (s ′ ).

Signed interaction graph.

The signed interaction graph extends the notion of dependence by classifying arcs in three categories: a monotonic increase in x j (sign 1), a monotonic decrease in x j (sign -1), or a non-monotonic interaction depending on the state of the other variable (sign 0). The signs are respectively labelled by: + for 1, -for -1, and ± for 0. Formally, the signed interaction graph of a Boolean graph ⟨X, , σ⟩, in which the relation x i x j is defined in the same way as for the interaction graph, and σ : ( ) → {-1, 0, 1} is the arc labelling function defined according to the following equations and graphically represented by {-, ±, +}:

x i + x j def == x i x j ∧ ∀s, s ′ ∈ S X : s x i ≤ s ′ x i ∧ s X\x i = s ′ X\x i =⇒ f j (s) ≤ f j (s ′ ), x i - x j def == x i x j ∧ ∀s, s ′ ∈ S X : s x i ≤ s ′ x i ∧ s X\x i = s ′ X\x i =⇒ f j (s) ≥ f j (s ′ ).
The arcs for which neither of the two equations is true, receive the label ±. Figure 2.5: The signed interaction graph of a Boolean network.

The arcs labelled + refer to positive arcs, whereas those labelledrefer to negative arcs.

Cycle.

In an interaction graph, a cycle is a finite sequence of distinct arcs in the same direction that joins a sequence of vertices in which the only repeated vertices are the first and last. In a signed interaction graph, the sign of a cycle is the product of the sign of its arcs.

• A cycle is a positive cycle if the product of the signs is equal to 1 (i.e., if and only if it contains an even number of '-' arcs and no '±' arcs).

• A cycle is a negative cycle if the product of the signs is equal to -1 (i.e., if and only if it contains an odd number of '-' arcs and no '±' arcs).

• A cycle is a positive/negative cycle (positive and negative at the same time) if the product of the signs is equal to 0 (i.e., if it contains at least a '±' arc). Depending on the instantiation of the variables of the network, such cycles can behave as positive or negative cycles.

• A cycle is a non-negative cycle if the product of the signs is not equal to -1 (i.e., the cycle is a positive cycle or a positive/negative cycle).

For example, in the interaction graph of F in Figure 2.5, the cycles {x 2 , x 2 }, {x 3 , x 3 }, are positive cycles, the cycle {x 2 , x 3 , x 2 }, is a negative cycle and the cycles {x 1 , x 1 }, {x 1 , x 2 , x 3 , x 1 }, are positive/negative cycles.

Strongly connected component.

A subgraph of a directed graph is called a strongly connected component (SCC) if every vertex is reachable from every other vertex. We can distinguish between trivial SCCs, which do not contain cycles, and complex SCCs, which contain one or more cycles. Since an SCC with more than one variable necessarily possesses a cycle, all trivial SCCs are of cardinality 1. All signed interaction graphs can be partitioned into SCC modules. For an example of a partitioned interaction graph into SCC modules, see Figure 2.6.

In the rest of this manuscript, we only study complex strongly connected components. For the sake of clarity, complex SCCs are simply referred to as SCCs.

Upstream, downstream, and disconnected variables. For the sake of proof in the remainder of this manuscript, we now define the notion of upstream, downstream, and disconnected variables in regards to a set of variables as follows:

y 1 y 5 y 6 y 2 y 3 y 4 x 1 x 2 x 3 x 4
Legend: Interaction graph partitioned into SCC modules where each color corresponds to a distinct SCC. The variables x 1 to x 4 belong to complex SCCs in contrary to the variables y 1 to y 6 which belong to trivial SCCs.

Figure 2.6: Interaction graph partitioned into SCC modules

Let A be a set of variables in the interaction graph of the network F . The variables of F can be classified according to A into four sets:

• A the set of the reference variables.

• A ↙ = {x | x ∈ X, x / ∈ A, ∃x ′ ∈ A : x * x ′ } the set of variables
upstream of the set of variables A.

• A ↘ = {x | x ∈ X, x / ∈ A, ∃x ′ ∈ A : x ′ * x} the set of variables
downstream of the set of variables A.

• A × = X\(A ∪ A ↙ ∪ A ↘ ) the set of variables disconnected from the set of variables A.

For example, in Figure 2.6, if we take the set of variables A = {x 1 } we will have A ↙ = {y 1 , y 6 }, A ↘ = ∅, and A × = {x 2 , x 3 , x 4 , y 2 , y 3 , y 4 , y 5 }, and if we take the set of variables B = {x 3 , y 4 }, we will have B ↙ = {x 2 , x 4 , y 2 , y 3 }, B ↘ = {x 4 , y 3 } and B × = {x 1 , y 1 , y 5 , y 6 }.

. Boolean control network

The Boolean control network (BCN) extends the Boolean network by adding controls on variables. A control is represented by an additional parameter whose state is set simultaneously and instantaneously when a control is applied.

More formally, a Boolean control network F U is a function generating a Boolean network from an interpretation µ ∈ S U of control parameters U = {u 1 , . . . , u j , . . . , u m }, which is called a control input. This input is defined as follows:

F U = {x i = f i (x 1 , . . . , x n , u 1 , . . . , u m ) | 1 ≤ i ≤ n},
For each instantiation of control input µ, the Boolean control network F U generates a Boolean network F µ , modelling the application of a control on the initial Boolean network F .

The freezing control assigns a definite value to each variable. The two possible freezing outcomes, 0 or 1, are supported by two parameters with two distinct regimes: either they freeze the variable or remain idle. By convention, inspired by the freezing temperature of water at 0 • C, the freezing action is triggered when the control parameter is set to 0, whereas 1 represents the idle situation. Implementing of the freezing control on a Boolean network augments the formulas of the network by adding the control parameter to obtain the expected control behaviour.

A control can be applied to a node. In this case, the control parameters are applied to the formula of the frozen variable. For a formula f i , adding the control parameters u 0 i ∈ U 0 and u 1 i ∈ U 1 to freeze the variable x i to 0 or 1, respectively, leads to the following specification:

x i = f i (x 1 , . . . , x n ) ∧ u 0 i for freezing to 0, (2.1)
x i = f i (x 1 , . . . , x n ) ∨ ¬u 1 i for freezing to 1. (2.2)
A control can be applied an arc. In this case, the control parameters are applied to the occurrence of variables in the functions of other variables. For a formula f i , adding the control parameters u 0 i,j ∈ U 0 and u 1 i,j ∈ U 1 to freeze the variable x j in the formula of x i to 0 or 1, respectively, leads to the following specification:

x i = f i (x 1 , . . . , x j ∧ u 0 i,j , . . . , x n ) for freezing to 0, (2.3)
x i = f i (x 1 , . . . , x j ∨ ¬u 1 i,j , . . . , x n ) for freezing to 1.

(2.4)

Many other types of controls are possible. In this manuscript, we focus on the freezing of nodes and do not consider the control applied on arcs. U 0 and U 1 control parameters can be combined to trigger the freezing to different values (i.e.,

x i = f i (x 1 , . . . , x n ) ∧ u 0 i ∨ ¬u 1 i ). Subsequently, U = U 0 ∪ U 1
represents the whole set of freezing control parameters, and u i ∈ U represents a generic freezing control parameter (u 0 i or u 1 i ). The active control set of a control input, μ, represents the set collecting all the activated controls: μ = {u | µ(u) = 0}. Note that µ and μ are equivalent descriptions of the control since we can define one from the other. Subsequently, for the sake of simplicity, a control µ will be described using μ to avoid a long description of the control including all inactive control inputs.

In Figure 2.7, we can see an example of the application of a control to the

F {u 1 1 ,u 0 1 } =      x 1 = (x 1 ∧ ¬x 2 ) ∨ (x 1 ∧ ¬x 3 ) ∨ (¬x 1 ∧ x 2 ∧ x 3 ) ∨ ¬u 1 1 ∧ u 0 1 x 2 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ x 2 ) x 3 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ ¬x 2 )
F {u 1 1 ,u 0 1 } .
From left to right, the respective controls are: no freeze, x 1 is frozen to 1, x 1 is frozen to 0. The active control parameters are mentioned below each dynamics. The dynamics are synchronous and the self-loops on states are not shown. For the sake of clarity, the set of updated variables m on the transition was omitted. The stable states of each dynamics are coloured in three shades of grey, and their contours are drawn in different styles. Each contour style is associated with a different control input. 1. the absence of control, 2. the freezing of the variable x 1 to 1 (u 1 1 = 0), 3. the freezing of the variable x 1 to 0 (u 0 1 = 0).

We can see that applying different freezing controls results in different behaviours in the dynamics of the system. These dynamics changes lead to different transitions and different equilibriums.

It is worth noticing that some variables are purposely uncontrolled to play the role of observers used for freely reporting the evolution of the states of a system. In biology, biomarkers play the role of these observers. An observer is always an uncontrolled variable used to assess the evolution of the system. Therefore, the uncontrolled variables are important for assessing the fate of the dynamical system. The set of controlled variables is denoted C X , and the set of uncontrolled variables is CX = X \ C X . In our example in Figure 2.7, the CX -variables are {x 2 , x 3 }, and the C X -variables are {x 1 }

The profile of a set of variables A denotes the instantiation of the variables of A in a given state s. In the sequel, the profiles of uncontrolled variables are denoted ' CX -profiles', and the profiles of controlled variables are denoted 'C X -profiles'.

-Control sequence dynamics

We build on previous studies by characterising control sequences to explore the inference of sequences of control,. Therefore, we need to define a framework that enables us to describe the notion of sequentiality of control in Boolean control networks. In this chapter, we define the control sequence dynamics and related concepts (Section 3.1), present the problem of control sequence discovery (Section 3.2), and discuss its complexity (Section 3.3).

. Control sequence dynamics

Controlled dynamics extend the Boolean network dynamics by specifying how the system evolves through a sequence of control inputs.

A sequence of controls is formally defined by the function µ : N + → (U → B) indexing control inputs, where µ i , i ≥ 1, is the i-th control input in the sequence and µ [k] stands for the sequence of size k starting with µ 1 and ending in µ k :

µ [k] = (µ 1 , . . . , µ k ).
Controlled dynamic. Given a Boolean control network F U , the model of controlled dynamics is defined as a labelled transition system that includes the control inputs as labels ⟨S X , S U × M, -→⟩, such that as transition is defined by:

s µ i ,m ---→ s ′ def == s ′ = (F µ i ) ↓m (s) ∪ s X\m . (3.1)
A control sequence µ [k] leads, therefore, to the following trajectory (path) of size k + 1 and in which, for each transition, a control is applied:

s 1 µ 1 ,m 1 ----→ . . . s i µ i ,m i ---→ s i+1 . . . s k µ k ,m k ----→ s k+1 .
In Equation 3.1 the state s i denotes the i-th state of the sequence. Each control is labelled by a pair of control and modality. For the sake of clarity, we omit the mode if it is not needed for explanation, meaning we consider the union relation:

µ -→= m∈M µ,m --→.
State trace. The trace defines the sequence of visited states in the control sequence trajectory:

(s i ) 1≤i≤k+1 . F {u 1 2 ,u 0 2 ,u 1 3 ,u 0 3 } =    x 1 = (x 1 ∧ ¬x 2 ) ∨ (x 1 ∧ ¬x 3 ) ∨ (¬x 1 ∧ x 2 ∧ x 3 ) x 2 = ((x 1 ∧ x 3 ) ∨ (¬x 1 ∧ x 2 ) ∨ ¬u 1 2 ) ∧ u 0 2 x 3 = ((x 1 ∧ x 3 ) ∨ (¬x 1 ∧ ¬x 2 ) ∨ ¬u 1 3 ) ∧ u 0
F {u 1 2 ,u 0 2 ,u 1 3 ,u 0 3 } .
From left to right, top to bottom, the respective controls are: no freeze, x 3 is frozen to 1, x 3 is frozen to 0, x 2 is frozen to 1, x 2 and x 3 are frozen to 1, x 2 is frozen to 1 and x 3 is frozen to 0, x 2 is frozen to 0, x 2 is frozen to 0 and x 3 is frozen to 1, x 2 and x 3 are frozen to 0. The active control parameters are mentioned below each dynamics. The dynamics are synchronous and the self-loops on states are not shown. The stable states of each dynamics are coloured in three shades of grey, and their contours are drawn in different styles. Each 2-tuples of contour styles and shades of grey is associated with a different control input. We can notice that the centre graph where x 2 and x 3 is frozen to 1 have a unique cyclic attractor and no stable states. For example, take the controlled Boolean network described in Figure 3.1 and its different controls. Let the initial state be 010, the sequential application of the sequence of control µ [START_REF] Barabási | Emergence of scaling in random networks[END_REF] = ({u 0 2 }, {u 0 2 }, {u 1 2 }, {u 1 2 }, ∅) leads to the following trajectory in the controlled dynamics:

010 {u 0 2 } ---→ 000 {u 0 2 } ---→ 001 {u 1 2 } ---→ 011 {u 1 2 } ---→ 110 ∅ --→ 100. (3.2)
In Equation 3.2, the control inputs are represented by their active control set, with elements indexed by the freeze value, and the stable states traversed by the trajectory are in boldface. The state trace of the trajectory is thus:

(010, 000, 001, 011, 110, 100) Classes of sequences. Control sequences can be categorised into families based on the evolution of the control between steps. The complexity of the sequential control evolution depends on the rule governing such control application strategies. Indeed, a chosen strategy can impact the inference of a sequence. It may exist a sequence of control for a given strategy that evolves a Boolean network dynamics towards an expected state, when for another strategy such problem cannot be solved. We propose two control application strategies:

• Total Control Sequence (TCS): All the controls are triggered during the first phase for all the controlled variables and remain active throughout the sequence. The values to which the variables are frozen may change.

• Open Control Sequence (OCS): No constraints regarding control parameters are imposed. A control can be changed or released freely.

The sequence described in the trajectory (3.2) is an OCS since x 2 is controlled, then uncontrolled. The TCS class is mainly used for proofs and algorithmic reasons. This sequence has no realistic biological application of its own. Indeed, in the case where we consider that CX -variables correspond to biomarkers, controlling all genes corresponding to C X -variables is not realistically feasible in vitro and in vivo. The OCS class is the most general class that may represent the action of the drugs on molecular networks, potentially implying the modification and the relaxation of the actions. The following inclusion between these families holds: TCS ⊊ OCS.

The control dynamics enable the change of control at any time in the dynamics. This observation leads to the following proposition: Proposition 3.1. For any control sequence µ [k] , there exists a total control sequence of the same size ν [k] ∈ TCS generating the same state trace under the synchronous mode.

Proof. Take a control sequence µ [k] and an initial state. For a transition s i µ i -→ s i+1 , 1 ≤ i ≤ k, two cases may occur for the control parameters of the controlled variables, x j ∈ C X :

1. If one of the two control parameters u 0 j , u1 j is already activated, then the configuration remains the same for ν.

2. If the control parameters are both idle (u 0 j = 1, u 1 j = 1), then we directly fix the expected final state value by setting the control appropriately, namely:

ν i (u 0 j ) = 0, ν i (u 1 j ) = 1 if s i+1 (x j ) = 0 and ν i (u 0 j ) = 1, ν i (u 1 j ) = 0 if s i+1 (x j ) = 1.
As the update is synchronous, then all the values of the controlled variables

x j lead to the state s i+1 (x j ) in a controlled way. For uncontrolled variables, x j ∈ CX , we have (f ν ) j = (f µ ) j since no modifications occur, meaning the update is the same.

Since a transition only depends on the previous state that can be obtained by applying of a TCS control input ν i , we can define a TCS control input for each step, finally leading to a total controlled sequence ν [k] , simulating the trajectory controlled by µ [k] from an s 1 .

Proposition 3.1 states the observational equivalence between OCS and TCS classes under the synchronous update mode, namely any OCS control sequence state trace can be reproduced by a TCS sequence. Thus, under the control dynamics, for each OCS control sequence, a TCS control sequence exists with the same state trace. For example, the OCS sequence of control µ[5] = ({u 0 2 }, {u 0 2 }, {u 1 2 }, {u 1 2 }, ∅), which generates the trajectory (3.2), has an equivalent TCS sequence of control 1 with the same state trace.

µ ′ [5] = ({u 0 2 , u 0 3 }, {u 0 2 , u 1 3 }, {u 1 2 , u 1 3 }, {u 1 2 , u 0 3 }, {u 0 2 , u 0 3 })
Let the initial state be 010, the control sequence µ ′ [START_REF] Barabási | Emergence of scaling in random networks[END_REF] leads to the following trajectory in the controlled dynamics. The control inputs are represented by their active control set, with elements indexed by the freeze value, and the stable states traversed by the trajectory are in boldface.

010 {u 0 2 ,u 0 3 } -----→ 000 {u 0 2 ,u 1 3 } -----→ 001 {u 1 2 ,u 1 3 } -----→ 011 {u 1 2 ,u 0 3 } -----→ 110 {u 0 2 ,u 0 3 } -----→ 100. (3.3)
In control sequence dynamics, allowing a change of control at any time has no concrete application in biology. Knowing the state of the phenotype of a cell at any time to administer a sequential therapy is impractical. On the contrary, waiting for the cell to reach a stable phenotype before changing the administered drug is practicable.

We could have considered other types of attractors; for example, a cyclic attractor for which a subset of components does not vary is instantiated to a desired phenotype. We have chosen to constrain ourselves to stable states due to them being the easiest type of attractors to find. Based on this choice, we define the following control dynamics:

Control Evolution based on Stable-State dynamics. The model of controlled dynamics is said to be Control Evolution based on Stable-State dynamics (ConEvs) if the modification of the control inputs instantiation only occurs at a stable state. The change of control modifies the dynamics and releases the stability; hence, the ConEvs dynamics fulfil the following property:

∀s 1 µ 1 -→ . . . µ k -→ s k+1 : µ i ̸ = µ i+1 ⇐⇒ stbl Fµ i (s i+1 ), given that s i µ i -→ s i+1 µ i+1 ---→ s i+2 , 1 ≤ i < k. (3.4)
Under the ConEvs dynamics, we impose as a restriction that the property must be validated on a stable state. When no state in the set of target states is stable in the dynamics of at least one of the possible controlled Boolean networks2 , the CoFaSe problem will have no solution.

In ConEvs dynamics, changing the control is the only way to evolve the dynamics since a stable state is reached with the current instance of the Boolean network, which results from applying a control input to the BCN. ConEvs dynamics model either the different mutational steps in which a mutation rewires the network reaching another phenotype, the molecular signature of which is stable, or a therapeutic regimen where the drug administering depends on the therapeutic evaluation modelled by a stable state assessment. The trajectory described in (3.2) is ConEvs, in contrast to the trajectory described in (3.3), in which the control is changed in state 011 which is not a stable state of F {u 1 2 ,u 1 3 } . Under the ConEvs dynamics, Proposition 3.1 is false. Therefore, some OCS sequences of control do not have a TCS equivalent sequence. Thus, it may exist an OCS sequence of control that evolves a Boolean network dynamics towards a desired state in which, for a TCS control strategy, the same problem is unsolvable. The trajectory described in (3.2) is a prime example of an instance in which no TCS equivalent sequence of control exists. The state trace of the Trajectory (3.2) cross, in this order, the states 001, 011, and 110. To reproduce such trace, two total controls would be needed since the C X -variables are different in 001, 011 and 110. In Figure 3.1, no controlled Boolean networks have in their dynamics 011 as a stable state. Thus, under the ConEvs dynamics, there is no TCS sequence of control that could reproduce the Trajectory (3.2) state trace.

Contracted control sequence.

The contracted control sequence retains only one instance of the control input for each sub-sequence with identical control inputs. For ConEvs dynamics, the contracted control sequence can be considered as the sequence making the dynamics evolve from stable states to stable states. Note that under the synchronous update mode and the ConEvs dynamics, the initial control sequence can be easily retrieved by connecting the encountered stable states for each F µ i using a trajectory controlled by µ i .The contracted control sequence notation, is therefore, an alternative ConEvs representation of a sequence of control, enabling a clearer visualisation of its control evolution. In the case of Example (3.2), the contracted sequence is thus represented by the active controls

({u 0 2 }, {u 1 2 }, ∅).
In the rest of this manuscript, all the results are based on the synchronous dynamics, in which all the variables are updated jointly. This choice was motivated by the fact that, under this update mode, the practical computation time of the reachability problem is reduced. Indeed, in the asynchronous update mode, one needs to tackle the fact that state transition becomes a relation inducing nondeterminism, that should not be exhaustively explored to ensure the efficiency of an algorithm.

. Control sequence discovery

Determining a control sequence that modifies the dynamics to evolve towards an expected state can be stated as a reachability problem:

Let S α , S ω ⊆ S X be two set of states, can we find a control sequence:

µ [k] = (µ 1 , . . . , µ k ) such that there exists a path s 1 µ 1 -→ . . . µ k -→ s k+1 , with: s 1 ∈ S α and s k+1 ∈ S ω ?
We refer to this problem as the 'Controlled Fate in Sequence' (CoFaSe) problem.

Consider, for example, the Boolean network from Figure 2.7. For this CoFaSe problem, the initial states are S α = {000}, whereas the final states are S ω = {010, 110}. x 1 is the sole controllable variable, whereas x 2 and x 3 are observers. Therefore, for this CoFaSe problem, we must find a control sequence reaching any state in which x 2 = 1 and x 3 = 0 from the initial state 000 by only controlling x 1 .

For all three possible controls (i.e., x 1 not freeze, x 1 freeze to 1 and x 1 freeze to 0), no paths connect 000 to 010 or 000 and 110. However, the freeze of x 1 to 1 leads to the state 111 (middle graph). From this state, the freeze of x 1 to 0 (rightmost graph) finally leads to the state 010. This sequence of controls, therefore, solves the above CoFaSe problem and the following trajectory. The control inputs are represented by their active control sets, with elements indexed by the freeze value, and the stable states traversed by the trajectory are in boldface.

000 ∅ --→ 001 {u 1 1 } ---→ 101 {u 1 1 } ---→ 111 {u 0 1 } ---→ 011 {u 0 1 }
---→ 010.

(3.5)

Applied to ConEvs dynamics, the CoFaSe problem implies that at least a state appearing in S ω is stable for F µ k . We suggest that all states of S α should be stable for uncontrolled F . When this is not the case, we consider the stable states have in their basin of attraction one of the initial states. For example, if we consider for the Boolean network from Figure 2.7 with S α = {000} and S ω = {010, 110}, to change the control, we would need to wait for F ∅ (000) * to reach the stable state 001. In this case, we simply consider that S α = {001}. In this case, the TCS contracted control sequence ({u 1 1 }, {u 0 1 }) resolves CoFaSe under the ConEvs dynamics with the following trajectory, in which all states are stable under the previous control:

001 {u 1 1 } ---→ * 111 {u 0 1 } ---→ * 010.
(3.6)

In another example, let us consider the Boolean network from Figure 3.1 with S α = {010} and S ω = {100}. In this case, the contracted OCS sequence ({u 0 2 }, {u 1 2 }, ∅) resolves CoFaSe under the ConEvs dynamics with the following trajectory, in which all states are stable under the previous control:

010 {u 0 2 } ---→ * 001 {u 1 2 } ---→ * 110 ∅ - → * 100.
(3.7)

In biological modelling, the outcome of reprogramming can be formulated as a condition on the biomarkers, checking whether the system has reached an expected signature. Note that achieving a given state for controlled variables is trivial and consists in merely assigning their expected values by setting the appropriate control inputs. Therefore, the main problem lies in indirectly influencing the state variation of the uncontrolled variables by applying freeze actions on controllable variables.

Minimal control sequences.

We now define some properties related to the size of sequences. We first consider the CoFaSe problem, in which the control can be changed at any time:

• A sequence µ [k]
is said to be minimal for the CoFaSe problem with respect to F U , S α , and S ω if no control sequences ν [l] satisfy the CoFaSe problem, such that l < k.

We now consider contracted control sequence under the ConEvs dynamics and resolving the CoFaSe (F U , S α , S ω ).

• A contracted control sequence µ [k] is called minimal for the CoFaSe problem with respect to F U , S α , and S ω if no contracted control sequence satisfying the CoFaSe problem has a lower number of steps.

To define the following notions on contracted control sequence, we first need to define the parsimony and minimality of a control input in a contracted sequence transition:

• A control input µ is called parsimonious for a contracted transition s µ -→ * s ′ ∧ ST BL Fµ (s ′ ) if ∄µ ′ ∈ S U , µ ′ ⊆ µ ∧ s µ ′ -→ * s ′ ∧ ST BL F µ ′ (s ′ ) • A control input µ is called minimal for a contracted transition s µ -→ * s ′ ∧ ST BL Fµ (s ′ ) if ∄µ ′ ∈ S U , |µ ′ | < |µ| ∧ s µ ′ -→ * s ′ ∧ ST BL F µ ′ (s ′ ).
A minimal control input with respect to a given contracted transition is, by definition, also parsimonious.

We now define the parsimony and control minimality of a contracted control sequence:

• A contracted sequence µ [k] is called parsimonious if it yields a trajectory s 1 µ 1 -→ * s 2 . . . s k µ k -→ *
s k+1 reaching a target state s k+1 ∈ S ω from an initial state s 1 ∈ S α , in which all the controls µ i , with 1 ≤ i ≤ k, are parsimonious controls for the contracted transition

s i µ i -→ * s i+1 . • A contracted sequence µ [k] is called control minimal if it yields a trajectory s 1 µ 1 -→ * s 2 . . . s k µ k -→ *
s k+1 reaching a target state s k+1 ∈ S ω from an initial state s 1 ∈ S α , in which all the controls µ i , with 1 ≤ i ≤ k, are minimal controls for the contracted transition

s i µ i -→ * s i+1
. If a sequence is control minimal, it is by definition also parsimonious.

The following sequences are examples of minimal and control minimal contracted control sequences:

• The TCS contracted control sequence ({u 1 1 }, {u 0 1 }) of Trajectory 3.6 is minimal and control minimal under the ConEvs dynamics.

• The OCS contracted control sequence ({u 0 2 }, {u 0 1 }, ∅) of Trajectory 3.7 is minimal and control minimal under the ConEvs dynamics. Note that no TCS sequence solving this CoFaSe problem exists.

The following sequences are examples of minimal or control minimal contracted control sequences, but not both:

• Let us consider the Boolean network from Figure 2.7 with S α = {000} and S ω = {010, 110}. The TCS contracted control sequence ({u 1 1 }, ∅, {u 0 1 }, {u 1 1 }, {u 0 1 }) that resolves CoFaSe under the ConEvs dynamics with the following trajectory is a control minimal contracted control sequence but is not minimal:

001 {u 1 1 } ---→ * 111 ∅ - → * 100 {u 0 1 } ---→ * 001 {u 1 1 } ---→ * 111 {u 0 1 } ---→ * 010. (3.8)
• Let us consider the Boolean network from Figure 3.1 with S α = {010} and S ω = {100}. The OCS contracted control sequence ({u 0 2 }, {u 1 2 }, {u 0 2 , u 0 3 }) that resolves CoFaSe under the ConEvs dynamics with the following trajectory is a minimal contracted control sequence but is not control minimal:

010 {u 0 2 } ---→ * 001 {u 1 2 } ---→ * 110 {u 0 2 ,u 0 3 } -----→ * 100.
(3.9)

Note that a minimal and control minimal sequence for a given CoFaSe problem may not be the sequence with the minimal total number of perturbations (i.e., number of freeze or unfreezing of variables). Indeed, there may be a control sequence with a minimal total number of perturbations that is not minimal in size.

. Complexity of CoFaSe

In this section, we show that the inference of a control sequence satisfying CoFaSe is PSPACE-hard. Since the freezing to 0 and to 1 cannot be triggered simultaneously for a single variable, the cardinality of possible controlled transitions from a state is 3 |X| • |M |. Finding a single parsimonious control without considering a set of initial states is NP-complete [START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF]. Thus, the CoFaSe problem is even less tractable than finding single controls (assuming that PSPACE ̸ = NP). Therefore, finding the control sequence by exhaustively exploring possible control spaces is not tractable.

To prove that CoFaSe inference is a PSPACE-hard problem, we lean on the fact that the problem of reachability in Boolean networks working in synchronous mode can actually be formalised as a CoFaSe problem. Indeed, reachability in a Boolean network is precisely the CoFaSe problem for a Boolean control network without controlled variables. Lemma 3.1 shows that this reduction is not merely an artefact. Indeed, We can construct a network with a non-empty set of control variables and reduce the CoFaSe problem for this network to a reachability problem for a standard Boolean network.

Lemma 3.1. Deciding whether a control sequence exists for the CoFaSe problem in the synchronous mode is at least as hard as reachability in (uncontrolled)

Boolean networks in synchronous mode.

Proof. Take an n-variable Boolean network F and construct a Boolean control network F ′ by adding to F the single control variable x 0 and defining the update functions f ′ i of F ′ in terms of the update functions f i of F in the following way:

f ′ i = f i ∧ x 0 , 1 ≤ i ≤ n, f ′ 0 = 0,
where f ′ 0 is the update function for x 0 . Consider the controls µ 1 = d 1 0 and µ 0 = d 0 0 controlling x 0 to 1 and 0 respectively. The previous two properties ensure that the state graph of F ′ µ 1 is that of F , with x 0 = 1 added to each state, and that the state graph F ′ µ 0 only contains transitions to the state 0, which is the state in which all variables are 0.

Let X be the set of variables of F . The set of variables of F ′ is thus X ′ = X ∪ {x 0 }. Fix a set of starting states S α ⊆ S X ′ and a set of target states S ω ⊆ S X ′ \ (S α ∪ {0}), such that the states in both sets satisfy x 0 = 1. The Co-FaSe problem for the tuple (F ′ , S α , S ω ) has a solution if and only if the states in S ω↓X are reachable from S α↓X in F . Indeed, by construction of F ′ and since 0 / ∈ S ω , the control sequence for this instance of CoFaSe may only be the singleton control sequence consisting of µ 1 , and it must ensure the reachability of S ω from S α in F µ 1 , whose state graph is trivially isomorphic to that of F .

In conclusion, an oracle for CoFaSe would allow to solve reachability in Boolean networks working in the synchronous mode with, at most, polynomial overhead, which proves the lemma statement.

It is known that the complexity of the reachability in Boolean networks working in synchronous mode is PSPACE-complete [START_REF] Paulevé | Reconciling qualitative, abstract, and scalable modeling of biological networks[END_REF][START_REF] Dennunzio | Complexity of the dynamics of reaction systems[END_REF]. 3 Below, we provide a sketch of an alternative proof of this complexity based on a reduction from Deterministic Linear Bounded Automaton (Lemma 3.2). In Lemma 3.3 we prove that the reachability of Boolean networks with the synchronous mode is PSPACE. Finally, these two lemmas result in the Theorem 3.1, which state the PSPACE-completeness of the reachability problem for Boolean networks with the synchronous update mode. Lemma 3.2. Given a Boolean network F with the variables X, a set of starting states S α ⊆ S X , and the set of target states S ω ⊆ S X \ S α , it is PSPACE-hard to decide whether F can reach any of the states in S ω from a state in S α in synchronous mode.

Proof. The proof idea is to polynomial-time reduce the acceptance problem of a Deterministic Linear Bounded Automaton (a DLBA) to reachability for Boolean networks working in synchronous mode.

An LBA is a Turing machine that is only allowed to use, at most, f (n) contiguous tape cells, in which n is the size of the input and f is a linear function.

Deciding whether a DLBA accepts a given input string is a PSPACE-complete problem (e.g., [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]).

Take a DLBA M and construct the Boolean network F simulating M in the following way. Define the Boolean variables A i,j and Q i,k , in which i indexes the tape cells of M , j indexes the symbols in the tape alphabet of M , and k indexes the states of M . The situation in which the i-th tape cell contains the j-th symbol is represented by setting A i,j to 1. The situation in which M is in the k-th state and the head is on the i-th tape cell is represented by setting Q i,k to 1. F operates by stepwise simulating the evolution of M : rewriting the j 1 -th symbol to the j 2 -th symbol in the i-th tape cell is done by setting A i,j 1 to 0 and A i,j 2 to 1, while moving the head from cell i 1 to i 2 and changing the state from k 1 to k 2 is simulated by setting

Q i 1 ,k 1 to 0 and Q i 2 ,k 2 to 1. The synchronous dynamics of F , therefore, faithfully simulate M , because M is deterministic.
For any input word w, the DLBA M reaches a configuration in the set of accepting configurations C A if and only F can reach the encoding of one of the configurations C A from the encoding of the initial configuration of M .

The statement of the lemma follows from the facts that the procedure of constructing F from M is polynomial and that acceptance for DLBA is PSPACEcomplete.

Lemma 3.3. Given a Boolean network F with the variables X, a set of starting states S α ⊆ S X , and the set of target states S ω ⊆ S X \ S α , it is in PSPACE to decide whether F can reach any of the states in S ω from one of the states in S α in synchronous mode.

Proof. The proof idea is to construct a DLBA M that accepts the input if and only if the Boolean network F can reach a state in S ω from a state in S α . The initial configuration of M consists of the following three segments:

1. the list of binary vectors representing the states in S α , each vector written in two copies; 2. the list of binary vectors representing the states in S ω , each vector written in one copy;

3. an |X|-bit binary counter initialised to 0, where |X| is the number of binary variables of F .

In the remainder of the proof, we implicitly assume that the states of F are represented as binary words. A state (x 1 , x 2 , ..., x n ) is thus represented by the word x 1 x 2 . . . x n . Consider a state s ∈ S α . The initial configuration of M contains a substring ss. M starts by simulating the transitions of F on one copy of s and replacing the other copy by the new state s ′ = F (s), thereby yielding the new substring ss ′ . The subsequent operation of M is divided into macrosteps, during which it carries out the following actions:

1. calculates the new state for each pair of states in Segment (1);

-State of the art in control inference

Algorithmic methods enabling the identification of control strategies of Boolean networks in order to identify therapeutic targets have been the subject of a number of publications in recent years. The controllability of biological systems has mostly been done in one-step. Sequential controllability analysis, in contrast, is still in its infancy. and has mainly been studied by Mandon et al. in [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF][START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF][START_REF] Mandon | Algorithmes pour la prédiction de stratégies de reprogrammation cellulaire dans les réseaux Booléens[END_REF]. We therefore explain their approach in detail and compare it with our works.

In this chapter, we first describe different approaches of one-step programming in Section 4.1. In Section 4.2, we then describe the sequential programming approach proposed by Mandon et al. Finally, we will conclude in Section 4.3 by explaining the principal differences between the sequential paradigm proposed by Mandon et al. and ours.

. One-step reprogramming

We briefly recall the existing approaches to one-step reprogramming, namely: simulation, max-SAT ATPG,attractors and Hamming distance, stable motifs, Gröbner basis, and prime implicants. These approaches differ according to their optimisation objectives and control application.

. Simulation

To the best of our knowledge, one-step reprogramming for Boolean networks was pioneered by Layek et al. in [START_REF] Layek | Cancer therapy design based on pathway logic[END_REF]. The authors present an approach for designing cancer therapies by assimilating cancerous perturbations with stuck-at-fault and bridging faults by analogy with the errors of electronic circuits. Relevant gene regulation pathway information is first used to produce an acyclic Boolean network. The resulting network has a set of input and output variables. The Boolean network is then transformed into a digital circuit from which an enumeration and classification of possible faults is realised.

Stuck-at-fault corresponds to the setting of a network variable to a particular value (0 or 1). Bridging faults correspond to the removal or incorporation of new interactions between system variables. A simulation-based method for implementing and identifying stuck-at-fault failures is proposed. The authors first model, from biological knowledge, the effect of existing n drugs. The authors then exhaustively simulate from a given initial state the 2 n possible drug binary vectors. If a particular drug is applied, it is assigned the value 1; otherwise, it is assigned the value 0. A drugs vector is considered effective if, for single failures or combinations of failures, its application to the system results in a healthy output state. The method proposed in this article is therefore based on a 'brute force' method of the exhaustive simulation of all possible single failures for acyclic Boolean networks.

. Max-SAT ATPG

In [START_REF] Kent | Application of Max-SAT-based ATPG to optimal cancer therapy design[END_REF], Lin et al. propose an improvement on the method by Layek et al. The authors present an efficient and extensible SAT-based ATPG1 methodology for cancer therapy and introduce the notion of optimality of therapies. The digital circuit presented in [START_REF] Layek | Cancer therapy design based on pathway logic[END_REF], in addition to the testing conditions, is converted into a conjunctive normal form (CNF). The conjunctive normal form is then augmented with the desired output and solved using a weighted partial Max-SAT solver. Each gene of the network is associated with an CNF formula. This formula is evaluated at 1 if and only if the variables representing its inputs and outputs take on values consistent with the gene truth table. An α failure is added to this formula as an input variable. The simulation of the activation of the failure consists in adding a clause α to the CNF, whereas the simulation of the non-activation of the failure consists of adding a clause ¬α to the CNF. To select the drugs that guarantee the best output from the network, weights are assigned to the clauses representing exit variables in the conjunctive normal form so that the healthy state is associated with the greatest weight, and the failed states the lowest with weight. In order to prioritise treatments that minimise the number and cost of drugs, positive weights proportional to the cost of a drug are assigned to failures corresponding to the action of the drug.

. Attractors and Hamming distance

In [START_REF] Paul | A decomposition-based approach towards the control of boolean networks[END_REF][START_REF] Paul | An efficient approach towards the source-target control of boolean networks[END_REF], Paul et al. propose an approach for finding single-step control, enabling the Boolean network to reach one of the desired attractors from a given initial state. The paper considers various types of control actions but focuses on temporary simultaneous perturbations. The authors aim is to make the control as least invasive as possible to the system as possible. This aim results in the search for the most parsimonious control. Simultaneous temporary perturbations were all applied for just a single time step at the same time. The perturbations induce a change in the value of some variables, but these variables can later be updated according to their original Boolean function. Thus, only the dynamics of the Boolean network without control needs to be considered.

The problem of finding a minimal control driving the system from an initial state to a desired attractor is PSPACE-hard. Thus, a simple global approach performing computations on the entire network will not scale well for large networks. Therefore, they propose a decomposition-based solution to this problem, which can be significantly quicker than existing approaches on large networks. This approach takes advantage of existing algorithms for computing the basin of attraction of an attractor.

The central assumption of Paul et al. is that the computed basins of attraction are smaller than the size of the transition system. This factor reduces the state space that needs to be considered and thus improves efficiency. A minimal control is determined by finding the minimal Hamming distance between the initial state and the state of a target attractor. The control can then be deduced from the substitutions of variable values required to jump from the initial state to the state of the target attractor. The algorithm presented in [START_REF] Paul | An efficient approach towards the source-target control of boolean networks[END_REF] performs efficiently for networks with a low number of small strongly connected components in the interaction graph as, in this case, the computed basins of attraction will also be small.

. Stable motifs

In this article [START_REF] Jorge | Cell fate reprogramming by control of intracellular network dynamics[END_REF], Zañudo et al. propose a network control approach that combines the structural and functional information of a Boolean network to identify control targets. The method builds on the concept of stable motifs and their relation to finding attractors. By connecting stable motifs with other stable motifs, the presented algorithm identifies targets whose manipulation ensures the convergence of the system to an attractor of interest form the original network dynamics. Stable motifs are defined as interaction subgraphs composed of minimal strongly connected components in which the states of the motif variables form a partial fixed point that, once reached, will not be changed by the dynamics. Stable motif control interventions are guaranteed to drive the network from all possible sets of initial states to the target attractor state. This outcome can be explained by the fact that controlling all cycles of a Boolean network results in a network with only one attractor. Furthermore, the control only needs to be applied transiently for the network to reach and stay in the desired attractors of the original network.

. Gröbner basis

The authors of [START_REF] Murrugarra | Identification of control targets in Boolean molecular network models via computational algebra[END_REF], Murrugarra et al., propose an approach that takes advantage of the rich algorithmic theory of computer algebra to infer potential intervention targets in synchronously updated Boolean networks. The paper considers two types of control actions: the deletion of arcs and the deletion (or constant expression) of nodes. The proposed methods are based on rewriting the Boolean network, its control actions, and the desired property as a system of polynomial equations. Three control actions are considered in the paper: the generation of new steady states representing a desirable cell fate,; the removal of existing steady states representing undesirable cell fates; and the blocking of regions in the state space in which particular values of variables trigger an undesirable pathway or are the signature of an abnormal cell. Based on these points, the authors obtain a system of polynomial equations (or a single equation) that needs to be solved to find the appropriate controls. The resolution of this system of equations is based on the calculation of the Gröbner basis. The controls inferred by using this approach do not guarantee the global reachability of a desired stable state because the inferred control modified the state space by augmenting the size of a desired stable state basin of attraction or removing undesired attractors. [START_REF] Biane | Abductive network action inference for targeted therapy[END_REF][START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Biane | Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery[END_REF] an approach for inferring the minimal sets of actions, enabling the reprogramming of Boolean networks updated synchronously or asynchronously. The authors introduce the formalism of controlled Boolean networks via arc freezing and variable freezing. The control formalism presented in Section 2.3 is drawn from the work of Biane et al. who present two reprogramming modes, possibility and necessity, in which, respectively:

. Prime implicants

Biane et al. propose in

• At least a stable state of the controlled Boolean network validates the desired property.

• All stable states of the controlled Boolean network validate the desired property.

Biane et al. prove that the computation of the parsimonious control strategy, in which the network needs to have stable states validating a property, is a problem of abductive inference in propositional logic. Using well-known methods for computing the prime implicants of Boolean functions, the authors developed algorithms computing all parsimonious control strategies.

The first algorithm recursively calculates all parsimonious control strategies. The algorithm is based on integer linear programming and rewrites the Boolean network, its control actions, and the desired property as a system of linear equations. This method also makes it possible to assign costs to reprogrammation and thus compute control strategies minimizing this cost. This algorithm is also used as a solver in one of the algorithms solving CoFaSe under the ConEvs dynamics that we present later.

The second algorithm based on the binary decision diagram calculates all parsimonious control strategies in one-step. This algorithm calculates the prime implicants from the formula specifying the stability and property conditions represented by a reduced ordered binary decision diagram. This algorithm obtains better performance than the first algorithm in the case of the necessity reprogramming mode.

. Sequential reprogramming

In [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF][START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF], Mandon et al. studied asynchronously updated Boolean networks and, more particularly, their interaction graph. The authors expected to find all control sequences reaching a desired property from a set of initial states and having a number of disturbances inferior to a defined limit. The authors considered the total number of perturbations realised throughout the sequence. A minimal sequence of control is considered to be a sequence with a minimal number of perturbations (i.e., a minimal number of controlled variables). The authors goal was to find sequential controls with fewer perturbations to bring new reprogramming solutions to biological networks for which one-step reprogramming strategies are already known.

To modify the dynamics of a Boolean network, Mandon et al. perturb either one of its functions or its current state. A function perturbation is considered to be a permanent perturbation as it induces a permanent state change of nodes to a desired profile of 1 or 0. Such perturbation is equivalent to node freezing. A state perturbation is considered to be a temporary perturbation as it induces a state change of nodes, but these nodes can later be updated according to their original Boolean functions. A state perturbation can also be viewed as a jump in the dynamics of the studied Boolean network.

Given a set of initial states and a set of target states, Mandon et al. classify successful reprogramming strategies according to different 'degrees of success':

• If the target is reachable in principle with the control strategy but might never be reached then the strategy is called existential.

• If the target is always reached, then the strategy is called inevitable.

Paper [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF] shows that the strongly connected components of the interaction graph considerably influence the dynamics of the Boolean network. The authors found that strongly connected components that contain loops are more important. Paper [START_REF] Mandon | Algorithmes pour la prédiction de stratégies de reprogrammation cellulaire dans les réseaux Booléens[END_REF] presents an algorithm that perturbs the strongly connected components in a given order, using sequentiality to reduce the size of the perturbations. However, the proposed algorithm does not always return minimal solutions and works only on networks with small strongly connected components.

Papers [START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF] propose a second algorithm that relies on a transition graph with k superposed layers corresponding to the number of k possible perturbations given by the user. This second algorithm, which enables the network to be perturbed in any state, returns a complete list of solutions for temporary and permanent perturbations but only works on small networks due to its slowness.

In the framework of the papers [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF], sequential reprogramming enables the network to be perturbed in any state. The authors claim this process requires complete observability of the system, which is very difficult to obtain experimentally in vivo and in vitro. To make the sequential reprogramming practical, the authors designed a sequential reprogramming strategy that uses attractors [START_REF] Paul | A decomposition-based approach towards the control of boolean networks[END_REF][START_REF] Paul | An efficient approach towards the source-target control of boolean networks[END_REF] as intermediate steps. This control update dynamics resembles our ConEvs dynamics but, unlike ConEvs, enable a change of control on cyclic attractors. The authors propose a third algorithm [START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF] using this new update control dynamics and inspired by their second algorithm, enabling only temporary perturbations. This algorithm is quicker than the other proposed methods in some cases and returns shorter perturbation sequences. However, the resulting sequences are fewer and generally have a larger number of perturbations than those yielded by the second algorithm.

. Conclusion

The algorithmic methods developed in the literature to calculate control strategies for Boolean networks differ in the objectives of the reprogramming, the modelled perturbation, the dynamics and topology of the studied networks, and the minimality of the solutions. For example, the one-step controllability methods based on simulation in [START_REF] Layek | Cancer therapy design based on pathway logic[END_REF][START_REF] Kent | Application of Max-SAT-based ATPG to optimal cancer therapy design[END_REF] and attractors and Hamming distance in [START_REF] Paul | A decomposition-based approach towards the control of boolean networks[END_REF][START_REF] Paul | An efficient approach towards the source-target control of boolean networks[END_REF] seek to infer controls that drive the system from a stable state to an attractor validating a desired property. In contrast, the one-step controlabillity methods based on stable motifs [START_REF] Jorge | Cell fate reprogramming by control of intracellular network dynamics[END_REF], the Gröbner basis in [START_REF] Murrugarra | Identification of control targets in Boolean molecular network models via computational algebra[END_REF], and the prime implicants in [START_REF] Biane | Abductive network action inference for targeted therapy[END_REF][START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Biane | Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery[END_REF] seek to infer controls that drive the system from all stable states to a set of attractors validating a desired property. In the literature, the main approaches have some similarities but also some differences in term of goal and framework.

For example, determining a control driving the system from an initial state to a desired attractor and determining a control resulting in a network with a given set of property on its fixed point attractors are two problems with differing complexities. The first is PSPACE-hard, whereas the second is NP-hard. Such differences mean that comparing these approaches can be a difficult exercise.

The sequential reprogramming framework we propose in this thesis differs from that introduced in [START_REF] Hugues Mandon | Temporal reprogramming of Boolean networks[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF][START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF][START_REF] Mandon | Algorithmes pour la prédiction de stratégies de reprogrammation cellulaire dans les réseaux Booléens[END_REF]. We seek to infer a minimal contracted control sequence in size. In contrast, Mandon et al. 's main objective was to minimise the total number of perturbations, particularly regarding known one-step controls. These fundamental differences in the objectives of the reprogramming and the definition of minimality form real variations in the way sequential control is defined and treated. Concretely, in all examples in which the algorithms by Mandon et al. found a sequential control smaller than an existing one-step control, our algorithms would return only a one-step control.

Another difference concerns the nature of perturbations: the third algorithm of Mandon et al. presented in [START_REF] Hugues Mandon | Sequential reprogramming of Boolean networks made practical[END_REF][START_REF] Hugues Mandon | Algorithms for the Sequential Reprogramming of Boolean Networks[END_REF] only addresses with temporary perturbations. In this case, the dynamics graph of the controlled Boolean network does not change with the control. This outcome differs from our paradigm of Boolean controlled network, in which each control can result in a different dynamics graph. Thus, despite similarities such as the importance of strongly connected components, which we explore later, our method deals with a slightly different problem.

-Dynamical sequence analysis

Finding a minimal control sequence by exhaustively exploring all possible control sequences is not tractable. Indeed, since controllable variables can alternate between being controlled to 1, 0 or uncontrolled indefinitely, the number of possible control sequences is infinite. Therefore, we need to design a method capable of inferring an appropriate control sequence without performing an exhaustive exploration of all the sequences.

In the trajectory of a minimal sequence µ [k] , the set of intermediary states s i , 1 < i ≤ k can be viewed as intermediary properties that must be reached before reaching a target state. By seeking for factors that limit the set of possible intermediary states, we should significantly reduce the search space in practice.

In order to find such factors, we study the dynamical properties of the Co-FaSe problem generated by the opposition between CX -variables and C X -variables. Proposition 3.1 states that when not in ConEvs dynamics, the dynamics of controllable variables can be ignored as they can be reproduced by a TCS sequence. This statement offers insights into the critical role of the uncontrolled variables in the resolution of the CoFaSe problem. As the variables in C X are fully controlled by the TCS sequence, their natural evolution is essentially discarded. Thus, visiting an already encountered CX -profile with a different C X -profile is irrelevant for solving a CoFaSe problem. Therefore, the dynamical properties that imply the necessity of a sequence of control should emerge from the update functions of CX -variables. The same observation is true for solving CoFaSe under the ConEvs dynamics.

In this chapter, we explore the dynamical properties of the CoFaSe problem emanating from the existence of a set of C X -variables. In the first section, we study the partitioning of the CX -variables and their properties. In the second section, we define a bound on the size of sequence in the CoFaSe problem. In the final section, we present bounds for the ConEvs dynamics.

. Partitioning of the CX -variables

This technical section defines the notions employed to solve the proofs of the upper bounds on sequence length (Sections 5.2 and 5.3).

. Partitioned dynamics.

We focused on the partitioning of the states of the Boolean networks with respect to their CX -profiles. Starting from a model of dynamics, we defined the quotient graph called partitioned dynamics, representing the transitions over the partition. The following equivalence relation is used for its definition:

∀s, s ′ ∈ S X : s ∼ s ′ ⇔ s CX = s ′ CX .
(5.1)

All the states with the same CX -profile belong to the same partition. Formally, the partitioned dynamics of the Boolean network F U is, thus, a labelled transition system ⟨S CX , U, ⟩.

[s] denotes the equivalence class of the state s according to the equivalence relation (5.1). The transition is defined as follows:

[s] [s ′ ] def == s, s ′ ∈ S X , ∃µ ∈ S U : s µ -→ s ′ . (5.2)
The resulting partitioned dynamics models the intrinsic dynamical interactions between the signature variations of the biomarkers and provides an overview of the possible sequence-controlled evolution of the network. In this subsection, we define the properties of equivalence classes and the properties of states belonging to equivalence classes.

Target equivalence class. Take s as a state; if ∃µ ∈ S U , ∃s ′ ∈ S X : s µ -→ s ′ , then [s ′ ] is defined as a target equivalence class of s. Propositions 5.1 and 5.2 provide observational properties of target equivalence classes and their states in synchronous evolution.

Proposition 5.1. In the synchronous mode, regardless of the control, each transition from a state leads to states belonging to a unique target equivalence class.

Proof. Assume an initial state s with s 1 and s 2 two states derived from the one step synchronous evolution of, respectively, F µ 1 and F µ 2 . Assume also that the following is true:

∃µ 1 , µ 2 ∈ S U : s µ 1 -→ s 1 ∧ s µ 2 -→ s 2 ∧ s 1 CX ̸ = s 2 CX
By definition CX -variables are not controllable. In synchronous mode, the dynamics is determined by anterior states (i.e., applying different controls cannot change the values of the CX -variables, because one step is not enough to propagate the updates). Thus, the states s 1 and s 2 cannot have different equivalence classes by means of controls. This point contradicts the above equation and substantiates the statement of this proposition.

Proposition 5.2. In the synchronous mode, a state can reach any state of its target equivalence class in a single step under an appropriate control.

Proof. The proposition follows from the fact that, in the synchronous mode, all C X -profiles are reachable by a total control in a single step Impermanent and enduring states. For a better understanding of the evolution of states with respect to equivalence classes, we distinguish impermanent states which cannot be stabilised whatever the applied control, from enduring states that can be stabilised by an appropriate control. This point is formally expressed as follows:

∀µ ∈ S U :¬ST BL Fµ (s) impermanent state, (5.3)
∃µ ∈ S U :ST BL Fµ (s) enduring state.

(5.4)

Any state s must either be impermanent or enduring: the definitions in Equations (5.3) and (5.4) are logical opposites. We can further derive CX -related properties from these definitions.

• If s is impermanent, s cannot be a stable state for any control. Therefore, we can deduce the following equation ∀µ : F µ (s) ̸ = s. We know that this point true even for the total control µ T , which fixes the C X -variables to their values in s (i.e., (F µ (s)) C X = s C X ). According to Proposition 5.1, no matter the control, (F µ (s)) CX will always have the same profile. Thus, s must be a state in which the CX -variables must evolve at the next dynamics step, ∀µ : (F µ (s)) CX ̸ = s CX .

• If s is enduring, then there must exist a control µ where F µ (s) = s. According to Proposition 5.1, no matter the control, (F µ (s)) CX will always have the same profile. Therefore, ∀µ : (F µ (s)) CX = s CX .

Therefore, an arc between two equivalence classes [s] and [s ′ ] in the partitioned dynamics implies the existence of a state in [s] whose target equivalence class is

[s ′ ]. If [s] = [s ′ ],
s must be an impermanent state. In the case where

[s] ̸ = [s ′ ],
s must be an enduring state. These dynamical properties are formally defined as follows: CX -profiles ex- ist, for 2 ≤ i < j ≤ k + 1, the sequence must have a state s i with the same CX -profile as s j . Note that 2 ≤ i because the first state s 1 may not be an impermanent state. Thus, from the state s i-1 having for target equivalence class

s is impermanent if: ∀µ ∈ S U : s µ -→ s ′ =⇒ s CX ̸ = s ′ CX , s is enduring if: ∀µ ∈ S U : s µ -→ s ′ =⇒ s CX = s ′ CX .

. Bounds on sequence size

µ [k] ≤ 2 | CX | . Proof. Assume that µ [k] , with k > 2 | CX | , is a minimal sequence solving the CoFaSe problem ⟨F µ , S α , S ω ⟩. The control sequence µ [k] yields the following sequence of states: s 1 µ 1 -→ s 2 . . . s k µ k -→ s k+1 ,
[s i ] = [s j ],
it is possible to reach s j and to yield the following sequence

s 1 µ 1 -→ . . . s i-1 µ ′ i-1
---→ s j µ j -→ . . . s k+1 . Hence, the sequence µ [k] is not minimal, thus contradicting the original assumption and proving the statement of the theorem.

For example, consider the Boolean network from Figure 2.7 with S α = {000} and S ω = {010, 110}. By following the minimal path between the equivalence classes [000] and [110] or [010] in the right graph of Figure 5.2, we obtain the two following minimal sequences solving the CoFaSe problem:

000 {d 1 1 } ---→ 101 {d 0 1 } ---→ 011 {d 1 1 } ---→ 110.
010 {d 2 1 ,d 3 1 } ----→ 011 {d 2 0 ,d 3 0 }
----→ 100.

. Bounds on sequence size for ConEvs dynamics

Determining low upper bounds on the size of control sequences would indicates that algorithms based on a direct exploration of the sequence space can be an efficient solution for sequence inference. Theorem 5.1 establishes such an upper bound, but it is proved for the particular context under which the control can be changed at any state. This bound is not therefore directly applicable to ConEvs, where control changes are only allowed at stable states.

The following theorems establish the upper bounds for this semantics. Theorem 5.2 provides an upper bound of 2 | CX | under the TCS control application strategies and Theorem 5.3 provides an upper bound of 2 | CX |+1 -1 under the OCS control application strategies. Thus, the exhaustive exploration of all possible profiles for the C X -variables should constitute an efficient approach for control sequence computation in comparison with an exhaustive exploration of possible control sequences. For the two theorems, we always consider that every initial state is enduring.

µ [k] ≤ 2 | CX | .
Proof. Consider the CoFaSe problem (F U , S α , S ω ) and assume that µ [k] ∈ TCS is a minimal contracted total control sequence solving it for the ConEvs model of dynamics. This control sequence leads to the trajectory

T = s 1 µ 1 -→ * s 2 . . . s k µ k -→ * s k+1
, with s 1 ∈ S α , s k+1 ∈ S ω , and the states s i , 1 ≤ i < k + 1, being the stable states at which the control is changed. We use the symbol τ to refer to the sequence of stable states, plus the initial and the final states: τ = (s i ) 1≤i≤k+1 . Now assume that k > 2 | CX | . Since k is greater than the number of all states over CX , it must be that τ contains two states with the same target equivalence class. Assume these two states are at positions 1 ≤ i ≤ j < k + 1 (i.e., for [s i ] = [s j ]).

According to Proposition 5.1, controlling s i with µ j reaches the state s j+1 in one step. Indeed, s i and s j are enduring states; for s i µ j -→ s ′ and s j µ j -→ s ′′ , we have s

′ CX = s ′′ CX . Furthermore, since [s i ] = [s j ], s ′ is equal to s ′′ , this leads to the trajectory T ′ = s 1 µ 1 -→ * s 2 . . . s i µ j -→ * s j+1 . . . s k µ k -→ * s k+1 ,
µ [k] ≤ 2 | CX |+1 -1.
Proof. Consider the CoFaSe problem (F U , S α , S ω ) and assume that µ [k] ∈ OCS is a minimal contracted control sequence solving it for the ConEvs model of dynamics. This control sequence gives rise to the trajectory T = s 1 µ 1 -→ * s 2 . . . s k µ k -→ * s k+1 , with s 1 ∈ S α , s k+1 ∈ S ω and the states s i , 1 ≤ i < k + 1 being the stable states at which the control is changed. We use the symbol τ to refer to the sequence of stable states, plus the initial and the final states:

τ = (s i ) 1≤i≤k+1 . Now assume that k > 2 | CX |+1 -1.
Since k + 1 is greater than double the number of all states over CX , it must be that τ contains three states with the same target equivalence class. Assume these three states are at positions

1 ≤ h < i < j ≤ k + 1 (i.e., for s h µ h -→ s h ′ , s i µ i -→ s i ′ and s j µ j -→ s j ′ ), this means we have [s h ′ ] = [s i ′ ] = [s j ′ ]
. Note that at least two different controls must appear between the states s h and s j because there is at least the stable state s i in between the two.

By construction the stable states s i , s j , and s h are enduring states, and thus have for target equivalence class their own equivalence class. According to Proposition 5.2, it is possible from s h to find a control µ ′ h reaching s j in one step. This gives rise to the following trajectory:

T ′ = s 1 µ 1 -→ * s 2 . . . s h µ ′ h -→ s j . . . s k µ k -→ * s k+1
. This trajectory contradicts our initial assumption that µ with s 1 ∈ S α , s k+1 ∈ S ω , and the states s i , 1 ≤ i < k + 1, being the stable states at which the control is changed. In this case, it is impossible to have two indices

1 < i < j ≤ k such that [s i ] = [s j ].
Proof. As the two target equivalence classes [s i ] and [s j ] are equal, and as s j and s i are enduring states by hypothesis, it follows from Proposition 5.2 and Theorem 5.2 that s j+1 can be reached from s i with the control µ j . Indeed, s i and s j are enduring states for s i µ j -→ s ′ and s j µ j -→ s ′′ , meaning we have

s ′ CX = s ′′ CX . Furthermore, since [s i ] = [s j ], s ′ is equal to s ′′ . Thus, in a minimal control sequence, it is impossible to have two indices 1 < i < j ≤ k such that [s i ] = [s j ].
Duplicates Theorem 5.3 highlights the possibility of the occurrence of states with identical equivalence class in the contracted trace. Since in minimal contracted control sequences all intermediary states are enduring states. The proof of the theorem also entails that any equivalence class may appear at most twice. Furthermore, such an appearance necessarily happens in consecutive states of the trace. We refer to these occurrences as duplicates. Intuitively, if duplicate equivalence classes appear in non-successive steps i and j, the whole evolution between i and j can be skipped by applying an appropriate control input. These observations exclude the first state as the equivalence class of the first state may appear three times at most. Indeed, if the first state is an impermanent state, then its target equivalence class and its own equivalence class will be distinct. The following corollary formalises this observation: Corollary 5.2. Consider a minimal contracted control sequence µ [k] ∈ OCS solving the CoFaSe problem (F, S α , S ω ) for the ConEvs model of dynamics under the synchronous mode. Take the sequence τ = (s i ) 1≤i≤k+1 of states induced by µ [k] , with s 1 ∈ S α , s k+1 ∈ S ω , and the states s i , 1 < i < k + 1, being the stable states at which the control is changed. If there exist two indices 1 < i < j ≤ k + 1 such that s i µ i -→ s i ′ , s j µ j -→ s j ′ and [s i ′ ] = [s j ′ ], then j = i + 1.

Proof. As the two target equivalence classes [s i ′ ] and [s j ′ ] are equal, and as s j is an enduring state by hypothesis, it follows from Proposition 5.2 and Theorem 5.3 that it is possible to find a control µ ′ i reaching s j from s i in one step whenever j > i + 1. Thus, in a minimal control sequence, if there exist two indices

1 < i < j ≤ k + 1 such that s i µ i -→ s i ′ , s j µ j -→ s j ′ and [s i ′ ] = [s j ′ ], then j = i + 1.
For example, the contracted trace of the trajectory 3.7 of the Boolean networks of Figure 3.1 contains the duplicate x 1 = 0 in the initial state 010 and the stable state 001.

Examples reaching the bounds. We demonstrate that with the Boolean control networks of Figures 5.3 and Figure 5.4, that the length of the minimal control sequences reaches the bounds outlined by Theorems 5.2 and 5.3.

F {u 1 3 ,u 0 3 ,u 1 4 ,u 0 4 } =                x 1 = x 1 ∨ (x 2 ∧ ¬x 3 ∧ x 4 ) x 2 = (x 1 ∧ x 2 ) ∨ (x 1 ∧ x 3 ∧ ¬x 4 ) ∨(¬x 1 ∧ ¬x 3 ∧ ¬x 4 ) ∨ (x 2 ∧ x 3 ) x 3 = (1 ∨ ¬u 1 3 ) ∧ u 0 3 x 4 = (1 ∨ ¬u 1 4 ) ∧ u 0 4 x 3 x 4 x 1 x 2 + + ± + ± + - - Legend: Boolean control network F {u 1 3 ,u 0 3 ,u 1 4 ,u 0
4 } with a minimal control sequence reaching the bound defined by Theorem 5.2. The Boolean control network is accompanied by the interaction graph of the corresponding Boolean network without control parameters.

0011 {u 0 3 ,u 0 4 } -----→ * 0100 {u 0 3 ,u 1 4 } -----→ * 1001 {u 1 3 ,u 0 4 } -----→ * 1110 {u 1 3 ,u 1 4 } -----→ * 1111. F {u 1 3 ,u 0 3 ,u 1 4 ,u 0 4 ,u 1 5 ,u 0 5 } =                                    x 1 = (x 1 ∧ ¬x 2 ) ∨ (x 1 ∧ x 3 ) ∨ (x 1 ∧ ¬x 4 ) ∨(x 1 ∧ x 5 ) ∨ (¬x 1 ∧ x 2 ∧ ¬x 3 ∧ x 4 ∧ ¬x 5 ) x 2 = (x 1 ∧ x 2 ∧ ¬x 3 ) ∨ (¬x 1 ∧ x 2 ∧ x 3 ) ∨(¬x 1 ∧ ¬x 2 ∧ ¬x 3 ∧ ¬x 4 ∧ ¬x 5 ) ∨ (x 2 ∧ x 5 ) ∨(x 1 ∧ ¬x 2 ∧ x 3 ∧ ¬x 4 ∧ ¬x 5 ) ∨ (x 2 ∧ x 4 ) x 3 = (1 ∨ ¬u 1 3 ) ∧ u 0 3 x 4 = (1 ∨ ¬u 1 4 ) ∧ u 0 4 x 5 = ((x 1 ∧ x 2 ∧ x 3 ∧ ¬x 4 ) ∨ (¬x 1 ∧ x 2 ∧ ¬x 3 ∧ x 4 ) ∨(¬x 1 ∧ ¬x 2 ∧ ¬x 3 ∧ ¬x 4 ) ∨ x 5 ∨ ¬u 1 5 ) ∧ u 0 5 x 1 x 3 x 2 x 4 x 5 ± ± + ± ± ± ± ± ± ± ± ± ± ± ± Legend: Boolean control network F {u 1

-Control sequence inference algorithms

Studying the dynamical properties of Total Control Sequence and Open Control Sequence control strategies in Chapter 5 enabled us to define the upper bounds on the length of minimal control sequences. These upper bounds reveal that the uncontrollable variables are central for the inference of a control sequence. As the number of uncontrolled variables is in practice markedly lower than the number of controlled variables (e.g., [START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Burga | Loss of BRCA1 leads to an increase in epidermal growth factor receptor expression in mammary epithelial cells, and epidermal growth factor receptor inhibition prevents estrogen receptornegative cancers in BRCA1-mutant mice[END_REF][START_REF] Chau | Validation of analytic methods for biomarkers used in drug development[END_REF]), the exhaustive exploration of all possible profiles for these variables constitutes an efficient approach for control sequence computation. Thus, we defined algorithms based on partitioning and the exploration of uncontrolled variable profiles. The algorithms infer control minimal sequences that solve the CoFaSe problem for the ConEvs model of dynamics.

In this chapter, we present two algorithms [START_REF] Pardo | Sequential reprogramming of biological network fate[END_REF][START_REF] Pardo | Sequential reprogramming of biological network fate[END_REF] based on CX -profiles exploration. In the first section, we present an algorithm for sequence inference. In the second section, we propose the TCS-based inference method, which is less costly but cannot find sequences containing duplicates. In the final section, we present and discuss the benchmarks of the two proposed algorithms.

. Inference of contracted control sequences

The algorithm inferring a control sequence under the ConEvs model of dynamics builds a tree describing the possible paths reaching a final state of S ω from the initial set of states S α . The shortest paths/trajectories are found in this tree, from which the control sequences are then directly derived. By construction, the algorithm avoids redundant operations. Indeed, exploring an already explored CXprofile is redundant as all CX -profiles reachable from such a profile would have already been reached in the algorithm in one step or with a duplicate. We impose that our set of initial states S α will be composed only of stable states of the uncontrolled dynamics of the studied network. This choice allows us to avoid cases in which an initial state belongs to a basin of attraction of a cyclic attractor.

∃s ∈ ζ, ∃s ′ , s ′′ ∈ S X : s µ -→ * s ′ ∧ stbl Fµ (s ′ ) ∧ [s ′ ] ⊆ [ζ] ∧ s ′ µ ′ -→ * s ′′ ∧ stbl F µ ′ (s ′′ ) ∧ P (s ′′ ). (6.2)
We note that in the first strategy, we first infer µ, and then µ ′ , whereas in the second we infer the pair directly. This difference is important as the first strategy may, in some cases, not find the intermediary state needed to reach the desired property. For example, let us consider the following Boolean network: Example 6.1.

F =                x 1 = (x 1 ∧ ¬x 2 ∧ ¬x 3 ) ∨ (¬x 1 ∧ x 2 ∧ x 3 ∧ x 4 ) x 2 = ¬x 4 ∧ x 2 x 3 = ¬x 4 ∧ x 3 x 4 = x 4
with CX = {x 1 }, C X = {x 2 , x 3 , x 4 }, S α = {0000}, and S ω = 1⋆⋆⋆ as CoFaSe parameters. The minimal and control minimal sequence of size 2 reaching a state in S ω from S α is µ [START_REF] Albert | The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in drosophila melanogaster[END_REF] = ({u 1 2 , u 1 3 }, {u 1 4 }) inducing the following trajectory:

0000 {u 1 2 ,u 1 3 } -----→ 0110 {u 1 4 } ---→ 0111 {u 1 4 } ---→ 1001.
Strategy 1 will not find this sequence. In fact, for s = 0000 Equation (6.1) only yields the parsimonious controls ({u 1 2 }, {u 1 3 }), giving the states 0100 and 0010, from which no states reached belongs to the set of target states S ω .

On the other hand, the second strategy finds all duplicates. In fact, equation (6.2) completely formalises the necessity of having a duplicate to validate the desired property. However, the second strategy is more costly computationally x 4 to 1. The next stable state 0111, in the same equivalence class, is reached by minimally freezing x 3 to 1. The stable state 1100 in the target equivalence class is then reached by minimally controlling x 4 to 0.

In contrast, applying a non-minimal and non-parsimonious control when considering the constraint of reaching the intermediate CX -profiles results in a smaller sequence. The application of the control {u 1 3 , u 1 4 } at the starting state 0000 reaches the stable state 0111 directly, thereby reducing the length of the control sequence ν to 2. The first control in ν can be considered a union of the first two controls appearing in µ, but such a union cannot be generalised.

Note that the algorithm can be modified in such a way that it returns all the minimal sequences when considering the constraint of minimal control to reach the intermediate CX -profiles. In the case where all the returned minimal sequences contain no duplicate, the returned sequences are minimal without considering the constraint on intermediate CX -profiles. Proof. The compliance of µ [k] with the ConEvs model of dynamics and its minimality, when considering the constraint of reaching the intermediate CX - profiles, is guaranteed by the use of the minimal one-shot inference algorithm from [START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Biane | Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery[END_REF]. This algorithm yields minimal controls, allowing to reach stable states satisfying certain properties. The fact that µ [k] solves the given CoFaSe problem follows from the end condition in Step 6. A black arc is a branch of the tree G connecting the previous initial states to the new set of stable states of F U , under the control given in the annotation. A green arc represents the possibility to reach a state validating the desired property by a set of parsimonious controls. A red arc corresponds to a failure to find a control input leading to the desired property.

Correctness. Algorithm 1 closely follows the proofs of

Example.

The returned sequential control is ({u 1 1 }, {u 0 1 }). other data structures are empty.

1. The first iteration of the algorithm is depicted in four parts that illustrate the construction of the tree during the four phases of the iteration: direct reachability of S ω , reachability of S ω via a duplicate, direct reachability of ∆, and reachability of ∆ via a duplicate. In this iteration, we first search for a potential trajectory from S α to the desired property via a direct control or via a duplicate (i.e., a pair of controls validating the Equation 6.1.) In Figure 6.1, we can see that no such trajectories exist.

As no sequences were found, all equivalence classes in ∆ are used as new targets. In Figure 6.

F u 1 1 --→ * 111, ζ ′ will be equal to {111}.
After creating the new arcs of the tree s {u 1 1 }

---→ ζ ′ with s ∈ S α , we search for new trajectories which would attain an equivalence class in the updated ∆ via a duplicate. In Figure 6.1, we see that the equivalence classes [⋆10] and [⋆00] are not reachable via duplicates.

Note that since S ω contains all the states of the equivalence class [⋆10], trying to reach directly or via a duplicate one of its states is pointless. Indeed, if such action were possible, the algorithm would have stopped at the previous phase. In such a case, deleting the equivalence class from the initial ∆ is a simple algorithm optimisation.

2. The second iteration of the algorithm is depicted in Figure 6.1 in one part of which displays only the first phase of the iteration. This iteration of the algorithm is started after updating all the sets of initial variables with new values: l = 2, Z 2 = {111}, and ∆ = {00, 10}. We can observe, in Figure 6.1, that a state with an equivalence class included in S ω is reachable from the initial state 111 under the control {u 0 1 }. Since a target state is reached, the main loop of the algorithm stops. After adding the last arc to G, the returned sequential control ({u 1 1 }, {u 0 1 }) is constructed by backtracking the resulting tree. This sequential control leads to the following trajectory:

001 {u 1 1 } ---→ * 111 {u 0 1 } ---→ * 010.

. TCS-based inference

In this section, we show a two-stage approach for inferring a control sequence: first, infer a total control sequence (TCS) driving the CX subnetwork to satisfy the target property (i.e., reaching a state with the same equivalence class as a state of S ω ); second, derive a control sequence with smaller-size controls (i.e., controls acting on as few control variables as possible). By first inferring a TCS control sequence, we significantly reduce the computation time of the problem for networks with a small number of uncontrolled variables. We will later reveal that this approach yields solutions of roughly the same quality as those given by Algorithm 1 but is considerably more efficient (Figure 6.3).

Step one: Inference of a TCS sequence of minimal length The first stage of the TCS-based inference is formally described in Algorithm 2, which exhaustively explores all possible CX -profiles by building a tree describing the possible paths from the initial states to a target state. As in Algorithm 1, the control sequences are directly derived from this tree by collecting the controls annotating its edges. In contrast to Algorithm 1, TCS inference does not need to explore duplicate states because Theorem 5.2 shows that no duplicate states can occur in minimal TCS sequences. Thus, no solutions are found by Algorithm 2 when the target property can only be reached by control sequences having a duplicate occurrence.

Phases of Algorithm 2. Algorithm 2 comprises two major phases.

The first phase (Step 1) corresponds to the search for a total control allowing to directly attain a state of S ω .

The second phase (Step 2) corresponds to visiting the intermediary equivalence classes of a given trajectory.

The total controls are inferred with an SAT solver.

Data structures.

The algorithm relies on the following data structures:

1. The list ∆ of equivalence classes according to the equivalence relation 5.1.

2.

The exploration tree G with nodes labelled by equivalence classes and arcs labelled by total controls.

Continue if states left:

If Z l+1 is non-empty, go to step 1 with l = l+1 i.e., discarding Z l .

4. Produce the result: Find the trajectory of the sequence of total controls by backtracking G from a leaf found in step 1 to a root equivalence class in Z 0 . If no such leaf was found, return ∅.

Step two: Control minimisation The second stage of the TCS-based inference is formally described in Algorithm 3. The stage reduce a sequence of total controls by testing, for each total control, whether one of its subsets enables reaching the same target equivalence class.

Algorithm 3 comprises only one iterated phase: for every total control µ T i appearing in a contracted control trajectory

(s i ′ µ T i --→ s i+1 ′ ) 1≤i≤n induced by a TCS sequence [µ T n ],
it considers all subsets of µ T i and selects the smallest that reaches the same equivalence class as [s i+1 ′ ]. As with all the previous algorithms, Algorithm 3 focuses mainly on the ConEvs model of dynamics.

Data structures. Algorithm 3 relies on the following data structures:

1. The input contracted total control trajectory

(s i ′ µ T i --→ s i+1 ′ ) 1≤i≤n .

The resulting reduced control sequence µ

[n] .
3. The sets S l , S l+1 of unexplored initial states of the reduced sequence for the current level of depth l, and the next level.

4. The set S µ of stable states the BCN can reach under a given control µ.

At the beginning, (s i ′ µ T i --→ s i+1 ′ ) 1≤i≤n is initialised with a contracted total control trajectory (e.g., one found by Algorithm 2), the depth l is 1, s 1 is equal to S α , and all the other data structures are empty.

Algorithm 3 Iterative reduction of total controls sequences 1. Reduce the current total control: For every control subset µ of the total control µ T l , construct the set of stable states S µ the BCN reaches from S l under µ. Pick the smallest control µ for which Parsimony & optimality. Algorithm 3 always selects the smallest control subsets. Therefore, if every control in a given TCS sequence is a superset of a corresponding control in a control sequence composed of minimal controls, Algorithm 3 will always find it. However, if the input control sequence is not a superset of such a control sequence, the result of Algorithm 3 will be a sequence of parsimonious controls but will not be composed of only minimal controls. In other words, the combination of Algorithm 2 and Algorithm 3 finds parsimonious control sequences.

[s l+1 ′ ] ∈ [S µ ]. Append µ to µ [n] and set S l+1 = {s | s ∈ S µ : [s] = [s l+1 ′ ]}.

. Summary of the algorithms

For reference, we give here a short summary of the approaches to inference and of the algorithms we presented in this section.

The first approach consists of an exhaustive exploration of all possible equivalence classes of CX -profiles and controlled trajectories between them. This approach is implemented in Algorithm 1, which organises the explored equivalence classes in a tree, stores the found controls on its arcs, and then derives a control minimal sequence from a path in the tree connecting the root-the starting equivalence classes in [S α ]-to the first leaf corresponding to one of the target states in S ω .

The second approach is also based on exhaustive exploration of equivalence classes and control trajectories, but this time only total controls are considered. Algorithm 2 works rather similarly to Algorithm 1: it constructs the tree of explored equivalence classes, whose arcs are annotated by the found total controls. Since freezing every single C X -variable is not always necessary, the controls in the output of Algorithm 2 are further individually reduced (Algorithm 3).

. Benchmarks

To assess the efficiency of the proposed approaches for the inference of control sequences, we benchmarked them on a set of randomly generated Boolean networks. We compared their computational time, memory used and the quality of their results. In the below subsections, we refer to the first approach as OCS-based inference and the second approach TCS-based inference.

. Experimental protocol

The experiments consist in comparing the effectiveness and the performance of one-step control inference by the two proposed approaches on random Boolean networks. Indeed, inferring a single control is the core part of both methods and the principal difference between them. Evaluating the performance of one-step inference is, therefore, a good indicator for comparing their computational costs. Furthermore, considering one-step inference only eliminates the potential bias in the observed resource consumption, which may be introduced by the presence of sequences of different lengths in the sample networks.

As our long-term perspective is to study the controllability of regulatory networks, we generated random networks sharing the same topological propriety. Since it appears that regulatory network topologic is scale-free [START_REF] Albert | Scale-free networks in cell biology[END_REF], we generated random Boolean networks from random scale-free interaction graphs obtained using the Barabási-Albert model [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. More precisely, a random Boolean network was randomly generated in two steps from the generated interaction graph:

1. Generation of an undirected graph with respect to a Barabási-Albert graph distribution in which a new node with 3 edges is added at each step with the dedicated function [START_REF]Barabasialbertgraphdistribution[END_REF] of the Wolfram Mathematica library.

2. Fix the orientation of the generated graph randomly with a probability of self-loop of 0.2 and a probability of generating a positive regulation of 0.6.

We generated networks of 10 to 35 variables with increments of 5. For each sizes, we tested on 100 different random Boolean networks for the inference of a one-step control, reaching a set of target states S ω from a set of initial states S α . The initial set of states S α originated from the set of stable states of the random Boolean network. The initial set of target states S ω originated from the enduring states. Around 30% of the network variables were randomly picked to be the uncontrollable variables in CX . Table 6 The Boolean formula f n+1

x i is the n-iterated symbolic composition of a variable

x i . It is obtained by replacing all variables in the f n x i formula with their respective Boolean formula in the initial controlled Boolean network. Below is an example showing the 3-iterated symbolic composition of the variable x 2 of the controlled Boolean network of Figure 2.7:

f x 2 (X, U ) = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ x 2 ) f 2 x 2 (X, U ) = (f x 1 (X, U ) ∧ f x 3 (X, U )) ∨ (¬f x 1 (X, U ) ∧ f x 2 (X, U )) = (u 0 1 ∧ ¬u 1 1 ∧ x 1 ∧ x 3 ) ∨ (u 0 1 ∧ ¬x 2 ∧ x 3 ) ∨ (¬u 0 1 ∧ x 1 ∧ ¬x 3 ) ∨(¬x 1 ∧ ¬x 2 ) f 3 x 2 (X, U ) = (u 0 1 ∧ ¬u 1 1 ∧ f x 1 (X, U ) ∧ f x 3 (X, U )) ∨ (u 0 1 ∧ ¬f x 2 (X, U )∧ f x 3 (X, U )) ∨ (¬u 0 1 ∧ f x 1 (X, U ) ∧ ¬f x 3 (X, U )) ∨ (¬f x 1 (X, U )∧ ¬f x 2 (X, U )) = (u 0 1 ∧ ¬u 1 1 ∧ x 1 ∧ x 3 ) ∨ (¬u 0 1 ∧ x 1 ∧ ¬x 3 ) ∨ (¬x 1 ∧ ¬x 2 ) f 4 x 2 (X, U ) = (u 0 1 ∧ ¬u 1 1 ∧ f x 1 (X, U ) ∧ f x 3 (X, U )) ∨ (¬u 0 1 ∧ f x 1 (X, U )∧ ¬f x 3 (X, U )) ∨ (¬f x 1 (X, U ) ∧ ¬f x 2 (X, U )) = (u 0 1 ∧ ¬u 1 1 ∧ x 1 ∧ x 3 ) ∨ (¬u 0 1 ∧ x 1 ∧ ¬x 3 ) ∨ (¬x 1 ∧ ¬x 2 ) Note that in the example f 3 x 2 (X, U ) = f 4 x 2 (X, U )
. This is a fixed point in the composition. Since the composition of x 2 reached a fixed point, we know that a state s will reach a state s ′ of an attractor of the dynamics of F µ in which s ′

x 2 = f 3 x 2 (s, µ). The Boolean formula encapsulating the synchronous reachability is obtained by a logical conjunction of the 20-iterated symbolic composition of all variables x i ∈ X. Preliminary experiments revealed that 20 compositions were enough to reach stable states in the sequence inferring algorithms.

The inference of one-step controls is time-constrained to 1 hour of computation time. Due to excessive computational time of OCS-based inference, the method is only applied to networks of size 10 and 15 (see Figure 6.2).

. Description of the resulting data

The figures, contain the median values for multiple computations since the outliers present in the dataset risk biasing the average. Figure 6.2 describes the percentage of timed-out computations. Figures 6.3, 6.4, and 6.6 are realised without considering the aborted inferences. Figure 6.3 illustrates the median of the total computational time of the two approaches, including the minimum and the maximum. Figure 6.4 displays the median, with the minimum and the maximum, of the total memory used in bytes of the two approaches. Figure 6.5 describes the median, with the minimum and the maximum, of the total memory used in bytes by the timed-out inferences. Figure 6.6 illustrates the median, with the minimum and maximum, of the number of variables controlled by the inferred one-step controls. Figure 6.7 displays the percentage of times the TCS-based inference finds a parsimonious but not optimal control (i.e., the inferred control is larger than the OCS-based inferred control.) We recall that as OCS-based inference is optimal by construction, a control inferred by the TCS-based inference cannot be smaller than the corresponding OCS-based inferred control.

. Discussion of the benchmarks

The benchmark clearly shows a performance gap between the computation time of the two approaches (Figure 6.3). This disparity becomes more obvious when taking into account that for networks of sizes 10 and 15, respectively 10% and 70% (Figure 6.2) of computations are aborted after 1 hour, and thus are omitted in Figure 6.3. Figure 6.2 reveals that, on networks of size 35, the TCS-based inference resulted in a similar number of aborted computations as the OCS-based inference for networks of size 10. Furthermore, Figure 6.3 shows that the times of the TCSbased inference on networks of size 35 are similar to the times of the OCS-based inference on networks of size 10. This correspondence is due to the fact that the TCS-based inference discards the dynamics of the controlled variables by freezing all of them. Since we selected around one-third of variables to be uncontrollable, the TCS-based inference considered the dynamics of only about 10 variables for networks of size 35.

In Figure 6.4, we observe a jump in median memory usage for networks of size 20. As minimum and maximum values seem within ranges that agree with the other bounds visible on the graph, this variation is probably random and unrelated to the intrinsic properties of the algorithm.

In Figures 6.4 and 6.5, for networks of size 10 and 35, we observe the same pattern as in Figures 6.2 and 6.3 while noting that the median memory used by the OCS-based inference is larger than its counterpart. This outcome can be attributed to the fact that Boolean formulas, for the reachability of the TCS-based inference, may generally be less complex for similar numbers of variables because the sets of CX -variables are randomly selected. Therefore, the CX -variables subnetwork does not follow the power-law distribution of scale-free networks. This difference should result in a network with fewer arcs than a scale-free network with a similar number of variables. In Figure 6.6, the size of inferred controls remains small, even when the size of the network increases. Therefore, we can conclude that the reduction carried out by Algorithm 3 generally results in rather small controls.

Since the size of the Boolean formula for reachability increases as the network size increases, the time needed for the inference of a one-step control by the solver also increases. By only considering the dynamics of CX -profiles, the TCS-based inference postpones the computational explosion, in contrast to the OCS-based inference. As we can see in all the figures, this entails a better performance in terms of time and memory used by the second approach compared with the first one. In Figure 6.7, the number of times where the TCS-based algorithm provides a parsimonious but not optimal solution is low. However, given the low number of instances where both algorithms returned a result (120 instances in total), this observation should be taken with caution.

In these benchmarks, we compared the effectiveness and the performance of one-step control inference of the OCS-based approach and the TCS-based approach on random Boolean networks. From these experiments, we observe that TCS-based inference, in comparison with the OCS-based inference, is less costly in computation time and memory usage. By definition, the OCS-based inference always returns the minimal control. By comparing the instance where the two algorithms return a result, we note that TCS-based inference seems to return minimal controls most of the time. From these observations, we conclude that the TCS-based approach infers solutions of good quality and is a rather viable alternative to the more computationally costly OCS-based approach.

-Structural sequence analysis

By relying on knowledge about the topology, it would be possible to use the sequence bound parameter as well as other topological properties to select fewer CX -profiles to explore in order to reduce the computational cost of the inference algorithm. The previous chapters proved an upper bound of the sequence with regard to the number of uncontrolled variables. In this chapter, we examine the determination of this bound according to the topology of the network. Indeed, we can establish a tighter upper bound for some topologies. The goal is to establish some causal relationship between the topology of the network and the control.

The approach presented in Section 5.3 offers a solution based on the dynamical properties of TCS and OCS control strategies. The proposed methodologies explore the set of CX -profiles of the controlled Boolean network to infer a sequence of controls. To limit the number of CX -profiles to explore, we are particularly interested in eliminating profiles that cannot have an impact the course of a sequence of controls. For example, CX -profiles containing no stable states do not need to be visited under the ConEvs model of controlled dynamics because a control change can only occur in a stable state.

We seek to answer the following question: 'Given a network topology, what is the upper bound of the control sequence minimal size? ' A controlled Boolean network is a function generating a set of Boolean networks with different dynamics. Thus, the dynamical behaviour of the Boolean network greatly depends on its control inputs. In controlled Boolean networks, CX -variables cannot be controlled. Their update functions are, therefore, the same regardless of the control. Since possible controls include total controls in which all C X -variables are controlled to '0' or '1', the properties that imply the necessity of a sequence of control should emerge from the update functions of CX -variables. As the interaction graph is a compact and static abstraction of Boolean network dynamics [START_REF] Paulevé | Static analysis of boolean networks based on interaction graphs: a survey[END_REF], studying the topology of the signed interaction graph of the CX -variables should offer insights into which dynamical interactions between CX -variables play a central role in the CoFaSe problem.

In this chapter, we formally describe the relationship between structure and the length of control sequences, and we provide the corresponding theorems. In the first section, we study the evolution of the interaction graph as a function of the control. We reveal that the only important part corresponds to the CX -subgraph. Based on this subgraph, we study the bounds on sequence length. Section 7.2, we study the structural properties of non-negative cycles. Finally, in Section 7.3, we present the new set of bounds.

. Impact of the interaction graph on the control

The goal of this section is to study the link between the sequential control and the interaction graph. We begin in the first subsection by presenting the CX -interaction graph which is a subgraph that remains invariant for all Boolean networks generated by the BCN. We conclude in the second subsection by describing the structural condition for the emergence of sequential control. This structural condition is the necessity of the presence of at least a positive loop in the CX -interaction graph for a minimal sequence of control to be of a size greater or equal to two.

. CX -interaction graph

A Boolean control network is a family of Boolean networks parameterised by the control input. Each valuation of the control, therefore, leads to a specific Boolean network. As an interaction graph is the structural representation of a Boolean network, the interaction graph is thus also modified by the control. Although the interaction graphs may differ for the generated Boolean networks, only the update functions of the C X -variables may be altered. Indeed, by construction, the update functions of CX -variables are not directly affected by a modification in control since they cannot be controlled. Thereby, whatever the control applied to a Boolean control network, the interactions between CX -variables do not vary. The CX -subgraph will be the same for any Boolean network generated by a Boolean control network with a given set of CX -variables. We denote this subgraph the CX -interaction graph. This representation is central for the structural analysis of the sequence bound.

CX -interaction graph. The CX -interaction graph of a Boolean control net- work captures the interdependence of the CX -variables of the network occurring in the dynamics. This subgraph is a directed graph ⟨ CX , ⟩.Strictly speaking, a BCN does not have an interaction graph, but since CX -variables are not controlled, the interactions between these variables remain the same regardless of the control input.

The CX -interaction graph can be constructed from the signed interaction graph of the Boolean network without the control parameter since its interaction graph corresponds to the interaction graph of the Boolean network yielded by the empty control.

Figure 7.1 illustrates the signed interaction graph of a Boolean network f of Figure 2.1 with the signed CX -interaction graph of two controlled Boolean networks with a different set of controllable variables on F :

• The BCN of Figure 2.7, F {u 0 1 ,u 1 1 } in which the variable x 1 is controlled • The BCN of Figure 3.1, F {u 0 2 ,u 1 2 ,u 0 3 ,u 1
3 } in which the variables x 2 and x 3 are controlled.

x 1 x 2 x 3 ± + + ± ± ± ± -+ x 2 x 3 + + - + x 1 ± Signed interaction graph of F Signed CX -interaction graph of F {u 0 1 ,u 1 1 } Signed CX -interaction graph of F {u 0 2 ,u 1 2 ,u 0 3 ,u 1 3 }
Legend: F is the Boolean network of Figure 2.1. On the left is the signed interaction graph of F . In the middle is the signed CX -interaction graph of F {u 0 1 ,u 1 1 } where the unique controllable variable is x 1 and the uncontrollable variables are x 2 and x 3 . On the right is the signed CX -interaction graph of F {u 0 2 ,u 1 2 ,u 0 3 ,u 1 3 } where the controllable variables are x 2 and x 3 and the unique uncontrollable variable is x 1 .

Figure 7.1: The signed CX -interaction graph of Boolean control net- works.

. Necessary conditions for sequences

We want to find the structural condition for the emergence of sequential control. In this section, we show that the size of the sequence depends on the structure of the CX -interaction graph. More precisely, we explain the necessity of a nonnegative cycle in the CX -interaction graph to have non-trivial control sequences (i.e., of size greater or equal to two).

One of the central conditions for the existence of non-trivial control sequences is that all controlled Boolean networks validating the target property1 on an attractor must have at least two basins of attraction. Indeed, no control allows to reach the property from the initial states. If this were the case, the sequence would be of size one. Moreover, under ConEvs dynamics, the property must be reached by a stable state.

Thus, since all Boolean networks necessarily fall into an attractor, the target property cannot be satisfied in all the reachable attractors from the set of initial states. Therefore, In the case of a minimal sequence of control of size greater than or equal to two, in all the Boolean networks produced by the controlled Boolean network and in which the property is validated by one of its stable states, there are at least two attractors: the one that satisfies the property an cannot be attainable from all states of S α , and the others.

Since the above sentence is true for all control inputs, it is also true for total control (i.e., control in which all C X -variables are controlled to 1 or 0). In this case, the fact that the control is total means that the attractors of the generated Boolean network must be generated by its set of CX -variables.

Note that for all controlled BCNs validating the target property on one of their stable states denoted s, there exists a total control in which all C X -variables are controlled to have the same instantiation as in s, which results in a Boolean network having s as a stable state. Thus, in the case of a minimal sequence of control of size greater than or equal to two, in all the Boolean networks produced by the controlled Boolean network, and in which the property is validated by one of its stable states, there must exist a total control also validating the property on one of its stable states and in which there are at least two attractors: the one attainable from all states of S α and the other that satisfies the property. If this were not true, all control sequences would be trivial and be reached in one step with total control. Therefore, the situations in which one-step controls are insufficient could be explained by the interactions between CX -variables.

We now seek to identify which structures generate multiple basins of attraction in the dynamics of a Boolean network. We then transpose these structures into a CX -interaction graph and observe what is their influence on sequences of control.

In Boolean networks, complex behaviours in dynamics require the presence of cycles [START_REF] Richard | Positive and negative cycles in boolean networks[END_REF]. To understand the influence of such cycles, we rely on the following results: Theorem 7.1 (Robert [52]). Let F be a Boolean network and assume that the interaction graph of F is acyclic. Then, F in synchronous and asynchronous modes has a unique attractor which is a fixed point. Theorem 7.2 (Aracena [3]). Let F be a Boolean network and assume that the interaction graph of F is strongly connected, has at least one arc, and has no positive cycle. Then, F in synchronous modes has no fixed points.

According to Theorems 7.1 and 7.2, for a Boolean network to have a fixed point and more than one attractor in its dynamics, its interaction graph must not be acyclic or a strongly connected component containing no positive cycles.

Relaying on Theorems 7.1 and 7.2, the following two theorems emphasise the importance of non-negative cycles in sequences of control. The following folklore theorem states that the interaction graph of a Boolean network must contain a non-negative cycle in order to have in the dynamics at least two attractors, among which is at least one fixed point. Theorem 7.3 (Folklore). Let F be a Boolean network and assume that the interaction graph of F has no non-negative cycle. Then, in synchronous modes, F cannot have two attractors among which at least one is a fixed point.

Proof. Consider the Boolean network F in which the interaction graph of F has no non-negative cycle. We assume, for the sake of contradiction, that F has at least a fixed point attractor and another attractor. Thus, the interaction graph of F cannot be acyclic and must contain a negative cycle (Theorem 7.1). According to the definition of a negative cycle, the interaction graph of F must contain at least a strongly connected component. Thus, we can define:

• B as the set of variables belonging to complex strongly connected components in F .

• B ↙ as the set of upstream variables of B.

For F to have a fixed point, B ↙ must not be empty. Indeed, since F has a fixed point, all complex SCC composed of negative cycles must be stabilised to a fixed point by a set of upstream variables (Theorem 7.2). We can then define F B ↙ as the subnetwork composed of the variables of B ↙ . By definition, there cannot be any arcs going from B to the variables of B ↙ , which means that the update functions for the variables of B ↙ do not depend on B, and therefore taking them separately provide a perfectly valid Boolean subnetwork. F B ↙ must have at least two fixed points such that one instantiation of the variables of B ↙ stabilises all complex strongly connected components to a fixed point, and another to destabilise at least one complex strongly connected component to a cyclic attractor or stabilises all complex strongly connected components to another fixed point. This is impossible because the interaction graph of F B ↙ is by definition acyclic (Theorem 7.1), thus validating the above theorem.

The presence of non-negative cycles in the CX -interaction graph is crucial for the emergence of sequential control. We observe that the presence in the CX -interaction graph of positive cycles and positive/negative cycles must play a preponderant role in the emergence of sequences of control. For example, all the previously presented Boolean networks with CoFaSe problems solved by minimal sequences of control of size greater than or equal to two, F {u 0 1 ,u 1 1 } with the sequence 3.6, and F {u 0 2 ,u 1 2 ,u 0 3 ,u 1 3 } with the sequence 3.7, have at least a non-negative cycle in their respective signed CX -interaction graphs (Figure 7.1). The following theorem confirms this central role. It states that without a non-negative cycle in the CX -interaction graph, all properties reachable with a control or sequence of controls will be reachable with a one-step control strategy. s k+1 , with s 1 ∈ S α and s k+1 ∈ S ω . As s k+1 is a stable state, it is possible to find a total control µ T such that

stbl F µ T (s k+1 ). Since µ [k] is minimal, s 1 µ T --→ *
does not reach the fixed point s k+1 . Thus, the dynamics graph of F µ T must have at least a fixed point and another attractor. According to Theorems 7.1 and 7.3, for F µ T to have at least a fixed point and another attractor, its interaction graph must contain at least one cycle that is not negative. Moreover, since µ T is a total control, the cycle must be enclosed in the CX -interaction graph of F U as all C X -variables are constant.

. Cycle structural properties

Finding what attractors can be generated by the application of the different control inputs of a Boolean control network is crucial for understanding the causality of the CoFaSe problem. Theorem 7.4 explains that such a basin of attractions must arise from non-negative cycles present in the CX -interaction graph.

In this section, we focus on studying the structural properties of single nonnegative cycles. This section is a technical section used to define new notions that solve the proofs of the new set of tight upper bounds (Section 7.3). In Subsection 7.2.1, we discuss what stable states an isolated positive cycle can have. In Subsection 7.2.2, we explore the effect of the upstream variables of a cycle on its dynamics. Finally, in Subsection 7.2.3, we formalise some of the structural and dynamical properties of non-negative cycles.

. The stable states of a positive cycle

We condiser the stable states that an isolated positive cycle can have and whether they have a particular property. Several structural properties have already been obtained by Robert [START_REF] Robert | Iterations sur des ensembles finis et automates cellulaires contractants[END_REF][START_REF] Robert | A Metric Tool[END_REF][START_REF] Robert | Les systemes dynamiques discrets[END_REF], Shih and Dong [START_REF] Shih | A combinatorial analogue of the jacobian problem in automata networks[END_REF], Aracena [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF][START_REF] Aracena | Positive and negative circuits in discrete neural networks[END_REF], Goles [START_REF] Goles | Block-sequential update schedules and boolean automata circuits[END_REF], Demongeot [START_REF] Demongeot | Combinatorics of Boolean automata circuits dynamics[END_REF], and Richard [START_REF] Richard | Positive and negative cycles in boolean networks[END_REF]. For the particular case of positive cycles, Aracena [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF] proved the following theorem. Theorem 7.5 (Aracena [3]). Let F be a Boolean network. Assume that its interaction graph is strongly connected, has at least one arc, and has no negative cycles.

Then, F has at least two attractors and two fixed points of opposite instantiations s = ¬s ′ . This theorem highlights the presence of two stable states of opposite instantiations in the dynamics of Boolean networks for interaction graphs consisting of a strongly connected component without negative cycles. However, this theorem is too general and encompasses more than a single positive cycle. We need to know exactly the nature and the number of fixed point attractors a positive cycle can generate.

From the work of Goles in [START_REF] Goles | Block-sequential update schedules and boolean automata circuits[END_REF], it can be found that an isolated positive cycles trivialy have two fixed points. This observation was made by Demongeot in [START_REF] Demongeot | Combinatorics of Boolean automata circuits dynamics[END_REF] and provides the following lemma: Lemma 7.1. Let F be a Boolean network. Assume that its interaction graph consists of a unique positive cycle. Then, F has at least two attractors and exactly two fixed points of opposite instantiations s = ¬s ′ .

Proof. This lemma is a weakening of the number of p-attractors of a positive Boolean cycle given in Theorem 1 of [START_REF] Demongeot | Combinatorics of Boolean automata circuits dynamics[END_REF]. Lemma 7.1 can be applied to a cycle without upstream in a larger interaction graph. Since, in such a network, c i has no upstream variables, we can study the evolution of the values of the variables of c i independently of the dynamics of the other variables. Concretely, we examine the projections of the trajectories of the network on the variables of c i . and notice that c i can be in exactly two stable states with opposite instantiations.

Opposite instantiations of a cycle. We denote the two opposite instantiations of a cycle c i as γ ⊤ c i and γ ⊥ c i . We also denote the set of states in which

s ′′ c i ̸ = γ ⊤ c i ∧ s ′′ c i ̸ = γ ⊥ c i as Γ ⊙ c i i.
e., Γ ⊙ c i is the set of instantiation of c i variables that are neither γ ⊤ c i nor γ ⊥ c i . We also denote as γ ⊙ c i any element of Γ ⊙ c i .

. Effects of the upstream variables of a cycle

In this subsection, we study the effect on a cycle of the instantiation of its upstream variables. For some upstream variables instantiation, a cycle can be considered to behave like a virtual cycle whit no upstream variables. If a virtual cycle is a positive cycle, Lemma 7.1 applies.

The instantiation of the upstream variables of a cycle can have two effects on it. To explain these effects, we define for a given cycle c the following sets of variables:

• {y 1 , . . . , y k } = c: the set of variables of the cycle,

• {z 1 , . . . , z l } = X \ c: the set of variables not belonging to the cycle.

We denote Φ(f ) as the minimal DNF of a Boolean formula f . A cycle c may have the following:

• A set of non-absorbing instantiations N c of its upstream variables in which the instantiation of the cycle can be considered to behave like a virtual cycle with no upstream variables. ∀s ∈ S X : s c ↙ ∈ N c =⇒ ∀y i ∈ c : Φ(f y i (y 1 , . . . , y k , s z 1 , . . . , s z l )) ̸ ∈ {1, 0}. For example, take the Boolean controlled network of Figure 7.2 in which C X = {x 1 } and CX = {x 2 }. In this case, the CX -interaction graph consists of a unique positive cycle c = {x 2 }, which has for upstream variables the set c ↙ = {x 1 }. {x 1 = 0} is an absorbing instantiation of the upstream variable of c as f x 2 = 0∧x 2 = 0. For any control µ in which x 1 is equal to 0, x 2 is equal to 0 at the next dynamics step (i.e., ∀µ ∈ S U : 0⋆ µ -→ 0⋆). 2 On the other hand, {x 1 = 1} is a non-absorbing instantiation of the upstream variable of c as f x 2 = 1∧x 2 = x 2 . For any control, when x 1 is equal to 1, x 2 is equal to itself at the next dynamics step (i.e., ∀µ ∈ S U , α ∈ B : 1α µ -→ ⋆α).

F {u 1 1 ,u 0 1 } = x 1 = x 1 ∨ ¬u 1 1 ∧ u 0 1 x 2 = x 1 ∧ x 2 x 2 x 1 + + +

. Cycle dynamics

In this subsection, we formalise the structural properties of the non-negative cycles when their upstream variables are set to non-absorbing instantiations. If a stable state has the upstream variables of the cycle c instantiated to one of its non-absorbing instantiations, then this state only has a limited set of possible instantiations for the variables of the cycle c. Indeed, c can be considered for each non-absorbing instantiation to have the dynamics of a virtual cycle denoted c without any upstream variables and with the same set of variables as the cycle c. Lemma 7.1 can be applied to the subgraph composed of cycle c. We define for a given cycle c the following sets of variables:

• {y 1 , . . . , y k } = c: the set of variables of the cycle.

• {z 1 , . . . , z l } = X \ c: the set of variables not belonging to the cycle.

The functions of the Boolean network f ′ , which has for interaction graph the subgraph composed of the cycle c, are defined as follows:

∀s ∈ S X : s c ↙ ∈ N c =⇒ ∀y i ∈ c : f ′ y i = Φ(f y i (y 1 , . . . , y k , s z 1 , . . . , s z l )). (7.3)
Since the Boolean network f ′ has for interaction graph a unique cycle c, each function of its variables has exactly one parameter. Thus, c has '±' arcs as such arcs require a function with at least two input parameters.

Therefore, for a state s in which s c ↙ ∈ N c , the non-negative cycle c can be considered to have the dynamics of a positive or a negative cycle c. We now introduce the following notations:

• For each pair {y j , y i } of variables of c in which y j + y i , the relation from y j to y i in c is labelled by 1 ('+').

• For each pair {y j , y i } of variables of c in which y j y i , the relation from y j to y i in c is labelled by -1 ('-').

F {u 1 1 ,u 0 1 } =      x 1 = 1 ∨ ¬u 1 1 ∧ u 0 1 x 2 = x 1 ∧ x 3 x 3 = x 2 F ′ {u 1 1 ,u 0 1 } =      x 1 = 1 ∨ ¬u 1 1 ∧ u 0 1 x 2 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ ¬x 3 ) x 3 = x 2 F ′′ {u 1 1 ,u 0 1 } =      x 1 = 1 ∨ ¬u 1 1 ∧ u 0 1 x 2 = (x 1 ∧ x 3 ) ∨ (¬x 1 ∧ ¬x 3 ) x 3 = (x 1 ∧ x 2 ) ∨ (¬x 1 ∧ ¬x 2 )
x 1

x 2

x 3

+ + + x 1 x 2 x 3 ± ± + x 1 x 2 x 3 ± ± ± ± Interaction graph of
⊤ c ′ = {x 2 = 0, x 3 = 1} and γ ⊥ c ′ = {x 2 = 1, x 3 = 0}.
From the definition regarding absorbing and non-absorbing instantiations, we can make two observations about the significant effect the upstream variables of a cycle have on a sequence of control.

• If the dynamics of a Boolean control network has a stable state s where s c is not in one of the opposite instantiations of the cycle, then the upstream variables of c should be instantiated to one of their absorbing instantiations (i.e., s c ↙ ∈ Γ ⊙ ).

• Consider a Boolean network in which none of the non-negative cycles of the CX -interaction graph are connected. In this case, all stable states s i of a minimal sequence µ[k] under the ConEvs model of dynamics must have the upstream of at least one of the positive cycles in the CX -interaction graph set to a non-absorbing instantiation.

. Maximal sizes of minimal sequences

In Chapter 6, we presented two algorithms inferring minimal sequences of control based on the exploration of all CX -profiles. Studying the topology of the CX -interaction graph enables us to limit the number of CX -profiles to explore by providing a more accurate specification of the upper bound. By relying on the properties of the non-negative cycles presented in Section 7.2, we determine tight upper bounds on the size of control sequences.

In the first subsection, we present new upper bounds for the general case when the subgraph of CX -variables contains strongly connected components. In the second subsection, we present new upper bounds for when the subgraph of CXvariables contains a single positive cycle. Treating this particular case provides insight into the mechanism behind the necessity of sequential control. In the final subsection, we draw conclusions about the topological approach and engage a discussion on mechanisms being sequential control.

. Bounds in the general case

In this subsection, we treat all Boolean networks that have a CX -interaction graph containing strongly connected components. As we showed in the previous section, for a sequence to be of a size greater than or equal to two, a cycle that is not negative must at least be present in the CX -variables. Therefore, we treat networks with at least a non-negative cycle in its CX -interaction graph.

To prove the following bounds, we generalise the notion of non-absorbing instantiations, so that it can be applied to any given SCC of F , in which F is a Boolean network. Therefore, an SCC denoted A of F may have a set of nonabsorbing instantiations N A of its upstream variables in which A can be considered to behave as if the SCC had no upstream variables. We define the sets of variables

{y 1 , . . . , y k } = A and {z 1 , . . . , z l } = X \ A. ∀s ∈ S X : s A ↙ ∈ N A =⇒ ∀y i ∈ A : Φ(f y i (y 1 , . . . , y k , s z 1 , . . . , s z l )) ̸ ∈ {1, 0}. (7.5)
The topological approach is based on Theorem 7.3, which shows that a sequence of size greater than or equal to two can only occur in the presence of a non-negative cycle in the CX -interaction graph. This theorem and the structural properties of cycles presented in Section 7.2 enable us to prove Theorem 7.6. Theorem 7.6 is central for understanding the causality of the sequence by highlighting the role of non-negative cycles in the sequence mechanism. From Theorem 7.4, we can extract the following observation: For a minimal sequence to be of a size greater than or equal to two, every stable state s i of its contracted dynamics, with 2 < i, must have at least two stable attractors. From this observation, we conclude that all s i states must have at least one cycle in one of their opposite instantiations.

Theorem 7.6. Let F U be a totally controlled Boolean control network and let C denotes the set of non-negative cycles in its CX -interaction graph. Let µ T

[k] be a minimal sequence of total controls of size k > 2 and resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode with the following trajectory:

s 1 µ T 1 --→ * s 2 . . . s k µ T k --→ * s k+1
, where s 1 ∈ S α , s k+1 ∈ S ω and s i with 1 ≤ i ≤ k + 1 are stable states. In this case, all states s j+1 with 1 < j < k + 1 will have at least one cycle of C having for a profile one of its opposite instantiations.

93

Proof. Since s i+1 is a stable state, there must exist a total control µ T such that F µ T (s i+1 ) = s i+1 . Furthermore, for the state s i+2 not to be directly reachable from s 1 , the Boolean network F µ T must have at least two attractors (Theorem 7.4). Since the control is total, all attractors of F µ T will have the same C X profile.

We note that since s i+1 is stable, any negative cycle c of the SCCs of the CX -interaction graph must have s i+1 c ↙ ∈ A c . Thus, there must exist a sub-SCC A that has s i+1 A ↙ ∈ N A and does not contain negative cycles. Indeed, if no such sub-SCC A exists,variables in all SCCs will depend on their upstream variables. Since all possible attractors have the same C X -profile under µ T , only one stable state attractor can exist, which is a contradiction.

Theorem 7.6 enables us to define new upper bounds on the sequence length. We first only considered networks whose CX -interaction graph forms a single SCC, and which operate under total control. We now introduce the following notations:

• Γ ⊤⊥ denotes the union of all pairs of opposite instantiations of a cycle.

• S stbl

X denotes the set of stabilisable states {s | s ∈ S X , ∃µ ∈ S U : ST BL Fµ (s)}.

• β denotes the cardinality of the set of CX -profile in which a stabilisable state with this profile exists and in which there is a cycle in one of its opposite instantiations. More formally, Proof. Take the trajectory induced by µ T

β = |{s | s ∈ S CX , ∃c ∈ C, ∃γ • ∈ Γ ⊤⊥ , ∃s ′ ∈ S stbl X , ∃µ ∈ S U : s c = γ • ∧ s ′ CX = s}|,
[k] : T = s 1 µ T 1 --→ * s 2 . . . s k µ T k --→ * s k+1
, where s 1 ∈ S α , s k+1 ∈ S ω and s i , 1 < i < k + 1 are stable states.

According to Corollary 5.1, in TCS any given CX -profile cannot appear twice between s 1 and s k . Thus, k will have for upper bound the number of different possible CX -profiles. According to Theorem 7.6, all states s i+1 , where 1 < i < k + 1, must have at least one cycle set to one of its opposite profiles. Thus, we can deduce that k -2 ≤ β, which proves the statement of the theorem. Theorem 7.7 provides a bound on the length of minimal sequences, which dependents on the number of equivalence classes in which a cycle in the CXinteraction graph is instantiated to one of its opposite instantiations. If the number of such equivalence classes for a Boolean network validating the condition of the theorem is 3, a minimal sequence will necessarily be of a size lower or equal to 5. We note that since we are in ConEvs dynamics, such an equivalence class should at least have an enduring state; otherwise, it would not be possible to stabilise a state of this equivalence class.

Note that s 1 and s 2 are the only states in which the CX -profile may contain no non-negative cycle instantiated to one of its opposite profiles. However, if a CX -variable has a self-loop with a '+' or '±'sign, then it will always be instantiated to one of its opposite profiles. In this case, the length of the sequence can reach the bound of 2 | CX | (Theorem 5.2) as S CX \ β = ∅ (i.e., the set of states in which no cycle is in one of its opposite instantiations is an empty set).

Example 5.1 of Section 5.3 is such a case. It is also, therefore, an example of a network reaching the upper bound of Theorem 7.7.

Note that it is possible to make a bound easier to calculate by ignoring the necessity of stable states: Corollary 7.1. Let F U be a totally controlled Boolean control network and let C denotes the set of non-negative cycles in its CX -interaction graph. A control sequence resolving the CoFaSe problem (F U , S α , S ω ) for the ConEvs model of dynamics cannot be of a size greater than min

(2 + |{s | s ∈ S CX , ∃c ∈ C, ∃γ • ∈ Γ ⊤⊥ : s c = γ • }|, 2 | CX | ). Proof. β ⊆ {s | s ∈ S CX , ∃c ∈ C, ∃γ • ∈ Γ ⊤⊥ : s c = γ • },;therefore, the above statement is true.
In the following, we extend this result to all TCS networks. We first prove that, under total control, the downstream and the disconnected variables of the CX -interaction graph have no influence on the upper bound under a TCS control strategy. We now introduce the following notations:

• V denotes the set of variables belonging to the SCCs of an CX -interaction graph.

• V ↙ CX denotes the set of upstream variables of V in the CX -interaction graph.

• V ⋄ denotes the union of V ↙ CX and V. More formally, V ∪ V ↙ CX .

• V ⇓ denotes the set of strictly downstream and disconnected variables of V in the CX -interaction graph. More formally, V ⇓ = CX \ V ⋄ . Lemma 7.2. Let F U be a totally controlled Boolean control network. Let µ T

[k] be any minimal sequence of total controls of size k > 2 that resolves the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode with the following trajectory:

s 1 µ T 1 --→ * s 2 . . . s k µ T k --→ * s k+1 , in which s i , where 1 ≤ i ≤ k + 1,
are stable states. In this case, there cannot exist a pair of states s i and s j , where 1 ≤ i < j < k + 1, which has the same V ⋄ -profile.

Proof. Assume there exist two states, s i and s j , in the trajectory T where

1 ≤ i < j < k + 1, s j CX ̸ = s l CX and s i V ⋄ = s j V ⋄ .
By definition, all paths from a V ⇓ variable to a variable in V must contain some C X -variables. Thus, since all C Xvariables are totally controlled, the profile of V ⇓ -variables cannot influence the profiles of V variables. Therefore, the profile s j+1 CX only dependents on s j V ⋄ .

In this case, s j+1 can be reached from s i under the total control µ T j . Thereby, we conclude that there cannot be two states in the trajectory of a minimal sequence of control total that have the same V ⋄ profile.

We then give an upper bound on the sequence length as a function of the number of equivalence classes whose states have a cycle in the CX -interaction graph instantiated to one of its opposite instantiations. Note that if we obtain two equivalence classes that only differ in the downstream or disconnected variables, then visiting only one of them is sufficient. We now introduce the following notations:

• β ′ denotes the cardinality of the set of V ⋄ -profile in which a stabilisable state with this profile exists and in which there is a cycle in one of its opposite instantiations. More formally, Proof. Take the trajectory induced by µ T

β ′ = |{s | s ∈ S V⋄ , ∃c ∈ C, ∃γ • ∈ Γ ⊤⊥ , ∃s ′ ∈ S stbl X : s c = γ • ∧ s ′ CX = s}|
[k] : T = s 1 µ T 1 --→ * s 2 . . . s k µ T k --→ * s k+1
, where s 1 ∈ S α , s k+1 ∈ S ω and s i , 1 < i < k + 1 are stable states.

We know from Theorem 7.6 that all states s i+1 with 1 < i < k+1 must have at least one of their cycles set at one of it opposite instantiation. Futhermore, according to Lemma 7.2, no a pair of states s i and s j , where 1 ≤ i < j < k +1, and that have the same V ⋄ exist in the trajectory. Thus, we can deduce that k -2 ≤ β ′ ., which proves the statement of the theorem.

Regarding Theorem 7.6, Example 5.1 of Section 5.3 is an example of a network reaching the upper bound of Theorem 7.8

We now further generalise this result from TCS to OCS control sequences. Lemma 7.3 proves that the downstreams of the SCCs and the disconnected variables have no influence on the lengths of minimal OCS control sequences.

s 1 µ 1 -→ * s 2 . . . s k µ k -→ * s k+1
, where s i , 1 ≤ i ≤ k + 1, are stable states. In this case, there exists at most a pair of states in the trajectory that has the same V ⋄ -profile.

Proof. Assume there exist three states, s i , s j and s l , in the trajectory T where 1 ≤ i < j < l ≤ k + 1 and the following conditions hold:

• s i CX ̸ = s j CX ∧ s i CX ̸ = s l CX ∧ s j CX ̸ = s l CX . • s i V ⋄ = s j V ⋄ = s l V ⋄ .
Here, the only differences between the three states are the values of downstream and disconnected variables of V in the CX -interaction graph (i.e., V ⇓ ).

Since s l is a stable state, there must exist a total control µ T such that F µ T (s l ) = s l . By definition, all paths from a V ⇓ variable to a V variable must contain some C X -variables. Thus, in the case of the total control µ T , V ⇓ variables cannot influence the profiles of V variables. Thus, s l must be reachable under µ T from any enduring state s with the property s l V ⋄ = s V ⋄ . Therefore, s l can be reached from s i . Thereby, the sequence µ [k] cannot be minimal, which is a contradiction. Theorem 7.9. Let F U be a Boolean control network. All minimal sequences of control µ [k] resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode will be of size min(2β ′ + 2, 2 |V ⋄ |+1 ).

Proof. Take the trajectory induced by µ

[k] : T = s 1 µ 1 -→ * s 2 . . . s k µ k -→ * s k+1
, where s 1 ∈ S α , s k+1 ∈ S ω , and s i , where 1 < i < k + 1, are stable states.

We know from Theorem 7.6 that all states s i+1 with 1 < i < k + 1 must have at least one of their cycles set at one of its opposite instantiations. Furthermore, according to Lemma 7.2 there cannot exist three states in the trajectory that have the same V ⋄ -profile, which proves the statement of the theorem.

Theorem 7.9 is similar to Theorem 7.8 but considers the possibility of having duplicates (Section 5.3). With duplicates, the upper bound becomes 2 | CX |+1 if the SCCs do not have downstream variables (i.e., CX = V ⋄ ). Thus, Example 5.2 of Section 5.3 is an example of a network reaching the upper bound.

. Bounds for a single positive cycle

In this subsection, we examine at the networks in which the CX -interaction graph consists of a unique positive cycle. This interaction graph is possibly equipped with acyclic appendages and accompanied by disconnected acyclic structures, as in Figure 7.4. Such configurations may lead to minimal sequences of length two at most, as shown in the following theorem. Theorem 7.10. Let F U be a totally controlled Boolean control network whose CX -interaction graph consists of a unique positive cycle. In this case, all minimal sequences of total control µ T

[k] resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode are of size ≤ 2.

Proof. Take the trajectory induced by µ T

[k] : T = s 1 µ T 1 --→ * s 2 . . . s k µ T k --→ * s k+1
, where s 1 ∈ S α , s k+1 ∈ S ω and s i , where 1 < i < k + 1, are stable states. We denote c as the unique cycle of the CX -interaction graph. We know from Theorem 7.6 that for all states s j+1 with 1 < j < k + 1, at least one cycle in the CX -interaction graph is in one of its opposite instantia- tions. Moreover, to reach s j+1 from s j , s j and s j+1 must be in the same basin of attraction in the dynamics of F µ T j .

x Legend: The CX -variables x 1 to x 5 form a positive cycle. The CXvariables y 1 and y 2 form its upstream, the CX -variables z 1 to z 3 form its downstream, while the CX -variables t 1 to t 4 form an acyclic structure disconnected from the positive cycle. Only the cycle is required to be positive. The signs on all other arcs in the graph can be arbitrary. The connections to controlled variables are not shown. This result can be generalised from TCS to the general OCS case. We begin by revealing that in Lemma 7.4 all non-total controls can always be replaced by a total control. This process enables us to prove the following theorem, which provides the same upper bound on the lengths of minimal OCS sequences as in Theorem 7.10. Proof. Since the CX -interaction graph is a positive cycle, for all controls reach- ing a stable state s ′ from s, there is a total control reaching the stable state s ′ from s (Lemma 7.4). Thereby, we conclude that if a sequence validates the CoFaSe problem under the ConEvs dynamics in synchronous update mode, a sequence of total controls validating the same problem also exists. The upper bound, is thus, the same as in Theorem 7.10, which proves the statement of the theorem.

We insist on the fact that Theorems 7.10 and 7.11 are only applied for positive cycles and not positive/negative cycles. For example, the Boolean network from Figure 3.1 in Section 3.1, which has for CX -interaction graph a unique positive/negative cycle {x 1 }, one can find minimal sequences of size 3 (Trajectory 3.7).

From the two theorems, we understand that a minimal sequence of control sets different cycles to profiles, which will drive them into one of their opposite instantiations in a specific order. To facilitate reading, we repeat the controlled Boolean network equations below:

F {u 1 1 ,u 0 1 } = x 1 = x 1 ∨ ¬u 1 1 ∧ u 0 1 x 2 = x 1 ∧ x 2 101
In Example 7.2, the attractor we want to reach is when the cycle c = {x 2 } has x 1 set to 0. In S α , x 2 is set to 1. Since the state 01 can be stabilised only by networks F {u 1 1 } and F ∅ , in which 11 is not in the desired attractor, we must drive the controlled network in a intermediary step to a state that would eventually end up in the desired attractor. This is realised by setting x 2 to 0.

. Discussion

This topological approach enables us to determine tight upper bounds. The approach limits the number of CX -profiles to explore and thus decreases the computation time. The most notable reduction is due to Lemmas 7.2 and 7.3, which reveal that the downstream and disconnected variables of the SCCs have no influence on the lengths of minimal sequences. Thus, a sequence can be found by considering the equivalence classes of V ⋄ -variables.

On the other hand, knowing that every4 stable state of a sequence dynamics must have at least one cycle in one of its opposite instantiations does not create any significant gain in algorithm computation time. Indeed, the stabilisable states in which no cycle is in its opposite instantiations can be reached from any states with a total control. Thus, they would be all reached from S α at the first iteration of the algorithms presented in Chapter 6. However, sequences that traverse such states in their trajectory are uncommon as they require complex Boolean formulas. Therefore, trying at first to infer sequences of control without considering states in which no cycle is in its opposite instantiations can be a good method for obtaining a better computation time in general. From Theorems 7.10 and 7.11,we can extract some interesting observations concerning a BCN whose CX -interaction graph contains a single SCC, which is a cycle. For example, if a sequence is of size two, the property that we wish to reach must require, according to Theorem 7.6, the CX -variables to be in one of the two opposite instantiations of the cycle. In this case, from the initial states, we have only one CX -profile to test: the profile in which the cycle is set in the same instantiation as one of the target states. In this situation, the cycle acts as a binary memory. The target states are in the 'good' memory state which can be translated into being blocked in a 'good' attractor. The initial states are in the 'bad' memory state or blocked in a 'bad' attractor. Thus, to reach the desired states, we must flip the memory to a 'good' state (i.e., drive the network to a state in the right attractor).

Under the simple premise of having for CX -interaction graph a unique positive cycle, finding the order in which cycles need to be set to 'good' attractors is trivial. In the general case, finding such an order cannot be done achieved using a topological analysis. The problem arises from the fact that the CX -interaction graph abstraction of the interactions between CX -variables is not granular enough to deduce such an order in complex topologies.

For example, if the cycle has upstream variables in it CX -variables, we must to refer to Theorem 7.8 for the TCS control strategy and Theorem 7.9 for the OCS control strategy. The example, below, shows a controlled network reaching the upper bound with a TCS control strategy and having only the positive cycle {x 1 , x 2 } in its CX -interaction graph. Our analysis also emphasised non-obvious complex features of the sequence, such as the occurrence of duplicates in which only the controlled variables evolve without changing the states of uncontrolled variables. Such occurrences were interpreted as the need to evolve to different stable states with the same profiles for uncontrolled variables, but which could not previously be reached.

We proposed two approaches for inferring control sequences. Both approaches are based on the exhaustive exploration of the possible intermediate profiles of uncontrolled variables [START_REF] Pardo | Sequential reprogramming of biological network fate[END_REF][START_REF] Pardo | Sequential reprogramming of biological network fate[END_REF]. The first approach is implemented in Algorithm 1 (page 63) and applies the single control inference algorithm from [8] 2 | CX |+1 -1 times in the worst case.

The second approach is implemented as a chaining of Algorithms 2 and 3 (pages 70 and 71). This approach focuses on inferring a total control sequence in which all controllable variables are frozen, and then reducing the sizes of individual controls. This technique implies that the second approach does not consider the occurrence of duplicates. Our benchmark revealed that inferring total controls is much cheaper because the dynamics of uncontrolled variables are neglected, while the quality of the solutions remains close to the quality of the sequences inferred by Algorithm 1.

We explored the relationship between the structure of the BCN and its dynamics to understand how the structure impacts the control sequences and thereby improves the bounds. Therefore, we studied the dynamics properties emanating from the interaction graph to characterise the bounds on the sequence length with respect to its topology. Taking topology into account makes it possible to find tighter bounds for minimal sequences of control. These upper bounds also enabled us to study the causal relationships that exist between structure and control. One of our major observations is the importance of non-negative cycles in the interaction subgraph generated by the CX -variables ( CX -interaction graph). We found that without a non-negative cycle in the CX -interaction graph, all properties reachable with control or a sequence of controls are reachable with a one-step control. This finding is due to the fact that for some instantiations of the upstream of a non-negative cycle, this cycle behaves as if it were an isolated subgraph, which therefore has only two opposite stable instantiations. Informally, a sequence of control is needed when an uncontrollable non-negative cycle acts as a memory that blocks the validation of the desired property until this memory is set to its un-blocking value.

We also revealed that all stable states encountered in a minimal sequence trajectory under the ConEvs dynamics and that cannot be reached from the set of initial states must set at least one of the cycles in one of its opposite instantiations. This process results in a bound dependent on the number of CX -profiles in which at least one cycle in the CX -interaction graph is instantiated to one of its opposite instantiations.

Perspectives. The perspectives of our work are threefold:

The analysis of the Boolean functions: The proposed dynamics analysis remains general but can be improved by considering the topological aspects or the structure of formulas. In this thesis, we chose to study the topological approach. Under this approach, the inference of a sequence of control is trivial if the CXinteraction graph consists of a unique positive cycle. However simply adding some more variables and more cycles in the CX -variables rapidly complicates the situation. This is due to the fact that multiple Boolean networks can have the same topology. For more complex networks, one of the possible approaches to consider is combining the study of the topology and the analysis of the update functions of the CX -variables. Indeed, by analysing the Boolean formulas of the non-negative cycles in the CX -interaction graph, we hope to find the order in which the cycles need to be blocked or unblocked to reach a state validating the desired property. Such a discovery should greatly improve inference times, enabling the inference on larger networks.

Sequential control in biological models: This thesis focused on the formal aspects of sequential control. Applying this method to biological cases to investigate complex treatment schemes, more specifically for cancer, seems a natural prospect. One other interesting perspective would involve conducting a survey on the existing biological Boolean models to determine how many contain non-negative cycles in their set of uncontrollable variables and require a sequence of control to reach the target property from the given initial states. Such a survey could provide a good understanding of the frequency of sequential control in biological models.

the findings would open a discussion on whether such frequency represented or under-represented biological mechanisms or whether it is an undesirable modelling effect.

Asynchronous CoFaSe problem: The final perspective revolves around studying sequential controls in a broader context, notably by considering other modes, such as the asynchronous one. For the asynchronous mode, one needs to tackle the fact that the transition becomes a relation inducing non-determinism that should not be exhaustively explored to ensure the efficiency of a minimal sequential control inferring algorithm. In the synchronous algorithms presented in this manuscript, the desired property is reached from at least one of the initial states. However, because of the non-deterministic nature of the asynchronous mode, the notion of necessity and the possibility of reaching the desired property must also be introduced.

Figure 2 . 1 :

 21 Figure 2.1: A Boolean network.

x 2 }

 2 Legend: Dynamics of the Boolean network F of Figure 2.1 under the updating policy M = {{x 1 , x 2 }, {x 3 }}. Arcs are labelled by the sets of updated variables realizing the transitions.

Figure 2 . 2 :

 22 Figure 2.2: Update mode of a Boolean network.

Figure 2 . 2

 22 [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF] shows the synchronous and asynchronous dynamics state graphs of the Boolean network of Figure

Figure 2 . 3 :

 23 Figure 2.3: Synchronous and Asynchronous update modes of a Boolean network.

Figure 2 .

 2 Figure 2.4 shows the interaction graph of the Boolean network of Figure 2.1.

x 1 x 2 x 3 Legend:

 23 Interaction graph of the Boolean network F of Figure 2.1.

Figure 2 . 4 :

 24 Figure 2.4: The interaction graph of a Boolean network.

  Figure 2.5 displays the signed interaction graph of the Boolean network of Figure 2.1. Signed Interaction graph of the Boolean network F of Figure 2.1.

  The Boolean network F of Figure2.1 is completed by the formulas of the freezing controls to produce the Boolean control network

Figure 2 . 7 :

 27 Figure 2.7: The synchronous dynamics of a Boolean control network.

variable x 1

 1 on the Boolean network of Figure2.1. The three depicted dynamics respectively correspond to the following:

3 Legend:

 3 The Boolean network F of Figure2.1 is completed by the formulas of the freezing controls to produce the Boolean control network

Figure 3 . 1 :

 31 Figure 3.1: The synchronous dynamics of a Boolean control network.

MTheorem 3 . 1 .Theorem 3 . 2 .

 3132 from the triple (F, S α , S ω ) is a polynomial-time procedure, meaning that an oracle for DLBA acceptance would allow deciding reachability for Boolean networks working in the synchronous mode with polynomial overhead. This point proves the statement of the lemma. Theorem 3.1 below is derived directly from Lemmas 3.2 and 3.3. Given a Boolean network F with the variables X, a set of starting states S α ⊆ S X , and the set of target states S ω ⊆ S X \ S α , it is PSPACE-complete to decide whether F can reach any of the states in S ω from one of the states in S α . Theorem 3.1 combined with Lemma 3.1, implies the complexity of CoFaSe is at least PSPACE-hard. This point is stated in Theorem 3.2. Whether solving CoFaSe is in PSPACE remains an open question. Deciding the existence of a control sequence for the CoFaSe problem in the synchronous mode is PSPACE-hard.

Figure 5 . 1 1 ,u 0 1 }work F {u 1 5. 1 . 2 .

 511112 Figure 5.1 displays the partitioned synchronous dynamics of the example Boolean networks from Figure 2.7 and Figure 3.1.

Figure 5 .

 5 Figure 5.2 shows the partitioned dynamics of the Boolean networks from Figures 2.7 and 3.1, together with the impermanent and enduring states, as well as their target equivalence classes.

Proposition 5 . 1 1 ,u 0 1 }

 511 2 and the definition of an impermanent state provide insights into the resolution of the CoFaSe problem. The dynamical properties related to equivalence classes enable us to define an upper bound on the length of minimal control sequences. A minimal sequence solving the problem should jump from an impermanent state to another until it reaches the equivalence class of a target state. A trajectory induced by a minimal control sequence should not pass through intermediary enduring states. Such an action would be redundant as all states of an impermanent target equivalence class of a state s are always reachable with a On the left are the enduring and impermanent states of the Boolean network F {u of Figure 2.7 where CX = {x 2 , x 3 } and on the right are the enduring and impermanent states of the Boolean control network F {u 1 2 ,u 0 2 ,u 1 3 ,u 0 3 } of Figure 3.1 where CX = {x 1 }. The enduring states of each equivalence class of the partitioned dynamics are coloured in grey and the impermanent states, in white, are connected to their target equivalence classes represented by a dotted circle.

Figure 5 . 2 :Theorem 5 . 1 .

 5251 Figure 5.2: Synchronous enduring and impermanent states and the partitioned dynamics of two Boolean networks.

  Consider now the Boolean network from Figure 3.1 with S α = {010} and S ω = {100}. By following the minimal path between the equivalence classes [010] and [100] in the left graph of Figure 5.2, we obtain the following minimal sequence solving the CoFaSe problem:

Theorem 5 . 2 .

 52 The size of the minimal contracted total control sequence µ [k] ∈ T CS solving the CoFaSe problem (F, S α , S ω ) for the ConEvs model of dynamics under the synchronous mode is at most 2 | CX | :

Theorem 5 . 3 .

 53 contradicting our initial assumption that µ [k] is minimal. Therefore, any control sequence solving the CoFaSe problem for the ConEvs model of dynamics with more than 2 | CX | elements is not minimal, which proves the statement of the theorem. The size of the minimal contracted control sequence µ [k] ∈ OCS solving the CoFaSe problem (F, S α , S ω ) for the ConEvs model of dynamics under the synchronous mode is at most 2 | CX |+1 -1:

Corollary 5 . 1 .

 51 control sequence solving the CoFaSe problem for the ConEvs model of dynamics and with more than 2 | CX |+1 -1 elements is not minimal, which proves the statement of the theorem. Theorem 5.2 implies the impossibility of having two states, s i and s j , 1 < i < j ≤ k + 1, in the contracted trace with identical equivalence class. This point extends to 1 ≤ i if the initial state is an enduring state. The following corollary formalises this observation: Consider a minimal contracted control sequence µ T [k] ∈ T CS solving the CoFaSe problem (F, S α , S ω ) for the ConEvs model of dynamics under the synchronous mode. Take the sequence τ = (s i ) 1≤i≤k+1 of states induced by µ T [k] ,

Figure 5 . 3 :

 53 Figure 5.3: Boolean network having a control sequence reaching the bound for TCS ConEvs.

Example 5 . 1 .

 51 In Figure 5.3, in which CX = {x 1 , x 2 }, the CoFaSe problem under the ConEvs dynamics in which S α = {0011}, S ω = {1111} has the following TCS sequence of size 2 | CX | (4) as a solution:

Figure 5 . 4 :Example 5 . 2 .

 5452 Figure 5.4: Boolean network having a control sequence reaching the bound for OCS ConEvs.

Theorem 6 . 1 .

 61 Theorem 5.3 and Corollary 5.2, which guarantees the correctness of the result. In other words, the sequences found by Algorithm 1 solve a CoFaSe problem for the ConEvs model of dynamics under the synchronous mode, and are control minimal and minimal when considering the constraint of reaching the intermediate CX -profiles. Algorithm 1 returns all minimal control sequences µ [k] solving the CoFaSe problem for the ConEvs model of dynamics under the synchronous mode when considering the constraint of reaching the intermediate CX -profiles.

Figure 6 .

 6 1 illustrates, on the Boolean control network F U of Figure 2.7, the computation of a control sequence reaching a state in S ω from the set of initial states S α . The data structures are initialised as follows: CX = {x 2 , x 3 }, S α = {001}, S ω = {010, 110}, l = 1, Z 1 = S α , ∆ = {11, 10, 00}, and all the

Figure 6 . 1 :

 61 Figure 6.1: Iterations of Algorithm 1 on the Boolean network of Figure 2.7.

3 .Algorithm 2 1 . 2 .

 3212 The sets Z l , Z l+1 of unexplored nodes of the tree for the current level of depth l, and the next level.At the beginning,∆ is initialised to [S X ]/[S α ], the depth is l = 1, Z 1 contains the root equivalence classes {[s] | ∀s ∈ S α } ofthe exploration tree, and all the other data structures are empty. Correctness. Algorithm 2 closely follows the proof of Theorem 5.2, which guarantees the correctness and the minimality of the result. More concretely, the sequences found by Algorithm 2 solve the CoFaSe problem for the totally controlled ConEvs model of dynamics under the synchronous mode. These sequences are minimal. Inference of minimal contracted total control sequences Direct reachability of S ω : For all ζ ∈ Z l , infer the total control µ T taking the BCN from the equivalence class ζ to one of the target state in S ω . If such a µ T exists, add the arc labelled by µ T to G and go to step 4. Direct reachability of ∆: For every ζ ∈ Z l , infer a set of total controls U T taking the BCN from the equivalence class ζ to some of equivalence classes in ∆. If U T is non-empty, add the arcs labelled by the controls from U T to G, delete from ∆ and store in Z l+1 the set of reached equivalence classes.

2 .

 2 Continue if the sequence is not finished: If l ≤ n, go to step 1 with l = l + 1. Otherwise return the reduced sequence µ [n] .

Figure 6 . 2 :Figure 6 . 3 :

 6263 Figure 6.2: Percentage of the OCSbased and TCS-based one-step inference runs, aborted after an hour of computation.

Figure 6 . 4 :

 64 Figure 6.4: Median of memory usage by OCS-based and TCSbased one-step inference, excluding aborted computations.

Figure 6 . 5 :

 65 Figure 6.5: Median of memory usage by OCS-based and TCS-based inferences in aborted computations.

Figure 6 . 6 :

 66 Figure 6.6: Median of the sizes of controls found by the OCS-based and TCS-based one-step inference, excluding aborted computations.

Figure 6 . 7 :

 67 Figure 6.7: Percentage of times OCS-based inference yields a smaller control than TCS-based inference.

Theorem 7 . 4 .

 74 Let F U be a Boolean control network. The existence of a sequence of minimal size µ[k] with k ≥ 2, solving the CoFaSe problem under the ConEvs model of dynamics and synchronous modes implies the presence of at least a non-negative cycle in the CX -interaction graph of F U . Proof. Consider the CoFaSe problem (F U , S α , S ω ) and assume that µ [k] with k ≥ 2 is a minimal contracted total control sequence solving the problem for the ConEvs model of dynamics. This control sequence gives rise to the trajectory T = s 1 µ 1 -→ * . . .

( 7 . 1 )•

 71 A set of absorbing instantiations A c of its upstream variables in which the instantiation of the cycle directly depends on its upstream variables.∀s ∈ S X : s c ↙ ∈ A c =⇒ ∃y i ∈ c : Φ(f y i (y 1 , . . . , y k , s z 1 , . . . , s z l )) ∈ {1, 0}.

1 1 ,u 0 1 }

 11 The synchronous dynamics of a Boolean control network F {u with its interaction graph. From left to right, the respective controls are: no freeze, x 1 is frozen to 1, x 1 is frozen to 0. The active control parameters are mentioned below each dynamics. The stable states of each dynamics are coloured in three shades of grey, and their contours are drawn in different styles. Each contour style is associated with a different control input.

Figure 7 . 2 :

 72 Figure 7.2: The synchronous dynamics of a BCN used to illustrate nonabsorbing and absorbing instantiations.

F∅ or u 1 1 ∅ or u 1 1 ∅ or u 1 1 }

 1111 Interaction . The dynamics are synchronous and the self-loops on states are not shown. The stable states of each dynamics are coloured in two shades of grey, and their contours are drawn in different styles. Each shade of grey is associated with different control input and each contour style is associated with a different Boolean network.

Figure 7 . 3 :

 73 Figure 7.3: Influence of upstream instantiations on a cycle behaviour.

  equivalent positive cycle c ′ with a '-' arc between x 2 and x 3 and between x 3 and x 2 . The cycle c has for opposite instantiations γ ⊤ c = {x 2 = 1, x 3 = 1} and γ ⊥ c = {x 2 = 0, x 3 = 0} and the cycle c ′ has for opposite instantiations γ

Theorem 7 . 7 .

 77 with C being the set of non-negative cycles in the CX -interaction graph. Let F U be a totally controlled Boolean control network. All minimal sequences of total controls resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode cannot be of a size greater than min(β + 2, 2 | CX | ).

Theorem 7 . 8 .

 78 Let F U be a totally controlled Boolean control network. All minimal sequences of total controls resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode cannot be of a size greater than min(β ′ + 2, 2 | CX | ).

Lemma 7 . 3 .

 73 Let F U be a Boolean control network. Let µ [k] be a minimal sequence of control of size k > 2 that resolves the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode with the following trajectory

Figure 7 . 4 :

 74 Figure 7.4: The single positive cycle on CX , accompanied by upstream, downstream, and disconnected acyclic structures.

Lemma 7 . 4 .′ ∧ s i+1 c ′ ̸ = s i+2 c ′ and s i+1 c′Theorem 7 . 11 .

 74ci+1711 Let F U be a controlled Boolean control network. Assume that its CX -interaction graph consists of a unique positive cycle c with {γ ⊤ c , γ ⊥ c } as its unique pair of opposite instantiations. Let s and s ′ be enduring states, with s ′ c ∈trajectory s i µ T --→ s i+1 ′ µ T --→ s i+2 ′ , in which s i c ̸ = s i+1 c ∈ {γ ⊤ c , γ ⊥ c }.Such a trajectory cannot be generated by a positive cycle with its upstream variables in absorbing or non-absorbing instantiation., which proves the statement of the theorem. Let F U be a totally controlled Boolean control network. Assume that its CX -interaction graph consists of a unique positive cycle. In this case, all minimal sequences of control resolving the CoFaSe problem (F U , S α , S ω ) under the ConEvs dynamics in synchronous update mode are of size ≤ 2.

Example 7 . 2 .1 ,u 1 1

 721 The controlled Boolean network F {u 0 } of Figure7.2, with CX = {x 2 }, is a prime example of a Boolean network reaching the bounds of Theorems 7.10 and 7.11. For the CoFaSe problem under the ConEvs dynamics, in which S α = {11} and S ω = {01}, the solution for the TCS and OCS control strategies is the following sequence of size 2

Example 7 . 3 .x 1 = 5 ) ∧ u 0 5 x 6 = (1 ∨ ¬u 1 6 ) ∧ u 0 6 x 7 = (1 ∨ ¬u 1 7 ) 7 }

 73155666777 The Boolean network in Figure7.5 has for CX -variables x 5 , x 6 and x 7 . Its CX -interaction graph contains only the positive cycle c = {x 1 , x 2 }. It is one of the simplest examples of a Boolean network with a sequence of control reaching the bound of Theorem 7.8. In this network, there are only 8 equivalence classes in which the positive cycle c is in one of its opposite instantiations:[0000 ⋆ ⋆⋆] [0001 ⋆ ⋆⋆] [0010 ⋆ ⋆⋆] [0011 ⋆ ⋆⋆] [1100 ⋆ ⋆⋆] [1101 ⋆ ⋆⋆] [1110 ⋆ ⋆⋆] [1111 ⋆ ⋆⋆]Therefore, the maximal theoretical sequence size for TCS should be 2 + 8. This bound is reached for the following CoFaSe problem under the ConEvs dynamics where S α = {1001011}, S ω = {1111111}. This problem has for a solution the sequence of size 10:(x 2 ∧ ¬x 3 ∧ ¬x 5 ) ∨ (x 2 ∧ x 6 )∨ (x 2 ∧ ¬x 7 ) ∨ (x 3 ∧ x 4 ∧ ¬x 6 ∧ ¬x 7 )∨ (x 3 ∧ ¬x 5 ∧ ¬x 7 ) ∨ (¬x 3 ∧ ¬x 4 ∧ x 5 ∧ ¬x 7 )∨ (¬x 3 ∧ x 5 ∧ x 6 ) ∨ (x 4 ∧ ¬x 5 ∧ ¬x 6 )∨ (¬x 4 ∧ x 6 ∧ x 7 ) ∨ (¬x 5 ∧ x 6 ∧ x 7 ) x 2 = (x 1 ∧ x 3 ∧ x 4 ∧ x 5 ∧ x 6 )∨ (x 1 ∧ x 3 ∧ ¬x 4 ∧ x 5 ∧ ¬x 7 )∨ (x 1 ∧ ¬x 3 ∧ x 4 ∧ x 5 ∧ ¬x 6 )∨ (x 1 ∧ ¬x 3 ∧ ¬x 4 ∧ ¬x 5 ∧ ¬x 6 )∨ (x 1 ∧ ¬x 3 ∧ ¬x 5 ∧ x 6 ∧ ¬x 7 )∨ (x 3 ∧ x 4 ∧ ¬x 5 ∧ ¬x 6 ∧ ¬x 7 )∨ (x 5 ∧ ¬x 6 ∧ x 7 ) x 3 = x 5 x 4 = x 6x 5 = (0 ∨ ¬u 1 having in its CX - interaction graph a unique positive cycle, for which there exists a minimal control sequence reaching the bound defined in Theorem 7.8. The Boolean control network is accompanied by the interaction graph of the corresponding Boolean network without control parameters.

Figure 7 . 5 :

 75 Figure 7.5: A Boolean network with a control sequence reaching the bound for TCS sequences .

Table 2 .

 2

1: Application of the Boolean functions of a Boolean network.

  2. compares each new state with the states written in Segment (2); if one of these comparisons is successful, M accepts, otherwise it continues to the following substep; 3. checks if all the bits of the binary counter in Segment (3) are 1; if yes, reject, otherwise, commence the next macrostep. Intuitively, M simulates the deterministic synchronous dynamics of F on every state in Segment (1), accepts if it sees a target state from S ω , or rejects after 2 |X| steps. Counting to 2 |X| = |S X | ensures that the entire state graph of F reachable from S α is visited. Therefore, M accepts if and only if F can reach at least one state in S ω from at least one state in S α . Constructing

  with s 1 ∈ S α and s k+1 ∈ S ω . Therefore, a minimal control sequence does not pass through two states with identical equivalence class. Since µ [k] is minimal, the states from s 2 to s k are impermanent states and the equivalence classes from [s 2 ] to [s k ] are different target equivalence classes of their former state. The sequence then spans k -1 ≥ 2 | CX | different equivalence classes. Since only 2 | CX |

	From Proposition (5.2), we know that all states of a target equivalence class
	are reachable in one step under the appropriate control. Since only the up-
	date of impermanent states evolves the uncontrolled variables, it is only pos-
	sible to reach the next desired impermanent state or property from another
	impermanent state.Then, the main steps for solving CoFaSe consist in find-

ing the minimal path, from a state of S α to a state of S ω , by traversing solely impermanent through impermanent states of different equivalence classes.

  Inference of control minimal contracted control sequences 1. Direct reachability of S ω : For all ζ ∈ Z l , infer the control µ taking the BCN from ζ to a state in S ω . If such a µ exists, add the arc labelled by µ to G and go to step 6. 2. Reachability of S ω via a duplicate: For all ζ ∈ Z l , infer a pair of controls (µ, µ ′ ) such that µ takes the BCN to a state with an equivalence class included in [ζ], and µ ′ takes the BCN from there to one of the target state in S ω . If such a pair of controls exists, add two chained arcs labelled by µ and µ ′ to G and go to step 6. For each such control µ, infer a parsimonious control input µ ′ such that the set of stable states S µ ′ of F µ ′ reachable from ζ ′ contains some elements satisfying the desired property (i.e., a state that has the desired equivalence class or a state that belongs to the set of target states S ω ). 2. Let ζ be a set of initial states. then, infer a pair of parsimonious control inputs µ and µ ′ validating the following equation, with P being the predicate applied to the individual constant x that determines whether x is a state that has the desired equivalence class or a state that belongs to the set of target states S ω :

1 Algorithm 1 3. Direct reachability of ∆: For every ζ ∈ Z l , infer a set of controls U taking the BCN from ζ to a state with an equivalence class included in ∆. If U is non-empty, add the arcs labelled by the controls from U to G, delete the equivalence class reached in ∆, and store the sets of stable states reached thank to the inferred controls in Z l+1 . 4. Reachability of ∆ via a duplicate: For every ζ ∈ Z l , infer a set of pairs of controls D = {(µ, µ ′ ) | µ, µ ′ ∈ S U } such that µ takes the BCN to a state with an equivalence class included in [ζ], and µ ′ takes the BCN from there to some of the equivalence classes in ∆ which could not be directly reached at the previous step. If D is not empty, add chained arcs labelled by the pairs of controls from D to G, delete the equivalence class reached in ∆ and store the sets of stable states reached thank to the inferred pairs of controls in Z l+2 . 5. Continue if states left: If one of Z l , Z l+1 , or Z l+2 is non-empty, go to step 1 with l = l + 1 i.e., discarding Z l . 6. Produce the result: Find the sequence of controls by backtracking G from a leaf found in steps 1 or 2 to the root S α . If no such leaf was found, return ∅. of ζ.

  Steps of the construction of the tree built by Algorithm 1. For the Boolean control network F U of Figure2.7 and the set of initial states S α = {001}, Algorithm 1 infers the control sequence allowing to reach S

			Iteration 1:
	Direct reachability of S ω	Reachability of S ω via a duplicate
	{001}		s ∈ S w	{001}	[001]	s ∈ S w
	Direct reachability of ∆	Reachability of ∆ via a duplicate
	{001}	({u 1 1 })	11	{001}	({u 1 1 })	{111}
			10			[001]	10
			00			[001]	00
			Iteration 2:
			Direct reachability of S ω
		{001} ({u 1 1 })	{111} ({u 0 1 })	s ∈ S w
	Legend:

ω = {010, 110}. The only controlled variable is C X = {x 1 } and the uncontrolled ones are CX = {x 2 , x 3 }.

  ⋆10] and [⋆00] are not reachable. Accordingly, we update ∆ by deleting 11 and adding to Z 2 the stable states ζ ′ of F u 1 1 belonging to the searched equivalence class [⋆11] and reachable from Z 1 . Since in this example, S α contains only a state and 001

1, we see that a state of the equivalence class [⋆11] is reachable from a state of S α with the control {u 1 1 }, whereas the equiva-lence classes [

Table 6 .

 6 .4.1 provides the exact values of different parameters and the technical specifications of the machine used to run the benchmarks.

	Characteristics of the	Model		Macbook Pro
	computer used to perform	CPU		Intel Core i7 of 2.8GHz
	the experiments	RAM		16Gb of DDR3
	Implementation language	Wolfram Mathematica
	Parameters of the generation of random	Barabási-Albert model distribution parameter		2.1
	Boolean networks	probability to have a self-loop	0.1
		probability of having positive
		regulation and not a negative regulation	0.6
	Generated Boolean
	networks size	10	15	20	25	30	35
	CX -profile size	3	4	6	8	9	10

1: Parameters of the benchmarks.

-→ * is the reflexive and transitive closure of the transition relation.

One result for each input value.

According to the definition of a TCS, µ ′[START_REF] Barabási | Emergence of scaling in random networks[END_REF] is also an OCS sequence of control.

We also consider the empty control (i.e., the Boolean network not controlled).

In[START_REF] Dennunzio | Complexity of the dynamics of reaction systems[END_REF],Dennunzio et al. prove that the reachability problem in reaction systems is PSPACE-complete. Since reaction systems form a subclass of Boolean networks, the PSPACE-hardness result is a lower complexity bound for the reachability problem in Boolean networks.

Automatic Test Pattern Generation and Automatic Test Pattern Generator is an electronic design automation method used to find an input that, when applied to a digital circuit, enables to automatically distinguish between correct circuit behaviour and faulty circuit behaviour caused by defects.

,u 0 2 ,u 1

,u 0 3 } of Figure 3.1 where CX = {x 1 }. Equivalence classes are represented by polygons containing the CX -profile of the states belong- ing to them.Figure 5.1: Synchronous partitioned dynamics of two controlled Boolean networks.

,u 0 3 ,u[START_REF] Albert | Scale-free networks in cell biology[END_REF]

,u 0 4 ,u[START_REF] Albert | Scale-free networks in cell biology[END_REF]

,u 0 5 } with a minimal control sequence reaching the bound defined by Theorem 5.3. The Boolean control network is accompanied by the interaction graph of the corresponding Boolean network without control parameters.

Under the ConEvs model of dynamics, the modification of the control inputs instantiation only occurs at a stable state. If the system is in a cyclic attractor, the control inputs cannot be changed.

A state that has a desired equivalence class or a state that belongs to the set of target states S ω .

0⋆ and ⋆0 respectively correspond to the sets of states {00, 01} and {00, 10}.

profiles of s i and its subsequent states to the same constants, the change of instantiation of CX -variables depends on their formula. Thus, the dynamics generated by the formula of the variables of the cycle c must contains the

Excluding the first two stable states of the trajectory.

Remerciements

Phases of Algorithm 1. Algorithm 1 comprises two major phases.

The first phase (Steps 1 and 2) involves searching for a control allowing to directly attain a state of S ω .

The second phase (Steps 3 and 4) involves searching for a trajectory visiting an intermediary state within an unexplored equivalence class.

At each step, a parsimonious control input is inferred using the method presented in [START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Biane | Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery[END_REF]. The evolution of the main steps is detailed in Figure 6.1.

Data structures.

The algorithm relies on the following data structures:

1. The list ∆ of equivalence classes according to the equivalence relation 5.1.

2.

The exploration tree G with nodes labelled by sets of stable states and arcs labelled by controls.

3. The sets Z l , Z l+1 , and Z l+2 of unexplored nodes of the tree for the current level of depth l and the next two levels, respectively.

At the beginning, ∆ is initialised to [S X ]\[S α ], the depth of l = 1, Z 1 contains the root node {S α } of the exploration tree, and all the other data structures are empty. Note that we extend the notation of equivalence class to sets of states:

Duplicate states.

A specific treatment is applied to consider the case in which a trajectory passes through duplicates (i.e., the occurrence of states with identical equivalence class). As all states in the explored sequence are stable, and thus enduring states (i.e., their target equivalence class is equal to their equivalence class), a pair of duplicate states can be described as two states belonging to the same equivalence class. By considering that duplicates can only occur in two successive states of any given minimal contracted sequence (Corollary 5.2), we propose two strategies:

1. Let ζ be a set of initial states and ζ ′ be the set of stable states of F µ reachable from ζ. then, infer the set of parsimonious control inputs µ validating the following equation:

Informally, µ is a control that brings the network into a stable state other than the states of ζ, but has the same equivalence class as one of the states speaking. In the inference of the pair of controls µ and µ ′ , the dynamics of both F µ and F µ ′ need to be evaluated at the same time, which effectively doubles the number of variables for which an assignment must be found.

Minimality & optimality.

The algorithm returns a control minimal sequence (i.e., all control inputs of the contracted sequence are minimal.), but it may be possible to find shorter control sequences.

In the algorithm, the minimality condition is satisfied for the control inputs at each step of the inference. Therefore, for all intermediary states, the returned minimal control is reaching the desired CX -profile with a minimal number of perturbations. However, the state reached by applying the minimal control may not be the same as the state that needed to be reached in the CX -profile to find the minimal control sequence. In this case, a duplicate is needed to reach such a state. Note that these cases remain rare as they rely on the same complex mechanisms that generate duplicates. Therefore, the algorithm returns a minimal sequence in size when considering the constraint of minimal control to reach the intermediate CX -profiles.

Consider the following Boolean network: Example 6.2.

However, the following sequence of size 2:

) also converges to the same final state 1100. Their trajectories are respectively:

Since the target equivalence class 11 ⋆ ⋆ cannot be directly attained from the starting state 0000, Algorithm 1 infers a control sequence driving the BCN through some intermediary states. In the example above, the equivalence class 01⋆⋆ is picked first, and the state 0101 is then reached by the single minimal freezing of • For each pair {y j , y i } of variables of c in which y j ± y i , the relation from y j to y i in c is labelled by 1 ('+') or -1 ('-') 3 .

From these observations, we can refine the Equation 7.1 as follows:

The following proposition helps reveal on the nature of the set of possible instantiations of variables of a cycle c in which a stable state has the upstream variables of c instantiated to one of its non-absorbing instantiations. The proof is based on the observation that in this situation the virtual cycle of c must be positive.

Proposition 7.1. Let c be a cycle in the interaction graph of a Boolean network F . For all stable states s of F where s c ↙ ∈ N c , s c is only equal to one of the opposite instantiations of one of its positive virtual cycles.

Proof. Let c be a cycle in the interaction graph of a Boolean network. For all states s where s c ↙ ∈ N c , c will behaves like a virtual cycle c. When s is a stable state, c must be a positive cycle. Indeed, since each function of the variables of the resulting virtual cycle c has exactly one parameter, this cycle cannot have '±' arcs. Thus, c can only be a positive or negative cycle. If c was negative, s would not be a stable state as the variable of c would have the dynamics of a negative cycle, which that cannot have a stable state (Theorem 7.2). Moreover, if s is a stable state, s c must have the same instantiation as one of the stable states of c. Thus, s c is equal to one of the opposite instantiations of the positive virtual cycle c.

Note that when a cycle does not contain two '±' arcs in its interaction graph, then in the set of stable states with a non-absorbing upstream instantiation, only two profiles of the cycle variables are possible. Indeed, in this case, only one virtual positive cycle c can exist. Thus, the two possible profiles are the pair of opposite instantiations of c.

3 Note, such a relationship is only possible when y j ± y i is not the only arc in which y i is the head of the arc (i.e., there exists an arc between x → y i with x ∈ {z 1 , . . . , z l }).

When a cycle c does contain two or more '±' arcs in its interaction graph, c can have multiple pairs of opposite instantiations. When the upstream variables of c are in one of their non-absorbing instantiations, its set of '±' arcs becomes '+' or '-' arcs. Thus, the cycle that c is considered to behave as may not always be the same, because multiple positive cycles can be generated by transforming the set of '±' arcs.

To summarise, a non-negative cycle will have a set of opposite instantiations pairs. If a cycle c is positive or if the number of '±' arcs is fewer than 2, then the set will be of size 1. In this case, we denote for the sake of simplicity the opposite profiles as γ ⊤ c and γ ⊥ c .

Example 7.1. Consider the Boolean networks F , F ′ and

1 } ,and F ′′ {u 1 1 ,u 0 1 } can freeze x 1 to 0 (u 0 1 = 0) and 1 (u 1 1 = 0) or not freeze x 1 (∅). In all these cases, the control input u 1 1 results in the same dynamics as the control input ∅. F , F ′ , and F ′′ have in their CX -interaction graph a cycle c = {x 2 , x 3 } with, respectively, zero, one, and two '±' arcs, and the set of upstream variables of each cycle is c ↙ = {x 1 }. We distinguish the following situations in the three networks:

1 } has for a set of non-absorbing instantiations N c = {{x 1 = 1}} and for absorbing instantiations A c = {{x 1 = 0}}. For all stable states s where s c ↙ ∈ N c , the upstream of c will has no impact on the dynamics of the cycle. In this case, c has for γ ⊤ c = {x 2 = 1, x 3 = 1} and γ ⊥ c = {x 2 = 0, x 3 = 0}.

• F ′ {u 1 1 ,u 0 1 } has for set of non-absorbing instantiations N c = {{x 1 = 1}, {x 1 = 0}} and for absorbing instantiations A c = ∅.For all stable states s where x 1 = 0, the cycle c will have the same dynamics as a negative cycle with a '+' arc between x 2 and x 3 and a '-' arc between x 3 and x 2 . For all stable states s where x 1 = 1 the cycle c will have the same dynamics as the equivalent positive cycle c with a '+' arc between x 2 and x 3 and between x 3 and x 2 .

The cycle c has for opposite instantiations γ

1 } , has for a set of non-absorbing instantiations N c = {{x 1 = 1}, {x 1 = 0}} and for absorbing instantiations A c = ∅. For all stable states s where s c ↙ ∈ N c , when x 1 = 1, the cycle c has the same dynamics as the equivalent positive cycle c with a '+' arc between x 2 and x 3 and between x 3 and x 2 . When, on the other hand, x 1 = 0, the cycle c has the same dynamics as the

-Conclusion

In this thesis, we studied the sequential control applied to Boolean networks. The results are concretely applied to network medicine, which uses the concept of networks as a modelling framework.

We proposed a new framework that defines sequential control for Boolean control networks. In particular, we considered freeze controls, under which the variables can be frozen to 0 or 1. The proposed controlled dynamics extends the Boolean network dynamics by revealing how the system evolves through a sequence of control inputs. We defined a model of controlled dynamics denoted ConEvs, in which the modification of the control only occurs at a stable state in the synchronous update mode.

To allow detailed theoretical analysis, the variables of the studied network were partitioned into two sets. The set of variables that are controllable were denoted C X -variables, and the set of variables that cannot be controlled were denoted CXvariables.

We referred to the inference problem of finding a control sequence modifying the dynamics to evolve towards a desired state or property CoFaSe (i.e., Controlled Fate in Sequence). We proved that this problem is PSPACE-hard.

We know from the complexity of CoFaSe that finding a minimal control sequence by exhaustively exploring all possible control sequences is intractable. By seeking for factors that limit the set of the possible intermediary states of the sequence, we significantly reduced the search space in practice.

By studying the dynamical properties of the CoFaSe problem, we found that the dynamical properties that imply the necessity of a sequence of control emerged from the update functions of CX -variables. These properties enabled us to define the upper bounds on the length of minimal control sequences. We found that a minimal control sequence cannot be larger than 2 | CX |+1 -1. These upper bounds indicate that the uncontrollable variables are central for the inference of a control sequence. As the number of uncontrolled variables is, in practice, markedly lower than the number of controlled variables (e.g., [START_REF] Biane | Abduction based drug target discovery using Boolean control network[END_REF][START_REF] Burga | Loss of BRCA1 leads to an increase in epidermal growth factor receptor expression in mammary epithelial cells, and epidermal growth factor receptor inhibition prevents estrogen receptornegative cancers in BRCA1-mutant mice[END_REF][START_REF] Chau | Validation of analytic methods for biomarkers used in drug development[END_REF]), the exhaustive exploration of all possible profiles for these variables constitutes an efficient approach for control sequence computation. Set of CX -variables upstream of the set of variables V in the Boolean network interaction graph. V ⋄ Union of V ↙ CX and V. V ⇓ Set of strictly downstream and disconnected variables of V in the CX -interaction graph.