La prédiction de la dynamique d’un réseau d’automates

Modules

La prédiction de la dynamique d’un réseau d’automates est un problème difficile, de par le fait que cette dynamique est exponentielle en la taille du réseau. Une des approches pour contourner ce problème est de diviser le réseau étudié en plusieurs sous-réseaux, dans l’espoir que la prédiction des éléments séparés permettent la prédiction de l’ensemble. Cette approche modulaire n’est pas nouvelle et a été explorée de plusieurs façons dans la littérature. Certains travaux (MILO, SHEN-ORR, ITZKOVITZ et al. 2002; U. ALON 2003) ont rassemblés des réseaux d’influences tirés de la biologie, de la biochimie, de l’écologie et de l’ingénierie et étudient la réccurence de motifs, c’est-à-dire des sous-graphes spécifiques dont la présence est anormalement haute dans ces réseaux naturels comparés à des réseaux générés aléatoirement. D’autres travaux  étudient des formalismes qui permettent la définition de sous-réseaux dans un réseau d’automate, avec l’objectif de comprendre la dynamique d’un réseau plus large à partir de l’étude de parties de ce réseau. Ces travaux développent également des méthodes qui permettent cette division en parties d’une façon efficace et pertinente. Un travail récent (ALKHUDHAYR et STEGGLES 2019) introduit une notion de composition de réseau d’automates booléens qui repose sur la fusion de deux automates. La fonction locale de l’automate obtenu par cette fusion est définie comme la composition par un opérateur booléen des fonctions locales des automates fusionnés. Notre approche peut être rapprochée de travaux dans le cadre non discret des réseaux de réactions (BAEZ et POLLARD 2017), où des entrées sont rajoutées à ces systèmes qui modélisent des réactions chimiques par l’emploi de réseaux de Petri ouverts. Dans le cadre des réseaux d’automates, notre formalisme diffère des précédents par le fait qu’il ne vise pas à décrire la nature d’un sous-réseau, mais bien la possibilité de tout réseau d’être influencé par un réseau extérieur par le biais d’entrées que nous rajoutons au modèle. Ainsi, la propriété de faire partie d’un réseau plus large peut être comprise comme la réduction de l’évolution de ces entrées. Nous appellons ces réseaux disposant d’entrées les modules. Ce chapitre présente les définitions associées aux modules en section 5.2, et présente un ensemble de résultats les concernant en section 5.3. 79 M

Définitions 

Entrées, fonctions locales, modules et graphe d’interaction 

Les modules sont une généralisation des réseaux d’automates. En ces termes, la plupart des définitions développées pour les réseaux d’automates s’appliquent également aux modules. Ainsi, si un réseau d’automates est défini avec un ensemble d’automates S ainsi qu’un ensemble d’états Λ, un module a également un ensemble d’entrées, que nous appellons par convention I . Par convention de nouveau, les entrées contenues dans cet ensemble sont désignées par des lettres grecques, en commencant par α. Les entrées d’un module représentent des influences extérieures, qui possèdent une valeur dans Λ à tout instant, et qui peuvent influencer les fonctions locales du module. Pour pouvoir définir cette influence, il est nécessaire de définir un état pour ces entrées. Cela est fait par le biais d’une configuration d’entrée. Définition 43 (Configuration d’entrée). Soit I un ensemble d’entrées et Λ un ensemble d’états. Une configuration d’entrée est un vecteur défini sur Λ I . Par convention, nous noterons les configurations d’entrée par la lettre i. Concaténer une configuration d’entrée i avec une configuration standard x nous donne un vecteur x · i défini sur Λ S∪I . Ce vecteur contient toute l’information nécessaire pour mettre à jour les fonctions locales du module. Ainsi, nous pouvons désormais développer la définition des fonctions locales des modules. Définition 44 (Fonction locale d’un module). Soit S un ensemble d’automates, I un ensemble d’entrées et Λ un ensemble d’états. Une fonction locale d’un module est une fonction f définie sur Λ S∪I → Λ. Nous pouvons à présent définir un module par une définition similaire à celle d’un réseau d’automates. Définition 45 (Module). Soit S un ensemble d’automates, I un ensemble d’entrées et Λ un ensemble d’états. Un module associe à tout s ∈ S une fonction locale fs : Λ S∪I → Λ. En ces termes, les entrées d’un module se comportent comme des automates dans le sens où leur valeur est définie dans une configuration et utilisée pour influencer les automates du réseau. Cependant, les entrées diffèrent des automates dans le fait qu’elles ne possèdent pas elles-mêmes de fonctions locales. Les entrées sont conçues comme une influence extérieure au réseau, et leur valeur est arbitrairement définie à tout instant. Exemple 38. Soit S = {a,b,c}, I = {α} et Λ = {0,1}. Soit M le module qui à a, b et c associe les fonctions suivantes : fa(x · i) = ¬xa ∧ iα, fb(x · i) = xa ∨ xc , et fc (x · i) = (¬xa ∧ ¬xc )∨iα. 80 5 Modules – 5.2 Définitions a b c α α FIGURE 5.1 – Graphe d’interaction du module développé dans l’exemple 38. L’influence qu’une entrée porte sur un automate se définit de façon similaire à l’influence entre deux automates. Définition 46 (Influence d’une entrée). Soit M un module, α une entrée de I et s un automate de M. On dit que α influence s si et seulement s’il existe une configuration x et une paire de configurations d’entrée i et i 0 telles que iβ = i 0 β ⇐⇒ β 6= α, et fs(x ·i) 6= fs(x ·i 0 ). Tout comme les réseaux d’automates, les modules sont propices à la représentation sous la forme d’un graphe. Le graphe d’interaction d’un module se définit de façon pratiquement équivalente au graphe d’interaction d’un réseau d’automates, à l’ajout prêt de flèches qui représentent l’influence des entrées du module sur les automates. Définition 47 (Graphe d’interaction de module). Soit M un module. On définit le graphe d’interaction de M comme le graphe orienté qui est défini sur les sommets de S, qui possède une arête de s vers r si et seulement si s influence r . De plus, chaque sommet s est décoré d’une flêche entrante annotée α pour chaque entrée α qui influence s. L’exemple 38 est représenté sous la forme d’un graphe d’interaction dans la figure 5.1. 

