INESC-ID   Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
technology from seed


Knowledge Discovery and Bioinformatics
Inesc-ID Lisboa

Identification and quantification of reachable attractors over asynchronous discrete dynamics

12/19/2014 - 14:30
12/19/2014 - 15:30

Models of discrete concurrent systems often lead to huge and complex
state transition graphs that represent their dynamics.
Here, we are particularly interested in logical models of biological
regulatory networks. Given an initial condition, it is of real interest
to identify reachable attractors that denote the potential asymptotical
behaviours of the system. These attractors are described as terminal
strongly connected components, that are either single (stable) states or
sets of states (denoting cyclical behaviours).

Beyond attractor identification, we propose to assess the probability to
reach each of them from an initial condition or from any portion of the
state space, relying on the structure of the state transition graph.
First, we present a solution to the problem with an original algorithm
called FIREFRONT, based on the exhaustive exploration of the reachable
state space. Then, for the cases where FIREFRONT is not applicable, we
define a modified Monte Carlo simulation, termed AVATAR.