Groupe d’études et de recherche en analyse des décisions

G-2002-47

Identification of all Steady States in Large Networks by Logical Analysis

, et

Generalized logical analysis aims at modelling complex biological systems, especially the so-called regulatory systems like genetic networks. The main feature of that theory is its capacity to find all steady states of a given system, and the functional positive and negative circuits which generate respectively multistationarity and a cycle in the graph of the sequences of states. So far this has been achieved by exhaustive enumeration, which severely limits the size of the systems which can be analyzed. In this paper, we introduce a mathematical function, called image function, which allows calculating the value of the logical parameter associated to a logical variable depending on the state of the system. So, the state table of the system is represented in an analytical way. We then show how all steady states can be derived as solutions of a system of steady state equations. Constraint programming, a recent method for solving constraint satisfaction problems, is applied for that purpose. To illustrate the potential of our approach we present results from computer experiments carried out on very large randomly generated systems (graphs) with hundreds or even thousands of interacting components and show that these systems can be solved using moderate computing time. Moreover, we illustrate the approach on two published applications. One of them concerns the computation times of all steady states for a large genetic network.

, 30 pages

Ce cahier a été révisé en novembre 2002