Mises à jour, exécutions et graphe de la dynamique

 Pour x une configuration et i une configuration d’entrée, un module M peut être mis à jour de la même façon qu’un réseau d’automates; par le biais d’une sélection de fonctions locales de M qui s’appliquent simultanément pour altérer la configuration x. Cette sélection est représentée par une mise à jour δ, dont la définition ne change pas; il s’agit toujours d’un sous-ensemble de S. La définition de l’application d’une telle mise à jour sur un module est intuitive. Définition 48 (Application de mise à jour sur un module). Soit M un réseau d’automates, x une configuration, i une configuration d’entrée et δ une mise à jour. L’application de la mise à jour δ sur les configurations x et i dans M est une nouvelle configuration notée Mδ(x ·i), qui est définie par : 81 5 Modules – 5.2 Définitions ∀s ∈ S,Mδ(x ·i)s = ½ fs(x ·i) si s ∈ δ xs sinon . Exemple 39. Considérons le module M développé dans l’exemple 38, ainsi que trois mises à jour δ1 = {a}, δ2 = {b,c} et S. Nous observons les faits suivants : Mδ1 (000 · 0) = 000 Mδ2 (000 · 0) = 001 MS(000 · 0) = 001 Mδ1 (101 · 1) = 001 Mδ2 (101 · 1) = 011 MS(101 · 1) = 011 On note que l’application d’une mise à jour sur un module ne génère pas une nouvelle configuration pour les entrées de ce module. Les configurations d’entrée sont considérées indépendantes du fonctionnement interne du module. Cela signifie que sur une séquence de mises à jour, l’affectation d’états aux entrées du module pourra évoluer de façon complètement arbitraire. Pour refléter cette nature arbitraire, nous définissons la notion de séquence d’entrée. Définition 49 (Séquence d’entrée). Soit I un ensemble d’entrée. Une séquence d’entrée est une séquence J = (i1,i2,…) finie ou infinie, où chaque ik est une configuration d’entrée définie sur I. Ainsi, tout ce qui est nécessaire pour mettre à jour un module sur plus d’une mise à jour à la suite, est une configuration initiale x, un mode de mise à jour ∆, et une séquence d’entrée J au moins aussi longue que ∆. Définition 50 (Exécution de module). Soit M un module, x une configuration, ∆ = (δ1,δ2,…) un mode de mise à jour fini et J = (i1,i2,…) une séquence d’entrée au moins aussi longue que ∆. On appelle exécution de M selon ∆ sur x et J la configuration définie par les équations récursives suivantes : M(δ1,δ2,…)(x, (i1,i2,…)) = M(δ2,…)(Mδ1 (x ·i1), (i2,…)) M( )(x,J) = x Exemple 40. Nous considérons M le module développé dans l’exemple 38. Soit ∆1 = ({a}, {b}, {c}), ∆2 = ({b,c}, {a}), et J = (1, 0, 1). Nous observons les faits suivant : M∆P ·∆P ·∆P (000,J) = 101