Task 2 summary

Task 2: Introduce chronology in static models: Graphs and constraints based approaches


A. Siegel (Coordinator), J. Nicolas, T. Schaub, A. Maass, I. Rusu, D. Eveillard, G. Fertin, P. Bordron, A. Paulevé, H. Mohamed-Babou, F. Fages, S. Soliman, A. Richard, J. Bourdon.


Nowadays, every biological labs have access to high throughput data (denoted here as *omic data), yielding observations on the whole cellular components. Such datasets can be classified into two categories. The first class of data informs about the structure of interactions between products. As an example, genetic interaction networks are obtained by matching genome maps and protein-protein interaction information. Resulting networks are often too numerous and the selection of an appropriate network must be performed manually. The second class of data addresses a behavioural and functional study of the living system. This class contains transcriptome data, metabolic maps and every comparative data (comparison between a normal situation and a stress situation). Such large scale data provide a rich description of the system. Nevertheless, they remain partially explored though could probably offer even more functional insights (dynamic). To that purpose, we will represent structural information by graphs, and these graphs will be matched with functionality information in order to extract some networks of interest. If we reformulate this question with the viewpoint of time, structural information informs about the topology of the network, that is, a static model, whereas functional information informs about the dynamics and the chronology of events in the model, that is, the asymptotic behaviour of the model. Therefore, the problem we are addressing can be reformulated as introducing chronology in static models. From a computational point of view, we propose to use several approaches to perform the confrontation between topological and functional information. (a) Graph theory (comparison, alignment, decomposition) is required to match genome map with metabolic and regulatory pathways. (b) Automatic reasoning is required to match regulatory pathways with variation or lethality data. Both these theoretical questions require new research in computer science: currently available methods on graphs are not appropriate to handle the notion of distance and orientation. Reasoning over propagation of influences into networks also requires efficient constraints-based approaches. We propose to gain into efficiency by using Answer Set programming approaches (Gebser'07) to handle this new range of complexity.


The goal of this task is to develop both new algorithms (based on graph theory) and constrained-based approaches to address the integration of dynamical-nature data in the process of regulatory networks construction. Constrained-based approaches will be used mainly in model construction and correction with the help of dynamical omic data (mainly transcriptome data), while algorithms on graphs are needed to take into account the (dynamical) information contained in other networks (metabolic networks or genome maps).

Targeted applications



Long-stay collaborations