Workshop sur la

Théorie des réseaux booléens
et ses applications en biologie


Hotel Saint-Paul, Nice – du 4 au 7 novembre 2014


Presentation Programme Participants Photos Accès























Présentation

La modélisation et l'étude des réseaux booléens est un domaine qui reste en plein essor pour la modélisation dans différentes sciences, en particulier en biologie moléculaire. Le plus souvent, la complexité des systèmes vivants étudiés nécessite une première étape de simplification qui consiste à isoler un sous-système discret dont on veut dans un second temps étudier l'ensemble des comportements. Naturellement, dans ce cadre, on fait appel à des systèmes dynamiques discrets, qui permettent de modéliser le comportement de systèmes d'entités en interaction, communément appelés réseaux booléens lorsque l'état de chaque entité ne peut prendre que deux valeurs. Les trajectoires des tels réseaux booléens dépendent uniquement du mode opératoire choisi (quelles sont les entités qui évoluent à chaque top d'horloge), de l'architecture des réseaux (pour chaque entité, quelles sont les autres entités qui l'influencent, et selon quelle règle) et de la configuration initiale choisie. Cependant, les réseaux booléens apparaissant en biologie moléculaire ont des propriétés spécifiques qui restreignent leurs dynamiques et qu'il convient de caractériser précisément. Le but de ce groupe de travail est de partager les dernières avancées de la théorie des réseaux booléens et de l’étude de leurs trajectoires ainsi que de discuter ce que ces avancées apportent au domaine de la biologie.

Organisateurs: Jean-Paul Comet, Elisabeth Remy, Adrien Richard, Sylvain Sené, Anne Siegel.


Programme

Mardi 4 Mercredi 5 Jeudi 6 Vendredi 7
        
9h30 - 10h45 S. Sené M. Gadouleau A. Siegel E. Formenti
Pause
11h15 - 12h30 J. Demongeot E. Goles J. Aracena A. Richard
Déjeuner
14h00 - 15h15 J.-F. Couchot D. Regnault E. Fanchon
Pause
15h30 - 16h45 K. Perrot L. Paulevé P.-A. Scribot
Pause
17h00 - 18h15 E. Remy J.-P. Comet S. Contassot-Vivier


Mardi 4

Sylvain Sené   (9h30 - 10h45)

Réseaux d'automates comme modèles de réseaux de régulation : un retour aux fondamentaux

L'informatique et la biologie sont intimement liées depuis les années 1940 à travers le terme de modèle, avec "modèle de calcul" d'un côté et "modèle représentationnel" de l'autre. Historiquement, le premier modèle fondamental qui tint une place clé à l'interface de ces deux disciplines fut celui des réseaux d'automates, et plus précisément des réseaux d'automates booléens. La raison à cela vient de leur simplicité de définition, de leur niveau d'abstraction élevé leur donnant d'importantes capacités de modélisation, et de leur disposition à capturer pertinemment la plupart des complexités et des hétérogénéités des systèmes réels. Cette présentation délivrera un point de vue sur les interconnexions entre l'informatique et la biologie, principalement dans le contexte des régulations génétiques. Cela se fera à travers un panorama des réseaux d'automates booléens, en expliquant pourquoi leur étude per se est importante pour aller plus loin dans la compréhension de certaines des lois générales qui gouvernent le vivant (sous réserve qu'elles existent).

SLIDES




Jacques Demongeot   (11h15 - 12h30)

Robustesse et Criticalité dans les réseaux de gènes

On présente des résultats récents sur la robustesse de réseaux Booléens de type Hopfield, fondés sur la notion de frustration des liens du réseau. On définit ensuite la notion de gènes et interactions critiques, c’est-à-dire susceptibles, lorsqu’ils sont absents ou changent de valeurs, de modifier considérablement le paysage des attracteurs du réseau (nombre, nature et/ou taille de bassins). Ces résultats théoriques seront mis en œuvre dans des applications biomédicales. Les réseaux applicatifs utilisés seront le réseau de contrôle de la morphogenèse des voies biliaires, étudié dans le cas d’une pathologie familiale appelée l’atrésie biliaire, ainsi que le réseau de contrôle de la morphogenèse de l’acrosome du spermatozoïde, étudié dans le cas d’infertilités masculines familiales.

Références :

  1. J. Demongeot, H. Ben Amor, H. Hazgui & J. Waku. Robustness in Neural and Genetic Regulatory Networks: Mathematical Approach and Biological Applications. Acta Biotheoretica, 62 (2014).
  2. S. Bandiera, R. Matégot, J. Demongeot & A. Henrion-Caude. MitomiRs: delineating the intracellular localization of microRNAs at mitochondria. Free Radical in Biology and Medicine, 64 (2013).
  3. J. Demongeot, H. Hazgui , S. Bandiera, O. Cohen & A. Henrion-Caude. MitomiRs, ChloromiRs and general modelling of the microRNA inhibition. Acta Biotheoretica, 61 (2013).
  4. C. Antonopoulos, V. Basios, J. Demongeot, P. Nardone & R. Thomas. Linear and nonlinear arabesques: a study of closed chains of negative 2-element circuits. Int. J. Bifurcation and Chaos, 23 (2013).




Jean-François Couchot   (14h00 - 15h15)

Traversing a n-cube without Balanced Hamiltonian Cycle to Generate Pseudorandom Numbers

This work presents a new class of Pseudorandom Number Generators. The generators are based on traversing a n-cube where a Balanced Hamiltonian Cycle has been removed. The construction of such generators is automatic for small number of bits, but remains an open problem when this number becomes large. A running example is used throughout the paper. Finally, first statistical experiments of these generators are presented, they show how efficient and promising the proposed approach seems.

Plus d'infos ici.

SLIDES




Kevin Perrot   (15h30 - 16h45)

Une technique pour démontrer l'émergence de régularités

Cette technique a été appliquée aux piles de sable (et en fait découverte sur ces modèles, où des grains s'éboulent selon des règles locales), et demande à être généralisée. Par une association d'arguments d'algèbre linéaire et de combinatoire, elle nous a permis de prouver formellement l'émergence de structures régulières dans ces réseaux d'interactions, sans nécessiter une compréhension fine de toute la dynamique.

SLIDES




Elisabeth Remy   (17h00 - 18h15)

Identification des attracteurs et estimation de leur atteignabilité
dans une dynamique asynchrone discrète

Les graphes de transitions d’états asynchrones, qui représentent l’évolution d’un système dynamique discret, atteignent des tailles telles qu’il nous est impossible de les explorer, rendant ainsi leur analyse très difficile. Dans le cadre des réseaux de régulation biologique en particulier, l'identification des attracteurs et leur atteignabilité étant donné un état initial (c’est à dire les comportements asymptotiques possibles du système étudié) sont des informations cruciales. Nous proposons ici deux méthodes qui, étant donné un ensemble d’états initiaux, permettent d’une part d’identifier les attracteurs atteignables, et de « quantifier » leur atteignabilité. La première (FIREFRONT) est une méthode quasi-exacte; la seconde, AVATAR, est une méthode de Monte-Carlo adaptée. Nous verrons ensuite, à travers la présentation d’un modèle logique de la progression du cancer de la vessie, que ces méthodes complètent une série d’outils déjà classiquement utilisés pour analyser la dynamique de réseaux de régulations Booléens (réduction, analyse de circuits…).

SLIDES



Mercredi 5

Maximilien Gadouleau   (9h30 - 10h45)

Points fixes des réseaux Booléens et théorie des codes

Nous nous intéressons au nombre maximal de points fixes d'un réseau Booléen étant donné son graphe d'interaction signé. Pour ce faire, nous utilisons des techniques provenant des codes correcteurs d'erreurs et du codage réseau. Nous obtenons ainsi de bien meilleures bornes inf et sup sur le nombre maximal de points fixes. Aussi, nous découvrons que le nombre de points fixes ne croît pas forcément avec le nombre de cycles positifs.

Travail en collaboration avec Adrien Richard et Søren Riis: http://arxiv.org/abs/1409.6144

SLIDES




Eric Goles   (11h15 - 12h30)

Threshold networks over undirected graphs :
dynamics and complexity under block-sequential iterations.

We will study the structure of attractors (cycles and fixed points) of threshold networks over an undirected graph for any block-sequential updating scheme. For that we will associate to the graph defining the network and index such that its signs characterize the convergence to fixed points or cycles. Further, depending of the updating scheme, exponential cycles may appear


SLIDES



Damien Regnault   (14h00 - 15h15)

Titre: TBA

Résumé: TBA




Loïc Paulevé   (15h30 - 16h45)

Abstractions de la causalité dans les réseaux d'automates non-déterministes

Dans cet exposé, je donnerai les bases d'une interprétation abstraite de la causalité pour différentes classes de réseaux d'automates spécifiés par des transitions (à la réseaux de Petri) - généraux, asynchrones, asynchrones avec restriction sur la cardinalité des pré-conditions. Ces abstractions exploitent la concurrence au sein des réseaux et permettent d'obtenir des représentations compactes, non redondantes, mais approchées, de l'ensemble des comportements possibles, en particulier sous la forme de Graphes de Causalité Locale (GCL). Je montrerai alors des conditions nécessaires ou suffisantes sur ces GCL pour la satisfiabilité de propriétés d'accessibilités (étant donné un état global du réseau, il existe une suite de transitions permettant d'atteindre un état local donné d'un automate donné) rendant possible l'analyse à très grande échelle de la dynamique des réseaux d'automates. J'illustrerai ces résultats avec des applications sur des réseaux biologiques composés de centaines et de milliers de composants pour la vérification de propriétés d'accessibilité, et l'identification de mutations permettant le contrôle de ces propriétés. Enfin, je conclurai avec plusieurs travaux récents et en cours, notamment pour la réduction de modèles, le calcul d'attracteurs, et les perspectives pour une théorie de la causalité et de la concurrence applicable aux très grands réseaux.

Plus d'infos:

SLIDES




Jean-Paul Comet   (17h00 - 18h15)

Plasticité des réseaux de neurones: Un modèle de Réseaux Booléens avec règle de Hebb

Dans cet exposé, nous présentons un modèle de réseaux de neurones avec règle de Hebb ainsi que les résultats obtenus par Shih et Tsai pour la dynamique asynchrone. La règle de Hebb permet de représenter une certaine plasticité synaptique : l'efficacité synaptique augmente lors d'une stimulation présynaptique répétée et persistante. Ainsi lorsque deux neurones sont excités conjointement, il se crée (ou se renforce) un lien les unissant. Dans le cadre considéré, toute trajectoire asynchrone et équitable converge. Ces résultats ouvrent la porte à d'autres questions portant sur l'apport de la règle de Hebb. On peut par exemple se demander si la règle de Hebb aide ou accèlère la stabilisation.

Références:

  1. E. Goles, J. Olivos, Periodic behaviour of generalized threshold functions, Discr. Math. 30 :187-189, 1980.
  2. F.Robert. Les systèmes dynamiques discrets, volume 19 of Mathematiques et Applications. Springer, 1995
  3. M.-H. Shih, F.-S. Tsai, Growth dynamics of cell assemblies, SIAM J. Appl. Math., 69(4) :1110-1161, 2009.

SLIDES



Jeudi 6

Anne Siegel   (9h30 - 10h45)

Méthodes de programmation logique (ASP) pour apprendre
et contrôler la réponse de réseaux de signalisation

Les modèles logiques s'avèrent propices pour comprendre et étudier la dynamique de réseaux de signalisation ou de régulation. Cependant, l'apprentissage des règles logiques décrivant la dynamique d'un réseau à partir de données expérimentale reste une tâche difficile. Cette tâche est souvent abordée en résolvant un problème d'optimisation linéaire qui cherche minimiser la distance entre les réponses du modèle booléen et les observations, tout en respectant un principe de parcimonie sur le choix des règles booléennes à inclure dans le modèle. En s'appuyant sur des paradigmes de programmation logique, nous discuterons de l'impact du bruit présent dans les données sur les solutions à ce problème d'identification. Cela permettra de proposer des méthodes robustes pour identifier des contrôleurs du système en présence de bruit dans les données, ainsi que des expérimentations pour réduire la variabilité.

SLIDES




Julio Aracena   (11h15 - 12h30)

Limit cycles and update schedules in Boolean networks: Robustness and Inverse Problem.

The dynamical behavior of a Boolean network, and in particular the set of limit cycles, is very sensitive against changes in the update schedule. In this talk we will present some theoretical results about two problems concerning the deterministic update schedules (parallel, sequential and block-sequential) and the limit cycles of a Boolean network: The first one is about the existence of update schedules yielding a same limit cycle (Robustness) and the second one about the inference of an update schedule from an observed limit cycle (Inverse Problem). We will show how the interaction digraph and the type of local activation functions of a Boolean network are related to the solutions of both problems.

SLIDES




Eric Fanchon   (14h00 - 15h15)

Quelques réflexions sur les réseaux de Thomas

Le formalisme de René Thomas est très utilisé en biologie, en particulier pour décrire la dynamique de réseaux de régulation génétique. Les règles de transition entre états (dits 'réguliers') procèdent d'une abstraction de systèmes différentiels linéaires par morceaux (avec une partition de l'espace des états en domaines rectangulaires, et une matrice diagonale dans chaque domaine de la partition) [1]. Une extension du formalisme de Thomas a été présentée en 2004 [2], dans laquelle des transitions entre états dits 'singuliers' (correspondant à des frontières entre domaines) sont prises en compte. Ce formalisme étendu est mathématiquement plus rigoureux mais computationnellement beaucoup plus lourd. En pratique le formalisme de Thomas reste très utilisé. Il est en effet souvent dit que les états singuliers n'apportent rien de qualitativement significatif dans les applications. Ceci n'est jusqu'à présent qu'une hypothèse de travail dont nous voulons ici évaluer le bien-fondé.

Plus précisément deux problèmes seront abordés : (i) identification des valeurs de paramètres (analogues discrets des paramètres cinétiques) pour lesquels il existe au moins un chemin C dans le graphe de transition incluant les états singuliers tel qu'aucun chemin régulier n'est voisin de C; (ii) identification des valeurs de paramètres, s'il en existe, pour lesquels l'ensemble des états atteignables depuis un état donné est différent dans les deux formalismes (Thomas vs Thomas étendu). Nous nous focaliserons sur les systèmes à 3 dimensions et présenterons notre approche basée sur une décomposition du problème en instances SAT (satisfiabilité booléenne).

Références :

  1. E. H. Snoussi, Dyn. Stab. Sys. 4, 189 (1989); E. H. Snoussi and R. Thomas, Bull. Math. Biol. 55, 973 (1993); R. Thomas & M. Kaufman, Chaos, 11, 180 (2001).
  2. H. de Jong et al, Bull. Math. Biol., 66, 301 (2004).

SLIDES - Partie 1
SLIDES - Partie 2




Pierre-Alain Scribot   (15h30 - 16h45)

Réseaux d'automates additifs

Les réseaux d'automates booléens peuvent être vus comme cas particuliers des réseaux d'automates à alphabet fini. En vue de comprendre l'impact de la non-monotonie sur la dynamique, il est naturel de commencer par étudier les réseaux additifs, dont le cas booléen correspond aux réseaux xor. Je présenterai dans cet exposé comment l'approche algébrique permet de décrire la dynamique synchrone dans le cas où l'alphabet est un corps.




Sylvain Contassot-Vivier   (17h00 - 18h15)

Titre: TBA

Resumé: TBA



Vendredi 7

Enrico Formenti   (9h30 - 10h45)

Complexity of the dynamics of general discrete dynamical systems

In this talk we discuss a general framework for studying the computational complexity of (finite) discrete dynamical systems. The technique will allow to find upper-bounds for the complexity of many natural decision problems such as the existence of a fixed point, of a fixed point attractor, of two disjoint attractors, and similar.




Adrien Richard   (11h15 - 12h30)

Points fixes dans les réseaux conjonctifs

On s'intéresse à la question suivante: Etant donné un graphe dirigé, comment attribuer un signe positif ou négatif sur les arcs du graphe afin que le réseau conjonctif résultant ai le plus grand nombre de points fixes possible? Cette question vise indirectement à mieux comprendre l'influence des cycles positifs et négatifs sur le nombre de points fixes. Nous présenterons une réponse partielle surprenante: Pour un graphe non dirigé sans cycle de longueur 4, on maximise le nombre de points fixes en n'attribuant que des signes négatifs.

C'est un travail en collaboration avec Julio Aracena et Lilian Salinas dans la continuité de l'aticle suivant: J. Aracena, A. Richard, L. Salinas. Maximum number of fixed points in AND-OR-NOT networks. Journal of Computer and System Sciences, 80(7):1175-1190, 2014. (PDF)

SLIDES



Participants
  1. J. Aracena
  2. G. Bernot
  3. J.-P. Comet
  4. S. Contassot-Vivier
  5. J.-F. Couchot
  6. J. Demongeot
  7. E. Fanchon
  8. E. Formenti
  9. M. Gadouleau
  10. E. Goles
  11. E. Jeandel
  12. T. Melliti
  13. L. Paulevé
  14. K. Perrot
  15. D. Regnault
  16. E. Remy
  17. A. Richard
  18. P.-A. Scribot
  19. S. Sené
  20. A. Siegel


Photos














Accès

Le workshop se déroule à L'hôtel Saint Paul, 29 boulevard Franck Pilatte, 06300 Nice. Cet hôtel se situe dans le quartier du port de Nice, à 20 minutes de marche du centre-ville et de la vieille ville.


(cliquer sur la carte pour l'agrandir)


Pour s'y rendre DEPUIS L'AEROPORT il faut prendre le bus 98 direction Centre Ville et descendre à l'arrêt Le port. Il faut ensuite marcher 15 minutes environ pour rejoindre l'hôtel, en suivant le trajet de la carte ci-dessous.


(cliquer sur la carte pour l'agrandir)


Pour s'y rendre DEPUIS LA GARE SNCF il y a deux solutions:

  1. Prendre le bus 30 direction Riquier et descendre à l'arrêt La Réserve, juste en face de l'hôtel. Attention: Le bus à une fréquence faible (25 minutes environ) et le dernier bus part à 19h10.


    (cliquer sur la carte pour l'agrandir)


  2. Prendre le Tramway 1 direction Hôpital Pasteur et descendre à l'arrêt Garibaldi. Il faut ensuite marcher 20 min environ pour rejoindre l'hôtel, en suivant le trajet ci-dessous.


    (cliquer sur la carte pour l'agrandir)