Pergamon BulletinofMathematicalBiology,Vol. 57, No. 2, pp. 247-276, 1995 Elsevier Science Ltd 9 1995 Society for Mathematical Biology Printed in Great Britain. All rights reserved 0092-8240/95 $9.50+ 0.00 0092-8240(94)00036-0 DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS--I. BIOLOGICAL ROLE OF FEEDBACK LOOPS AND PRACTICAL USE OF THE CONCEPT OF THE LOOP-CHARACTERISTIC STATE RENI~ THOMAS and DENIS THIEFFRY Laboratoire de G6n&ique, Universit6 Libre de Bruxelles, Rue des chevaux, no. 67, B-1640 Rhode Saint Gen6se, Belgium (E.mail: dthieffr@ulb.ac.be) MARCELLE KAUFMAN Service de Chimie-Physique, Universit6 Libre de Bruxelles, Campus Plaine CP 231 Bd du Triomphe, B-1050 Bruxelles, Belgium (E.mail: mkaufma@ulb.ac.be) In the field of biological regulation, models dictated by experimental work are usually complex networks comprising intertwined feedback loops. In this paper the biological roles of individual positive loops (multistationarity, differentiation) and negative loops (homeostasis, with or without oscillations, buffering of gene dosage effect) are discussed. The relationship between feedback loops and steady states is then clarified, and the problem: "How can one conveniently disentangle complex networks?" is then considered. Initiated long ago, logical descriptions have been generalized from various viewpoints; these developments are briefly discussed. The recent concept of the loop-characteristic state, defined as the logical state located at the level of the thresholds involved in the loop, together with its application, are then presented. Biological applications are also discussed. 1. Introduction. 1.1. Generalfeatures. Feedback loops. Regulations may be defined as the constraints that adjust the rate of production of the elements of a system to the state of the system and of relevant environmental variables. The main operators of these adjustments are feedback loops. In this paper, elements of a system form a feedback loop when their interactions can be represented by an oriented circuit. [Graph theoreticians use the word "circuit" (sometimes "cycle": Eisenfeld, 1987) for a 247 248 R. THOMAS et al. closed oriented pathway of any length. They reserve the word "loop" for the particular case of one-element circuits. In contrast, Tyson (1975) uses "loop" for circuits comprising at least three elements. In between, biologists use the term "feedback loops" for regulatory circuits of any length. This usage is adopted in this paper.] For a detailed analysis see, for example, Thomas and D'Ari (1990). Let us here simply recall a few essential points: (1) In a feedback loop each element exerts an influence on the evolution of all elements of the loop, including itself. There are loops in which each element exerts a positive influence on its own further development ("positive loops") and loops in which each element exerts a negative influence on its own further development ("negative loops"). Whether a loop is positive or negative depends only on the parity of the number of negative interactions in the loop: one deals with a positive or negative loop according to whether the number of negative interactions is even or odd. (2) Assuming (see sections 2 and 3) that the essential role offeedback loops is to ensure homeostasis (if negative) or multistationarity (if positive), a loop is considered functional if it actually fulfils this role. Networks and their symbolization. Many biological systems can be seen as networks, usually comprising intertwined feedback loops, directly or indirectly connected to external inputs and outputs. It is often convenient to symbolize these networks by graphs of interactions, in which the vertices represent crucial elements and the edges their interactions. If element j exerts a positive (vs + negative) action on element i, one writesj ~ i (vsj ~i); one thus deals with oriented signed graphs. Alternatively, a network can be represented by a matrix in which element aij (i.e. the element located at thejth column of the ith row) describes whether and how element j acts on the evolution of element i. Shape of the interactions and incidence on formal description. It is important to remark that, depending on the situation, the elements considered can be molecules, cells, populations of cells or organisms. Accordingly, the nature of the interactions can be extremely diverse (edges may represent chemical transformations, positive or negative regulations, allosteric transitions, etc.). Those interactions which have a regulatory character are, in general, nonlinear. In fact, the relationship between the concentration of a regulator and its effect is most often doubly non-linear: there is a threshold of concentration below which the regulator is inefficient and two boundary values of the rate of expression of the regulated element. This type of situation is described by a socalled sigmoid curve (Fig. 1). The threshold above which variable j acts on DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 249 rateof expression upperboundary ~ l lowerboundary t concentrationof the (positive)regulator threshold Figure l. Example of a positive sigmoid interaction. variable i is labelled Sij. Strictly speaking, the notion of threshold is completely unambiguous only in the idealized case of step functions. In sigmoids, like the Hill functions, a typical nominal value of the threshold is the value of the variable for which the function has its half-maximal value. However, it would be just as possible to define the threshold of a variable as the value corresponding to the inflexion point. As is well-known, the non-linear character of regulatory interactions complicates analysis, essentially because non-linear differential equations cannot usually be treated analytically. Simplified description using linear idealizations hold only in the close proximity of steady states. A diametrically opposite attitude consists of reasoning as if the regulator is "absent" below its threshold concentration and fully active above it. This "step function" is an infinitely non-linear idealization. Contrary to the linear caricature, it turns out that the stepwise caricature keeps all the essential characters of systems whose interactions are sigmoid in shape (see Glass and Kauffman, 1973; Thomas and D'Ari, 1990). In particular, the number, nature and location of steady states (if not the stability of foci) is generally preserved when one proceeds from a sigmoidal system to a stepwise description. To take advantage ofthis situation, one can describe regulatory systems with "piecewise linear" differential equations (see Glass and Pasternak, 1978; Snoussi, 1989), or use a logicaldescription (seeKauffman, 1969; Thomas, 1973; Glass, 1975), in which variables and functions can take only a limited number of values, typically only two (0 and 1). Biological application of the concept of the loop-characteristic state. As described brieflyin section 2 (see also Thomas and D'Ari, 1990; Thomas, 1991), 250 R. THOMAS et al. the logical description has become more and more sophisticated. Nevertheless, thanks to the concept of the loop-characteristic state (state located at the thresholds involved in the loop; Thomas, 1991; Snoussi and Thomas, 1993), the genuine simplicity of the method has been restored. In short, a complex network is now treated by focusing on the loops it contains and their interactions, rather than on the individual interactions. Or, using a metaphor, we operate as a clock-maker who first analyses a clock by focusing on the wheels and their interactions rather than immediately on the individual teeth of the wheels. The main purpose of this, and the following, paper is to show how this concept can be used in biological systems. 1.2. Biological role of negative loops. Homeostasis and oscillations. In a negative loop each element exerts a negative control on its own development via the other elements (if any) of the loolY-an essential result is homeostasis. The loop operates as a thermostat and tends to maintain the variables involved in the loop at, or near, supposedly optimal intermediate values, somewhere between the low boundary level which would prevail if the synthetic device was off and the high boundary level which would prevail if the device was fully on. In fact, each of the elements of the loop stabilizes at, or around, a level corresponding to its own threshold of activity in the loop. More specifically, when it is said that this homeostasis can stabilize products at, or around, this or that level we allude to the fact that, according to the case, the steady state may be stable or unstable. If it is stable the typical dynamics is a damped oscillation, tending toward a stable value; ifit is unstable the typical situation is a sustained oscillation, with a trajectory tending toward a limit cycle. Many systems can be described by autonomous ordinary (usually nonlinear) differential equations relating the rates of synthesis to the concentrations. It can be shown that, for proper parameter values, a negative loop has the following properties: (1) If it is a one-element loop it generates a single, stable, steady state; (2) If it is a two-element loop it generates a single steady state which is a focus; this means that it is approached or departed from in a periodic way. This focus is stable unless it is destabilized by a positive loop grafted on one of the elements of the negative loop (in this case one can have a limit cycle in spite of the low dimensionality). (3) Negative loops with three or more elements can generate damped or stable oscillations depending on parameter values. Some descriptions use differential equations with finite time delays, At, such that the rate of synthesis of a product at time t is related to the situation of the DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 251 system at time t-At. In this case, one can find oscillations, even with oneelement negative loops. Note that the use of finite time delays is in fact often justified in biology. For example, when one switches "on" a gene, there is an absolute delay before the very first molecule of active gene product appears. In any case, the essential role of a negative loop is to generate homeostasis around a steady state located near the thresholds. Our definition of homeostasis covers, in fact, two physiologically different situations. When the steady state is stable, or leads to weak oscillations, the system really functions as a thermostat and the oscillations can be considered as imperfections of the stabilizing device; however, when it leads to sizeable oscillations these oscillations may have a physiological meaning of their own (see Goldbeter, 1990). Buffering of gene dosage effect. A number of genes are negatively autoregulated. An important aspect of the physiological meaning of this situation has not been understood. When gene X is negatively controlled by another regulator there is, of course, a reduction of its level of expression, but this level nevertheless remains sensitive to gene dosage. This means that if there are n copies of gene X it will be expressed n times more than if there is a single copy (even though in both cases the rate of expression will be reduced by a given factor by the repressor). The picture is completely different for a gene which is negatively autoregulated. As mentioned above, if the negative loop is functional the gene product will stabilize at a steady level near its own threshold of efficiency;more concretely, ifthe product of gene X inhibits its own synthesis when its concentration exceeds a threshold, s, the steady level of this product is close to s, and this is independent of the number of copies of gene X. Thus, if negative autoregulation is efficient, it will tend to abolish gene dosage effects. [A concrete example (cro negative autoregulation) is described in the second paper of this series.] 1.3. Biological role of positivefeedback loops. As far as we know, the first clear suggestion that epigenetic differences and, by inference, differentiation might be ascribed to multistationarity is found in a short comment by Delbr/ick following a paper by Sonneborn (Delbr/ick, 1949). Thereafter, two concrete cases of epigenetic differences were described and clearly understood. The first situation deals with bacterial populations which can be durably (150 generations or more!) Mocked in either of two phenotypical states (lac operon, on or off) depending on a detail of their previous history (Novick and Weiner, 1957; Cohn and Horibata, 1959). The second example concerns the decision for or against immunity in temperate bacteriophages (see the second paper of this series). 252 R. THOMAS et al. The mechanism proposed by Delbrfick (1949) consists of two metabolic chains that are cross-inhibited by their products. In the Novick-Cohn system the presence of intracellular inducer is required for the synthesis of permease but, under the experiments used, the internalization of inducer requires permease: a vicious circle. In the lambda system the alternative states are due to the existence of two genes, cI and cro, which repress each other (see the second paper of the series). The common thread to all these theoretical and experimental situations is the presence of a positive feedback loop in the logics underlying the processes. It can be shown that positive feedback loops can generate multistationarity, or, more generally, a multiplicity of regimes. Consider, for example, the situation of two stable limit cycles whose basins are separated by an unstable limit cycle; even though we do not have multiple steady states, the system has a choice between two attractors (which in this situation are not punctual). Typically, a single positive loop gives the variables involved in the loop a stable choice between two extreme values, a low level close to the boundary value, which would prevail if the synthetic device was off, and a high level close to the boundary value which would prevail if the device was fully on. Somewhere between these two stable states there is typically a third, unstable, steady state on the separatrix separating the two basins of attraction. It is now clear that at least one positive loop is a necessary condition for multistationarity. This statement, proposed by one of us as a conjecture (Thomas, 1981, 1983) has now been formally demonstrated in differential terms, independently by Snoussi, Plahte and Thomas (see Thomas, 1994; Thieffry et al., 1995; Plahte et al., 1995). The interest of this statement stems from the increasing evidence that differentiation is essentially epigenetic in nature, i.e. differentiation is essentially the biological modality of multistationarity. As a positive loop is a necessary condition for multistationarity, it would be implied that any explanation of most developmental processes must involve at least one positive loop in its underlying logics, whatever the detailed molecular mechanisms. A concrete prediction is that in order to discover the key genes involved in differentiation one should find a way to identify the genes which exert a positive control (direct or indirect) on their own expression. An isolated positive loop can provide just two alternative sets of stable values for the variables of the loops. But, in developmental processes, one has to account for many steady states (assuming that each cellular type corresponds to a stable steady state ofthe system). It can easily be shown that m independent positive loops can generate 3" steady states, 2" of which are stable. (Additional interactions usually tend to reduce the number of steady states, except however, if they create additional positive loops.) Thus, seven genes subject to positive autoregulation could account for 27 (128) cellular states; more DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 253 generally, in order to have many steady states several positive loops are required. This holds for logical systems and for differential systems using sigmoid interactions. Note that isolated positive loops comprising only positive interactions are vicious circles in the sense that it is understood that they can be stably "on" or "off", but there is no way to control which situation will be realized. In fact, whenever such a loop is found in nature there are additional devices which permit control of their state. The interesting point is that a positive loop ("switch") can be switched on (or off) durably by a transient signal ("trigger"). In embryonic development, the authors feel strongly that an act of determination will often be found associated with a positively autocontrolled gene, responsible for the possibility to have binary choice, together with an additional mechanism responsible for the decision itself. 2. Formal Descriptions. 2.1. Differential description. Like Glass (1975), generally use differential equations of the forms: and many others, we xi=kiFii(x1, x 2, x 3 .... Xn)--k_ixi, in which F/involves sigmoid functions or their Boolean caricature and k_ ixi is a linear term of decay which exists for each constituent and consequently does not need to be explicitly mentioned in the logical description. Note: 1. In order to avoid any confusion, italic characters are used for real variables and parameters (as in differential equations) and Roman characters for logical variables and parameters. 2. The sigmoids most currently used are Hill functions. Thus, one uses as increasing sigmoids: F+(x)= x"/(s" + x"), which have the value 0 for x = 0, the value 1for high x and the value 0.5 for x = s. When n tends to infinity these curves tend to step functions with a well-defined threshold, noted s (s from the French seuil). Similarly, for decreasing sigmoids, one uses: F-(x)-=s"/(s"+x"), with F-= 1-F +. 2.2. Generalized logicalformalism. The core of the present paper deals with the use of the concept of loop-characteristic states in the analysis of biological regulatory systems. First consider some notions that are necessary for understanding this concept (Thomas and D'Ari, 1990; Thomas, 1991; Snoussi and Thomas, 1993). Asynchronous description. With each pertinent element of the system a logical variable x, whose discrete value describes the level of the element, is associated. The present state of the sytem is thus described by a state vector. In order to describe the evolution of the system, with each element we also 254 R. THOMAS et al. associate an operator X = fx(X,y, z,...) which describes the factors acting on the evolution of x. For each combination of values of the variables (i.e. each state of the system) there is a value X. X is termed the image of x because its value is the value toward which x tends when the system is in the state considered; in other words, when X # x there is an order for x to adopt the value of X. In this perspective, the evolution of the variable depends on the following simple rules: (1) if X=x, variable x is steady; (2) if X > x, variable x has an order to increase its value; (3) if X < x, variable x has an order to decrease its value. It might be said that, in a genetic system, x = 1 means that the gene product is present and X = 1 that the gene is "on"; indeed, if the gene is "on" the product is being synthesized and it will be present after a proper delay. Similarly, x = 0 means that the gene product is absent, X = 0 that the gene is "off"; indeed, if the gene is "off" the product (which is perishable) will disappear after a proper time delay (Thomas, 1973; Glass, 1975). Note: X is not a rate of synthesis, but rather the prospective value of x; its dimensionality is that of a concentration (like x). However, the value of X is related to the rate of synthesis of x in the sense that when this rate is high enough the future level of x will be high. At any time, the state of the system is described by the state vector (x, y, z,...) and its evolution by the image vector (X, Y, Z,...). When the state and image vectors are the same it is a stable logical state. When the state and image vectors are different it is essential to realize that the image of a state is usually not its next state, simply because usually only one variable switches offor on at a time. If two or more genes are switched on by a common signal it will take different times before their products reach an efficient level, and if two or more genes are switched off together it will take different times before their products become inactive, only if because different proteins have different life times. Example. Let us examine the system X = 5', Y =~, which exists in genetics: two genes which "contradict" each other in the sense that the product of one gene prevents the expression of the other, like genes cI and cro in bacteriophage lambda. The state table is: x y X Y 6611 [-0 1] 0 1 [1 011 0 1 0 0 The + and - superscripts on the elements of the state vector are used when a DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 255 variable and its image have different logical values; xy/XY=00/ll can be written more compactly as 6i~. In the table 6~/11 appears, which is redundant but convenient. It can be seen that for states 01 and 10 the state and image vectors are the same and consequently one deals with stable states (square brackets in the table). In states i~j and T1 there are two orders. In state 6~ there is an order to switch x from 0 to 1 and an order to switch y from 0 to 1. The possibility that these orders are obeyed in exact simultaneity is certainly unlikely; in most real cases it must be expected that either x or y will reach its threshold value first. The next state of ~J~Jwill thus usually not be 11, but rather [-10] or [01]; note that these are stable states, and in either case the "second" order has disappeared. Thus, we write: [10] y)~ ~ TT [01l This example already shows that a positive loop can generate multistationarity. As a matter of fact, any isolated positive loop would behave this way. Use of n-valued logical variables. The criterion to endow a variable with more than two (0 or 1) logical values (0, 1, 2,...) is simple: ifa variable has two or more distinct actions it is assumed that these actions take place above distinct thresholds. Thus, if a variable has n actions, generally n thresholds are used, and the variable has n + 1 logical values (Van Ham, 1979). Introduction of logical parameters. To render the logical description more supple and more general, Snoussi has introduced logical parameters (Snoussi, 1989; Snoussi et al. in Thomas and D'Ari, 1990). Logical parameters assign a "weight" to each interaction. These parameters have discrete values, with the same scale as the corresponding variable. The space of logical parameters thus comprises a finite and often small number of boxes, which display characteristic behaviour (see example on p. 258). Attribution of a logical value to thresholds. In systems comprising step or sigmoid interactions some of the steady states are located at, or near, threshold values and are not "seen" in classical logical descriptions. A logical scale is introduced, explicitly including the threshold values, 0, s(1), 1, s~2), 2,..., in which sm, s~2), ... are the generalized logical values ascribed to the lower, second, ... thresholds, whatever their real values s(~), s(2), .... Singular (vs regular) states are those in which one or more variable has a threshold value. 256 R. THOMAS et al. The image of singular logical states has to be defined. The general idea is that the image of a singular state can be derived from the images of the regular states that flank the singular state considered. Thus, the image of a singular state can be an interval. This leads to the generalization of the notion of logical steady state as follows: a logical state is steady iff for each variable i the image is consistent with the relation X~= x~. If n of the variables of a singular state are located on thresholds then this state has 2nadjacent regular states. Snoussi (1989) has demonstrated that in order to check the steadiness of a singular state one has to consider only two "relevant" adjacent states: those whose images are maximal and minimal (Snoussi and Thomas, 1993). Thus, a singular state is steady if its image is comprised in the interval of the images of the relevant adjacent states. Example.Let us illustrate the use of this generalized formalism by a simple example. The graph: or the matrix: (0+:) tell us that x is under negative control ofy and that y is under positive control of x and itself. y acts both on x and on itself, and there is no reason why the negative control exerted on x and the positive control exerted on y should involve the same threshold. Thus, we endow variable y and its image Y with two thresholds, s~1) and s(2), and three logical values 0, 1 and 2. We write: Multi-level logical variables Real variables Boolean variables y=0 ys ~21 ytl)=l yt2)=l y~l)and y{2)are Boolean variables whose value, 1 or 0, tells whether or not y exceeds threshold s~l) or st2), respectively. In contrast, x acts at a single level. Thus, it is assigned a single threshold and only two logical values, 0 and 1. DYNAMICALBEHAVIOUROF BIOLOGICALREGULATORYNETWORKS 257 Let us assume that y acts on x above its lower threshold s(~) and on itself above its higher threshold s(2). The graph and matrix become: +1 -1 and respectively. This could be provisionally described by the Boolean equations: X=y(1) (y(1) means "not ym,,) y = x(1)+ y(2), the state table is then completed as follows: (1) if condition y(1) is fulfilled, we write X= 1, otherwise X=0; (2) if either or both conditions x(1), y(:) is fulfilled, then we write Y= l, otherwise Y = 0. However, we want to further refine the description and introduce logical parameters which give a weight to the terms of the logical expressions. We associate: (1) with term y(~), parameter K~; (2) with term x(1), parameter K2; (3) with term yt2), parameter K3; (4) with the logical sum xm + yt2), parameter K23. The state table can now be filled with the values of images X and Y: (1) if condition y(1)is fulfilled (i.e. y = 0) we write X = K1; otherwise (i.e. y = 1 or 2) we write X = 0; (2) if condition x~1)is fulfilled (i.e. x= 1) we write Y= K2; (3) if condition y(2) is fulfilled (i.e. y=2) we write Y=K3; (4) if conditions x(~) and y(2) are both fulfilled (i.e. x = 1 and y = 2) we write Y=K23; (5) if neither xm nor y(2) is fulfilled (i.e. x=0 and y=0 or 1) we write Y=0. In addition, logical functions and parameters are allowed to take the same values as the corresponding multi-level variables (i.e. function X and parameter 258 R. THOMAS et al. K~ will take values 0 or 1, whereas function Y and parameters K2,K 3 and K23 will take values 0, 1 or 2). This gives: xy 00 01 02 10 11 12 or, in a disposition which recalls the X Y K 1 0 0 0 0 K 3 K1 K2 0 K 2 0 K23 variable space: 0210K 3 ~- 12/0K23 01/00 "q- II/0K 2 00/K10 10/K1K 2 0 1 x In this table the commands (suffixes, - or +, and arrows), which are present whatever the values of the parameters, are given. It is immediately apparent, for example, that state 00 will be steady iff K t = 0, state 02 will be steady iff K 3--2 and state 10 iff K 1= 1 and K 2= 0; the other states cannot be steady. As variable x has two values, parameter K 1can take the values 0 or 1, and as variable y has three values, parameters K 2, K 3 and K23 can take the values 0, 1 or 2 (with the restriction that K23 ~>K2, K3). Depending on the value of these parameters, this general state table splits up into several particular state tables, which describe all the qualitatively different situation. As an example, three tables are given, corresponding to some combinations of the parameter values: Y Y Y 2 2 2[02] -',- 12 oi "- i] 00 -~ [101 [02] ".- i2 1 01 ,,i- il 1 (; t.0 00 -~" 10 0 02 "-- 12 Ol ~'- il (; t+00 -*" 10 0 1 x 0 1 x 0 1 DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 259 where the compact notation has been used to describe the commutation commands. In the first situation the system has a choice between two stable states [0 2] and [1 0]; in the second situation there is a choice between a stable state [02] and an oscillation around the thresholds sm ofx and sm of y; in the third case the oscillation is the same, but there is no stable state in 02. The introduction of the logical parameters has made the analysis both more refined and more general. Each term in the logical expression has its proper weight and the state table covers all the qualitatively distinct situations, rather than describing a particular situation. Instead of being obliged to scan a number of real parameters for all possible values there is a finite number of combinations of values of the logical parameters. The attribution of logical values to the thresholds allows to find all the steady states. Example. For instance, in the preceding example, the logical variable can now take any of three values, 0, s(1)and 1, whereas y can take any of five values, 0, s~ 1, s~2)and 2. We distinguish between two types of state: (1) "regular states" (e.g. 00, 01, 11, 02, etc.), for which each variable has an integer value; (2) "singular states" (e.g. s(1)0, 0 s(*), s(*)s(1), s(1)S(2), etc.), for which one or more variable has a threshold value. The complete state tables are: Y Y 2 2[021 "~-- i2 01 "~-- 11 O0 --~ [101 2 02 .9-- 12 1 OT/~ "11 0 O0 _ 0 1 x0 1 x 0 1 x It is easy to check, for the parameter values chosen, that the singular states mentioned are indeed steady. For example, in the first and second situations, the regular states adjacent to 0 s(2) and their images are: xy O1 0 S(2) 02 X Y 0 0 0 2 It can be seen that in state 0 S(2), X = X = 0 and S(2) is located within the interval 260 R. THOMAS et al. 0-2 of the images of the adjacent states. Thus, 0 S(2) is a steady state of the system for the parameter values chosen. 3. Loop Characteristic States and Steady States. 3.1. Loops and unions of disjoint loops. There is a surprisingly simple relation between loops and "singular steady states", i.e. those logical steady states located on one or more threshold(s). In order to grasp this relation in its full generality, we first extend the notion of loop and consider not only loops proprio sensu but also unions of disjoint loops (disjoint loops are loops which have no variable in common). This generalization has already been proposed by Eisenfeld and De Lisi (1985) and Eisenfeld (1987), who use the term "g-cycles" ("g" for "generalized"). Consider the system of Fig. 2--it is easy to localize five individual loops (Fig. 3A). Each element of the "main" diagonal of the interaction matrix represents a one-variable loop, pairs of elements symmetrical to this diagonal represent two-variable loops, etc. The unions of disjoint loops are given in Fig. 3B. Note, that like the individual loops, the unions ofdisjoint loops may or may not involve all the variables of the system. (A) x y z X 0 0 a13 Y a21~/a23 Z 0 a32 Q (B) Figure 2. Example ofa three-variable regulatory network. (A) Graph ofinteractions (without specification of weights and signs); (B) the corresponding matrix of interactions. In (B) the existant (i.e. non-zero) interactions have been labelled aU according to their location in the matrix; the loops are indicated by lines or circles for the one-element loops. (A) (B) ~3 a32 | a32 ] /231a32 ] | 0 6 | | @ 0) %/ Figure 3. The feedback loops of the three-variable system of Fig. 2. (A) Individual loops; (B) unions of disjoint loops. DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 261 As mentioned in Snoussi and Thomas (1993), loops and unions of disjoint loops correspond to sequences ofelements (aij) ofthe matrix ofinteractions (or, as well, of the Jacobian matrix in the differential description), such that the sequence ofthej's is a permutation ofthe sequence of the i's. As a matter of fact, individual loops correspond to cyclic permutations and generalized loops to permutations in general. [The permutations of {1, 2, 3} are: (a) 12 3, (b) 13 2, (c) 2 13, (d) 2 3 1, (e) 3 12, (f) 3 2 1. In a12 a23 a31 the sequences of thej's and of the i's are related by permutation d--*a; in all a/3 a32 by permutation b--,a; in all a22 a33 by permutation a--,a.] 3.2. Loop-characteristic state. The characteristic state of a loop or a union ofdisjoint loops is the singular state located at the thresholds of the loop, i.e. at the thresholds above which the variables of the loop are operative. Although this notion arises from the logical description it will be illustrated firstly in differential terms. Figure 4 describes the positive loop x~t"-----~; in differential terms. In _ . ~ J Fig. 4A the loop is functional, i.e. multi-stationarity is ensured, in Fig. 4B it is not. This depends on parameter values, and more specifically on the relation Y Y 1 1 s (1) 4-4- 0 dy/dt=O dx/dt=O ~_ 4-- ~l~" j ,r s(!) 1 (A) Figure 4. A system consisting dx/dt=O s (Y 4--dy/dt=O 0 , , ~(~ x 0 s (~) 1 x (B) of a two-element positive loop. x(~)y(-~) is represented in differential terms in the space of the real variables xy. The nullclines dx/dt=O and dy/dt=O have been plotted. The steady states are, of course, the intersections of these curves. (A) and (B) represent two typical situations and correspond to different sets of parameter values. In (A) the loop-characteristicstate sm sI1)is steady and there are three steady states. In (B) the loop-characteristicstate s(a)s(1)is not steady and there is a single steady state at the level of the boundaries of the system. "+ -" indicates that dx/dt > 0 and dy/dt < 0, etc. The arrows indicate the direction of the trajectories. The equations used are dx/dt = kl +k~2 F~ (y)k ~x and dy/dt-= k2-Fk2tF~ (x)-k_2y, where F-s are decreasing Hill functions with threshold= 1 and non-linearity coefficient=20; the other parametric values are: (A) k1=k2=0.2, k_ 1=k 2= 1, k~2=k21 =2; (B) the same as (A) except that kzl =0.5. 262 R. THOMAS et al. between kl/k and the thresholds. For a step function, the condition is simply kl/k_ >s. For a sigmoid kl/k_ must be sufficiently >s. In Fig. 4A, but not Fig. 4B, there is a steady state near the threshold values of the loop. Figure 5 describes the negative loop x..k j y in differential terms. As expected, there is a single steady state. In Fig. 5A the loop is functional (homeostasis is realized), in Fig. 5B it is not. (As in the loop described by Fig. 4, this depends on parameter values.) In Fig. 5A, but not Fig. 5B, there is a steady state near the thresholds of the loop. These examples illustrate the idea that when a loop, positive or negative, is functional, there is a steady state near the thresholds of the loop. In the logical description the situation is even more clear-cut: whenever a loop is functional the singular logical state located at the thresholds of this loop is steady. This leads to the introduction of the concept of the loop-characteristic state, defined as the logical state located at the thresholds involved in the loop. This concept applies to the subspace of the variables actually involved in the loop. Thus, if a loop involves all the variables of the system its functionality is associated with the presence of a steady state of the system at (step or logical functions) or near (sigmoid functions) the intersection of the thresholds of the loop. Ifa loop involves only some of the variables of the system its functionality requires only steadiness of the loop-characteristic state in the subspace of the Y 1 s(1) dy/dt=O I I I 0 s (~) 1 Y s(1, +o ~+ I I x 0 s (~) 1 x (A) (B) Figure 5. A two-variable negative loop xI1)y(- 1)represented in the space of the real variables xy. (A) There is a steady state at the level of the loop-characteristic state stl)s(1) and it is seen that the system oscillates (at least transiently) around the steady state (a focus). (B) There is no steady state at the level of the loop-characteristic state; there is no homeostasis since the unique steady state is located at the level of the boundaries of the system. The equations used are dx/dt = k 1+ k12F~ (y)-k ix and dy/dt = k2 ~- k21F2 (x)- k 22, where F + and F are increasing and decreasing Hill functions, respectively, with threshold = 1 and non-linearity coefficient = 20; the other parametric values are: (A) kl = k2 = 0.2, k_ 1= 1.1, k_ 2= 0.9, k12= k21 = 2; (B) the same as (A) except k21 =0.5. DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 263 variables of the loop. But this state will be a steady state of the whole system only if the other variables are also steady. It has been observed by Thomas (1991), and subsequently formally demonstrated by Snoussi and Thomas (1993) that: (1) among the singular states of a system, only those which are loopcharacteristic can be steady; (2) conversely, if a state is loop-characteristic there exist combinations of parameter values for which it is steady. From a practical viewpoint, these results are very useful. Instead of having to scan each singular state for steadiness only the loops and their characteristic states have to be identified. Then, it can be checked which of the characteristic states are steady (if the parameters are known a priori), or else the parameters which render a loop-characteristic state steady can be determined. From a fundamental point of view, these results shed new light on the relation between feedback loops and steady states. Example. Let us return to the example on p. 256 and now treat it in terms of loop-characteristic states. The system comprises two feedback loops, a twovariable negative loop, denoted x~l)y~- 1), and a one-variable positive loop, denoted y~2).Their characteristic states are s~a)sm and x s~2), respectively (in which x means that the value of x remains open). Depending on the parameter values, either one or both of these singular states can be steady (see tables on p. 259). On the contrary, the other singular states, which are not loop-characteristic (e.g. s~1)S(2)) cannot be steady for any combination of values of the parameters. 3.3. State characteristic of a loop, of a union of disjoint loops and of a union of connected loops. A state can be a "loop-characteristic" state, irrespective of whether it is characteristic of a single loop or of a union of loops. Three typical cases of characteristic state are given in Fig. 6: (1) a state characteristic of a single three-variable loop; (2) a state characteristic of two disjoint loops; (3) a state characteristic of two connected loops. The conditions for the steadiness of single loop-characteristic states remain valid for states characteristic of unions of loops. 4. Regulatory Networks as Combinations of Feedback Loops. Table 1 describes, in a compact way, various simple situations, including one-element positive and negative loops and their combinations, and two-element positive and negative loops. It applies to parametric conditions for which the loops are 264 R. THOMAS et al. S(1) z (i) S (I) S S (I) S(3) z (A) (B) (C) Figure 6. Examples of loop combinations that can lead to singular steady states located on three thresholds: (A)a singlethree-elementfeedbackloopwith S(2) S(1) S(2) as the characteristic state; (B) two disjoint feedback loops with s(I)s(1)st2) as the common characteristic state; (C)two non-disjoint feedbackloops with st2)sI1)st3)as the common characteristic state; in the latter case the two interactions exerted by element x must occur at the same threshold for the two loops to share the same characteristic state. functional; these conditions can easily be determined, either "by hand" or by using computer programs (Thieffry et al., 1993), depending on the complexity. Each of these examples must be viewed not as a system comprising only the elements explicitly shown, but as a building bloek of complex networks. Which of the loops or unions of loops remain functional when one proceeds to this construction depends on the values of the parameters and of the other variables. For a given set of parametric values a loop or a union of loops can be functional or not, depending on the region of the space of the variables. But, whatever the complexity of the system, what is said about the component loops remains true in a subspace of the variables of the loops considered. This way of thinking can be used both analytically (deductively) or synthetically (inductively), i.e. to analyse the properties of a given network or to construct a network which has expected properties. Figure 7 shows two systems whose dynamics are not easily predictable by conventional methods. Using our method, which consists of first identifying the feedback loops, one immediately sees that the system in Fig. 7A has only negative feedback loops. In the absence of any positive loop it is known that there cannot be any multistationarity, whatever the parameter values used. The system can have only one steady state and, depending on the parameter values, this steady state can be the characteristic state of either of the loops, or unions of loops, of the network, or it can be a regular state if none of the loops is functional. The system in Fig. 7B shows that an additional interaction creates a positive loop. Either this loop is non-functional, and we return to the preceding DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 265 Table 1. Examples of feedback loops, with a description of their dynamical properties and characteristic states loops and their matrix description One-element positive loop on x (r One-element negative loop on x (o) Typical pattern in the variable space One-element y positive loops on x j andy (.%) One-element y negative loops on x / and y s o, ! One-element loops, y , S(1)} [3.] lower upper boundary boundary a positive one on x, a negative one on y (%) Two-element positive loop (o0) Another twoelement positive loop (| Two-element negative loop ,.... ~,,",, ~boundary boundary 1 I \ lJ" -;+, i T Ii sO) x I ! s(O I s (l) =x sO) s (11 x s (I) x Logical description Three steady states : [0] and {1] are attractive, [ls] is repulsive A single steady state : [1s] is attractive Nine steady states: [00], [01], [10] and [11] are attractive; ![0ts], [ls0 [lsl] and 11s] are repu s ve along one direct on; [lsls] is repulsive along both directions A single, stable state: lsls] is attractive along both directions Muitistationadty on variable x, homeostasis on variable y; three steady states: [0 ls], [lsls] and [1 ts]; the loop-characteristic state [lsls] is repulsive in x, attractive in y Multistationahty on both vadables; three steady states: [01] and [10] are attractive; [isis] is repulsive in one direction, attractive in the orthogonal direction Multistationadty on both vadables. Three steady states: [00] and [11] are attractive; dlSls] is attractive in one irection, repulsive in the orthogonal direction Differential description Three steady states: 2 stable 1 unstable A single stable steady state: a stable node 32 steady states: - 4 stable nodes - 4 saddle points t unstable node A single stable steady state: a stable node Three steady states: -2 stable nodes -1 saddle point Three steady states: - 2 stable nodes -1 saddle point Three steady states: - 2 stable nodes - 1 saddle point 'L 'r s(,) ( ~ s(t) Ix A single steady state, [lsts], surrounded by a logical cycle: 0i -, i] t A single steady state: - a stable focus Roots of the characteristic equation real: + real: real: +,+, + real: real: +,- real: +,- real: +,- complex, real part negative Remarks [lsls) is the characteristic state of the union of the two loops [tsts] is the charactedstic state of the union of the two loops 1sis] is the characteristic state of the union of the two loops The elements are Iexclusive of each other; either x [10], !or y:[01] is present The elements are interdependent; one has either both [11] or neither [00] element present instead oI ~ to indicate the order of theIn the text of this table, we have used the notation is ~ ~(1) threshold for compactness. 266 R. THOMAS et al. 9 0 9 (A) (B) Figure 7. Two examples of a three-element regulatory network. The three-element loop formed by the interactionsfrom x to y, from y to z and back to x, is symbolized by "x y z". The sign of this loop is negative since it is equal to the product of the signs of its interactions. (A) There are six negative loops: x, y, z, x y, y z and x y z. (B) An additional interaction introduces a positive loop (xz), together with an additional negative loop (x z y). situation, or it is functional, and we know that there are three steady states, one of which is the characteristic state of the positive loop. As an example of the synthetic use of our method, consider a steady state that is attractive along the z-axis and repulsive in a periodic way in the plane xy. How could one build a small system with such a steady state? In order to be attractive along the z-axis the system must have a negative loop ofz on itself. In order to be periodic in the plane xy it must have a negative loop between x and y. But, it is known that in a two-variable system, a focus is stable unless it is destabilized by autocatalysis (one-element positive loop) on one of its elements (this point does not come from the logical description). This leads to the matrix: x y z X Y + + Z It is easy to find a system of this structure that behaves as expected. Note that the properties of the roots of the characteristic equation (one real negative root and a pair of complex conjugate roots with a positive real part) can immediately be derived from the matrix provided the loops have the proper strength. It is interesting to note that although our method arises from a logical formalism, the type of reasoning can be used, mutatis mutandis, for a linear DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 267 Y 2.0 -2.0 0 . 0 ~ -2.0 z 2.0 0.0 -2.0 2.0 x Figure 8. A steady state that is attractive along the z-axis and repulsive (up to infinity) in a periodic way along the xy plane. The (linear) equations used are dx/dt = -2y, dy/dt = 2x + 0.5y and dz/dt = -10z; the initial point is (0.1, 0.1, 2). system; for example, the steady state just mentioned can be obtained in a linear system (Fig. 8). 5. A Biological Illustration: The Regulation of Arginine Anabolism. In order to show the application of the notion of loop-characteristic state to a concrete biological system, an example, inspired from a beautiful experimental work of W. Maas and his co-workers, is considered. We will focus here on some aspects that have not been touched so far in the experimental work. Let us first summarize the most salient experimental facts. In E. coli, the enzyme Ornithine Transcarbimylase (OTCase) catalyses the last step of the anabolism of arginine. Arginine combines with a repressor, which reduces the rate of synthesis of OTCase and of itself. However, in addition to its negatively auto-controlled promotor, the gene coding for the repressor has a second promotor responsible for a minor constitutive expression. This simplified description is represented by the reaction scheme shown in Fig. 9A. The graph of interactions (Fig. 9B) and the matrix of interactions (Fig. 9C) include additional assumptions regarding the order of the thresholds. As both the repressor and arginine act at two levels in this scheme, two threshold values, sm and s~2)(and consequently three logical values, 0, 1 and 2), are ascribed to both variables. The matrix of interactions can thus be completed in four ways, 268 R. THOMAS et al. y repressox ~0 0 '" z ~.~ Y~ 121(i) ~ s > arginin~ s x OTCase z (A) (S) (C) Figure 9. Model for the regulation of arginine synthesis. (A) Reaction scheme; (B) graph of interaction; (C) matrix of interactions, x=arginine concentration; y = repressor concentration; z = OTCase concentration. (A) Regulatory interactions are symbolized by simple arrows, whereas metabolic transformation is symbolizedby a double arrow. Note, in the proposed model, x and y both have two distinct actions; thus, associated with these variables are two thresholds and three logical levels (0, 1 and 2). In contrast, z acts only on x; consequently, there is ascribed to it only one threshold and two logical values (0 and 1). (B) The signs + and - correspond to the sign of the interactions; the s(i)s symbolize the corresponding threshold. In this graph it is easy to locate the three feedback loops of the system (two negative loops, y, x z, and one positive loop, xyz). (C) The feedback loops of the system are indicated by a circle (auto-inhibition on y) and lines. depending on the order of the thresholds. Which of these possibilities is most appropriate is not obvious, but various experimental and theoretical arguments may be used to distinguish between them. In particular, one may favour the idea that the repression of OTCase synthesis requires lower levels of repressor (> s~1))than the auto-repression of repressor synthesis (> s~2)).If this was not the case, the steady level ofrepressor would, at least at first sight, be too low to exert an efficient repression of OTCase synthesis. We focus on one of the four threshold combinations, shown in Fig. 9B and C, which is favoured by W. Maas (pers. comm.). It is seen immediately that this structure comprises three feedback loops: (1) a negative loop between x and z, symbolized by x(-1)z (+1), which describes the mutual regulation between arginine and OTCase; (2) a negative loop on y, symbolized by y(-2), which describes the auto-regulation of the repressor; (3) a positive loop, x~- /) y(-1) z~+a), whose existence was not obvious a priori. In addition, the union of the disjoint loops x(- i) z(+ 1)and y(- z) (symbolized by x(- 1)z(+1)+ y(- 2)) must be considered. The presence of a positive feedback loop suggests that under appropriate conditions the system might display multi-stationarity. This means that for proper parameter values (e.g. in proper mutants) there could be different states DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 269 of regulation of repressor and OTCase synthesis, depending not on the present environmental conditions, but on a historical detail, e.g. whether or not there has been a pulse of arginine in the external medium in the past. The logical analysis of the situation is summarized in the appendix. In any case, one can immediately read from the graph or matrix of interactions that the loop-characteristic state of the union of the negative loops is [s~1)s~2)sm], and that the loop-characteristic state of the positive loop is [s~2)sm s~)]. It is now quite easy to compute (see Thieffry et al., 1993) the constraints on the parameters that render Is(a)S(2) S(1)]or Is(2)S(1) S(1)],or both, steady. This would render, respectively, the negative or the positive loops, or both, functional, with resultant homeostasis on all three variables, multistationarity or both. A closer analysis of the parameter values that would render the positive loop functional shows (see appendix) that for the threshold combination chosen the positive loop cannot be functional unless parameter K3.2 is nil. This is not reasonable, because it would mean that the repressibility of OTCase only depends on arginine and not on the presence of the repressor! However, for other threshold combinations, it is found that realistic parameter values are consistent with multiple steady states. Thus, even though one does not expect multistationarity with the standard strains, it would be worthwhile checking mutants with altered threshold orders. It was mentioned above that the state of a positive loop is typically determined by a transient signal. Depending on whether or not the signal has been given, the system is durably blocked in either of its permanent states. In the present case, an obvious signal is the extraceUular concentration of arginine. The model suggests that for proper parameter values the state of the system will durably depend not only on the present but also on the past extracellular concentration of arginine. Of course, arginine must then be introduced as an input variable in the model. For mutants thermosensitive for one of the gene products, transient temperature shifts as a signal may also be used. But, what is really meant by "for proper parameter values"? The logical parameters describe the strength of the different interactions of the system, which is, here at least, partly genetically determined. A mutation affecting the coding part of the repressor could modify its affinity for the promoters (parameters K2. 2 and K3.2) or its interaction with arginine, thus its combined effect with arginin on its own synthesis and on the synthesis of OTCase (parameters K2.t2 and K3.~2), etc. Thus, it is expected that mutants will exhibit a whole range of values of the logical parameters. If the wild-type does not lead to such interesting behaviour as multistationarity the constraints on the parameters can be used in order to determine which mutants might. In the appendix the parameter range chosen (all three loops functional) is the richest from the dynamical viewpoint. However, it is by no means the only 270 R. THOMAS et al. interesting one. In fact, it seems obvious that the realistic values for some of these parameters will be different for E. coli K12 and E. coli B. Maas and his coworkers found striking behavioural differences, which can be ascribed to a single amino-acid difference in the sequences of the repressor (Lim et al., 1988; Tian et al., 1994). 6. Discussion. Few works consider regulatory networks in terms of feedback loops (see, however, Rosen, 1968; Eisenfeld and De Lisi, 1985; Eisenfeld, 1987). Of special relevance is the paper in which Tyson (1975) starts from the concept of "community matrix", previously developed by Quirk and Ruppert (1965) and May (1973). For a system dxi/dt=Fi(xl, x2, ..., Xi, ..., Xn), one can derive a matrix A = [aij]0, in which aij = (~Fi/c3xj)o , i.e. the Jacobian matrix of the system at a steady state, and analyse the relation between the presence of feedback circuits and the stability of the steady state. The situation is considered here under a slightly different angle. First, as most biological regulations have a sigmoid shape, our systems can often be described by equations in which the F~sare monotonic in each of the variables (when it is not the case, it prevents description of the system with a matrix of interactions, but not from performing its logical analysis). Thus, most terms of the Jacobian matrix usually have a well-defined sign throughout the space of the variables. Consequently, instead of considering the signs of the terms of Jacobian matrices at steady states, we have a qualitative Jacobian matrix which is descriptive of the whole system. In fact, in our case, the signs of the terms of the Jacobian matrix coincide with those of the matrix of interactions of the system. According to the limited choice of logical parameter values, each "logical structure" (e.g. each system as described by a graph or by a matrix of interactions) splits up into a finite (and often small) number of qualitatively distinct schemes, each representative of a qualitatively distinct facet of the system. In practice, this is seen in the general state table, in which the elements of the image vectors are parameters that can each take a limited number of integer values. A distinctive feature of this present approach consists of operating at the level of the feedback loops of the system rather than at the level of its individual elements. Firstly, the feedback loops and their characteristic state are identified, then for each loop (or union of disjoint loops) the parametric constraints which make the loop functional are computed. This analysis (see appendix) fully respects the interactions between the loops, however complex they are. Depending on the logical structure and parameter values, one or more feedback loops are functional, with straightforward consequences regarding the number, location and nature of the steady states. In this respect, the analysis is almost immediate in those systems that DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 271 comprise only negative loops; whatever the complexity of the network, it is known that in this particular case there cannot be any trace of multistationarity. Thus, in such a system, there is only one steady state, which may be either of the loop-characteristic states. If none of the loops is functional the steady state is a regular and stable state (Snoussi, 1989). Ifa system has just one positive loop, either this loop is not functional and we revert to the preceding situation, or it is functional and we know immediately that the system has three steady states, one of which is characteristic of the positive loop. It should be noted that logical states are generally not points; in the real space of the variables a regular logical state is a segment, a surface, a threevolume or an n-volume, according to whether the system has 1, 2, 3 or n variables. Thus, it is not surprising that a logical state can have a choice between two or more successors; this, at least, is the case in the asynchronous logical description used here (Thomas, 1973). The factors of the choice between follower states are not discussed in this paper. It suffices to recall that they are usually treated in terms of time delays, which are generally different for each transition, and which can introduce stochasticity, if each delay has an average value and a distribution rather than a fixed value (Thomas, 1979; Van Ham, 1979). The generalized logical method described here has already been used to analyse genetic, immunological and neurobiological regulatory networks (Kaufman, 1988; Thomas and D'Ari, 1990; Thieffry et al., 1993). The second paper in this series deals with the modelization of the genetic regulation of bacteriophage lambda. We wish to thank Werner Maas for fruitful discussions, as well as Leon Glass and Lee Segel for many useful suggestions. D. T. has been supported by a Grant T~l~vie (Fonds National de la Recherche Scientifique, Belgium). M. K. acknowledges financial support by the Belgian program on interuniversity attraction poles. R.T. acknowledges financial support from Actions de Recherche Concert~e, Solvay Company and Fonds National de la Recherche Scientifique. All simulations of differential systems have been made using GRIND, kindly provided by R. J. de Boer. 272 R. THOMAS et al. APPENDIX A1. A Partial Analysis of the System of Fig. 6. x y z 0 0 +1 -2 -2 0 -1 -1 0 X Y Z Table A1. State table for the threevariable example. For each value of the state vector (x y z), this table gives the value of the image vector in terms of logical parameters. K i ("basal term") corresponds to the expression of element i in the absence of its activators, but in the presence of its inhibitors; Ki4 corresponds to the expression of element i in the presence of element j if it is an activator of element i, or in the absence ofj if it is an inhibitor. Ki.jk represents "positive contributions" of both elements j and k on element i yz X Y 0 0 K 1 K2A 2 0 1 K1.3 K2.12 1 0 K 1 K2.12 1 1 K1.3 K2.12 2 0 K 1 K2.1 2 1 K1.3 K2.1 0 0 K 1 K2.12 0 1 K1.3 K2.12 1 0 K 1 K2.12 1 1 K1.3 K2.12 2 0 K 1 K2.1 2 1 K1.3 K2.1 0 0 K 1 K2.2 0 1 K1.3 K2.2 1 0 K 1 K2.2 1 1 K1.3 K2.2 2 0 K 1 K 2 2 1 K1.3 K 2 Z K3.12 K3.12 K3.1 K3.1 K3.1 K3.1 K3.2 K3.2 K3 K3 K3 K3 K3.2 K3.2 K3 K3 K 3 K 3 DYNAMICAL BEHAVIOUR OF BIOLOGICAL REGULATORY NETWORKS 273 AI.1. State table. As described in previous papers, from the above matrix it is possible to construct a state table (Table A 1). How can the state table be completed starting from the matrix of interactions? In the matrix, box i-j (ith row,jth column) describes the effect of the level of element j on the evolution of element i, i.e. the effect of the value of variable j on the value of I, the image of variable i; thus, box 1-3 describes the effect ofz on X. "+ 1" in box 1-3 means that there is a contribution to X, represented by parameter K~.3, if z > s(1). Thus, when column X of the state table is filled in, K~.3is entered each time z = 1. Similarly, "-2" in box 2-1 means that there is a contribution K2.~ to Y for x < sIz)and, accordingly, for x = 0 or 1 K/.1 is entered in column Y. If conditions x < s~2)and y < st/) are both fulfilled, boxes 2-1 and 2-2 both contribute to the value of Y and K2.12 is entered in column Y, etc. [Following Snoussi (1989), the logical parameters K2.1 and K2.2 result from the discretization of the real parameters k2.t and k2.2, respectively. K2.12 refers to the discretization of (k2.1+ k2.2). It is usually not equal to K2.1 + K2.2- For example, one can have kz.x s 12). In this case, K2.1 and K2.2=0, but K2.12 =2. However, K2A2 is necessarily ~>K2.a, Kz.z. ] In addition, allowance is usually made for a constant term (labelled in the present case as Ka, K 2 and K3, for functions X, Y and Z, respectively) which may correspond to the constitutive expression of the gene, or, in other cases, to an input variable. A 1.2. Identification of the loops. There are three feedback loops: (1) a positive loop x(- 2)yl- 1~zI+17(characteristic state s~2)s") s(~)); (2) a negative loop x(- ~)z~+~ (characteristic state s") y s")); (3) a negative loop y~-2) (characteristic state x s(2)z); plus the union of the two disjoint (negative) loops: x(-l)z~+l)+y(-2) (characteristic state S(I) S(2)S(1)). A 1.3. Conditions of steadiness of s(2)s~1)s(1) and s~) s12)sta). State st2)s~) s(x) is located at the junction between 23= 8 regular states; the pair of "relevant" adjacent states (see Snoussi and Thomas, 1993) and their images are: x y z X Y Z 2 1 0 K 1 K2, 2 K 3 1 0 1 K1. 3 K2,12 K3. 2 The conditions for the state to be steady is that thresholds s~t/), Sy(1), Sz(1) be included in the interval of the corresponding images, i.e.: K 1