Master d'Informatique - Systèmes Complexes

Ces cinquante dernières années ont  été les témoins d'avancées majeures en médecine et en biologie. Se fondant sur le constat que la compréhension de la régulation génétique devait nécessairement passer par une formalisation mathématique afin de dépasser la connaissance observationnelle, les travaux de de René Thomas [1, 2] ont marqué un virage important dans le domaine de la biologie théorique. En particulier, ils ont placé les mathématiques discrètes et l'informatique théorique au centre des recherches sur cette thématique. C'est dans ce cadre interdisciplinaire fortement ancr e en informatique théorique que se place ce stage de Master 2 Recherche. Plus précisément, ce stage se situe dans la lignée des récentes  etudes des propriétés dynamiques des réseaux booléens [3, 4, 5, 6, 7, 8, 9], lorsque ceux-ci sont modélisées par des réseaux d'automates booléens.

L'un des défis scientifiques actuels dans le domaine des systèmes biologiques modélisés par réseaux d'automates booléens est celui du passage à la "réalité structurelle". Les topologies diffèrent d'un système à un autre. Les systèmes inter-cellulaires sont naturellement plongés dans des grilles 3D, tandis que des travaux récents [10], étayés par des études statistiques, ont avancé des arguments en faveur de structures de type "petit-monde" dans les réseaux de régulation génétique (au niveau intra-cellulaire).  A ce jour, aucun résultat n'est connu sur le comportement des réseaux à structure irrégulière. Une des difficultés réside dans la modélisation de ces topologies particulières.

Ce stage propose d'étudier la dynamique et la complexité des réseaux d'automates booléens. Plusieurs approches sont possibles. Une premiére approche théorique consisterait  à rechercher un modèle traitable de réseaux "petit-monde" et d'en caractériser le comportement pour certains automates simples pour commencer (le graphe aléatoire de Watts et Strogatz [11] pourrait être un bon candidat). Une autre approche serait de mener des simulations intensives et raisonnées afin d' etablir une carte des différences entre la dynamique sur ces topologies et sur les topologies régulières de type grille (vitesse de convergence, bassin d'attraction. . . ). Ces deux approches sont bien sûr complémentaires. Par ailleurs, notons que même sur les graphes très réguliers, la dynamique des réseaux booléens reste largement incomprise. Ainsi, une troisième approche pourrait être d' etendre les résultats existant sur les grilles afin d'affiner les connaissances qu'on en a.

L'objectif du stage proposé est par conséquent d'extraire des réseaux d'automates booléens des propriétés caractéristiques de leur dynamique. Pour ce faire, il conviendra de développer des outils (théoriques et/ou simulations) adaptés à l'étude des propriétés de : dynamique (attracteurs, vitesse de convergence...), complexité (structure des bassins d'attraction selon l'automate, sa puissance et son réseau sous-jacent), robustesse (face à des perturbations des modes de mises à jour).

• Le stage pourra se dérouler sur l'un des trois sites de rattachement des encadrants selon les préférences de l'étudiant, à savoir le LIAFA à Paris, l'IBISC à Evry ou encore l'IXXI à Lyon.
• 
  
• Une indemnité de stage à hauteur de 417 euros mensuels est prévue.
• 
  
• Une pousuite en thèse est envisageable.
• 
  

[1] Thomas, R. : Boolean formalisation of genetic control circuits. Journal of Theoretical Biology 42 (1973) 563-585.
[2] Thomas, R. : On the relation between the logical structure of systems and their ability to generate multiple steady states and sustained oscillations. Springer Series in Synergetics 9 (1981) 180-193.
[3] Sené S. : Influence des conditions de bord dans les réseaux d'automates booléens à seuil et application à la biologie. Thèse de doctorat de l'université Joseph Fourier, Grenoble 1 (2008).
[4] Regnault, D. : Sur les automates cellulaires probabilistes : comportements asynchrones. Thèse de doctorat de l'Ecole Normale Supérieure de Lyon (2008).
[5] Richard, A. : Positive circuits and maximal number of fixed points in discrete dynamical systems. Discrete Applied Mathematics 157 (2009) 3281-3288.
[6] Schabanel, N. : Systèmes complexes & algorithmes. Habilitation à diriger des recherches de l'université Denis Diderot, Paris 7 (2010).
[7] Demongeot, J., Noual, M., Sené, S. : On the number of attractors of positive and negative Boolean automata circuits. In : WAINA'10, IEEE Press (2010) 782-789.
[8] Regnault, D., Schabanel, N., Thierry, E. : On the analysis of "simple" 2D stochastic cellular automata. Discrete Mathematics and Theoretical Computer Science 12 (2010) 263-294.
[9] Demongeot, J., Noual, M., Sené, S. : Combinatorics of Boolean automata circuits dynamics. Submitted to Discrete Applied Mathematics.
[10] Barabási, A.L., Oltvai, Z.N. : Network biology : understanding the cell's functional organization. Nature Reviews Genetics 5 (2004) 101-113.
[11] Watts, D.J., Strogatz, S.H. : Collective dynamics of "small-world" networks. Nature 393 (1998) 440-442.