Study of the block-sequential operator on Boolean networks. Application to discrete network analysis.

Abstract

A Boolean network is a system of n interacting Boolean variables, which evolve, in a discrete time, according to a regulation rule and to a predefined updating scheme. They have applications in many areas, including circuit theory, computer science, social networks and biological systems. The structure of such a network is often represented by a digraph, called interaction digraph, where vertices are network components, and where there is an arc from one component to another when the evolution of the latter depends on the evolution of the former. The relationship between the structure of a regulatory network and its dynamical behavior is crucial to understand for instance how and why biological networks have evolved. Further, this relationship can be used to construct networks with desirable dynamical properties. In the original scheme of a Boolean network all the nodes are synchronously updated at each time step (this scheme is also called parallel schedule). A more general scheme, introduced in [67], is to consider that the set of network nodes is partitioned into blocks and that the nodes in a block are updated simultaneously. Differences in the dynamical behaviors of Boolean networks with different update schedules has been studied mainly from an experimental and statistical point of view. In this tesis, the variations of the interaction digraph of a Boolean network with respect to changes in the update schedule and its relation with some dynamical properties of the network are studied. In order to achieve this goal, three main topics are discussed. First, the variations in the parallel digraph of some structural characteristics (number of strongly connect components, transversal number, packing number) with respect to changes in the update schedule are analyzed. Second, an algorithm is constructed to find the fixed points of a Boolean network taking advantage of knowledge about the upper bound of the fixed points of a network, in this case we use the positive transversal number. Finally, a new, so far unexplored problem is defined, which states that given a Boolean network f, find a Boolean network h and an update schedule s that are dynamically equivalent to f. In this sense, several variations of the original problem are presented, many of which can be solved in polynomial time.