Graduate Thesis of Marco Montalva
 | Program | PhD in Applied Sciences with mention in Mathematical Engineering, Universidad de Concepción |
|---|---|---|
| Enrollment Year | 2006 | |
| Senior Year | 2011 | |
| Thesis Title | Feedback Set Problems and Dynamical Behavior in Regulatory Networks | |
Thesis Summary:In the nature there exist numerous examples of complex dynamical systems: neural systems, communities, ecosystems, genetic regulatory networks, etc. These latter are particulary of interest to us. Basically, a genetic regulatory network corresponds to the interaction of a group of genes and gene products of a cell or a group of cells, that origin diverse cellular functions such as morphogenesis, metabolism, etc. The discrete modeling of genetic regulatory networks was introduced by Kauffman more than thirty years ago (Kauffman, 1969, 1973, 1993). The central hypothesis is that the acquision of a specific cellular state (mobility, differentiation, proliferation, change of shape, metabolic adaptation, etc.) is determined by the profile of activation of a group of components that conforms a genetic regulatory network in the cell. This interaction can be mathematically modeled by a Boolean network. A Boolean network can be viewed as a digraph, where the vertices correspond to genes or gene products, while the arcs denote interactions among them. A gene expression level is modeled by binary values, 0 or 1, indicating two transcriptional states, either active or inactive, respectively, and this level changes in time according to some local activation function which depends on the states of a set of nodes (genes). The joint effect of the local activation functions defines a global transition function. Thus, the other element required in the description of the model is an update schedule, which determines when each node has to be updated, and hence, how the local functions combine into the global one (in other words, it must describe the relative timings of the regulatory activities). Since a Boolean network with n vertices has 2n global states, from a starting state, within a finite number of udpates, the network will reach a fixed point or a limit cycle, called attractor. The attractors of a Boolean network are often associated to distinct phenotypes (cellular states) defined by patterns of gene activity. A regulatory Boolean network (REBN) is a Boolean network where each interaction between the elements of the network corresponds either to a positive or to a negative interaction. Thus, the interaction digraph associated to a REBN is a signed digraph where a circuit is called positive (negative) if the number of its negative arcs is even (odd). In this context, there are diverse studies about the importance of the positive and negative circuits in the dynamical behavior of non-linear systems in Biology (Demongeot, 1998; Demongeot et al., 2000; Kauffman, 1973; Thomas and D’Ari, 1990). In fact, one has demonstrated that the positive circuits are necessary for the multistationarity (Plahte et al., 1995; Snoussi, 1998; Gouz´e, 1998; Cinquin and Demongeot, 2002; Soul´e, 2003; Richard and Comet, 2007; Richard, 2009), whose biological meaning can be differentiation and memory, and the negative circuits are a necessary condition for the existence of stable regularities what in biology represents the homeostasis (Snoussi and Thomas, 1993; Thomas et al., 1995; Demongeot et al., 2000; Aracena et al., 2003). In addition, a simple result between the disjoint positive circuits and the number of stable configurations has been established (Thomas and Richelle, 1988; Thomas and Kaufman, 2001). Indeed the starting point of this thesis is based on a result of Aracena (2001, 2008), saying that the maximum number of fixed points of a REBN depends on a minimum cardinality vertex set whose elements intersects to all the positive cycles (also named a positive feedback vertex set) of the associated signed digraph. On the other hand, in (Sontag et al., 2008) was shown that, as the number of independent negative feedback loops increases, the number of limit cycles of the REBN tends to decrease and its length tends to increase. In other words, the limit cycles in a REBN are related with the minimum cardinality of a negative feedback vertex set. Both decision problems of finding; a positive feedback vertex set and a negative feedback vertex set, of minimum cardinality, where introduced in (Montalva, 2006) as PFVS and NFVS respectively, where begins the study of the complexity of these problems. Besides, PFVS and NFVS can be viewed as variants of the important classical decision problem: Feedback Vertex Set (FVS) for digraphs, which is well-known to be NPcomplete (Karp, 1972) and for which there are many variants (some of them consider weights on the vertices or on the arcs), almost all of them have been proved to be NPcomplete as well. Furthermore, feedback problems are fundamental in combinatorial optimization, having many applications: circuit design, certain scheduling problems and cryptography are some examples. For this reason, they have been extensively studied (see (Festa et al., 1999) for a good survey). In consequence, as the study of complexity of PFVS and NFVS is a key feature in the understanding of REBNs as well as an interesting theoretical problem, this thesis starts deepening in these and other related problems. On the other hand, another important aspect of circuits is their role in the robustness of Boolean networks with respect to different deterministic update schedules. In this context, some of the pioneering works were made by Robert (1986) and Goles (1986). The choice of deterministic update schedules is given by the fact that information processing performed in the living cell has to be extremely robust and therefore requires a quasi deterministic dynamics. Another reason for determinism is the need to model some periodical behaviors; when randomness is introduced, attractors become regions of the phase space, but are no longer exact dynamical cycles. Both stochastic and deterministic models are common in the biological literature, and a frequent strategy is to consider a deterministic dynamics and look at its robustness under small random perturbations. The impact of perturbations of the update schedule on a Boolean network dynamics have been greatly studied (Chaves et al., 2005; Elena et al., 2008; Ben-Amor et al., 2008; Demongeot et al., 2008; Elena, 2009), mainly from a statistical point of view and more recently, also from an analytical point of view (Salinas, 2008; G´omez, 2009). Some analytical works on perturbations of update schedules have been made in a particular class of discrete dynamical networks, called sequential dynamical systems, where the connection digraph is symmetric or equivalently is an undirected graph and the update schedule is sequential. For this class of networks, the team of Hansson, Mortveit and Reidys studied the set of sequential update schedules preserving the whole dynamical behavior of the network (2001), and the set of attractors in a certain class of Cellular Automata (2005). In (Salinas, 2008) were defined equivalence classes of deterministic update schedules in Boolean networks according to the labeled digraph associated to the network (update digraph) and whose labels on the arcs are defined as follows: an arc (u, v) is said to be positive if the state of vertex u is updated at the same time or after than v, and negative otherwise. Hence, a cycle in the labeled digraph is called positive (negative) if all its arcs are positive (negative). This leaves in evidence that talk of “positive” and “negative” has different meanings depending on the contex: signed digraphs or labeled digraphs. Besides, in (Salinas, 2008; Aracena et al., 2009) was proven that two update schedules in the same class yield exactly the same dynamical behavior. Motivated by this result, we study, from a mathematical point of view, the update digraphs and the number and size of these equivalence classes associated to it. All this, in order to get an idea of the possible different dynamics of networks according to the update schedule used. Such a study represents the core of this thesis. In general terms, we found out that these concepts are closely related to the feedback arc sets of the connection digraph associated to the network. These relations were reflected in combinatorial and structural aspects relating the schedule classes of update digraphs with the feedback arc sets of their connection digraphs. In summary, we will see in this thesis relationships between feedback sets, as above mentioned, and the dynamics of Boolean networks through the analytical study of two fundamental mathematical objects: the signed (connection) digraph and the update digraph. | ||
| Thesis Director(s) | Julio Aracena, Jacques Demongeot | |
| Thesis Project Approval Date | 2008, March 31 | |
| Thesis Defense Date | 2011, August 18 | |
| Professional Monitoring | ||
| PDF Thesis | Download Thesis PDF  | |
ISI Publications from the ThesisJulio ARACENA, Eric FANCHON, Marco MONTALVA, Mathilde NOUAL: Combinatorics on update digraphs in Boolean networks. Discrete Applied Mathematics, vol. 159, 6, pp. 401–409, (2011). |
||
<< Back to list of Graduate Thesis.