# Analyse statique et réduction de modèles pour un langage de réécriture de graphes à sites

Jérôme Feret

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jérôme Feret. Analyse statique et réduction de modèles pour un langage de réécriture de graphes à sites. Informatique [cs]. ENS-PSL, 2023. tel-04326091

HAL Id: tel-04326091

https://inria.hal.science/tel-04326091

Submitted on 13 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Analyse statique et réduction de modèles
pour un langage de réécriture de graphes à sites

Présentation des travaux par

Jérôme FERET

Le 12 décembre 2023

Discipline

Informatique

## Composition du jury :

Élisabeth, REMY
Directrice de recherche, CNRS/I2M
Présidente

Franck, DELAPLACE
Professeur, université d'Évry/Paris-Saclay
Rapporteur

Roberto, GIACOBAZZI
Professeur, The University of Arizona
Rapporteur

Éric, GOUBAULT
Professeur, X/Université Paris-Saclay
Rapporteur

Bernadette, CHARRON-BOST
Directrice de recherche, CNRS/ENS/PSL
Examinatrice

Patrick, COUSOT
Professeur, New York University
Examinateur

Walter, FONTANA
Professeur, Harvard Medical School
Examinateur

Marc, POUZET
Professeur, ENS/CNRS/PSL
Examinateur

Xavier, RIVAL
Directeur de recherche, INRIA/ENS/PSL
Examinateur

Adelinde, UHRMACHER
Professeure, Universität Rostock
Examinatrice

<figure><img src="image_3.png" /></figure>
# Table des Matières

i

## 1 Introduction

1

1.1 Contexte et motivations .................................................... 1

1.2 Modélisation de systèmes d'interactions moléculaires .................... 1

1.3 Le langage Kappa .......................................................... 2

1.4 Interprétation abstraite .................................................... 4

1.5 L'écosystème Kappa .......................................................... 5

1.5.1 Analyses statiques .................................................... 5

1.5.2 Analyses causales .................................................... 6

1.5.3 Réduction de modèles .................................................... 8

1.6 Contenu ............................................................................ 11

## 2 Réécriture de graphes à sites

13

2.1 Signature ............................................................................ 13

2.2 Configurations d'espèces biochimiques .................................. 14

2.3 Motifs .................................................................................. 15

2.4 Plongements entre motifs .................................................... 16

2.5 Isomorphismes entre motifs .................................................. 18

2.6 Règles d'interaction ............................................................ 19

2.7 Isomorphismes entre règles .................................................. 21

2.8 Réactions induites par une règle d'interaction ................................ 22

2.9 Réseaux de réactions sous-jacents ............................................ 23

## 3 Analyse des motifs accessibles

27

3.1 Accessibilité dans un réseau réactionnel .................................. 27

3.2 Abstraction d'un ensemble d'états ........................................ 29

3.3 Transferts de point-fixes .................................................... 32

3.4 Analyse par ensembles de motifs orthogonaux ............................ 35

3.5 Pour aller plus loin ............................................................ 37

## 4 Flot d'information dans la sémantique différentielle d'un modèle Kappa

43

4.1 Une brèche dans le mur de la combinatoire ................................ 43

4.1.1 Les causes de l'explosion combinatoire ................................ 43

4.1.2 Le flot d'information .................................................... 44

4.1.3 Réduction de la combinatoire ............................................ 44

4.2 Exemple jouet ........................................................................ 45

4.3 Réduction de systèmes d'équations différentielles ............................ 49

4.4 Application à Kappa ............................................................ 54

4.4.1 Sémantique différentielle ................................................ 54

4.4.2 Inférence du flot d'information ........................................ 54

4.4.3 Pré-fragments et fragments ................................................ 56

4.4.4 Sémantique différentielle réduite .................................... 57

4.4.4.1 Raffinements orthogonaux ............................................ 57
<table>
  <tbody>
    <tr>
      <td>4.4.4.2</td>
      <td>Spécialisation des règles</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.4.4.3</td>
      <td>Termes de consommation et de production d'un motif</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Étude de performance</td>
      <td>64</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Pour aller plus loin</td>
      <td>64</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Flot d'information dans la sémantique stochastique d'un modèle Kappa</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Sémantique stochastique</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.1.1</td>
      <td>Sémantique de traces et simulation</td>
      <td>68</td>
    </tr>
    <tr>
      <td>5.1.2</td>
      <td>Équation maîtresse</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.1.3</td>
      <td>Retour sur les pas de calculs</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Cas d'étude</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.2.1</td>
      <td>Un exemple d'indépendance entre deux liaisons</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.2.1.1</td>
      <td>Réduction de la sémantique différentielle</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.2.1.2</td>
      <td>Réduction de l'équation maîtresse</td>
      <td>75</td>
    </tr>
    <tr>
      <td>5.2.2</td>
      <td>Un exemple avec une dissociation inconditionnelle</td>
      <td>76</td>
    </tr>
    <tr>
      <td>5.2.2.1</td>
      <td>Réduction de la sémantique différentielle</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.2.2.2</td>
      <td>Réduction de l'équation maîtresse</td>
      <td>79</td>
    </tr>
    <tr>
      <td>5.2.2.3</td>
      <td>Conclusion</td>
      <td>82</td>
    </tr>
    <tr>
      <td>5.2.3</td>
      <td>Un exemple de contrôle à distance</td>
      <td>83</td>
    </tr>
    <tr>
      <td>5.2.3.1</td>
      <td>Réduction de la sémantique différentielle</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.2.3.2</td>
      <td>Réduction de l'équation maîtresse</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.2.3.3</td>
      <td>Conclusion</td>
      <td>86</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Réduction de la sémantique stochastique</td>
      <td>86</td>
    </tr>
    <tr>
      <td>5.3.1</td>
      <td>Analyse statique</td>
      <td>86</td>
    </tr>
    <tr>
      <td>5.3.2</td>
      <td>Réduction de modèles</td>
      <td>88</td>
    </tr>
    <tr>
      <td>5.3.2.1</td>
      <td>Abstraction d'un graphe à sites</td>
      <td>88</td>
    </tr>
    <tr>
      <td>5.3.2.2</td>
      <td>Abstraction d'un ensemble de règles</td>
      <td>90</td>
    </tr>
    <tr>
      <td>5.3.2.3</td>
      <td>Impact sur la sémantique stochastique</td>
      <td>91</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Pour aller plus loin</td>
      <td>92</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Symétrie dans les graphes à sites</td>
      <td>95</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Le cas d'études</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.1.1</td>
      <td>Modèle</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.1.1.1</td>
      <td>Les constituants du modèle et ses règles d'interaction</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.1.1.2</td>
      <td>Le comportement du modèle</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.1.1.2.1</td>
      <td>Équation maîtresse.</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.1.1.2.2</td>
      <td>Sémantique différentielle.</td>
      <td>99</td>
    </tr>
    <tr>
      <td>6.1.1.3</td>
      <td>Symétries et propriétés comportementales</td>
      <td>99</td>
    </tr>
    <tr>
      <td>6.1.2</td>
      <td>Modèle simplifié</td>
      <td>99</td>
    </tr>
    <tr>
      <td>6.1.2.1</td>
      <td>Configurations d'espèces biochimiques et règles d'interaction.</td>
      <td>99</td>
    </tr>
    <tr>
      <td>6.1.2.2</td>
      <td>États des systèmes stochastiques et différentiels sous-jacent.</td>
      <td>100</td>
    </tr>
    <tr>
      <td>6.1.2.3</td>
      <td>Systèmes dynamiques sous-jacent</td>
      <td>100</td>
    </tr>
    <tr>
      <td>6.1.2.3.1</td>
      <td>Équation maîtresse.</td>
      <td>100</td>
    </tr>
    <tr>
      <td>6.1.2.3.2</td>
      <td>Sémantique différentielle.</td>
      <td>101</td>
    </tr>
    <tr>
      <td>6.1.3</td>
      <td>Comparaison des dynamiques des deux modèles</td>
      <td>101</td>
    </tr>
    <tr>
      <td>6.1.3.1</td>
      <td>Quotient</td>
      <td>101</td>
    </tr>
    <tr>
      <td>6.1.3.2</td>
      <td>Invariants quantitatifs</td>
      <td>105</td>
    </tr>
    <tr>
      <td>6.1.4</td>
      <td>Conclusion sur le cas d'étude</td>
      <td>108</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Échanges de sites dans des graphes à sites</td>
      <td>108</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>Échanges d'une paire de sites dans la configuration d'une espèce biochimique</td>
      <td>108</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>Échanges d'une paire de sites dans les occurrences d'une protéine d'un motif</td>
      <td>109</td>
    </tr>
    <tr>
      <td>6.2.3</td>
      <td>Échanges d'une paire de sites dans les occurrences d'une protéine dans une règle</td>
      <td>111</td>
    </tr>
    <tr>
      <td>6.2.4</td>
      <td>Échanges de sites dans les occurrences d'une protéine dans un plongement</td>
      <td>111</td>
    </tr>
    <tr>
      <td>6.2.5</td>
      <td>Échanges d'une paire de sites dans les occurrences d'une protéine dans le raffinement d'une règle</td>
      <td>118</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Symétries et conséquences sur le comportement des modèles</td>
      <td>120</td>
    </tr>
  </tbody>
</table>
<table><tr><td>6.3.1</td><td>Ensembles de règles</td><td>120</td></tr><tr><td>6.3.1.1</td><td>Orbites de règles d'interaction</td><td>120</td></tr><tr><td>6.3.1.2</td><td>Ensembles symétriques de règles</td><td>120</td></tr><tr><td>6.3.1.3</td><td>Orbites de motifs</td><td>121</td></tr><tr><td>6.3.1.4</td><td>Propriété fondamentale</td><td>123</td></tr><tr><td>6.3.2</td><td>Effet des symétries dans la sémantique différentielle</td><td>125</td></tr><tr><td>6.3.2.1</td><td>Orbites des configurations d'espèces biochimiques</td><td>125</td></tr><tr><td>6.3.2.2</td><td>Bisimulation en avant</td><td>126</td></tr><tr><td>6.3.2.3</td><td>Bisimulation en arrière</td><td>128</td></tr><tr><td>6.3.3</td><td>États discrets</td><td>132</td></tr><tr><td>6.3.3.1</td><td>Bisimulation en avant</td><td>132</td></tr><tr><td>6.3.3.2</td><td>Bisimulation en arrière</td><td>134</td></tr><tr><td>6.4</td><td>Étude de performance</td><td>135</td></tr><tr><td>6.5</td><td>Pour aller plus loin</td><td>137</td></tr><tr><td>7</td><td>Conclusion</td><td>145</td></tr><tr><td colspan="2">Références bibliographiques</td><td>147</td></tr><tr><td colspan="2">Index</td><td>157</td></tr></table>
# Chapitre 1

# Introduction

## 1.1 Contexte et motivations

Décrire et analyser les systèmes à grande échelle et fortement combinatoires qui sont issus de certains modèles mécanistiques de biologie des systèmes est encore hors de portée de l'état de l'art. Dans de tels modèles, le comportement individuel des occurrences de protéines, qui peuvent établir des liaisons et modifier leur capacité d'interactions, est influencé par des compétitions pour des ressources communes. De plus, les occurrences de protéines peuvent former une grande diversité de configurations d'espèces biochimiques différentes. La con-currence entre des interactions à différentes échelles de temps génère des boucles de rétro-actions non linéaires qui contrôlent l'abondance des configurations des espèces biochimiques. Enfin, ces systèmes font intervenir des interactions entre de très petites molécules, comme des ions ou des ligands et des espèces biochimiques gigan-tesques comme les brins d'acide désoxyribonucléique, le ribosome, ou le signalosome. Comprendre comment le comportement collectif des populations de protéines qui définit le phénotype, est engendré par le comportement individuel des occurrences de ces protéines reste un problème largement ouvert et un enjeu crucial.

Alors que les progrès technologiques permettent d'obtenir rapidement une quantité toujours plus importante de détails à propos des interactions mécanistiques potentielles entre les occurrences de protéines, et ce, à un prix très accessible, la communauté scientifique est encore bien loin de comprendre globalement comment le comportement macroscopique des systèmes émerge de ces interactions. C'est l'objectif annoncé de la biologie des systèmes. Mais ce but est sans espoir à moins que des méthodes spécifiques et innovantes pour décrire ces systèmes complexes et analyser leur propriété ne soient conçues. Bien entendu, ces méthodes devront passer à l'échelle de la très grande quantité d'informations qui est publiée dans la littérature à un rythme qui augmente de manière exponentielle.

## 1.2 Les langages de modélisation de systèmes d'interactions moléculaires

Les langages formels ont été beaucoup utilisés pour décrire des modèles d'interactions mécanistiques entre occurrences de protéines. Ils procurent des outils mathématiques pour traduire ces interactions et définir rigoureusement le comportement des systèmes ainsi représentés grâce à un choix de sémantiques qualitatives, stochastiques ou différentielles.

Les langages tels que les réseaux réactionnels [67] ou les réseaux de Petri classiques [95], se basent sur le paradigme de la réécriture multi-ensemble. Les interactions consistent à consommer des réactifs en échange de produits. Des constantes cinétiques permettent de préciser soit la vitesse, soit la fréquence moyenne – selon le choix de la sémantique – d'application des différentes réactions. Ceci les rend très utiles pour décrire et formaliser le comportement de systèmes d'interactions de petite ou moyenne taille. Cependant, ces langages peinent à représenter de grands modèles car ils ont besoin d'un nom (ou d'un emplacement dans le cas des réseaux de Petri) par type de configurations d'espèces biochimiques.

Des langages de plus haut niveau, inspirés des différents paradigmes de programmation, tels que les tableaux d'états à messages [49], les automates communicants [118], les algèbres de processus [122, 37], les langages orientés objet [62], les réseaux de Petri colorés [83] et la réécriture de graphes à sites [59, 65, 5, 100], exploitent le fait que les interactions dépendent généralement de conditions locales sur les configurations des occurrences de
protéines au sein des espèces biochimiques. Ces langages permettent ainsi de traduire les systèmes d'interactions entre les occurrences de protéines de manière plus parcimonieuse : seuls les détails qui importent pour une interaction donnée sont mentionnés pour décrire ces interactions.

Il est important de distinguer les approches basées sur les agents de celles basées sur les règles de réécriture. Dans celles basées sur les agents, chaque entité, que ce soit un processus [37] ou un objet [62], doit contenir la description de tous ses comportements possibles. Les changements entre les configurations des différentes entités se synchronisent par le biais de règles de communication. Ces règles, généralement en très petit nombre, définissent la sémantique opérationnelle des langages. Il est possible de conditionner le comportement d'un agent à des propriétés de l'état d'un autre agent auquel cet agent serait lié, mais cela nécessite de recourir à des processus fictifs pour aller chercher cette information. Cette astuce était en fait déjà utilisée dans les premiers modèles décrits en π-calcul [122]. Cependant, en général, les approches basées sur les agents donnent lieu à des systèmes de processus à états finis [102]. Ceci permet d'étudier leur comportement à l'aide d'outils de vérification symbolique de modèles comme PRISM [107]. Lorsque les occurrences des protéines admettent trop de configurations différentes ou lorsque leurs capacités d'interactions dépendent trop des occurrences des protéines auxquelles elles sont liées, les approches fondées sur les agents ne passent pas à l'échelle, tant au niveau de la description des modèles, que pour le calcul de leurs propriétés.

Les approches fondées sur les règles définissent les modèles par des règles d'interactions. Chaque règle définit sous quelles conditions sur les configurations des agents une interaction peut avoir lieu et quels sont les effets de cette interaction. Ainsi l'état des agents ne définit pas une fois pour toute les capacités d'interactions de cet agent. Ce sont les règles du modèle qui le font. Il n'est pas non plus nécessaire de donner la liste exhaustive de toutes les configurations des agents. Les règles peuvent se contenter de ne mentionner que les parties importantes des agents pour l'interaction qu'elles décrivent. Les approches fondées sur les règles passent mieux à l'échelle et facilitent la mise à jour des modèles. De plus, comme il n'est pas nécessaire de spécifier explicitement toutes les capacités d'interactions des occurrences des protéines, elles encouragent à une modélisation sans *a priori* où les interactions émergent des règles au fur et à mesure de la conception du modèle.

Le calcul des ambients [31, 32], des bioambients [121] et celui des membranes [30] sont un peu particuliers. Ils permettent de décrire des boîtes ou des compartiments, qui peuvent être arbitrairement imbriqués au sein d'une arborescence, alors que des agents, contenus dans les boites dans le cas des ambients, ou dans leurs parois dans le cas des membranes, permettent à ces compartiments de se déplacer ou de se fusionner. Les capacités d'interactions des agents peuvent alors dépendre de leur localisation dans la hiérarchie des compartiments. La calcul projectif des membranes [60] représente plus fidèlement la disposition des compartiments au sein d'une cellule, en rendant la description de l'état du système indépendante du choix de la racine de l'arborescence des compartiments.

## 1.3 Le langage Kappa

Les langages de réécriture de graphes à sites [59, 65, 5, 100] permettent de représenter de manière transparente les réseaux d'interactions entre des occurrences de protéines grâce à leur syntaxe inspirée de la chimie.

Dans Kappa, chaque configuration d'espèces biochimiques est représentée par un graphe à sites. Un exemple de graphe à sites est donné en figure 1.1(a). Dans un graphe à sites, des nœuds qui représentent des occurrences de protéines, sont associés à une liste de sites d'interactions. Ces sites peuvent être libres ou liés deux à deux. En outre, certains sites portent une propriété qui peut servir à représenter un niveau d'activation. Les interactions entre occurrences de protéines peuvent modifier leurs conformations en dépliant ou en repliant leurs chaînes de nucléotides, ce qui peut révéler ou cacher des sites d'interactions. Dans Kappa, la structure tri-dimensionnelle des occurrences de protéines n'est pas représentée explicitement. En revanche, les conditions pour qu'un site d'interactions soit visible sont spécifiées dans la description des interactions elles-mêmes.

L'évolution d'un système Kappa se décrit grâce à des règles de réécriture hors-contexte. En figure 1.1(b) est dessinée une règle pour la formation de dimères. Deux occurrences du récepteur (EGFR) qui sont tous deux liées à des occurrences du ligand (EGF) peuvent se lier entre elles pour former un dimer. En figure 1.1(c) est donnée une règle issue d'un modèle de réparation de l'ADN, dans laquelle l'occurrence d'une enzyme, la Glycolase (DG), peut glisser aléatoirement dans les deux sens, le long d'un brin d'ADN [104].

Une règle peut être comprise de manière intentionnelle comme une transformation locale de l'état du système ou de manière extensionnelle comme l'ensemble, qu'il soit fini ou non, des réactions biochimiques qui peuvent être obtenues en spécifiant entièrement les différents contextes d'application de ces règles. De cet ensemble de réactions, diverses sémantiques peuvent être définies pour décrire le comportement des systèmes. Ces séman-
<figure><img src="image_4.png" /><figcaption>Figure 1.1: En 1.1(a) est dessiné un graphe à sites. Il s'agit de la configuration d'une espèce biochimique composée de deux occurrences du ligand (EGF), de deux occurrences du récepteur membranaire (EGFR), d'une occurrence de la protéine d'échafaudage (Shc), de deux occurrences de la protéine de transport (Grb2) et d'une occurrence de la protéine Sos. En 1.1(b) est donné un exemple de règle de liaison. Deux occurrences du récepteur membranaire (EGFR), lorsqu'elles sont toutes deux activés par une liaison avec des occurrences du ligand (EGF), peuvent se lier. Les autres sites sont omis car ils ne jouent aucun rôle dans cette interaction. En 1.1(c) est donnée une règle de déplacement. Une occurrence de l'enzyme Glycolase (DG) peut glisser dans les deux directions (selon une marche aléatoire) le long d'un brin d'ADN.</figcaption></figure>

tiques peuvent être qualitatives, stochastiques ou différentielles, comme pour le cas des réseaux réactionnels et des réseaux de Pétri (les sémantiques quantitatives — stochastiques ou différentielles — requièrent l'ajout d'une constante d'interactions à chaque règle). Il est toutefois possible de simuler un modèle Kappa directement, sans passer par le réseau réactionnel sous-jacent. La simulation consiste alors à itérer la boucle événementielle suivante (celle-ci correspond à l'algorithme de Gillespie [86]). Étant donné l'état du système, représenté par un graphe à sites, l'ensemble de tous les événements possibles est calculé. Un événement consiste à appliquer une règle dans le graphe à une occurrence du motif qui constitue le membre gauche de cette règle. Chaque événement a une propension qui correspond à la constante de la règle correspondante. Le prochain événement est tiré au hasard selon une probabilité proportionnelle à sa propension, alors que le délai entre deux événements est tiré aléatoirement selon une loi exponentielle dont le paramètre est la somme des propensions de tous les événements potentiels du système. Il n'est pas raisonnable de recalculer la liste des événements potentiels à chaque fois après l'application d'une règle. Cet ensemble peut être mis à jour dynamiquement en tenant compte uniquement des nouveaux événements potentiels et des événements qui ne sont plus possibles du fait de l'application du dernier événement choisi [54]. Le simulateur actuel tire profit au maximum des sous-motifs communs dans les motifs qui apparaissent dans le membre gauche des règles pour découvrir les nouveaux événements et retirer les événements devenus obsolètes plus rapidement [17].

Le langage Kappa souffre de plusieurs limites. Par exemple, les sites d'interactions d'une même occurrence d'une protéine doivent porter des noms différents ; par ailleurs, en ce qui concerne les propriétés géométriques, Kappa ne permet ni de représenter la structure tridimensionnelle des occurrences de protéines, ni leur répartition dans l'espace. Avoir des sites deux à deux différents dans chaque occurrence de protéines facilite grandement la recherche des occurrences des motifs dans les graphes, ce qui est non seulement crucial pour simuler les modèles de manière efficace, mais est aussi à la base de plusieurs constructions utilisées pour l'analyse statique et la réduction de modèles. Certains langages lèvent cette contrainte soit directement comme dans les langages BNGL [65] et mod [4], soit indirectement en utilisant un codage sous forme d'hyperliens comme dans le langage React(C) [100]. Toutefois, l'efficacité des moteurs de simulation est fortement réduite quand de telles constructions sont utilisées. Pour ce qui est de la géométrie des protéines, les conditions liées aux conformations spatiales des protéines peuvent être encodées dans les règles de réécriture. Certaines extensions du langage permettent
de représenter des contraintes sur la position relative des occurrences de protéines et des sites d'interactions dans les configurations des espèces biochimiques, afin de restreindre l'ensemble des événements possibles à ceux qui satisfont ces contraintes [57]. Enfin, dans Kappa, la distribution des occurrences de protéines dans l'espace est passée sous silence. Il est fait l'hypothèse que les occurrences de protéines sont parfaitement mélangées. Il est donc impossible de retrouver les phénomènes d'encombrement qui peuvent être dus à des accumulations d'occurrences de protéines dans certaines régions de la cellule. De même, les gradients de concentration locaux qui pourrait être dus à la présence d'une occurrence d'une protéine d'échafaudage, ne peuvent pas être représentés (en Kappa, chaque occurrence d'une protéine d'échafaudage n'agit qu'en maintenant des occurrences de protéines dans la même espèce biochimique, une fois libérées, ces occurrences de protéines ne sont pas supposées rester, même pour un court instant dans le même voisinage). Une solution partielle consiste à encoder en Kappa une grille pour représenter de manière discrète les positions potentielles des occurrences de protéines. Ensuite, celles-ci peuvent glisser le long de cette grille grâce à des règles implémentant la diffusion des occurrences de protéines. Le langage SpatialKappa [125] utilise ce procédé de manière transparente. Par ailleurs, le langage ML [96] permet de représenter des modèles d'interactions entre occurrences de protéines qui peuvent se déplacer de manière continue dans un milieu. Il est possible de munir un modèle Kappa d'un ensemble de compartiments statiques. Toutefois, ceci ne permet pas de modéliser le transport d'occurrences de protéines par le biais de vésicules. La machine formelle cellulaire [48] répond à cet enjeu, sans toutefois fournir de moteurs de simulation efficaces.

Les langages de réécriture de graphes à sites permettent de représenter les réseaux d'interactions entre occurrences de protéines, et ce, malgré leur forte combinatoire. Si le comportement de ces réseaux peut être formellement défini et simulé, des abstractions restent nécessaires pour calculer les propriétés du comportement collectif des populations de protéines.

## 1.4 Interprétation abstraite

L'interprétation abstraite a été introduite il y a un peu plus de quarante ans comme un cadre mathématique pour établir des liens formels entre le comportement de programmes, vu à différents niveaux d'abstraction. Depuis, l'interprétation abstraite est utilisée non seulement pour comparer différentes méthodes et algorithmes d'analyse statique [45], mais aussi pour développer des analyseurs statiques pour calculer automatiquement les propriétés sur le comportement des programmes [8, 66]. L'interprétation abstraite s'est désormais développée dans l'industrie (entre autres, Amazon, Meta, IBM, Google, MicroSoft et MathWorks ont chacune leurs propres analyseurs statiques basés sur l'interprétation abstraite).

L'interprétation abstraite repose sur la démarche suivante. Le comportement d'un programme (ou d'un modèle) peut en général être décrit comme le plus petit point fixe $lfp \in \mathbb{F}$ d'un opérateur $\mathbb{F}$ agissant sur les éléments d'un ensemble appelé le domaine concret $D$. Le domaine concret est habituellement l'ensemble des parties $\wp(S)$ d'un ensemble d'éléments $S$, qui peuvent être des états, des traces de calcul, et cetera. Une abstraction est alors vue comme un changement de granularité dans la description du comportement des programmes (ou des modèles) et ce changement de granularité peut prendre en langage mathématique diverses formes telles qu'un opérateur de clôture supérieure, une famille d'idéaux, une famille de Moore ou une correspondance de Galois. Les correspondances de Galois se sont vite imposées comme l'outil le plus populaire pour décrire une interprétation abstraite. Un changement du niveau d'observation du comportement d'un programme (ou d'un modèle) peut ainsi être décrit en choisissant un ensemble $D^\#$ de propriétés d'intérêt. C'est le domaine abstrait. Cet ensemble est ordonné par un ordre partiel $\sqsubseteq$. Chaque élément $a^\#$ de ce domaine abstrait représente intentionnellement l'ensemble des éléments concrets qui satisfont cette propriété. Cet ensemble est noté $\gamma(a^\#)$. La fonction $\gamma$, ainsi définie, est croissante (si $a^\# \sqsubseteq b^\#$, alors $\gamma(a^\#) \subseteq \gamma(b^\#)$). Ainsi, l'ordre $\sqsubseteq$ représente le niveau d'information.

Un élément abstrait $a^\#$ est dit être une abstraction d'un ensemble $a$ d'éléments concrets, si et seulement si $a$ est un sous-ensemble de l'ensemble $\gamma(a^\#)$. Une correspondance de Galois est obtenue quand chaque sous-ensemble $a$ de l'ensemble $S$ admet une meilleure abstraction, c'est à dire, que pour chaque partie $a$ de l'ensemble $S$, il existe un élément abstrait, noté $\alpha(a)$ qui est d'une part une abstraction de l'ensemble $a$ et d'autre part, qui est plus petit (pour l'ordre $\sqsubseteq$) que n'importe quelle abstraction de l'ensemble $a$. Dans un tel cas, n'importe quelle fonction croissante $\mathbb{F}^\#$ opérant sur le domaine abstrait $D^\#$ et telle que $[\alpha \circ \mathbb{F} \circ \gamma](a^\#) \sqsubseteq \mathbb{F}^\#(a^\#)$ pour chaque élément abstrait $a^\# \in D^\#$, admet un plus petit point fixe (pour l'ordre $\sqsubseteq$) noté $lfp \in \mathbb{F}^\#$. De plus, la concrétisation de ce plus petit point fixe est un sur-ensemble du plus petit point fixe de la fonction $\mathbb{F}$ ; ainsi le comportement du programme ou du modèle peut être calculé dans le domaine abstrait au prix d'une perte potentielle d'information puisque le résultat final est un sur-ensemble de l'ensemble de tous les comportements
possibles. Par construction, l'approche est correcte : aucun comportement de la sémantique concrète n'est
oublié. Par contre, quand le sur-ensemble ainsi calculé est un sur-ensemble strict, des comportements fictifs ont
été introduits par l'analyse.

Le choix du domaine abstrait est crucial. Du point de vue de l'expressivité, le domaine abstrait doit permettre
de décrire les propriétés d'intérêt des programmes (ou des modèles) ainsi que les propriétés intermédiaires qui
sont nécessaires pour en établir la preuve de manière inductive. D'un point de vue algorithmique, ils doivent
correspondre à des propriétés qui sont relativement simples à manipuler en machine. Enfin, la structure des
chaînes croissantes d'éléments abstraits (pour l'ordre $\sqsubseteq$) est également importante pour que puissent être définis
des opérateurs d'extrapolation précis, dans le cas où le domaine admettrait des chaînes croissantes infinies.

Plusieurs interprétations abstraites ont été proposées pour calculer automatiquement les propriétés des
modèles en biologie des systèmes. Les premières ont été inspirées par les analyses de flot d'information [12,
69] et de dénombrement [113, 70] dans le $\pi$-calcul et le calcul des ambients. Ces analyses permettent de
détecter avec précision dans quels compartiments des entités peuvent entrer dans des modèles-jouet de virus
infectant des cellules. Elles trouvent également des exclusions mutuelles [87, 11]. Les analyses de dénombrement
permettent aussi souvent de retrouver les invariants correspondant à la conservation du nombre de chaque sorte
de protéines dans les réseaux réactionnels lorsque la composition des configurations d'espèces biochimiques n'est
pas représentée explicitement [1, 2]. Ces invariants sont aussi appelés invariants de places dans les réseaux de
Petri.

Les modèles biologiques sont fortement concurrents et souffrent de l'explosion combinatoire dans le nombre
d'entrelacements potentiels des différents événements possibles. L'interprétation abstraite a été utilisée pour ou-
blier la séquentialité dans les traces d'exécution dans les processus de frappes [115], puis plus généralement pour
les réseaux asynchrones discrets booléens ou multivalués [81]. Dans les modèles réseaux booléens ou multivalués,
l'interprétation abstraite a également été utilisée pour calculer une approximation des ensembles constituant
des trappes [41, 103], dans lesquels les systèmes ne peuvent plus sortir une fois entrés. Ces ensembles facilitent
le calcul des trajectoires périodiques des modèles. Dans les modèles de réseaux métaboliques, l'interprétation
abstraite a été utilisée pour décrire une analyse de dépendances, qui calcule l'impact potentiel de l'inhibition
éventuelle d'une règle sur la concentration à l'équilibre des composants du système [101, 3].

L'interprétation abstraite peut servir à la calibration d'un modèle [105], en réalisant une partition de l'espace
des paramètres en trois régions : une première région dans laquelle le modèle satisfait une propriété temporelle
donnée par l'utilisateur, une seconde qui ne la satisfait pas et une troisième pour laquelle l'analyse n'a pu
conclure si la propriété était satisfaite ou non.

L'interprétation abstraite est également très utilisée pour le calcul des trajectoires des systèmes hybrides
[88].

## 1.5 L'écosystème Kappa

Plusieurs outils pour analyser et manipuler des modèles Kappa sont présentés ici.

### 1.5.1 Analyses statiques

Un outil d'analyse statique [15], basé sur le cadre de l'interprétation abstraite, permet de calculer automatiquement certaines propriétés des modèles. Le but est d'améliorer la confiance dans les règles qui constituent le modèle. Il s'agit de retrouver des propriétés d'intérêt que le modélisateur pouvait, ou non, avoir en tête lors de la conception de son modèle ou bien de trouver des erreurs dans la modélisation.

Cette analyse utilise un ensemble de motifs d'intérêt. Parmi ces motifs, l'analyse prouve que certains ne peuvent apparaître dans aucun état potentiel du modèle. Les autres sont déclarés potentiellement accessibles : soit ils le sont effectivement, soit c'est une conséquence de la sur-approximation de l'analyse.

Les motifs d'intérêt permettent de poser des questions sur la structure biochimique des occurrences des
configurations des espèces biochimiques lors de l'exécution du modèle. Actuellement, l'analyse pose trois types
de questions : Existe-t-il une relation entre l'état de plusieurs sites dans les occurrences d'une protéine ? Lorsque
deux occurrences de protéines sont liées entre-elles, existe-t-il une relation entre l'état de leurs sites respectifs
? Est-ce qu'une occurrence d'une protéine peut être doublement liée à une autre occurrence d'une protéine,
est-ce qu'une occurrence de protéines peut être liée à des occurrences différentes d'un même type de protéines
? La première catégorie est une analyse relationnelle classique. Elle permet, par exemple, de détecter si un
site ne peut être lié sans qu'un autre ne le soit ou de détecter si un site ne peut être lié sans être phosphorylé.
La seconde est utile quand des sites fictifs permettent d'encoder la localisation des occurrences de protéines, il est alors possible de vérifier, chaque fois que deux occurrences de protéines sont liées, si elles se situent nécessairement dans un même compartiment. Enfin, la troisième analyse la formation de doubles liaisons entre les occurrences de protéines. Le choix exact des questions posées par l'analyseur est fixé automatiquement suite à une inspection statique des règles du modèle.

Le résultat final de l'analyse d'accessibilité est présenté à l'utilisateur sous deux formes. D'une part, les règles dont le membre gauche est en contradiction avec les motifs qui ont été prouvés inaccessibles par l'analyse sont mentionnées à l'utilisateur. D'autre part, les propriétés intéressantes sur la structure des configurations d'espèces biochimiques sont listées sous la forme de lemmes de raffinement.

Par exemple, les trois lemmes suivants :

<figure><img src="image_5.png" /></figure>

informer l'utilisateur que (pour le premier) dans une occurrence du récepteur membranaire, le site *c* ne peut être lié sans que le site *r* ne le soit également, que (pour le second) le site *r* ne peut être lié sans que le site *l* ne le soit aussi, et que (pour le troisième) quand une occurrence du récepteur membranaire a ses sites *r* et *c* tous deux liés, ils sont nécessairement liés tous deux à une même occurrence du récepteur membranaire.

Un lemme de raffinement est ainsi présenté comme une implication entre un motif et une liste de motifs. Ici, les listes de motifs sont toutes réduites à un élément. Il faut interpréter une telle implication par le fait que toute occurrence du membre gauche de l'implication dans un état accessible peut se raffiner dans au moins un des motifs du membre droit.

Lorsque l'utilisateur obtient des propriétés auxquelles il ne s'attend pas, il doit retourner à son modèle pour comprendre l'origine du problème. Les erreurs typographiques sont assez courantes. Il arrive aussi souvent que certaines parties du modèle manquent, il faut aller les compléter ou les remplacer par des règles fictives si l'information n'est pas disponible dans la littérature. Il se peut aussi que l'état initial du modèle ait été mal choisi. Enfin, les erreurs peuvent aussi être dues à des relations causales complexes. L'analyse statique peut alors être complétée par l'analyse causale [51, 50] et par l'analyse contre-factuelle [108] pour comprendre comment les configurations inattendues se produisent.

## 1.5.2 Analyses causales

La causalité est un outil très utile pour comprendre le comportement individuel des occurrences des protéines dans un modèle Kappa. Son but est d'étudier en quoi certains événements ont été nécessaires pour que d'autres événements aient pu avoir lieu.

Une trace causale est alors un ensemble d'événements dont certaines paires sont ordonnées par une relation de causalité. Celle-ci indique si l'application d'un événement a rendu possible l'application d'un autre. Un exemple de trace causale est donné en figure 1.2. Il s'agit de l'ensemble des événements pour qu'une occurrence du récepteur membranaire recrute une occurrence de la protéine *Sos* par le biais de son site *Y68*. Il faut tout d'abord activer deux occurrences du récepteur membranaire *EGFR* en les liant à des occurrences du ligand *EGF*. Les deux occurrences du récepteur peuvent alors établir une liaison symétrique, puis une liaison asymétrique ce qui permet de différencier une des deux occurrences du récepteur membranaire. Le site *Y68* de cette occurrence peut alors être phosphorylé pour qu'il puisse se lier à une occurrence de la protéine de transport *Grb2*. Indépendamment, cette occurrence de la protéine de transport peut s'être liée à une occurrence de la protéine *Sos*.

Dans cette trace, tous les événements sont nécessaires, mais d'autres *scenarii* peuvent exister. Par exemple, les occurrences du récepteur membranaire peuvent recruter une occurrence de la protéine *Sos* par le biais du site
<figure><img src="image_6.png" /><figcaption>Figure 1.2: Une des deux traces causales pour le recrutement d'une occurrence de la protéine *Sos* par une occurrence du récepteur membranaire. Les nœuds verts représentent l'introduction des occurrences de protéines, les nœuds bleus représentent l'application des règles, le nœud rouge représente le but à observer. Les arcs décrivent les relations causales entre les événements.</figcaption></figure>

Y48, ce qui donne lieu à une autre trace causale. Une trace causale décrit, en fait, un ensemble d'événements qui sont nécessaires dans un scénario potentiel.

Les traces causales sont obtenues en partant des résultats de la simulation, en relevant toutes les occurrences d'un événement d'intérêt. Pour chaque occurrence, une trace est extraite en collectant les événements nécessaires à cette occurrence ou récursivement à tout autre événement lui-même nécessaire [51]. Les événements sont ensuite organisés sous la forme d'un graphe acyclique orienté grâce à la transformation de Mazurkiewicz [110]. Cette transformation exploite le fait que certains événements, causalement indépendants, commutent. Un moteur de recherche opérationnelle est ensuite utilisé pour retirer de cette trace causale les événements qui peuvent l'être. Une description de cette approche dans un formalisme catégorique est décrit dans cette publication [50].

Les traces causales donnent une vision des voies de signalisation qui privilégie l'acquisition du signal. Dans un modèle, toutes les interactions sont en général réversibles, ce qui est nécessaire pour que l'occurrence d'une kinase, par exemple, puisse agir sur plusieurs occurrences de sa protéine cible à tour de rôle. Cet aspect, gestion de ressources, n'est pas du tout décrit dans les traces causales. Les traces causales ne peuvent dont pas remplacer les règles d'un modèle. Il s'agit juste d'un outil pour comprendre comment un objectif peut être atteint, mais qui ne permet pas à lui seul de définir le comportement collectif du modèle.

Les traces causales dépendent fortement de la syntaxe du langage. En effet, la syntaxe définie quelles préconditions peuvent être utilisées dans les règles, ce qui a une incidence sur le fait que deux événements puissent être vus ou non, comme indépendants causalement. Aussi, le fait que Kappa utilise de la réécriture hors contexte où seuls les sites qui ont une importance dans une interaction ont besoin d'être mentionnés, permet d'avoir plus d'événements qui commutent. Chaque trace causale peut alors résumer un plus grand nombre de traces classiques.

En figure 1.3 est considéré l'exemple d'une sorte de protéines avec deux sites de phosphorylation. Chaque site peut être phosphorylé indépendamment de l'état de l'autre site, ce qui se traduit en Kappa par les deux règles données en figure 1.3(a). Ces règles peuvent être appliquées dans n'importe quel ordre. Il y a donc une seule trace causale pour obtenir une occurrence de protéines doublement phosphorylée. Cette trace est dessinée
<figure><img src="image_7.png" /><figcaption>Figure 1.3: En 1.3(a), un modèle formé de deux règles d'interactions. En 1.3(b) l'ensemble des toutes les configurations d'espèces biochimiques accessibles à partir d'une occurrence de la protéine entièrement non phosphorylée, un nom est donné à chaque configuration. En figure 1.3(c), le réseau réactionnel sous-jacent. Contrairement aux règles d'interactions, les réactions testent l'intégralité de l'état de l'occurrence de la protéine. Ainsi, les réactions qui phosphorylent les deux sites ne commutent pas. Il y a donc deux traces causales, selon que le site droit ou gauche ait été phosphorylé en premier avec les réactions (figure 1.3(d)). En Kappa, les règles de phosphorylation d'un site s'appliquent quelque soit l'état de l'autre site. Ainsi les traces causales ne distinguent pas quel site est phosphorylé en premier. Il n'y a alors qu'un seul type de trace causale (figure 1.3(e))).</figcaption></figure>

en figure 1.3(e). Dans un réseau réactionnel, les configurations d'espèces biochimiques sont nommées et leur structure biochimique ne peut pas être utilisée. Il faut donc quatre réactions pour simuler ces deux règles Kappa. Or, chacune de ces réactions spécifie exactement quel réactif elle utilise, ce qui empêche les réactions de commuter. Il y alors deux traces causales différentes selon que le site de droit ou de gauche ait été phosphorylé en premier.

Pour conclure sur la causalité, il est important de remarquer que les traces causales s'appuient sur une vision positive de la causalité. Ce n'est en général pas suffisant pour comprendre le comportement des voies de signalisation intracellulaire. En effet, il y a souvent dans ces voies des événements qui ne sont certes pas nécessaires mais qui rendent d'autres événements plus probables. C'est le cas d'une interaction qui stabiliserait une structure instable pour lui laisser le temps de réaliser une certaine interaction. D'un point de vue logique, la stabilisation de la structure n'est pas requise. Mais il est improbable que sans elle, l'autre interaction puisse avoir lieu. Ces effets cinétiques sont capturés par les notions de causalité contre-factuelles [90], dont l'adaptation à Kappa [108] ouvre des pistes de recherches pleines de promesses.

### 1.5.3 Réduction de modèles

La réduction de modèles consiste à simplifier un modèle en ajustant le grain d'observation. Les réductions de modèles peuvent se formaliser comme des transformations de graphes [84], des transformations tropicales [120], des bisimulations [27, 34], ou, tout simplement, des changements de variables [74]. Elles peuvent être classées selon la classe de propriétés qu'elles préservent.
Des outils de réduction exacte permettent de simplifier à la fois les systèmes d'équations différentielles [74, 53] et les systèmes stochastiques [76] qui sont décrit en Kappa. Ces algorithmes trouvent automatiquement des changements de variables par inspection statique des règles initiales des modèles et dérivent des modèles réduits en conséquence. La preuve de correction de ces algorithmes est faite par interprétation abstraite : le modèle réduit définit la projection exacte, par le changement de variables découvert par l'analyse, du comportement transitoire du modèle avant réduction. L'ensemble des configurations des espèces biochimiques, le changement de variables et la description extensionnelle du modèle avant réduction ne sont jamais représentés explicitement, ce qui permet à la méthode de passer à l'échelle.

Les outils de réduction de modèles pour Kappa combinent deux types d'abstraction : le premièr exploite les symétries potentielles au sein des sites d'interactions des occurrences des protéines du modèle, alors que le second identifie parmi les corrélations éventuelles entre les états des sites des occurrences des protéines, celles qui n'ont aucun impact sur leur comportement collectif. Les symétries sont décrites comme des actions de groupes qui préservent l'ensemble des règles de réécriture qui constituent un modèle [27, 73]. Elles induisent une relation d'équivalence entre les configurations d'espèces biochimiques qui, elle-même, défini une relation de bisimulation sur les différents états du modèle. Les états en relation seront regroupés en un seul dans le modèle réduit. Intuitivement, cette analyse détecte quels sites ont exactement les mêmes capacités d'interactions et ignore la différence entre ces sites : dans le modèle réduit, la configuration d'une occurrence d'une protéine est définie par le nombre de sites dans un certain état en faisant abstraction de quels sites précis sont dans cet état. Ceci engendre une réduction d'un facteur exponentiel : par exemple, pour un type de protéines avec *n* sites symétriques pouvant chacun prendre deux états différents, la réduction permet de passer de $2^n$ configurations potentielles à seulement ($n + 1$).

La deuxième approche se base sur l'analyse du flot d'information entre les différents sites d'interactions dans les configurations d'espèces biochimiques. Cela permet de comprendre quelles corrélations entre l'état des différents sites peuvent avoir une influence sur le comportement global du système et de passer les autres sous silence. Une approximation qualitative du flot d'information est calculée en répertoriant, au sein des règles de réécriture, tous les chemins entre les sites dont l'état est testé (ceux qui apparaissent dans le membre gauche d'une règle) et les sites dont l'état est modifié (ceux qui apparaissent dans le membre droit de cette règle avec un état différent de celui du membre gauche) (voir en figure 1.4(a)). Chaque motif est alors annoté en regroupant le flot d'information présent dans chacune des règles qui peut s'y appliquer. Les motifs intéressants sont ceux pour lesquels il existe un site d'interactions qui est accessible par tous les autres en suivant cette annotation. Par exemple, la configuration d'espèces biochimiques dessinée en figure 1.1(a) contient les quatre motifs d'intérêt donnés en figure 1.4(b) avec leur annotation. Dans ce modèle, les motifs d'intérêt sont exactement ceux qui décrivent l'état d'un seul site Y48 ou Y68. Ainsi la corrélation entre l'état des différents sites Y48 et Y68 n'est plus représentée dans le modèle réduit. D'un point de vue combinatoire, ceci permet de passer de $m^2 \cdot n^2$ configurations d'espèces biochimiques à $m+n$ motifs d'intérêt (où *m* et *n* représentent respectivement le nombre de configurations différentes pour la partie de l'espèce biochimique liée aux sites Y48 et Y68).

Sur un modèle plus complet [10, 124, 20, 51], cet outil permet de passer de $10^{20}$ configurations d'espèces biochimiques à 175,000 motifs d'intérêt, en environ de 3 minutes.

Des méthodes approchées utilisent des formes tronquées de développement formels de la sémantique stochas-
tique [85], alors que les méthodes de tropicalisation exploitent la séparation entre les échelles de temps et de
concentration [119]. Ces méthodes ne procurent pas de bornes d'erreur explicites. Par ailleurs, elles nécessitent
une description extensionnelle des réseaux réactionnels sous-jacents. Des méthodes exactes opèrent de manière
analytique pour extraire des relations d'équivalence entre les différentes espèces biochimiques de la description
explicite des réseaux réactionnels [34] ou même directement des systèmes d'équations différentielles [36]. Elles
permettent de calculer la meilleure bisimulation en avant, parmi celles qui sont basées sur un partitionnement
des variables ou quelles variables prennent toujours la même valeur. La notion de symétries développée pour
Kappa est plus restrictive car elle se concentre sur les bisimulations qui correspondent à un certain groupe de
transformations. En revanche, elle permet de détecter des relations de proportionnalité entre variables. Par
ailleurs, elle ne nécessite de représenter, ni les réseaux réactionnels, ni les systèmes différentiels sous-jacents, évi-
tant ainsi un calcul dont la durée est souvent prohibitive [29]. La réduction de modèles basée sur l'étude du flot
d'information est à la fois une généralisation et une formalisation d'approches systématiques existantes [13, 40].
L'utilisation d'un langage formel et l'interprétation abstraite de sa sémantique a permis d'établir formellement
la correction de ces approches.
<figure><img src="image_8.png" /><figcaption>(a) La règle de formation de dimères annotée par le flot d'information qu'elle induit.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) Les quatre motifs d'intérêt qui apparaissent dans les configurations d'espèces biochimiques de la figure 1.1(a).</figcaption></figure>

Figure 1.4: En 1.4(a), chaque chemin entre un site dont l'état est testé et un site dont l'état est modifié dans une composante connexe du membre gauche d'une règle induit un flot d'information. Ici, la capacité de lier le site *r* d'une occurrence du récepteur dépend du fait que cette occurrence soit liée à une occurrence du ligand. En 1.4(b) sont représentés les quatre motifs d'intérêt qui apparaissent dans les configurations d'espèces biochimiques dessinées en figure 1.1(a). Ils sont tous quatre annotés par une relation qui spécifie comment l'information se propage – ou s'est propagée – à travers leurs différents sites d'interactions (cette relation est obtenue en recopiant le flot d'information des règles compatibles avec ces motifs). Ils contiennent chacun un site accessible par tous les autres en suivant cette relation.
## 1.6 Contenu

Le reste de ce mémoire décrit le langage Kappa [58, 59] sous forme graphique, ainsi que l'analyse statique qui permet de détecter quels motifs peuvent se former lors de l'exécution des modèles [56, 71, 79, 15] et des méthodes de réduction de modèles pour diminuer la complexité combinatoire de la sémantique différentielle et de le sémantique stochastique de ces modèles [74, 53, 24, 27, 26, 23, 76, 116].

En particulier, la notion de graphe à sites, qui représente l'état des systèmes modélisés, est introduite en chapitre 2, ainsi que celle de règle de réécriture. Par soucis de simplicité, seul un fragment du langage est considéré. En effet, certaines constructions du langage complet font intervenir des effets de bord (qui peuvent provoquer des transformations de l'état des occurrences de protéines, en dehors des occurrences des motifs de réécriture). S'il est possible d'adapter les différentes définitions pour traiter les effets de bords, cela n'apporte pas grand chose conceptuellement.

L'analyse statique, présentée en chapitre 3, permet de détecter, au sein d'un ensemble de motifs d'intérêt paramètre de l'analyse, lesquels ne peuvent jamais se former quelle que soit l'exécution du système. C'est une analyse approchée. Les motifs déclarés inaccessibles sont bien inaccessibles. Par contre, l'analyse n'apporte aucune information à propos des autres motifs. Par soucis d'efficacité, les ensembles de motifs sont organisés sous la forme d'une collection d'arbres de décision dans lesquels des motifs initiaux sont raffinés peu à peu en ajoutant de l'information contextuelle [79]. Cette analyse est implantée dans l'analyseur statique KASA [15] et le choix des arbres de décisions, qui paramétrise l'analyse, est fait automatiquement par une pré-analyse.

En chapitre 4 est présentée une méthode de réduction de modèles pour la sémantique différentielle. Les sémantiques différentielles classiques introduisent une variable par catégorie d'espèces biochimiques, ce qui ne passe en général pas à l'échelle. Il s'agit donc de trouver un changement de variables qui réduise la taille de la sémantique différentielle des modèles décrit sous formes d'ensembles de règles de réécriture de graphes à sites. Pour cela, la méthode s'appuie sur la notion de flot d'information entre les sites des configurations d'espèces biochimiques, qui approche supérieurement quels sites influencent l'évolution de quels sites. Du flot d'information peuvent être découvertes des paires de sites pour lesquels la corrélation entre l'état n'a pas d'incidence sur la dynamique du système. Ces corrélation peuvent donc être oubliées, ce qui revient à considérer des morceaux de configurations d'espèces biochimiques, plutôt que des configurations d'espèces biochimiques en entier. Par construction, le résultat est un ensemble de portions de configuration d'espèces biochimiques dont l'évolution peut s'exprimer de manière autonome. L'interprétation de ces portions de configurations comme la combinaison linéaire des configurations d'espèces biochimiques dans lesquelles elles apparaissent pondérés par le nombre de leurs occurrences dans ces configurations, définit alors un changement de variables. Le système différentiel réduit, qui décrit l'évolution de la valeur de ces combinaisons linéaires peut alors être dérivé directement, sans avoir à générer le système différentiel initial.

En chapitre 5, cette analyse est portée à la réduction de la sémantique stochastique. Trois cas d'études sont donnés pour expliquer les principals enjeux de la réduction de la sémantique stochastique des modèles de réécriture de graphes à sites. Il en ressort, que la sémantique stochastique est beaucoup plus difficile à reduire que la différentielle. En effet, en stochastique, des pas de calculs peuvent agir de manière conjointe sur deux morceaux de configurations d'espèces biochimiques, ce qui impose d'en connaître les corrélations. Par ailleurs, des termes de différents ordres de grandeur apparaissent. Certains sont à l'origine de petits flots d'information qui établissent des correlations entre les états de différents morceaux de configurations des espèces biochimiques. Ces termes disparaissent dans la sémantique différentielle à la limite thermodynamique. Une analyse statique est alors proposée pour identifier des morceaux de configurations de protéines dont les occurrences se comportent de manière indépendante. Il en résulte une relation de bisimulation avant-arrière : les états équivalents à échange de morceaux d'occurrences de protéines près se comportent de la même manière vis à vis des classes d'équivalence d'états, et par ailleurs, les probabilités des états équivalents sont liées, au cours du temps, par des relations de proportionalité.

En chapitre 6 est proposé un cadre pour inférer, raisonner et exploiter les symétries potentielles dans les ensembles de règles Kappa. La présentation se concentre sur le cas des paires de sites qui exercent exactement les mêmes capacités d'interaction. Il en découle une notion de symétrie qui peut s'appliquer aux motifs, aux plongements, aux règles et aux pas de calculs, et qui définie une relation de bisimulation avant-arrière à la fois pour la sémantique différentielle et la sémantique stochastique. Ainsi, dans un modèle généré par un ensemble de règles symétriques, deux états symétriques – en sémantique différentielle – et deux distributions symétriques d'états – en sémantique stochastique – se comportent de la même manière par rapport respectivement aux classes de symétries des états et à celles des distributions d'états. Par ailleurs, si l'état initial ou si la distribution initiale des états sont symétriques, ils le restent tout au long de l'exécution du système.
Ce document se conclut en chapitre 7 et quelques perspectives sont données. La description du langage et de l'analyse reste volontairement assez haut niveau. Une formalisation complète et rigoureuse est disponible dans les articles scientifiques qui sont cités dans le corps du texte.
# Chapitre 2

## Réécriture de graphes à sites

Le chapitre présent décrit, dans un premier temps, la notion de graphe à sites, qui permettra de représenter à la fois les différents états possibles pour les systèmes modélisés, mais aussi, les motifs qui seront utilisés, dans un second temps, pour décrire, grâce à des règles de réécriture, l'évolution de l'état de ces systèmes.

### 2.1 Signature

Il faut tout d'abord définir la signature des modèles. La signature d'un modèle décrit tous les ingrédients qui peuvent intervenir dans celui-ci. Elle peut être représentée graphiquement par une *carte de contacts*, comme celle dessinée en figure 2.1. Une carte de contacts comprend des nœuds pour représenter les différentes *sortes de protéines*. Ces nœuds sont nommés et adoptent des formes et des couleurs variées pour les distinguer plus facilement. Chaque sorte de protéines est associée à un ensemble de *sites d'interaction*. Ces sites sont représentés en périphérie de chaque sorte de protéines par des cercles colorés et nommés, eux-aussi. En Kappa, une sorte de protéines donnée ne peut avoir deux sites portant le même nom. Chaque site d'interactions est associé à un ensemble de pastilles colorées qui peuvent servir à représenter son état d'activation, comme par exemple le fait d'être – ou non – phosphorylé ou comme le fait d'être méthylé – ou non. Un état d'activation peut aussi éventuellement servir à représenter la localisation d'une occurrence d'une protéine au sein d'un ensemble fini et fixe de compartiments cellulaires. Les sites d'interactions peuvent également porter un état de liaison : les sites qui portent le symbole `|` peuvent potentiellement rester libre ; la carte de contacts contient aussi des arcs non-orientés entre les sites qui peuvent potentiellement être liés deux à deux. En particulier, un site peut être lié à plusieurs sites dans la carte de contacts (il sera expliqué plus tard que de telles liaisons sont en compétition). Par ailleurs, un site peut être lié à lui-même dans une carte de contacts (il sera expliqué plus tard que ceci signifie que deux sites de deux occurrences différentes d'une même sorte de protéines peuvent être liés entre-eux).

**Exemple 2.1.1** *En figure 2.1 est donné un exemple de carte de contacts qui correspond aux premières interactions qui interviennent dans l'activation du facteur de croissance de l'épiderme. Cet exemple est inspiré d'un modèle BNGL disponible dans la littérature [9]. Ce modèle a été étendu pour décrire la liaison asymétrique entre les récepteurs EGFR et traduit en Kappa. Cette carte introduit cinq sortes de protéines : des ligands*.*

<figure><img src="image_10.png" /><figcaption>Figure 2.1: Une carte de contacts. Elle définit la signature d'un modèle en donnant la liste de toutes les sortes de protéines, leurs différents sites d'interactions, les différents états internes que peuvent prendre ces sites et les différentes liaisons potentielles entre ces sites.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 2.2: Une configuration d'une espèce biochimique. Elle contient plusieurs occurrences de protéines. Chaque occurrence documente l'ensemble de ses sites d'interactions. Les sites qui peuvent porter un état interne en ont un. Par ailleurs, les sites sont soit libres, soit liés deux à deux.</figcaption></figure>

EGF, des récepteurs membranaires EGFR, des protéines d'échafaudage ShC, des protéines de transport Grb2 et des protéines cibles Sos (ces dernières seront ensuite phosphorylées ce qui initiera les étapes suivantes de la cascade d'interactions). Chaque occurrence du ligand EGF a un seul site qui est nommé *r* ; chaque occurrence du récepteur membranaire EGFR à six sites qui sont nommés respectivement *l*, *r*, *c*, *n*, *Y48* et *Y68* ; chaque occurrence de la protéine d'échafaudage ShC dispose de deux sites qui sont nommés respectivement *Y7* et *pi* ; chaque occurrence de la protéine de transport Grb2 a deux sites qui sont respectivement nommés *a* et *b* ; enfin chaque occurrence de la protéine cible Sos a un seul site qui est nommé *d*. Seuls les sites *Y48* et *Y68* des occurrences de la protéine EGFR et le site *Y7* des occurrences de la protéine ShC portent un état interne. Ces sites sont annotés par deux pastilles colorées, une blanche et une noire. La pastille blanche indique que ces sites peuvent être dans l'état non phosphorylé, alors que la noire indique que ces sites peuvent être dans l'état phosphorylé. De plus, chaque site peut être libre (symbole ∨) ou lié. Les liaisons possibles entre sites sont entre le site *r* d'une occurrence de la protéine EGF et le site *l* d'une occurrence de la protéine EGFR ; entre les sites *r* de deux occurrences différentes de la protéine EGFR ; entre le site *c* et le *n* des occurrences de la protéine EGFR (il sera bientôt expliqué que la carte de contacts ne précise pas si ce doit être entre deux occurrences différentes de la protéine EGFR) ; entre le site *Y48* d'une occurrence de la protéine EGFR et le site *pi* d'une occurrence de la protéine ShC ; entre le site *a* d'une occurrence de la protéine Grb2 et le site *Y68* d'une occurrence de la protéine EGFR ; entre le site *a* d'une occurrence de la protéine Grb2 et le site *Y7* d'une occurrence de la protéine ShC (il y a donc conflit entre ces deux liaisons potentielles) ; enfin entre le site *b* d'une occurrence de la protéine Grb2 et le site *d* d'une occurrence de la protéine Sos.

## 2.2 Configurations d'espèces biochimiques

Les modèles Kappa décrivent l'évolution d'une soupe d'occurrences de *configurations d'espèces biochimiques*. Une configuration d'espèces biochimiques est formée de plusieurs occurrences de protéines. Chaque occurrence d'une protéine est associée à un ensemble de sites d'interactions. Chaque site peut éventuellement porter un état d'activation, mais un seul. De ce fait, si un site peut être activé de deux manières différentes, avec un état de phosphorylation et un état de méthylation par exemple, ou si un site peut être doublement activé, doublement phosphorylé par exemple, il est important de définir une pastille différente pour toutes les combinaisons potentielles d'états de ce site. Enfin, chaque site doit être soit libre, soit lié à exactement un autre site. Contrairement à la carte de contacts, un site ne peut pas être lié à lui-même dans une configuration d'espèces biochimiques. De plus, un site ne peut pas être lié simultanément à deux sites. Une configuration d'espèces biochimiques forme un graphe connexe, ce qui signifie qu'il est possible de passer de n'importe quelle occurrence de protéines à n'importe quelle autre, en suivant zéro, un ou plusieurs liens.
**Exemple 2.2.1** *En figure 2.2 est donné l'exemple d'une configuration d'espèces biochimiques. Celle-ci est formée de deux occurrences du ligand EGF, de deux occurrences du récepteur membranaire EGFR, de deux occurrences de la protéine d'échafaudage ShC, de deux occurrences de la protéine de transport Grb2 et d'une occurrence de la protéine Sos. Chaque occurrence du récepteur membranaire est liée au site r d'une occurrence du ligand par son site l. Les occurrences du récepteur membranaire forment un dimère grâce à une double liaison, une liaison symétrique par leurs sites r respectifs et une liaison asymétrique entre le site c de l'un et le site n de l'autre. L'occurrence du récepteur membranaire dont le site c est lié, a son site Y68 phosphorylé et libre, alors que son site Y48 est phosphorylé et lié au site pi d'une occurrence de la protéine d'échafaudage. Le site Y7 de cette occurrence de la protéine d'échafaudage est phosphorylé et lié au site a d'une occurrence de la protéine de transport dont le site b est lié au site d d'une occurrence de la protéine Sos. L'autre occurrence du récepteur a son site Y48 phosphorylé et lié au site pi de l'autre occurrence de la protéine d'échafaudage. Le site Y7 de cette occurrence de la protéine d'échafaudage n'est ni phosphorylé, ni lié à un autre site. Enfin, le site Y68 de cette seconde occurrence du récepteur membranaire est lié au site a de l'autre occurrence de la protéine de transport. Celle-ci a son site b libre.*

La signature d'un modèle restreint l'ensemble des configurations des espèces biochimiques de ce modèle. Toutes les configurations des espèces biochimiques qui sont correctes du point de vue de la syntaxe ne sont ainsi pas adéquates. Ce rôle est assuré par la carte de contacts, qui d'une part, donne la liste de tous les sites d'interactions de chaque sorte de protéines en indiquant lesquels peuvent porter un état de liaison et un état d'activation et d'autre part, résume l'ensemble des états potentiels de ces sites. Plus précisément, toute occurrence de protéines dans la configuration d'une espèce biochimique doit mentionner les mêmes sites que le nœud correspondant dans la carte de contacts. De plus, un site dont le site correspondant dans la carte de contacts admet au moins un état d'activation doit nécessairement avoir un état d'activation. Il en est de même pour l'état de liaison. Ces contraintes assurent que l'état de chaque occurrence de protéines d'une configuration d'espèces biochimiques est entièrement défini. Trois contraintes supplémentaires assurent que l'état des sites est conforme à la carte de contacts : premièrement, un site ne peut porter un état d'activation que si le site correspondant dans la carte de contacts porte également cet état d'activation ; deuxièmement, un site ne peut être libre que si le site correspondant dans la carte de contacts peut l'être lui-aussi ; troisièmement, deux sites ne peuvent être liés que si les deux sites correspondants le sont également dans la carte de contacts. Ces trois dernières contraintes peuvent se formaliser par le fait que chaque configuration d'une espèce biochimique se projette sur la carte de contacts : ainsi la fonction qui associe à chaque nœud d'une configuration d'espèces biochimiques l'unique nœud de la même sorte dans la carte de contacts doit être un *homomorphisme*. En d'autres termes, la carte de contacts peut être vue comme un repliage de toutes les configurations d'espèces biochimiques du modèle et chaque nœud de la carte de contacts résume toutes les configurations possibles des protéines du type correspondant.

**Exemple 2.2.2** *En figure 2.3 est représentée la projection entre la configuration de l'espèce biochimique dessinée dans la figure 2.2 et la carte de contacts donnée en figure 2.1. Cette projection montre que cette configuration d'espèces biochimiques est compatible avec cette carte de contacts.*

## 2.3 Motifs

L'évolution des configurations d'espèces biochimiques est décrite par des règles de réécriture. Celles-ci définissent à la fois les conditions qui doivent être réalisées pour qu'une interaction puisse avoir lieu et les effets potentiels de cette interaction. Avant d'expliquer ce que sont ces règles de réécriture, il est nécessaire d'expliquer la notion de motifs. Celle-ci permet de spécifier sous quelles conditions une interaction peut avoir lieu.

Nous nous concentrons sur les motifs connexes. Des motifs plus élaborés peuvent être obtenus en juxta-
posant plusieurs motifs connexes. Un motif connexe est une portion contigüe dans la configuration d'une espèce
biochimique. De ce fait, il peut comporter zéro, une ou plusieurs occurrences de chaque sorte de protéines.
Chaque occurrence de protéines est associée à un ensemble de sites d'interactions. Chaque site peut éventuelle-
ment porter un état d'activation. Enfin chaque site peut être libre, lié sans que le site auquel il est lié ne soit
précis ou lié exactement à un autre site (différent de lui-même donc). L'état de liaison d'un site peut également
ne pas être spécifié.

**Exemple 2.3.1** *En figure 2.4 est donné un exemple de motif connexe. Ce motif est formé de deux occurrences du récepteur membranaire EGFR et d'une occurrence de la protéine d'échafaudage ShC. L'occurrence de la*
<figure><img src="image_12.png" /><figcaption>Figure 2.3: L'unique projection entre la configuration de l'espèce biochimique de la figure 2.2 et la carte de contacts de la figure 2.1. Cette projection est obtenue en associant chaque occurrence de protéines de la configuration de l'espèce biochimique à l'unique sorte de protéines correspondante dans la carte de contacts.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 2.4: Un motif connexe. Il contient plusieurs occurrences de protéines. Chaque occurrence de protéines documente un sous ensemble de ses sites d'interactions. Chaque site peut éventuellement porter un état interne et éventuellement un état de liaison (en conformité avec la signature du modèle, donnée en figure 2.1). Comme état de liaison, un site peut être libre, lié sans que le site partenaire ne soit précisé ou être lié à un autre site.</figcaption></figure>

protéine d'échafaudage mentionne uniquement son site pi. Celui-ci est lié au site Y48 d'une des deux occurrences du récepteur membranaire. L'état d'activation de ce dernier site n'est pas précisé. Cette occurrence du récepteur membranaire mentionne également son site Y68, sans en préciser ni l'état interne ni l'état de liaison, et son site r, lui-même lié au site r de l'autre occurrence du récepteur membranaire. Cet autre occurrence mentionne également son site Y48 qui est phosphorylé mais dont l'état de liaison n'est pas spécifié et son site l qui est lié à un site qui n'est pas précisé.

Comme c'était le cas pour les configurations d'espèces biochimiques, la carte de contacts contraint les motifs que l'on peut écrire dans un modèle. Ainsi, une occurrence de protéines dans un motif ne peut comporter que des sites d'interactions qui sont associés à cette sorte de protéines dans la carte de contacts. Un site ne peut porter un état d'activation que si le site correspondant dans la carte de contacts admet cet état d'activation. Un site ne peut être libre que si le site correspondant peut être libre dans la carte de contacts. Un site ne peut être lié sans préciser à quel site que si le site correspondant est lié à au moins un site dans la carte de contacts. Enfin, deux sites ne peuvent être liés ensemble que si les deux sites correspondants sont liés ensemble dans la carte de contact. En d'autres termes, comme c'était le cas pour les configurations d'espèces biochimiques, il doit être possible de projeter le motif sur la carte de contacts.

## 2.4 Plongements entre motifs

Un motif peut contenir plus ou moins d'information. En effet, il est possible d'ajouter des sites dans l'occurrence d'une protéine qui ne mentionne pas tous ses sites. Par ailleurs, il est possible d'ajouter un état de liaison et/ou un état interne à un site qui en manque. Il est possible de préciser à quel site un site est lié quand le partenaire de celui-ci n'est pas précisé. Il est même possible de lier un site au site d'une nouvelle occurrence de protéines.
<figure><img src="image_14.png" /><figcaption>Figure 2.5: Deux plongements entre le motif donné dans la figure 2.4 et la configuration d'espèces biochimiques donnée dans la figure 2.2. En 2.5(a) l'occurrence de la protéine d'échafaudage est associée à l'occurrence de la protéine d'échafaudage dont le site Y7 est libre. En 2.5(b) l'occurrence de la protéine d'échafaudage est associée à l'occurrence de la protéine d'échafaudage dont le site Y7 est lié.</figcaption></figure>

Nous dirons alors que le premier motif apparaît dans le second ou encore que le second motif contient une occurrence du premier. Dans ce cas, la relation entre les occurrences de protéines du motif initial et celle du motif ainsi obtenu est formalisée par un plongement. Un plongement d'un motif vers un autre motif est une fonction qui envoie chaque occurrence de protéines du premier motif vers une occurrence de protéines du second tout en préservant la structure des graphes à sites, c'est à dire les sortes de protéines, les sites qui sont mentionnés, les états internes et les états de liaisons qui sont documentés.

Il est intéressant de remarquer que les configurations d'espèces biochimiques sont des motifs connexes particuliers. Dans ces derniers, chaque occurrence de protéines décrit tous ses sites, avec un état interne et un état de liaison quand ils en ont un. Il n'est donc pas possible d'ajouter d'information dans la configuration d'une espèce biochimique. Une configuration d'espèces biochimiques ne peut se plonger dans aucun autre motif connexe.

**Exemple 2.4.1** Deux exemples de plongements d'un motif dans une configuration d'espèces biochimiques sont donnés en figure 2.5. Ce sont les seuls plongements entre ce motif et cette configuration d'espèces biochimiques. Dans le premier (voir en figure 2.5(a)) l'unique occurrence de la protéine d'échafaudage du motif est associée à l'occurrence de la protéine d'échafaudage de la configuration d'espèces biochimiques dont le site Y7 est libre. L'occurrence du récepteur membranaire qui est liée à l'occurrence de la protéine d'échafaudage du motif est associée à l'occurrence du récepteur membranaire qui est liée à l'occurrence de la protéine d'échafaudage dont le site Y7 est libre. Enfin, l'autre occurrence du récepteur membranaire du motif est associé à l'autre occurrence du récepteur membranaire. Il est possible de remarquer que le site 1 de cette dernière occurrence du récepteur est lié dans le motif, sans que le site partenaire ne soit précisé, alors qu'il est explicitement lié au site r d'une occurrence du ligand dans de la configuration de l'espèce biochimique.

Dans le second plongement (voir en figure 2.5(b)) l'occurrence de la protéine d'échafaudage du motif est associée à l'occurrence de la protéine d'échafaudage de la configuration d'espèces biochimiques dont le site Y7 est lié. L'occurrence du récepteur membranaire qui est liée à l'occurrence de la protéine d'échafaudage du motif est associée à l'occurrence du récepteur membranaire qui est liée à l'occurrence de la protéine d'échafaudage dont le site Y7 est lié. Enfin, l'autre occurrence du récepteur membranaire du motif est associée à l'autre occurrence
<figure><img src="image_15.png" /><figcaption>Figure 2.6: Un isomorphisme entre deux motifs. Il est possible de contruire un plongement en associant, par exemple, l'occurrence de gauche de la protéine *EGFR* du motif du bas à celle de droite du motif du haut. Réciproquement, il est possible de construire un plongement en associant, par exemple l'occurrence de gauche de la protéine *EGFR* du motif du haut à celle de droite du motif du bas.</figcaption></figure>

du récepteur membranaire de la configuration de l'espèce biochimique.

Il est important de remarquer qu’un plongement d’un motif connexe vers un autre motif est entièrement caractérisé par l’image d’une occurrence de protéines. Pour avoir les autres associations, il suffit de suivre les liens et d’utiliser le fait qu’ils sont nécessairement préservés par le plongement. Cette propriété facilite la recherche d’occurrences de motifs dans les autres. Les graphes Kappa sont dits rigides [53, 117].

## 2.5 Isomorphismes entre motifs

Deux motifs sont *isomorphes* si et seulement si il existe un plongement de l'un vers l'autre, et réciproquement. Ces deux plongements sont alors appelés des *isomorphismes*. De ce fait, l'occurrence d'une protéine et son image par un isomorphisme contienne exactement la même information : ce sont des occurrences de la même protéine ; elles documentent les mêmes états internes et les mêmes états de liaisons ; enfin, si deux sites sont liés, leurs images par l'isomorphisme sont également liées. Un isomorphisme entre deux motifs connexes est caractérisé par l'association de l'occurrence d'une protéine du premier motif et de l'occurrence d'une protéine du second motif. Il convient alors de vérifier, en suivant les liens entre paires de sites, que cete association se prolonge bien en un isomorphisme.

**Exemple 2.5.1** *En figure 2.6 est donné un exemple d'isomorphisme entre deux motifs.*

Il s'agit d'un motif comprenant trois occurrences de protéines, deux occurrences de la protéine EGFR et une occurrence de la protéine ShC. L'occurrence de la protéine ShC documente son site pi qui est lié au site Y48 de la première occurrence de la protéine EGFR. L'état interne de ce site n'est pas documenté. La première occurrence de la protéine EGFR documente également le site Y68 sans préciser ni son état de liaison, ni son état interne et le site r qui est lié au site r de la deuxième occurrence de la protéine EGFR. Cette dernière a son site l lié, sans que ne soit préciser à quel site ce site est lié. Elle documente également le site Y48 qui est phosphorylé, mais dont l'état de liaison n'est pas spécifié.

Le motif est représenté de deux manières isomorphes en inversant l'ordre dans lequel les occurrences de protéines sont dessinées. La relation entre les occurrences de protéines dans les deux représentations de motifs sont exprimées par un isomorphisme.

Par ailleurs, un plongement d'un motif dans lui-même est appelé un *automorphisme*.

**Exemple 2.5.2** *En figure 2.7 sont donnés des exemples de motifs qui admettent des automorphismes non triviaux, c'est-à-dire non réduits à la fonction qui associe chaque occurrence de protéine à elle-même. Dans*
<figure><img src="image_16.png" /><figcaption>Figure 2.7: Deux exemples de motifs avec leur nombre d'automorphismes. En 2.7(a), le motif comporte exactement 2 automorphismes : l'automorphisme trivial et celui engendré par la transformation miroir qui échange les occurrences deux occurrences de la protéine *EGFR*. En 2.7(b), le motif comporte exactement 4 automorphismes : chaque automorphisme est engendré par l'association d'une occurrence donnée de la protéine *A* donnée à l'une des quatre occurrences, ce qui consiste à faire opérer une permutation circulaire sur les occurrences de la protéine *A*.</figcaption></figure>

Le premier, figure 2.7(a), un motif est composé de deux occurrences de la protéine EGFR liées entre elles par leur site *r* respectif. Chacune mentionne que son site *l* est lié (sans précisé à quel site) et que sont site Y68 est phosphorylé et lié au site *a* d'une occurrence de la protéine Grb2 dont le site *b* n'est pas documenté. Ce motif admet une symétrie mirror. En effet, il est possible d'échanger les deux moitiés du motif en échangeant les deux occurrences du site *r* dans les occurrences de la protéine EGFR. Dans le second, figure 2.7(b), quatre occurrences d'une protéine *P* sont liées circulairement par leurs sites *g* et *d*, le site *g* de chaque occurrence de la protéine *A* étant lié au site *d* d'une autre protéine. Il est possible d'opérer une permutation circulaire des occurrences de la protéine *A* tout en conservant le même motif, ce qui permet d'obtenir les 4 automorphismes du motif.

Il n'existe en fait que deux types d'automorphismes non-triviaux : les automorphismes miroir qui sont engendrés par l'échange de deux sites du même type qui sont liés entre eux (voir figure 2.7(a)) et les automorphismes circulaires qui sont engendrés par l'échange d'une partie d'un motif qui se répète en formant un anneau (voir figure 2.7(b)).

## 2.6 Règles d'interaction

Les motifs permettent de spécifier l'évolution potentielle de l'état des systèmes modélisés en Kappa, grâce à des règles de réécriture. Afin de simplifier la présentation, seul un fragment du langage Kappa est présenté. En particulier, les règles de réécriture qui sont introduites dans cette section n'engendrent pas d'effets de bord. Un effet de bord est une transformation à l'extérieur du membre gauche des règles. Les effets de bords peuvent être dus à des sites libérés sans préciser à quels sites ils sont liés ou à des occurrences de protéines dégradées. Ces constructions n'ont pas été considérées afin de simplifier la présentation et de présenter tous les différents concepts de la syntaxe et de la sémantique de Kappa sous forme graphique.

Les occurrences de configurations d'espèces biochimiques peuvent se transformer en appliquant des règles d'interactions. Une règle d'interaction est définie par une paire de motifs, qui contiennent exactement les mêmes sortes de protéines. Le premier motif spécifie quelles conditions locales doivent être réalisées pour permettre à l'interaction de se produire. La différence entre ces deux motifs décrit quelle transformation résulte de cette interaction. Aussi le second motif d'une règle doit pouvoir être obtenu à partir du premier en changeant uniquement l'état interne et/ou de liaison de certains sites d'interactions.

**Exemple 2.6.1** Des exemples de règles d'interactions sont données en figure 2.8. Celles-ci décrivent les interactions qui sont impliquées dans le recrutement des occurrences de la protéine cible par les occurrences du récepteur membranaire par leur site Y68, dans le modèle des premières étapes de l'acquisition du facteur de croissance de l'épiderme. Le recrutement par le site Y48 implique des règles d'interactions similaires, qui ne seront donc pas détaillées. La colonne de gauche décrit les interactions qui font progresser le recrutement d'une occurrence de la protéine cible. La première étape est l'activation d'une occurrence du récepteur membranaire par une occurrence du ligand (voir en figure 2.8(a)). En se liant à une occurrence du ligand, une occurrence du récepteur change de conformation et peut alors établir une liaison symétrique avec une autre occurrence du
<figure><img src="image_17.png" /><figcaption>Figure 2.8: Règles d'interactions impliquées dans le recrutement d'une occurrence de la protéine cible par la voie de signalisation courte (sans passer par la protéine d'échafaudage).</figcaption></figure>

récepteur qui doit pour cela être elle-même activée (voir en figure 2.8(c)). Comme seules les occurrences du ligand peuvent se lier aux sites l des occurrences du récepteur, il n'est pas nécessaire de mentionner les occurrences du ligand dans la règle. Il suffit d'écrire que les sites l des deux occurrences du récepteur doivent être liés sans préciser à quels sites. Après cette étape, les deux occurrences du récepteur tiennent le même rôle. Pour les distinguer, une liaison asymétrique peut alors s'établir (voir en figure 2.8(e)) entre le site c d'une des deux occurrences et le site n de l'autre occurrence. Le site Y68 de l'occurrence du récepteur qui est liée par son site c peut alors se faire phosphoryler par l'autre occurrence du récepteur membranaire (voir en figure 2.8(g)). Cela change la conformation de cette occurrence du récepteur membranaire et lui permet de se lier à une occurrence de la protéine de transport (voir en figure 2.8(i)). Indépendamment, les occurrences de la protéine de transport peuvent se lier aux occurrences de la protéine cible (voir en figure 2.8(k)).

Chacune de ces interactions est réversible. Cependant les interactions inverses ne peuvent s'effectuer que sous certaines conditions. Ces interactions sont décrites dans la colonne de droite. Les liaisons symétriques entre les occurrences du récepteur membranaire capturent les occurrences du ligand qui ne peuvent alors pas se libérer (voir en figure 2.8(b)). Les liaisons asymétriques empêchent les liaisons symétriques de se briser (voir en figure 2.8(d)). Les liaisons asymétriques peuvent se briser sans condition (voir en figure 2.8(f)). La phosphorylation du site Y68 d'une occurrence du récepteur est bloquée quand ce site est lié (voir en figure 2.8(h)). Les liaisons entre les occurrences du récepteur et les occurrences de la protéine de transport d'une part, et celles entre les occurrences de la protéine de transport et celles de la protéine cible d'autre part, peuvent se défaire sans condition (voir en figures 2.8(j) et 2.8(l)).
<figure><img src="image_18.png" /><figcaption>Figure 2.9: Un exemple d'isomorphisme entre deux règles. Il s'agit de la règle qui vient ajouter une liaison asymétrique entre le site *c* et le site *n* respectif de deux occurrences de la protéine *EGFR* déjà liées par leurs sites *r*. Cette règle d'interaction existe sous deux formes isomorphes selon que l'occurrence de la protéine *EGFR* qui lie son site *n* soit à droite ou à gauche du membre gauche de la règle.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Figure 2.10: Deux exemples de règles avec leur nombre d'automorphismes. En 2.10(a), la règle d'interaction ne comporte que l'automorphisme trivial. En 2.10(b), la règle d'interaction comporte exactement 2 automorphismes : l'automorphisme trivial d'une part et l'automorphisme qui consiste à échanger les deux occurrences de la protéine *EGFR* d'autre part.</figcaption></figure>

Dans le langage complet, il est possible de détruire un lien entre deux occurrences de protéines en ne spécifiant qu'un seul des deux sites de liaisons. De plus, une règle peut également détruire des occurrences de protéines. Ces constructions peuvent induire des effets de bord, puisqu'appliquer de telles interactions est susceptible de libérer des sites qui ne sont pas décrits dans les membres gauches des règles correspondantes. Par ailleurs, le langage complet permet aussi de synthétiser de nouvelles occurrences de protéines.

## 2.7 Isomorphismes entre règles

Il est possible de changer les membres gauches et droits d'une règle d'interaction par un isomorphisme commun. La règle obtenue et la règle initiale seront alors dites *isomorphes*.

**Exemple 2.7.1** En Fig. 2.9 est donné un exemple d'isomorphisme entre deux règles d'interaction. La règle en question est la règle de liaison asymétrique (voir en figure 2.8(e)) qui ajoute une liaison asymétrique entre le site *c* et la site *n* de deux occurrences de la protéine *EGFR* à la condition que celles-ci soient déjà liées par leurs sites *r*. Dans la règle initiale, l'occurrence de la protéine *EGFR* qui lie son site *c* est à gauche dans le membre gauche de la règle. En échangeant les deux occurrences de la protéine *EGFR* dans le membre gauche et dans le membre droit de la règle, une autre règle est obtenue, isomorphe à la première.

Comme pour les motifs, un isomorphisme d'une règle vers elle-même est appelé un *automorphisme*.

**Exemple 2.7.2** Deux exemples de règles sont donnés en figure 2.10, avec leurs nombres d'automorphismes. La première règle d'interaction, en 2.10(a) est celle de la liaison asymétrique entre deux occurrences de la protéine *EGFR*. Ces deux occurrences ne sont pas dans le même état dans le membre droit de la règle. En effet, la première a son site *c* lié, alors qu'il est libre dans la seconde. La règle ne comporte donc qu'un automorphisme : l'automorphisme triviale qui ne procède à aucun échange d'occurrences de protéines. La seconde règle d'interaction, en 2.10(b) est celle de la liaison symétrique entre deux occurrences de la protéine *EGFR*. Cette fois-ci les deux occurrences peuvent être échanger dans le membre gauche et dans le membre droit
<figure><img src="image_20.png" /><figcaption>(a) La règle de liaison symétrique entre deux occurrences de la protéine A.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(c) La règle de liaison asymétrique entre deux occurrences de la protéine A.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(b) La règle de liaison symétrique entre deux occurrences de la protéine A dessinée sous la forme d'un motif.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(d) La règle de liaison asymétrique entre deux occurrences de la protéine A dessinée sous la forme d'un motif.</figcaption></figure>

Figure 2.11: Règles vues comme des motifs dont l'interface des occurrences de protéines a été dupliquée. En 2.11(a) est rappelée la règle pour former une liaison symétrique entre deux occurrences de la protéine A. En 2.11(b) est représentée la même règle, mais sous forme de motif unique. Des sites ont été ajoutés à chaque occurrence du motif du membre gauche pour représenter le membre droit. Leurs noms ont été primés et leurs contours sont dessinés en rouge. Leurs états sont également dessinés en rouge. Le motif obtenu admet exactement deux automorphismes, quitte à échanger les deux occurrences de la protéine A ou non. C'est effectivement le nombre d'automorphismes admis par la règle représentée par ce motif. En 2.11(c) est rappelée la règle pour former une liaison asymétrique entre deux occurrences de la protéine A. En 2.11(d), cette règle est représentée sous forme d'un motif. Ici encore, l'état du membre droit de la règle a été ajouté au membre gauche en rouge avec des sites aux noms primés. Ce dernier motif n'admet que l'automorphisme trivial, comme c'était effectivement le cas également avec la règle correspondante.

sans changer la règle d'interaction. La règle admet donc exactement deux automorphismes : l'automorphisme trivial d'une part, et l'automorphisme qui consiste à échanger les deux occurrences de la protéine d'autre part.

Il est en fait possible de voir les isomorphismes et les automorphismes de règles comme des isomorphismes et des automorphismes de motifs, quitte à dupliquer chaque site dans la signature du modèle, avec une version du site documentant l'état du site dans le membre gauche de la règle et une autre documentant celui dans le membre droit.

**Exemple 2.7.3** En figure 2.11 sont donnés deux exemples de règles et leurs représentations sous forme de motifs uniques. Cette dernière s'obtient en dupliquant les sites qui apparaissent dans les occurrences de protéines dans les membres de la règle. Ainsi pour chaque site apparaissant dans une occurrence de protéines dans la règle représentée, deux sites figurent dans l'occurrence correspondante du motif : un site avec le même nom qui représente le site et son état dans le membre gauche de la règle et un site avec le nom primé et le contour en rouge qui représente lui le site et son état dans le membre droit. L'état des sites primés est également dessiné en rouge.

La première règle donnée en exemple est celle de formation des liaisons symétriques entre deux occurrences de la protéine EGFR. Que ce soit dans la représentation sous forme de règle (voir en figure 2.11(a)) ou dans celle sous forme de motif unique (voir en figure 2.11(b)), les deux occurrences de la protéine peuvent être échangées sans modifier la règle ou le motif. Il y donc bien exactement deux automorphismes dans la règle et dans sa représentation sous forme de motif unique. La seconde règle est celle de la formation des liaisons asymétriques dans les configurations du dimère de la protéine A. Il n'y a qu'un automorphisme dans la règle car l'état du site n n'est pas le même dans les deux occurrences de la protéine A dans son membre droit (voir en figure 2.11(c)). De même, dans la représentation sous forme de motif unique, il n'y a qu'un automorphisme car l'état du site n' n'est pas le même dans les deux occurrences de la protéine (voir en figure 2.11(d)).

## 2.8 Réactions induites par une règle d'interaction

Comme signalé précédemment, le membre gauche d'une règle d'interactions spécifie dans quel contexte cette interaction peut avoir lieu. Il est alors possible d'ajouter des contraintes sur les conditions d'application d'une
règle en raffinant les motifs qui apparaissent dans les membres gauches et droits des règles exactement de la même manière. Une règle d'interactions qui ne peut plus être raffinée (sans ajouter de nouvelles composantes connexes) est alors appelée une règle-réaction [93].

**Exemple 2.8.1** *En figure 2.12 est montré un exemple de deux raffinements d'une même règle d'interactions en deux règles-réactions. La règle d'interactions est celle qui permet de casser, en l'absence de lien asymétrique, le lien symétrique entre deux occurrences du récepteur membranaire (voir en figure 2.8(d)).*

1. Dans le premier raffinement (voir en figure 2.12(a)), la règle est appliquée à un dimère dont la première occurrence du récepteur est liée par son site Y48 à une occurrence de la protéine d'échafaudage dont le site Y7 est libre et phosphorylé et par son site Y68 à une occurrence de la protéine de transport elle-même liée à une occurrence de la protéine cible. La deuxième occurrence du recepteur de ce dimère est liée par son site Y48 à une occurrence de la protéine d'échafaudage dont le site Y7 est libre et non phosphorylé et par son site Y68 à une occurrence de la protéine de transport dont le site b est libre.

2. Dans le second (voir en figure 2.12(b)), les deux occurrences de la protéine d'échafaudage ont été inter-
verties. Ainsi, la règle est appliquée à un dimère dont la première occurrence du récepteur est liée par son
site Y48 à une occurrence de la protéine d'échafaudage dont le site Y7 est libre et non phosphorylé et par
son site Y68 à une occurrence de la protéine de transport elle-même liée à une occurrence de la protéine
cible. La seconde occurrence du récepteur de ce dimère est liée par son site Y48 à une occurrence de la
protéine d'échafaudage dont le site Y7 est libre et phosphorylé et par son site Y68 à une occurrence de la
protéine de transport dont le site b est libre.

Bien que les deux configurations d'espèces biochimiques qui apparaissent dans les membres gauches de ces deux règles-réactions soient formés exactement des mêmes occurrences de protéines et dans les mêmes configurations, puisque seul l'agencement entre ces occurrences change, il apparaît que les deux règles-réactions obtenues ne produisent pas les mêmes configurations d'espèces biochimiques. Ceci justifie pleinement le choix, dans Kappa, de représenter la topologie des liens entre les occurrences de protéines. Sans celle-ci il est impossible de décrire fidèlement la séparation des occurrences de récepteurs, tout en respectant la distribution des différentes occurrences de protéines et de leurs configurations dans chacune des configurations d'espèces biochimiques résultant de cette séparation. Par exemple, dans le langage BCS [61], les configurations d'espèces biochimiques sont représentées par l'ensemble des occurrences de protéines qui les constituent, ainsi que leurs configurations, mais sans préciser la topologie des liens entre ces occurrences de protéines. Aussi il est impossible de représenter fidèlement la règle de déliaison qui est dessinée en figure 2.8(d) dans ce langage.

2.9 Réseaux de réactions sous-jacents

Un ensemble de règles peut alors être traduit en un ensemble – éventuellement infini – de règles-réactions en remplaçant chaque règle d'interactions par l'ensemble des règles-réactions qui peuvent être obtenues comme raffinement de ces règles. Ensuite, quitte à donner un nom à chaque configuration d'espèces biochimiques qui peut intervenir dans les règles-réactions ainsi obtenues, ces règles-réactions peuvent être assimilée à un réseau de réactions (éventuellement infini), dans lequel chaque réaction est spécifiée par une liste de réactifs et une liste de produits parmi un ensemble d'espèces biochimiques représentées uniquement par des noms (en passant sous silence leurs structures biochimiques). Ce réseau de réactions est défini de manière unique modulo le choix des noms associés aux espèces biochimiques.

**Exemple 2.9.1** *Pour conclure cette section, nous détaillons la génération d'un réseau de réactions à partir d'un ensemble jouet de règles Kappa. Nous considérons un modèle avec une seule sorte de protéines qui admet deux sites, g et d, chacun pouvant être phosphorylé ou non. La signature du modèle est donnée par la carte de contacts qui est dessinée en figure 2.13(a). Le phosphorylation et la déphosphorylation de chaque site dans une occurrence de protéines peut se faire indépendamment de l'état de l'autre site, ce qui est formalisé dans les quatre règles données en figure 2.13(b). Ainsi ni les règles de phosphorylation, ni celles de déphosphorylation d'un site, ne mentionnent l'état de phosphorylation de l'autre site.*

Les règles-réactions associées à ce modèle jouet s'obtiennent en explicitant dans quel contexte local elles peuvent s'appliquer. Ici chaque règle Kappa donne lieu à deux règles-réactions selon que le site qui n'est pas mentionné dans la règle initiale est phosphorylé ou non. Ces règles-réactions sont données en figure 2.13(c).
<figure><img src="image_24.png" /><figcaption>Figure 2.12: Deux exemples de raffinements d'une même règle d'interactions en deux règles-réactions. Les différences entre ces deux raffinements sont mises en valeur par des cercles rouges (les deux occurrences de la protéine ShC ont été échangées). Dans les deux cas, la règle-réaction est obtenue en ajoutant dans le membre gauche et dans le membre droit de la règle d'interactions exactement la même information sur le contexte d'application de la règle.</figcaption></figure>
<figure><img src="image_25.png" /><figcaption>Figure 2.13: Un modèle formé d'une carte de contacts et de quatres règles d'interactions et sa traduction sous forme réseau réactionnel.</figcaption></figure>

La prochaine étape est de nommer les différentes configurations d'espèces biochimiques qui interviennent dans les règles-réactions ainsi obtenues. La configuration de la protéine dans laquelle aucun site n'est phosphorylé, est appelée A, celle dans laquelle seul le site d est phosphorylé, est appelée B, celle dans laquelle seul le site g est phosphorylé, est appelée C et celle dans laquelle les deux sites sont phosphorylés, est appelée D. Les réactions données en figure 2.13(e) sont obtenues en remplaçant chaque occurrence de configuration d'espèces biochimiques par son nom dans les règles-réactions.

Le choix d'une sémantique en terme de réseaux réactionnels a été fait pour simplifier la présentation. C'était ainsi que le langage BNGL avait été implanté initialement [9]. Une telle sémantique est toutefois assez peu utile en pratique, car un modèle Kappa engendre en général un trop grand nombre de réactions. Par contre, la sémantique de Kappa peut être formalisée directement, soit sous forme d'une algèbre de processus [56, 76], soit dans un cadre catégorique [50, 73]. La première méthode est plus opérationnelle alors que la seconde abstrait au contraire beaucoup de détails. Il faut cependant noter que les cadres catégoriques usuels de la réécriture de graphes, que ce soit par des sommes amalgamées simples [109], par des sommes amalgamées doubles [43] ou par des sommes amalgamées et demi [42]) ne représentent pas fidèlement les effets de bord avec la définition usuelle des plongements entre graphes à sites. Deux approches connues permettent d'y remédier. Il est possible soit de changer la définition des plongements [50, 73], soit d'enrichir les objets de la catégorie par des contraintes [6].

La simulation d'un modèle Kappa opère directement par réécriture du graphe qui représente l'état du système, sans avoir à considérer le réseau de réactions sous-jacent [54, 17].
# Chapitre 3

## Analyse des motifs accessibles

Si la carte de contacts (e.g. voir en figure 2.1 à la page 13) donne un aperçu rapide de toutes les interactions potentielles entre les différents sites des occurrences des protéines dans un modèle, elle n’est en général pas suffisante pour décrire précisément la structure de la configuration de ses espèces biochimiques. En effet, l’état des différents sites d’interactions de la configuration d’une espèce biochimique est souvent contraint par des invariants structurels. Par exemple, dans le modèle des premières étapes de l’acquisition du facteur de croissance de l’épiderme, les sites Y48 et Y68 des occurrences du récepteur membranaire, ainsi que le site Y7 des occurrences de la protéine d’échafaudage, ne peuvent être liés à un autre site sans être phosphorylés (à moins que ce soit le cas dans l’état initial). Par ailleurs, lorsque les deux sites *r* et *c* d’une occurrence du récepteur sont liés simultanément, ils sont nécessairement liés respectivement au site *r* et au site *n* d’une même occurrence du récepteur (ce qui forme une double liaison). Un autre exemple concerne les modèles avec des compartiments, comme, par exemple, une cellule dont on distingue le noyau du cytoplasme. La localisation de chaque occurrence de protéines peut alors être spécifiée comme l’état d’activation d’un site fictif. Dans de tels modèles, toutes les occurrences de protéines de la même occurrence d’une espèce biochimique sont en général localisées dans un même compartiment, ce qui se traduit par la contrainte que le site fictif de deux occurrences de protéines liées entre elles doit toujours être dans le même état. Dans certains cas, il est toutefois possible d’avoir des espèces biochimiques transmembranaires avec des portions localisées dans des compartiments voisins, c’est à dire de part et d’autre d’une membrane.

Dans ce chapitre est décrite une analyse statique qui permet de détecter automatiquement ces contraintes. Le but est de vérifier que les propriétés auxquelles peut s’attendre le modélisateur sont bien vérifiées ou bien de détecter certaines erreurs de modélisation. En particulier, cette analyse permet de trouver des règles mortes. Ce sont des règles qui ne peuvent jamais s’appliquer dans un modèle, car les contraintes qui sont exprimées dans leurs membres gauches ne sont pas réalisables. C’est souvent la conséquence d’erreurs typographiques (par exemple, quand une même sorte de protéines est désignée par deux noms différents dans l’encodage d’un modèle), d’un état initial incomplet, d’interactions manquantes dans le modèle (par exemple, quand l’activation d’un site n’est pas décrite, alors qu’elle est nécessaire pour la suite de la cascade d’interactions) ou de conditions causales plus complexes qu’il faut alors élucider.

Cette analyse est implantée dans l’analyseur statique KASA [15] et intégrée dans la plate-forme de modélisation en ligne dédiée au langage Kappa [19]. Ceci permet d’assister le modélisateur pendant l’écriture du modèle en lui fournissant les contraintes structurelles qui sont vérifiées par les configurations des espèces biochimiques et en l’avertissant de la présence de règles mortes, après chaque ajout ou modification d’une règle d’interactions.

### 3.1 Accessibilité dans un réseau réactionnel

La première étape consiste à définir l'ensemble des états accessibles dans un modèle Kappa. Comme nous l'avons vu dans la section 2.9 page 23, un modèle Kappa induit un réseau réactionnel, ce qui permet de définir directement l'ensemble des états accessibles d'un modèle Kappa sans recourir à des constructions compliquées.

Soit un réseau réactionnel, c’est à dire un ensemble d’espèces biochimiques *S* et un ensemble de réactions *R*. Chaque réaction est donnée par deux listes d’espèces biochimiques : ses réactifs et ses produits. Ce réseau induit un système de transitions dans lequel l’*état* du réseau est défini comme un certain nombre (éventuellement nul) d’occurrences de chacune des espèces biochimiques – c’est à dire une fonction de l’ensemble *S* vers l’ensemble N
$$ \begin{cases} A \to B \\ 2B \to C \end{cases} $$

<figure><img src="image_26.png" /><figcaption>(b) Système de transitions sous-jacent.</figcaption></figure>

Figure 3.1: Un réseau réactionnel et sa sémantique. En 3.1(a) un réseau réactionnel formé de deux réactions. La première permet de transformer une occurrence de l'espèce biochimique A en une occurrence de l'espèce biochimique B, la seconde permet de transformer deux occurrences de l'espèce biochimique B en une occurrence de l'espèce biochimique C. La restriction de l'ensemble de toutes les transitions possibles aux états qui sont atteignables à partir d'un état initial formé de six occurrences de la protéine A est dessinée en 3.1(b) sous la forme d'un système de transitions.

des entiers naturels — et les transitions permettent de sauter d'un état à un autre en consommant les réactifs d'une réaction et en ajoutant les produits de cette même réaction (en tenant compte de leurs multiplicités respectives). Une transition n'est possible que si l'état courant du système contient tous les réactifs qui sont nécessaires à la réaction (en tenant compte, une nouvelle fois, de leurs multiplicités respectives). Une transition d'un état $q$ vers un autre état $q'$ est alors notée $q \to q'$.

**Exemple 3.1.1** Un système de transitions est donné comme exemple en figure 3.1(b). Il correspond à la restriction du système de transitions associé aux réactions qui sont données en figure 3.1(a) aux états accessibles à partir d'un état initial formé de six occurrences de l'espèce biochimique A. Dans ce réseau, la somme entre le nombre d'occurrences de A, de B et deux fois celui de C est toujours égal à la quantité initiale de A. En effet, cette quantité n'est modifiée par l'application d'aucune des réactions du réseau.

Étant donné un ensemble d'états initiaux potentiels, $\mathcal{I} \subseteq \mathcal{S}^N$, nous définissons l'ensemble des états accessibles comme étant ceux susceptibles d'être atteints à partir d'un état initial (de l'ensemble $\mathcal{I}$) en appliquant un nombre arbitraire (éventuellement nul) de transitions. Cet ensemble peut se définir comme le plus petit point-fixe de la fonction suivante :

$$ \mathbb{F} : \begin{cases} \wp(\mathcal{S}^N) \to \wp(\mathcal{S}^N) \\ X \to \mathcal{I} \cup \{q' \mid \exists q \in X, q \to q'\}. \end{cases} $$

Il faut noter que la fonction $\mathbb{F}$ est croissante, ce qui signifie que si $X_1$ et $X_2$ sont deux ensembles d'états tels que l'ensemble $X_1$ soit un sous-ensemble de l'ensemble $X_2$, alors l'ensemble $\mathbb{F}(X_1)$ est nécessairement un sous-ensemble de l'ensemble $\mathbb{F}(X_2)$ lui-aussi. Comme, de plus, cette fonction est définie sur l'ensemble des parties d'un ensemble, le théorème de Tarski [127] assure que la fonction $\mathbb{F}$ admet un point fixe, plus petit que tout autre point fixe de $\mathbb{F}$. Ce plus-petit point fixe, que l'on note $lfp \mathbb{F}$, est en fait l'ensemble des états accessibles.

Malheureusement, le calcul de ce plus petit point fixe peut être coûteux, voire ne pas terminer. Ceci motive la construction d'abstractions pour calculer un sur-ensemble des états accessibles en un temps de calcul acceptable.
<figure><img src="image_27.png" /><figcaption>Figure 3.2: Un ensemble de motifs d’intérêt pour l’analyse des configurations accessibles des espèces biochimiques dans le modèle des premières interactions qui interviennent dans l’acquisition du facteur de croissance de l’épiderme. Les huit premiers motifs permettent de s’intéresser aux relations potentielles entre l’état de liaison des sites *l*, *r* et *c* dans les occurrences du récepteur membranaire. Ces 8 motifs correspondent exactement à chaque combinaison possible pour l’état de ces 3 sites, chacun de ces sites pouvant être libre ou lié. Les deux derniers motifs permettent de distinguer deux occurrences du récepteur liées par une double liaison d’une chaîne d’au moins trois occurrences du récepteur.</figcaption></figure>

## 3.2 Abstraction d'un ensemble d'états

Lorsqu’un réseau est induit par un modèle Kappa, la structure biochimique associée aux espèces de ce réseau peut être utilisée pour construire une abstraction. Une possibilité consiste à choisir un ensemble de motifs connexes afin d’abstraire les ensembles d’états par le sous-ensemble parmi ces motifs de ceux qui apparaissent au moins une fois dans au moins un état de cet ensemble. Le choix des motifs connexes considérés est important : il définit le compromis entre l’expressivité de l’abstraction, c’est à dire son niveau d’approximation, et sa complexité, c’est à dire le coût pour effectuer des calculs à ce niveau d’abstraction.

**Exemple 3.2.1** *Un exemple de motifs d'intérêt pour le modèle des premières interactions de l'acquisition du facteur de croissance de l'épiderme est donné en figure 3.2. Les huit premiers motifs se concentrent sur l'analyse des relations potentielles entre l'état des sites l, r et c dans les occurrences du récepteur membranaire. Ils correspondent à toutes les combinaisons syntaxiquement possibles pour l'état de liaison de ces 3 sites. Ce sont des vues locales (ou plus précisément des sous-vues locales) [56]. Elles permettent d'abstraire un ensemble de configurations d'espèces biochimiques par l'ensemble de toutes les configurations potentielles de toutes ses occurrences de protéines, vues indépendamment les unes des autres. Ceci revient à garder uniquement l'information à propos de l'état de liaison et l'état d'activation de chaque site dans chaque occurrence de protéines tout en passant sous silence à quel site chaque site lié l'est.*

La formation de dimères dans ce modèle fait intervenir des doubles liaisons. Il est légitime de se demander s'il est possible de former des chaines comportant successivement au moins trois occurrences du récepteur membranaire. C'est le but des deux derniers motifs de l'ensemble. Ils permettent de distinguer le cas d'une double liaison entre deux occurrences du récepteur de celui de trois occurrences du récepteur liées consécutivement, en s'interrogeant pour chaque occurrence du récepteur membranaire dont les sites r et c sont liés, si elle peut être liée à une même occurrence du récepteur ou si elle peut être liée à deux occurrences différentes. En toute rigueur, pour s'assurer qu'une chaîne d'au moins trois occurrences du récepteur ne peut pas se former, il faut également considérer des motifs d'intérêt similaires pour la paire de sites r et n et la paire de sites c et n.

Plus précisément, l'abstraction est paramétrée par le choix d'un ensemble *P* de motifs connexes. L'ensemble *P* regroupe des motifs d'intérêt, ainsi que des motifs qui seront utilisés de manière intermédiaire dans la preuve que certains de ces motifs d'intérêt sont inaccessibles. Une sous-partie de l'ensemble *P* est appelée une propriété abstraite. Chaque propriété abstraite représente un ensemble d'états concrets : un état concret *q* sera dît compatible avec une propriété abstraite $X^q$ si et seulement si aucun motif qui est dans l'ensemble *P* sans être
dans l'ensemble $X^\#$ n'apprait dans la configuration d'une espèce biochimique présente dans l'état $q$. L'ensemble de tous les états concrets compatibles avec la propriété abstraite $X^\#$ est alors noté $\gamma_P(X^\#)$. Qui peut le plus, peut le moins : plus nombreux sont les motifs autorisés, plus nombreux sont les états compatibles. La fonction $\gamma_P$ est donc croissante. Elle permet de définir formellement la notion d'abstraction d'un ensemble d'états : une propriété abstraite $X^\#$ sera dite être une abstraction d'un ensemble d'états $X$ si et seulement si l'ensemble $X$ est inclus dans l'ensemble $\gamma_P(X^\#)$. La fonction $\gamma_P$ est couramment appelée la *fonction de concrétisation*. De plus l'image d'une propriété abstraite par cette fonction, est appelée sa *concrétisation*.

Réciproquement, étant donné un ensemble d'états $X$, l'ensemble des éléments de l'ensemble $\mathcal{P}$ qui apparaissent dans au moins une configuration d'espèces biochimiques d'un état élément de l'ensemble $X$ sera noté $\alpha_{\mathcal{P}}(X)$. La fonction $\alpha_{\mathcal{P}}(X)$ est croissante également. La propriété abstraite $\alpha_{\mathcal{P}}(X)$ est en fait la meilleure approximation de l'ensemble d'états $X$, ce qui signifie, d'une part, que c'est une abstraction de l'ensemble $X$ (i.e. $X \subseteq \gamma_{\mathcal{P}}(\alpha_{\mathcal{P}}(X))$) et, d'autre part, que c'est un sous-ensemble de toute autre abstraction de $X$ (i.e. pour tout sous-ensemble $Y$ de l'ensemble $\mathcal{P}$ tel que $X \subseteq \gamma_{\mathcal{P}}(Y)$, l'inclusion $\alpha_{\mathcal{P}}(X) \subseteq Y$ est vérifiée). La paire de fonctions $(\alpha_{\mathcal{P}}, \gamma_{\mathcal{P}})$ est alors appelée une *correspondance de Galois* [46, 44].

**Exemple 3.2.2** *En figure 3.3 est introduit un exemple jouet pour mieux comprendre le comportement des fonctions d'abstraction et de concrétisation. La signature de ce modèle peut être consultée en figure 3.3(a). Il existe une seule sorte de protéines, qui est appelée A. Cette protéine est munie de deux sites g et d (pour gauche et droite). La carte de contacts spécifie que chaque site peut être libre et qu'un site g peut être lié à un site d d'une même ou d'une autre occurrence de la protéine A. L'abstraction induite par l'ensemble des motifs d'intérêt donné en figure 3.3(b) repose sur les vues locales des occurrences de cette protéine. Elle permet de se poser la question de l'existence ou non, d'une relation entre l'état de liaison des sites g et d dans chaque occurrence de la protéine A.*

**Exemple 3.2.3** *Des exemples de meilleures approximations sont donnés en figure 3.3(c). Par abus de langage, nous appelons la meilleure approximation de la configuration d'une espèce biochimique, la meilleure approximation de l'ensemble formé d'un seul état lui même formé de cette seule configuration d'espèces biochimiques. Le modèle admet deux types de configurations d'espèces biochimiques. Les occurrences de la protéine A peuvent former des chaines d'occurrences de protéines liées successivement par leur site d et g, laissant le site g de la première occurrence de la protéine A et le site d de la dernière occurrence de la protéine A libres. Les occurrences de la protéine A peuvent aussi former des anneaux en reliant le premier et le dernier sites d'une chaine d'occurrences de protéines. La meilleure approximation d'une chaine d'occurrences de la protéine A dépend de la taille de cette chaine. Ainsi, la meilleure approximation d'une chaine réduite à une occurrence de la protéine A est l'ensemble qui contient uniquement la vue locale dont les deux sites sont libres ; la meilleure approximation d'une chaine formée d'exactement deux occurrences de la protéine A est l'ensemble qui contient deux vues locales : l'une avec le site g libre et le site d lié, l'autre avec le site g lié et le site d libre ; enfin la meilleure approximation des chaines d'occurrences de la protéine A de longueur au moins égale à 3 contient également la vue locale dont les deux sites g et d sont liés. Par contre, la meilleure approximation d'un anneau d'occurrences de la protéine A est toujours l'ensemble formé uniquement de la vue locale dont les deux sites g et d sont liées, et ce, quelle que soit la longueur de cette anneau. La fonction qui associe à chaque ensemble d'états sa meilleure approximation est distributive. Cela signifie que la meilleure approximation d'un ensemble d'états est l'union de la meilleure approximation des singletons correspondants.*

**Exemple 3.2.4** *Des exemples de concrétisations sont donnés en figure 3.3(d). Par définition, la concrétisation de l'ensemble formé uniquement de la vue locale dans laquelle les deux sites sont libres, est l'ensemble de tous les états qui ne contiennent pas d'autres vues locales. Il s'agit donc des états qui ne contiennent que la configuration de l'espèce biochimique composée d'exactement une occurrence de la protéine A. Par la même démarche, la concrétisation de l'ensemble formé uniquement de la vue locale dont les deux sites sont liés est l'ensemble de tous les états qui ne contiennent que des anneaux d'occurrences de la protéine A (quitte à utiliser cette vue locale plusieurs fois). Par contre, toute configuration d'espèces biochimiques contenant une vue locale avec exactement un site libre, doit contenir également une vue locale avec l'autre site, libre. De ce fait, la concrétisation d'un ensemble composé d'une seule vue locale avec un site libre et l'autre lié, est l'ensemble ne contenant que l'état vide (qui est noté $\emptyset$). Si seules les deux vues locales où un site est lié et l'autre libre sont autorisées, seules des chaines de deux occurrences de la protéine A peuvent être construites. Enfin, si seule la vue locale avec les deux sites libres est interdite, il est possible de former n'importe quelle chaine d'occurrences de la protéine A de taille au moins égale à 2 et n'importe quel anneau d'occurrences de protéines (sans restriction de taille). La*
$$ \gamma_P \left( \alpha_P \left( \begin{smallmatrix} A \\ \bullet \\ \bullet \\ \bullet \end{smallmatrix} \right) \right) = \left\{ n_1 \cdot \left( \begin{smallmatrix} A \\ \bullet \\ \bullet \\ \bullet \end{smallmatrix} \right) + n_2 \cdot \left( \begin{smallmatrix} A \\ \bullet \\ \bullet \\ \bullet \end{smallmatrix} \right) + \dots \mid n_1, n_2, \dots \in \mathbb{N} \right\} $$

(a) Exemple d'application de la fonction $\gamma_P \circ \alpha_P$.

$$ \alpha_P \left( \gamma_P \left( \begin{smallmatrix} A \\ \bullet \\ \bullet \\ \bullet \end{smallmatrix}, \begin{smallmatrix} A \\ \bullet \\ \bullet \\ \bullet \end{smallmatrix} \right) \right) = \left\{ \begin{smallmatrix} A \\ \bullet \\ \bullet \end{smallmatrix} \right\} $$

(b) Exemple d'application de la fonction $\alpha_P \circ \gamma_P$.

Figure 3.4: Suite de l'exemple donné en figure 3.3. Un exemple d'application de la composée de fonctions $\gamma_P \circ \alpha_P$ est montré en 3.4(a). Celui-ci montre que l'abstraction ne permet pas de distinguer des ensembles d'anneaux d'occurrences de la protéine A et ce quels que soient leurs tailles et leurs nombres. En 3.4(b) donne un exemple d'application de la composée de fonctions $\alpha_P \circ \gamma_P$. Cette fonction calcule que la vue locale avec le site g libre et le site d lié ne peut pas apparaître dans une espèce biochimique qui ne contiendrait pas la vue avec le site g lié et le site d libre.

fonction de concrétisation n'est pas distributive (l'image de l'union de deux ensembles de vues locales peut être un sur-ensemble strict de l'union de leurs images).

Les fonctions $\alpha_P$ et $\gamma_P$ se composent dans les deux sens. Ces compositions sont révélatrices des traits principaux du choix de l'abstraction. La composée $\gamma_P \circ \alpha_P$ caractérise le niveau d'approximation. En effet, pour tout ensemble d'états $X$, $\gamma_P(\alpha_P(X))$ est le plus grand ensemble d'états qui a la même meilleure approximation que $X$. Il est impossible ainsi de distinguer ces deux ensembles en terme de propriétés abstraites. En revanche, la composée $\alpha_P \circ \gamma_P$ témoigne d'une certaine combinatoire dans le domaine abstrait. Elle associe à chaque propriété abstraite, la plus petite propriété abstraite qui est satisfaite par le même ensemble d'états concrets. Appliquer cette composée permet donc de raffiner une propriété abstraite, par déduction, et ce sans perdre le moindre état concret.

**Exemple 3.2.5** Appliquée à l'ensemble formé d'un seul état composé uniquement d'un anneau de taille 1, la composée de fonctions $\gamma_P \circ \alpha_P$ donne l'ensemble des états formés uniquement d'anneaux d'occurrences de la protéine A. En effet, la meilleure approximation d'un anneau de taille 1, est l'ensemble de vues locales composé uniquement de la vue dont les deux sites sont liés. Or, voir également en figure 3.3(d), la concrétisation de cet ensemble de vues locales est l'ensemble de tous les états formés uniquement d'anneaux. Ainsi le niveau d'abstraction ne permet de distinguer, ni le nombre d'occurrences, ni la taille des anneaux d'occurrences de la protéine A.

**Exemple 3.2.6** Appliquée à l'ensemble formé exactement des deux vues locales, la première avec le site g libre et le site d lié, la seconde avec les deux sites liés, la composée de fonctions $\alpha_P \circ \gamma_P$ retourne l'ensemble formé d'une seule vue locale, celle avec les deux sites liés. En effet, la première vue ne peut apparaître dans un état sans que celui-ci ne contienne une occurrence de la vue locale avec le site d libre et le site g lié. De ce fait, elle ne peut apparaître dans aucun état de la concrétisation de l'ensemble formé par ces deux vues locales et n'est donc pas un élément de la meilleure approximation de l'ensemble de ces états. Ainsi, un état abstrait peut contenir des motifs d'intérêt, qui ne peuvent apparaître dans aucune configuration d'espèces biochimiques sans contenir des occurrences de motifs d'intérêt interdits. Retirer ces motifs ne change pas l'ensemble des états concrets qui satisfont la propriété abstraite, mais cette étape peut requérir un temps de calcul substantiel.

## 3.3 Transferts de point-fixes

Le plus petit point fixe qui définit l'ensemble des configurations d'espèces biochimiques accessibles dans un réseau réactionnel, pour un état initial donné, peut se calculer au niveau des propriétés abstraites grâce à la correspondance de Galois $(\alpha_P, \gamma_P)$.

Pour cela, il faut tout d'abord construire la *contre-partie abstraite* de la fonction $\mathbb{F}$, qui agira, non pas sur des ensembles d'états concrets, mais directement sur les propriétés abstraites. Cette *contre-partie abstraite* se définit de manière systématique : il suffit, pour chaque propriété abstraite $X^\sharp$, de considérer l'ensemble des états concrets $\gamma_P(X^\sharp)$ qui vérifient la propriété $X^\sharp$, puis d'appliquer la fonction $\mathbb{F}$ à cet ensemble et enfin d'appliquer à ce résultat la fonction $\alpha_P$ pour en calculer la meilleure approximation. C'est même la manière correcte la
plus précise de procéder : la fonction $\alpha_P \circ F \circ \gamma_P$ est, en effet, la meilleure contre-partie abstraite de la fonction $F$ [47]. Elle permet de déléguer le calcul des états accessibles au domaine abstrait en contre-partie d'une perte éventuelle de précision. Pour ce faire, il suffit de remarquer que la fonction $\alpha_P \circ F \circ \gamma_P$ est croissante (comme composée de fonctions croissantes) et définie sur l'ensemble des parties d'un ensemble. Elle admet donc un plus petit point fixe qui sera noté $lfp(\alpha_P \circ F \circ \gamma_P)$. L'inclusion suivante : $lfp F \subseteq \gamma_P(lfp(\alpha_P \circ F \circ \gamma_P))$ se prouve alors par induction [47]. Autrement dit le plus petit point fixe de la fonction $\alpha_P \circ F \circ \gamma_P$ est une abstraction de l'ensemble des états accessibles du modèle considéré. C'est à dire que la propriété abstraite $lfp(\alpha_P \circ F \circ \gamma_P)$ est satisfaite par chaque état accessible du modèle.

Le calcul des itérations de la fonction $[\alpha_P \circ F \circ \gamma_P]$ peut prendre beaucoup de temps. Il est possible d'ajuster le compromis entre précision et temps de calcul en remplaçant celle-ci par une fonction moins précise. En effet, pour toute fonction croissante $F^\sharp$ telle que $[\alpha_P \circ F \circ \gamma_P](Y) \subseteq F^\sharp(Y)$ pour tout ensemble de motifs $Y \subseteq P$, l'inclusion $lfp F \subseteq \gamma_P(lfp(F^\sharp))$ est également satisfaite [47].

Une telle fonction $F^\sharp$ peut être dérivée à la main. Pour cela, il faut d'abord donner une définition plus explicite de la fonction $[\alpha_P \circ F \circ \gamma_P]$. Appliquée à un sous-ensemble $Y \subseteq P$ de motifs d'intérêt, cette fonction ajoute l'ensemble des nouveaux motifs d'intérêt qui peuvent apparaître dans un état accessible en une étape de réécriture à partir d'un état qui ne contient aucun motif de l'ensemble $P$ qui ne serait pas dans l'ensemble de motifs $Y$. Or, une telle étape de réécriture est nécessairement induite par une règle-réaction, elle-même induite par une règle du modèle. Chaque nouveau motif $P$ doit donc apparaître dans le membre droit d'une règle-réaction et l'ensemble d'états singleton formé du membre gauche de cette règle-réaction ne doit contenir aucune occurrence de motifs de l'ensemble $P \setminus Y$. Dans cette règle-réaction, l'occurrence du motif $P$ dont il est question et l'image du membre droit de la règle sous-jacente ont nécessairement au moins une occurrence de protéines en commun (sinon le motif $P$ apparaîtrait également dans le membre gauche de la règle-réaction et ne serait dont pas un nouveau motif). Il est alors possible de fixer le motif $P$ au membre droit de cette règle, en unifiant les occurrences de protéines du motif $P$ et de la règle du modèle qui sont communes dans la règle-réaction. Ceci forme alors un raffinement du membre droit de la règle. Un raffinement de la règle peut alors être construit en ajoutant toute information présente dans le motif $P$ qui n'est pas déjà présente dans le membre droit initial de la règle, dans le membre gauche de la règle. Le résultat est une spécialisation de la règle à la production du motif $P$ à cette position particulière. Par construction, le membre gauche de la règle raffinée apparaît dans un état dans la concrétisation de $Y$.

Ainsi, pour calculer les nouveaux motifs d'intérêt de l'ensemble $[\alpha_P \circ F \circ \gamma_P](Y)$, il suffit de calculer tous les chevauchements possibles entre un nouveau motif d'intérêt potentiel (dans $P \setminus Y$) et un membre droit d'une règle du modèle. Chaque chevauchement induit un raffinement de la règle correspondante. Si le membre gauche de la règle raffinée apparaît dans un état de l'ensemble $\gamma_P(Y)$, alors ce motif appartient bien à l'ensemble $[\alpha_P \circ F \circ \gamma_P]Y$.

**Exemple 3.3.1** Un exemple de cette construction est dessiné en figure 3.5. L'état abstrait actuel est donné en figure 3.5(a). Seules trois vues locales sont pour l'instant autorisées, celle avec aucun des sites l, r, c lié, celle avec seul le site l lié et celle avec seuls les sites l et r liés. Par ailleurs, ni les doubles liaisons, ni les chaînes d'au moins trois récepteurs ne sont autorisées à cet instant de l'analyse. La preuve que l'on peut construire une occurrence de protéines avec les trois sites l, r et c liés, est donnée en figure 3.5(b). Il suffit d'identifier cette vue locale à l'occurrence gauche du récepteur dans le membre droit de la règle (les plongements en pointillés bleus et marrons envoient ces deux occurrences de protéines sur une même occurrence de protéines) qui permet d'établir une liaison asymétrique entre deux récepteurs membranaires (voir en figure 2.8(e)). Ceci est possible car les sites en commun dans ces deux occurrences de protéines sont dans un état compatible : en effet, la vue locale demande que ces sites soient liés, alors que le membre droit de la règle précise à quels sites ils le sont. La règle est alors spécialisée à la production de la nouvelle vue locale pour ce chevauchement particulier entre la vue locale et le membre droit de la règle. Cela consiste à ajouter dans les membres gauche et droit de la règle l'information que le site l est lié. Pour conclure, il suffit alors d'exhiber un plongement (ici dessiné en pointillés rouges) en le membre gauche de la règle ainsi raffinée et le configuration d'une espèce biochimique, en vérifiant que celle-ci ne contient aucune occurrence des motifs d'intérêt non encore autorisés. Le dimère avec uniquement une liaison symétrique et dans lequel les deux occurrences du récepteur membranaire sont toutes deux liées à des occurrences du ligand et les sites Y48 et Y68 non phosphorylés et libres rempli parfaitement ces conditions. Ainsi la vue locale dans laquelle les trois sites l, r et c sont liés simultanément sera utilisable dès la prochaine itération de l'analyse.

Lors du calcul de l'ensemble $[\alpha_P \circ F \circ \gamma_P](Y)$, l'étape la plus coûteuse en temps de calcul est de vérifier
<figure><img src="image_28.png" /><figcaption>(a) Un état abstrait.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(b) La construction de la vue locale dans laquelle les trois sites sont liés peut être construite en une étape à partir de cet état abstrait.</figcaption></figure>

Figure 3.5: Découverte d'un nouveau motif d'intérêt accessible dans le modèle des premières étapes de la voie de l'acquisition du facteur de croissance de d'épiderme (voir en figure 2.8 page 20). En 3.5(a), il est supposé qu'à ce moment de l'analyse, seules trois vues locales sont autorisées. Par ailleurs, il n'est permis de former ni des doubles liaisons entre récepteurs membranaires, ni des chaînes de trois récepteurs ou plus. En 3.5(b), la preuve que la vue locale doit être déclarée accessible à ce niveau d'abstraction est représentée sous forme de diagramme. Elle consiste à appliquer la règle de liaison asymétrique en identifiant la vue locale au récepteur de gauche dans le membre droit de la règle et en raffinant la règle en conséquence. Le membre gauche de la règle obtenue apparaît dans une configuration d'espèces biochimiques ne contenant aucun motif d'intérêt non encore découvert, ce qui conclut la preuve.
que les membres gauches des règles raffinées peuvent apparaître dans un état de l'ensemble $\gamma_P(Y)$. La section suivante a pour but de réduire ce coût moyennant une approximation supplémentaire.

## 3.4 Analyse par ensembles de motifs orthogonaux

Ajouter des hypothèses sur l'ensemble des motifs d'intérêt et simplifier le test de réalisabilité du membre gauche des raffinements de règles en le remplaçant par une condition nécessaire, mais pas toujours suffisante, permet de rendre ce calcul plus efficace au prix d'une perte de précision de l'analyse. Ceci permet de définir une approximation correcte de la fonction $\alpha_P \circ F \circ \gamma_P$.

Pour ce faire, l'ensemble des motifs d'intérêt peut être organisé sous la forme d'un ensemble fini d'ensembles finis de motifs orthogonaux [79]. Chaque ensemble de motifs orthogonaux est un arbre de décision raffinant progressivement un motif initial, dans le but de répondre à une question spécifique. Un ensemble de motifs orthogonaux est construit de manière à ce que toute occurrence du motif initial dans une configuration d'espèce biochimiques, puisse être complétée en exactement une occurrence d'un de ces raffinements. En conséquence, les raffinements du motif initial sont deux à deux incompatibles et ils recouvrent, en quelque sorte, tous les cas possibles pour le motif initial.

Le choix exact des ensembles de motifs orthogonaux repose sur une analyse préliminaire qui calcule, par inspection des règles du modèle, quelles questions intéressantes se posent. Trois catégories de questions sont considérées par défaut dans l'analyseur KASA (mais il est possible de paramétrer l'analyse pour en désactiver une ou deux). La première infère des relations entre les états des différents sites de chaque sorte de protéines, cela correspond à l'analyse des vues locales [56]. La seconde permet de détecter des relations entre l'état des sites dans des occurrences de protéines qui partagent un lien [79] dans le but d'analyser le déplacement des occurrences des espèces biochimiques lorsque celui-ci est codé par des transformations de l'état d'activation de sites fictifs. L'analyse permet alors de vérifier si oui ou non deux occurrences de protéines sont toujours localisées dans le même compartiment quand elles sont liées entre elles. La troisième permet de détecter si une même occurrence de protéines peut être liée simultanément à deux occurrences différentes de protéines ou si une même occurrence de protéines peut être liée au moins doublement à une autre occurrence de protéines [79]. Une quatrième sorte d'ensembles de motifs orthogonaux est en cours d'implantation. Elle se concentre sur la formation des espèces biochimiques cycliques : son but est de prouver l'absence de espèces biochimiques de taille non bornée [18].

Les ensembles finis de motifs orthogonaux peuvent être construits récursivement, en remplaçant un des motifs par plusieurs motifs le raffinant. Il suffit de choisir une information non spécifiée dans ce motif et de considérer tous les cas possibles pour cette information, d'où la représentation sous forme d'arbre de décision. L'ensemble de motifs orthogonaux est alors formé par les feuilles de cet arbre, alors que les nœuds de cet arbre représentent les motifs intermédiaires qui ont été remplacés par des motifs plus précis.

**Exemple 3.4.1** L'ensemble des motifs d'intérêt introduit en figure 3.2 est inclus dans la réunion de deux ensembles de motifs orthogonaux. En effet, l'ensemble des vues locales peut être obtenu, en partant d'une occurrence de la protéine EGFR sans aucun site, en se demandant successivement si le site l est libre ou non, si le site r est libre ou non et si le site c est libre ou non. L'arbre de décision correspondant se trouve en figure 3.6(a). Les deux derniers motifs d'intérêt sont obtenus en se demandant si un récepteur peut établir des liaisons doubles. Partant d'une occurrence de la protéine EGFR sans aucun site, il faut se demander si le site r est libre ou non, puis dans le cas où le site r est lié, si le site c est lié ou non, et enfin, dans le cas où le site c est également lié, si ces deux sites sont liés à une même occurrence de récepteur membranaire ou à deux occurrences différentes. L'arbre de décision ainsi obtenu est donné en figure 3.6(b).

Les différents ensembles de motifs orthogonaux collaborent au sein de l'analyse, qui effectue ainsi une induction mutuelle sur ces derniers. Ceci présente deux avantages par rapport à des analyses séparées ou en cascades (où chacune utiliserait le résultat des analyses précédentes). D'une part, il n'est pas nécessaire de définir quel ensemble de motifs orthogonaux doit être analysé avant quel autre. D'autre part, une induction mutuelle est strictement plus expressive. La collaboration entre les différents ensembles de motifs orthogonaux permet de prouver plus souvent que le membre gauche des règles raffinées n'est pas réalisable étant donné les motifs qui sont autorisés à un moment donné de l'analyse (voir en figure 3.5), et donc que la règle peut être ignorée à ce moment de l'analyse. Pour faire cette preuve, le raffinement d'une règle est construit de la manière habituelle. Il suffit ensuite de trouver une occurrence de protéines dans le membre gauche de la règle raffinée qui soit incompatible avec l'état actuel de l'analyse sur au moins un des ensembles de motifs orthogonaux pris
<figure><img src="image_30.png" /><figcaption>(a) Ensemble de motifs orthogonaux pour les vues locales.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>(b) Ensemble de motifs orthogonaux pour discuter des doubles liaisons.</figcaption></figure>

Figure 3.6: Deux exemples d'ensemble de motifs orthogonaux. En 3.6(a), l'ensemble des vues locales (voir les huit premiers motifs en figure 3.2 page 29) sous forme d'arbre de décision. En 3.6(b), celui pour discuter de la présence potentielle de doubles liaisons entre des récepteurs et de la présence potentielle de trimers (voir les deux derniers motifs en figure 3.2).
<figure><img src="image_32.png" /><figcaption>Figure 3.7: L'étape abstraite de la figure 3.5 revisitée avec la procédure de décision approchée. Au lieu de vérifier que chaque motif connexe du membre gauche de la règle raffinée se plonge dans la configuration d'une espèce biochimique dans la concrétisation de l'état abstrait, il suffit de s'assurer, pour chaque occurrence de protéines dans ce motif et chaque ensemble de motifs orthogonaux portant sur ce sorte de protéines si il contient un motif compatible déjà découvert par l'analyse.</figcaption></figure>

en paramètre de l'analyse. Pour cela, la racine de l'ensemble de motifs orthogonaux doit être de la même sorte que l'occurrence de la protéine en question et l'information contextuelle de cette occurrence de protéines dans ce membre gauche de la règle raffinée ne doit être compatible avec aucun des motifs de cet ensemble de motifs orthogonaux déjà déjà déclarés potentiellement accessibles par l'analyse. Dans le cas contraire, l'analyseur ne peut pas prouver que le motif est inaccessible. Le motif est alors considéré comme potentiellement accessible pour la suite de l'analyse. Il s'agit bien entendu d'une approximation.

**Exemple 3.4.2** En figure 3.7, l'étape de calcul qui avait été décrite en figure 3.5 est rejouée en remplaçant le test de réalisabilité par cette procédure approchée. Au lieu de construire un plongement du membre gauche de la règle raffinée vers la configuration d'une espèce biochimique afin de vérifier qu'il ne contient pas de motif non encore autorisé, la nouvelle procédure se contente de vérifier pour chaque occurrence de protéines dans le membre gauche de la règle raffinée et pour chaque ensemble de motifs orthogonaux portant sur cette sorte de protéines si celui-ci contient un motif autorisé compatible avec cette occurrence. Dans ce cas, cela revient à vérifier qu'il existe bien une vue locale déjà autorisée dans laquelle les deux sites l et r sont liés, alors que le site c est libre et que le motif dans lequel le site r est lié et le site c est libre est autorisé dans le deuxième ensemble de motifs orthogonaux.

Outre le fait de ne pas vérifier l'existence de la configuration d'une espèce biochimique qui pourrait compléter le collage obtenu entre les motifs connexes du membre gauche de la règle raffinée et les motifs déjà déclarés potentiellement accessibles par l'analyse, il est intéressant de remarquer que la procédure de décision approchée évite le calcul de tous les chevauchements entre les motifs d'intérêt non encore découverts par l'analyse, en se focalisant sur la racine de chaque ensemble de motifs orthogonaux. Ce sont les deux sources de pertes d'information dues à l'affaiblissement de la procédure de décision.

**Exemple 3.4.3** Le résultat de l'itération pour le modèle formé des règles qui avaient été décrites en figure 2.8 pour les ensembles de motifs orthogonaux qui avaient été introduits en figure 3.6, est donné en figure 3.8. Cette itération a été initialisée avec une quantité arbitraire d'occurrences de protéines de chaque sorte, mais avec tous leurs sites libres. Pour ce qui est des vues locales (voir en figure 3.8(a)), seules 4 configurations sont possibles pour l'état des sites l, r, et c des récepteurs membranaires. Ainsi, le site c ne peut être lié sans que le site r ne le soit et le site r ne peut être lié sans que le site l ne le soit. De son côté, l'analyse des doubles liaisons (voir en figure 3.8(b)) montre qu'il est impossible de former des chaînes d'au moins trois récepteurs membranaires.

Il est important de rappeler que l'analyse ne donne qu'une sur-approximation des états accessibles. Ainsi, tout motif prouvé comme non accessible est bien inaccessible. Par contre, il n'y a aucune garantie qu'un motif non prouvé inaccessible puisse apparaître dans un état accessible depuis un des états initiaux.

## 3.5 Pour aller plus loin
<figure><img src="image_33.png" /><figcaption>Figure 3.8: Résultat de l’analyse pour les deux ensembles de motifs orthogonaux donnés en figure 3.6. Les motifs orthogonaux sont aux feuilles des arbres de décision. Ceux qui sont barrés en rouge n’apparaissent dans aucune exécution du modèle (pour n’importe quel état initial sans lien). Par construction de l’arbre de décision, les nœuds dont tous les enfants sont inaccessibles sont également inaccessibles et donc barrés eux-aussi.</figcaption></figure>
L'itération de point-fixe est suivie d'une phase de traitement du résultat. Le but est essentiellement de rendre le résultat de l'analyse plus compréhensible pour l'utilisateur. Dans un premier temps, un parcours de chaque arbre de décision est effectué et chaque nœud dont tous les fils sont déclarés inaccessibles est déclaré inaccessible lui-aussi. Ensuite, tous les nœuds des arbres de décision sont explorés en répertoriant ceux dont les enfants n'ont pas tous le même statut. Ceci témoigne d'une propriété intéressante puisque dans ce cas, un des raffinements d'un motif accessible n'est pas accessible. Cette information est alors présentée sous la forme d'une implication, appelée *lemme de raffinement*, entre un motif (le nœud en question) et une liste de motifs (ses fils qui n'ont pas été prouvés inaccessibles). Une telle implication s'interprète de la manière suivante : chaque occurrence du motif de la précondition dans une configuration accessible d'une espèce biochimique peut toujours se raffiner en l'un des motifs de la postcondition.

**Exemple 3.5.1** *Le résultat de l'analyse décrit en figure 3.8 donne lieu aux implications suivantes :*

<figure><img src="image_34.png" /></figure>

Cela prouve que dans une occurrence du récepteur membranaire, le site *c* ne peut être lié sans que le site *r* ne le soit également, et que le site *r* ne peut être lié sans que le site *l* ne le soit ausst. De plus, une occurrence du récepteur dont les sites *r* et *c* sont tous deux liés, est nécessairement liée doublement à une même occurrence du récepteur.

Par ailleurs, l'analyseur vérifie pour chaque règle si son membre gauche est compatible avec le résultat de l'analyse (avec la procédure de décision simplifiée présentée Sec. 3.4). Les règles pour lesquelles ce n'est pas le cas sont reportées à l'utilisateur.

Nous avons utilisé l'analyseur statique KASA sur plusieurs modèles. Les résultats de ces analyses sont décrites en table 3.1. Les onze premiers modèles sont des traductions directes des modèles qui sont fournis avec la distribution du logiciel BNGL [9]. Le modèle ‘egfr’ décrit les premiers événements de l’acquisition du facteur de croissance de l’épiderme (il comprend entre autres les règles données en figure 2.8). Le modèle ‘egfr, erk, mapk, ras’ va beaucoup loin dans la voie de signalisation [51, 10, 124, 20]. Les modèles ‘machine’ et ‘ensemble’ sont deux versions de la voie de signalisation MAPK, publiées par Eric Deeds et Ryan Suderman [126]. Les versions du modèle ‘korkut’ concernent la voie de signalisation de la protéine Ras. Ce modèle a été conçu par John Bachman et Benjamin Gyori (Sorger lab) dans le cadre du projet DARPA Big Mechanism [38] en utilisant des outils de traitement automatique du langage naturel pour extraire des faits de la littérature, en assemblant ces faits en Kappa, puis en corrigeant manuellement les modèles obtenus [89]. Le modèle ‘tfg’ s’intéresse lui à la matrice extra-cellulaire de la protéine tgf-β. Cinq versions de ce modèle ont été analysées. Elles ont été assemblées à la main d’après la littérature par Nathalie Théret et Jean Coquet, puis corrigées avec l’aide de l’analyseur KASA. Enfin, plusieurs versions du modèle de la voie de signalisation de la protéine Wnt, écrites par Héctor F. Medina Abarca (Fontana Lab) dans le cadre du projet DARPA Big Mechanism [38] ont été analysées. Ce modèle a également été assemblé manuellement après lecture humaine de la littérature. Dans ce dernier modèle, le grand nombre de règles vient du fait que des scripts ont été utilisés pour raffiner des règles d’interactions génériques afin d’ajuster leurs cinétiques en fonction d’informations contextuelles sur les configurations des occurrences de protéines qui interagissent et de celles de leurs voisines.

Pour chaque modèle et chaque version, nous avons reporté le nombre total de règles, ainsi que nombre d’implications découvertes par l’analyse portant sur des relations soit entre au moins deux sites, soit entre les états de liaison et d’activation d’un même site. Nous avons également donné le nombre de règles qui ont été trouvées mortes par l’analyseur statique (du fait de l’approximation, l’analyseur peut manquer des règles mortes, par contre, toute règle détectée morte l’est). Nous donnons également le temps de calcul total de
<table><caption>Table 3.1: Résultats expérimentaux (calculés sur un MacBook Pro avec une puce Intel Core i7-6567U (cadencée 3.3 GHz)). Pour chaque modèle et chaque version, le nombre de règles est donné, ainsi que le nombre de contraintes découvertes par l'analyse et le nombre de règles mortes trouvées (qui ne sont donc jamais utilisées dans le modèle). Le temps total de l'analyse est également fourni.</caption><thead><tr><th>modèle</th><th>nombre de règles</th><th>nombre de contraintes inférées</th><th>nombre de règles mortes détectées</th><th>temps d'analyse (secondes)</th></tr></thead><tbody><tr><td>repressilator</td><td>42</td><td>0</td><td>0</td><td>0.005</td></tr><tr><td>egfr_net</td><td>39</td><td>4</td><td>0</td><td>0.011</td></tr><tr><td>egfr_net_red</td><td>45</td><td>6</td><td>0</td><td>0.013</td></tr><tr><td>fceri_fyn</td><td>46</td><td>4</td><td>0</td><td>0.025</td></tr><tr><td>fceri_fyn_lig</td><td>48</td><td>4</td><td>0</td><td>0.025</td></tr><tr><td>fceri_fyn_trimer</td><td>362</td><td>4</td><td>36</td><td>0.301</td></tr><tr><td>fceri_fyngamma2</td><td>59</td><td>5</td><td>0</td><td>0.036</td></tr><tr><td>fceri_fyn_ji</td><td>36</td><td>4</td><td>0</td><td>0.019</td></tr><tr><td>fceri_fyn_ji_red</td><td>32</td><td>4</td><td>0</td><td>0.017</td></tr><tr><td>fceri_fyn_lyn_745</td><td>40</td><td>4</td><td>2</td><td>0.021</td></tr><tr><td>fceri_fyn_trimer</td><td>192</td><td>4</td><td>0</td><td>0.136</td></tr><tr><td>egfr</td><td>20</td><td>9</td><td>0</td><td>0.010</td></tr><tr><td>egfr, erk, mapk, ras</td><td>69</td><td>7</td><td>0</td><td>0.046</td></tr><tr><td>machine</td><td>220</td><td>13</td><td>7</td><td>0.405</td></tr><tr><td>ensemble</td><td>233</td><td>26</td><td>0</td><td>0.364</td></tr><tr><td>korkut (2017/01/13)</td><td>3916</td><td>0</td><td>1610</td><td>7.92</td></tr><tr><td>korkut (2017/01/17)</td><td>12896</td><td>0</td><td>874</td><td>24</td></tr><tr><td>korkut (2017/02/06)</td><td>5750</td><td>0</td><td>884</td><td>57</td></tr><tr><td>TGF (V19)</td><td>97</td><td>19</td><td>10</td><td>0.223</td></tr><tr><td>TGF (V20)</td><td>99</td><td>30</td><td>10</td><td>0.275</td></tr><tr><td>TGF (V21)</td><td>211</td><td>18</td><td>0</td><td>0.652</td></tr><tr><td>TGF (2017/04/01)</td><td>235</td><td>13</td><td>0</td><td>0.534</td></tr><tr><td>TGF (2018/04/19)</td><td>292</td><td>13</td><td>0</td><td>0.625</td></tr><tr><td>BigWnt (2015/12/28)</td><td>356</td><td>2</td><td>1</td><td>2.06</td></tr><tr><td>BigWnt (2016/09/28)</td><td>1419</td><td>1</td><td>0</td><td>6.64</td></tr><tr><td>BigWnt (2017/03/22)</td><td>1486</td><td>14</td><td>12</td><td>8.74</td></tr></tbody></table>

l'analyse, ce qui montre que KASA passe à l'échelle même sur des modèles comportant un grand nombre de règles d'interactions.

Les informations trouvées par l'analyse statique sont utiles. Une même démarche a été suivie pour améliorer la qualité de ces modèles, qu'ils soient écrits à la main ou assemblés automatiquement par fouille automatique de la littérature. La première étape est la vérification des règles mortes. Ces règles sont souvent la conséquence, soit d'erreurs typographiques, soit d'états initiaux incomplets, soit de règles manquantes, soit de relations de causalité qui ne peuvent pas être satisfaites. La lecture des contraintes trouvées par l'analyseur permet de mieux comprendre leurs origines. Elle permet également de vérifier que les invariants structurels auquel le modélisateur peut s'attendre sont bien vérifiés. L'étape suivante est d'étudier comment une occurrence de protéines peut passer d'une configuration à une autre. L'analyse des traces locales [77, 78] calcule des systèmes de transitions à partir des vues locales. Ceci permet d'avoir une cartographie des changements de configuration de chaque occurrence de protéines en faisant abstraction de l'état des occurrences de protéines auxquelles cette occurrence est liée. En particulier, une étude de ces systèmes de transitions permet de calculer efficacement des transitions qui sont définitives : c'est à dire celles qui transforment la configuration d'une occurrence de protéines, sans retour possible, quel que soit le nombre de transitions ultérieures.

**Exemple 3.5.2** Le système de transitions qui représente les traces locales des occurrences du récepteur membranaire dans le modèle des premières interactions qui interviennent dans l'activation du facteur de croissance de l'épiderme, est dessiné en figure 3.9. La succession entre les différentes configurations possibles y est clairement décrite. Ainsi, partant d'un récepteur avec les sites l, r, c et n libres (le site n a été ajouté pour rendre
<figure><img src="image_35.png" /><figcaption>Figure 3.9: Le système de transitions pour les vues locales des occurrences du récepteur membranaire. L'état du site *n* a été ajouté pour rendre l'exemple plus intéressant. Ce système de transitions explique les étapes que traverse ces occurrences lorsque leurs sites deviennent liés. Les transitions en sens inverse, qui correspondent aux règles de libération des sites sont aussi représentées.</figcaption></figure>

l'exemple plus intéressant), le site *l* peut devenir lié en premier, ensuite le site *r* peut devenir lié, ensuite soit le site *c*, soit le site *n* peut devenir lié. Par contre, ces deux liaisons sont exclusives : les sites *c* et *n* d'une occurrence de protéines ne peuvent pas être liés tous les deux simultanément. Par ailleurs, toutes les liaisons peuvent se défaire dans l'ordre inverse de leur création.

Bien que très efficace, la principale limite de l'analyse d'accessibilité présentée dans ce chapitre est qu'elle reste trop lente pour être utilisée en cours de mise à jour d'un grand modèle dans un éditeur de texte. Dans ce contexte, le calcul des invariants recommence de zéro à chaque modification. Une analyse incrémentale, qui serait capable de tirer profit des analyses précédentes quand une règle est ajoutée ou retirée, ou quand l'état initial est changé, serait plus appropriée. Les ajouts de règles ne posent pas de grandes difficultés. Il suffit de continuer l'itération à partir du point fixe précédent. Par contre, lorsqu'une règle est enlevée, une telle approche conduirait à une trop grande perte de précision, puisque la règle en question est susceptible d'être nécessaire à l'accessibilité de certains motifs, ce qui serait alors impossible d'exploiter pour obtenir un résultat précis. Un algorithme de saturation opérant sur des clauses de Horn permettra de mieux gérer la suppression de règles. Dans cette approche, chaque clause constitue une implication formalisant le fait que s'il est impossible, avec le niveau d'abstraction fixé, de prouver que certains motifs sont innaccessibles et que si une règle donnée existe dans le modèle, alors il est impossible de prouver que tel autre motif est innaccessible. En fait, chaque instance du diagramme donné en figure 3.5(a), se traduit en une clause de Horn. En plus, de l'ensemble des motifs dont il a été prouvé qu'il est impossible de prouver l'inaccessibilité, l'analyseur se rappellera quels prédicats et quelles clauses ont été utilisées pour prouver chaque prédicat. Il sera alors plus facile des les invalider de proche en proche lors de la suppression d'une règle avant de reprendre l'algorithme de saturation, pour vérifier s'il n'existe pas d'autres preuves des prédicats ainsi invalidés.
# Chapitre 4

## Flot d'information dans la sémantique différentielle d'un modèle Kappa

Les sémantiques quantitatives permettent de définir et d'étudier le comportement des modèles au cours du temps. Dans ce chapitre, seule la sémantique différentielle sera considérée. Elle décrit l'évolution des quantités de chaque constituant du modèle sous la forme d'équations différentielles ordinaires. Elle est donc déterministe. La sémantique différentielle demande de préciser la vitesse des réactions biochimiques. Il suffit pour cela d'associer à chaque règle de réécriture une constante pour spécifier la vitesse des réactions induites par ces règles. Toutefois, une telle sémantique ne passe pas à l'échelle des grands systèmes d'interactions, car elle requiert une variable par configuration d'espèces biochimiques. Il est donc nécessaire de proposer des méthodes de réduction pour définir des systèmes différentiels de dimensions plus petites.

La méthode présentée ici s'appuie sur l'analyse du flot d'information entre les différents sites des espèces biochimiques. Elle permet d'identifier des paires de sites dont la corrélation entre les états n'a aucune influence sur la dynamique du système considéré. Chaque configuration d'une espèce biochimique peut alors être séparée en portions plus petites qui se comportent de manière autonome. L'explosion combinatoire due à la taille des espèces biochimiques est alors contournée.

En section 4.1 est illustrée une des raisons principales de l'explosion combinatoire en nombre de configurations potentielles des espèces biochimiques dans les modèles de réécriture de graphes à sites. En section 4.2 les calculs pour réduire la dimension d'un cas d'étude jouet sont effectués à la main. En section 4.3 la notion de réduction de modèle différentiel est formalisée. Ce cadre générique est ensuite appliqué aux modèles écrits en Kappa, en section 4.4.

## Remerciement

Ces travaux sont principalement issus de mon post-doc auprès de Walter Fontana, qui ont été publiés dans [74]. La thèse de Ferdinanda Camporesi a permis une formalisation plus complète et une extension dans le cas non-uniforme [23].

### 4.1 Une brèche dans le mur de la combinatoire

#### 4.1.1 Les causes de l'explosion combinatoire

Le début de ce chapitre explique une des raisons de l'explosion combinatoire dont souffrent les systèmes d'équations différentielles qui émergent des modèles d'interactions biochimiques entre protéines.

En figure 4.1 est dessinée une configuration typique d'une occurrence d'un dimère dans le modèle des premières étapes dans l'acquisition du facteur de croissante de l'épiderme [9]. Dans ce modèle, il est intéressant de mesurer la quantité de la protéine cible *Sos* qui est attachée à la membrane de la cellule. C'est à dire la quantité de cette protéine attachée soit directement à la membrane par le biais d'une occurence de la protéine de transport *Grb2*, soit indirectement par l'intermédiaire d'une occurrence de la protéine d'échafaudage *ShC*. Chaque occurrence d'un dimère contient deux occurrences du récepteur *EGFR* et chaque occurrence du récepteur contient deux sites *Y48* et *Y68* susceptibles de recruter une occurrence de la protéine *Sos*. Les deux
<figure><img src="image_36.png" /><figcaption>Figure 4.1: Un exemple de configuration pour un dimère. Cette configuration contient deux occurrences du site Y48 et deux occurrences du site Y68 chacune suceptible de recruter une occurrence de la protéine SoS, d'où l'explosion combinatoire du nombre potentiel de configurations d'espèces biochimiques.</figcaption></figure>

occurrences de la protéine recepteur étant distinguées dans le dimère, il y aura donc $n_{short}^2 \cdot n_{long}^2$ où $n_{short}$ est le nombre d'états intermédiaires dans l'acquisition de la protéine Sos par la voie directe et $n_{long}$ est le nombre d'état intermédiaire dans l'acquisition de la protéine Sos par la voie indirecte.

Toutefois, plutôt que de mesurer la quantité de chaque configuration d'espèces biochimiques en multipliant par le nombre d'occurrences de la protéine Sos que chacune a recruté, chaque occurrence des sites Y48 et Y68 peut être vue indépendamment en oubliant qu'ils apparaissent sur la même occurrence d'une configuration de dimères. Ceci revient à considérer la configuration d'un dimère comme un composant qui contient quatre processus, tout en estimant que savoir que ces quatres processus sont sur la même configuration d'un dimère n'est pas une information primordiale. Ces processus auraient tout autant pu se trouver sur des occurrences différentes, l'évolution de la quantité globale de la protéine Sos recrutée par la membrane aurait été la même. Ces processus ont alors $2 \cdot (n_{short} + n_{long})$ états différents (le facteur 2 vient du fait que les deux occurrences de la protéine récepteur sont distinguées par leur liaison asymétrique).

## 4.1.2 Le flot d'information

Le flot d'information entre les sites d'interactions de la configuration d'une espèce biochimique permet d'établir l'indépendance de ces quatre processus. Intuitivement, le flot d'information est une relation entre les sites d'une configuration d'espèces biochimiques qui indique l'état de quels sites est susceptible d'influencer la modification de l'état de quels autres sites. Elle prend la forme d'un graphe dont les nœuds sont les sites d'interactions d'une configuration d'espèces biochimiques et les arcs (orientés) peuvent relier soit deux sites sur une même occurrence de protéines, soit deux sites liés entre eux. Un chemin d'un site source vers un site cible témoigne que l'état du site source influence potentiellement la capacité à modifier l'état du site cible. Par contre, l'absence d'un tel chemin signifie que l'état du site source n'a aucune influence sur la modification éventuelle de l'état du site cible. La notion de flot d'information dans les modèles écrits en Kappa sera formalisée en section 4.4.2.

## 4.1.3 Réduction de la combinatoire

Une fois annotée par une sur-approximation de son flot d'information, il est possible d'identifier des portions de configurations d'espèces biochimiques dont le comportement peut être décrit de manière indépendante.

Ceci repose sur une décomposition en composantes fortement connexes des graphes formés par le flot d'information entre les sites d'interactions des configurations de chaque espèce biochimique. Il faut ainsi regrouper sur chaque graphe toute paire de sites tels qu'il existe un chemin de l'un vers l'autre et réciproquement. La décomposition du flot d'information dessinée en figure 4.2(a) est donnée en figure 4.2(b). Deux sortes de composantes fortement connexes sont à distinguer. Celles en rouge sont dites terminales car il n'est pas possible
<figure><img src="image_37.png" /><figcaption>Figure 4.2: Flot d'information dans la configuration d'un dimère. En 4.2(a), des flèches rouges relient deux sites sur une même occurrence de protéine ou deux sites sur un liaison. Un chemin d'un site source vers un site cible témoigne que l'état du site source influence potentiellement la capacité à modifier l'état du site cible. En 4.2(b), le graphe du flot d'information est décomposé en composantes fortement connexes. Chaque composante fortement connexe est représentée par une forme arrondie. Les composantes fortement connexes terminales sont dessinées en rouge alors que les autres le sont en noir.</figcaption></figure>

d'en sortir en suivant le flot d'information. Les autres sont représentées en noir. Pour obtenir une portion de la configuration d'un dimère dont le comportement peut être décrit indépendamment des autres sites d'interactions de cette configuration, il suffit de compléter chaque composante fortement connexe terminale en suivant le flot d'information en arrière. Ceci donne quatre portions de configuration d'espèces biochimiques, chacune correspondant à l'état d'avancement d'une occurrence du site Y48 ou Y68 dans le recrutement d'une occurrence de la protéine *Sos*, ce qui était le but.

Il semble ainsi possible d'exploiter l'absence de flot d'information pour détecter les corrélations inutiles, et ainsi découper les configurations d'espèces biochimiques en portions plus petites qui auront un comportement autonome.

## 4.2 Exemple jouet

Un exemple jouet permetra de mieux comprendre comment tout ceci fonctionne en pratique. Celui-ci implique une seule sorte de protéine, munie de trois sites : un site en haut, en rouge ; un site gauche, en vert ; et un site droit, en bleu. Chaque site pourra être phosphorylé ou non. Il n'y a pas de liaisons dans ce modèle.

Des hypothèses sont faites en ce qui concerne comment l'état de chaque site influence la modification de l'état des autres sites. Dans chaque occurrence de la protéine, l'état du site rouge contrôle à la fois l'évolution de l'état du site vert et celle du site bleu, comme indiqué dans la carte de contacts annotée en figure 4.4(a). Par contre, l'état du site vert n'a pas d'incidence sur l'évolution de l'état du site bleu, et réciproquement, l'état du site bleu n'a pas d'incidence sur l'évolution de l'état du site vert.

Pour permettre de donner l'expression de toutes les dérivées, seul un ensemble minimal de règles-réactions sera considéré. Elles sont appelées règles-réactions car ce sont des règles Kappa dans lesquelles l'état de tous les sites des protéines qui interagissent est spécifié. Elles peuvent donc être vues comme des réactions entre des configurations d'espèces biochimiques. Ces règles-réactions sont dessinées en figure 4.4(b). La première spécifie que le site du haut, en rouge, peut se faire phosphoryler quand les deux autres sont déphosphorylés. La constante de cette règle-réaction est $k^c$. Une fois le site du haut phosphorylé, le site gauche, en vert, et le site droit, en bleu, peuvent se faire phosphoryler à leur tour. Le fait que la phosphorylation au préalable du site du haut soit nécessaire à cela justifie le flot d'information du site du haut vers les deux autres sites. Sur la deuxième ligne de règles-réactions, la constante de phosphorylation, $k^g$, du site gauche, en vert, ne dépend pas
<figure><img src="image_38.png" /><figcaption>Figure 4.3: Chaque composante fortement connexe terminale est complétée des sites qui ont une influence sur elle. Chacune donne lieu à une portion de dimère qui se comporte de manière indépendante.</figcaption></figure>

du fait que le site droit, en bleu, soit déjà phosphorylé ou non. Il n'y a donc pas de flot d'information du site bleu vers le site vert. De même, sur la troisième ligne de règles-réactions, la constante de phosphorylation, $k^d$ du site droit, en bleu, ne dépend pas du fait que le site gauche, en vert, soit déjà phosphorylé ou non. Il n'y a donc pas de flot d'information entre l'état du site vert vers l'état du site bleu.

Le comportement de ce modèle est défini par l'application de la loi d'action de masse. Chaque réaction (ou ici règle-réaction) induit une contribution au système d'équations différentielles. L'activité de la réaction s'exprime comme le produit de la constante de la réaction et de la quantité des réactifs (qui apparaissent dans le membre gauche de la règle). Chaque réactif est alors consommé proportionnellement à l'activité de la réaction correspondante alors que chaque produit est ajouté dans la même quantité.

**Exemple 4.2.1** La première règle-réaction a pour activité $k^c$. [ ] . Elle induit deux termes dans le système d'équations différentielles :

$$ \left\{ \begin{array}{l} \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{绿} \\ \text{黄} \\ \text{蓝} \\ \text{白} \end{smallmatrix} \right] \quad \pm \quad k^c \cdot \left[ \begin{smallmatrix} \text{绿} \\ \text{黄} \\ \text{蓝} \\ \text{白} \end{smallmatrix} \right] \\ \\ \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{绿} \\ \text{黄} \\ \text{蓝} \\ \text{白} \end{smallmatrix} \right] \quad \pm \quad k^c \cdot \left[ \begin{smallmatrix} \text{绿} \\ \text{黄} \\ \text{蓝} \\ \text{白} \end{smallmatrix} \right] \end{array} \right. $$

Le système différentiel complet est donné en figure 4.4(c).

Il existe plusieurs conventions pour tenir compte des symétries éventuelles quand une réaction contient plusieurs occurrences d'un même réactif [15]. Elles prennent alors la forme d'un facteur correctif à appliquer à l'activité des réactions. Ce n'est le cas d'aucune réaction de cet exemple.
<figure><img src="image_39.png" /></figure>

$$
\left\{
\begin{aligned}
\frac{d}{dt} \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Green Ball} \\ \text{Blue Ball} \end{smallmatrix} \right] &= -k^c \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Green Ball} \\ \text{Blue Ball} \end{smallmatrix} \right] \\
\frac{d}{dt} \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] &= k^c \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] - (k^g + k^d) \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] \\
\frac{d}{dt} \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] &= k^d \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] - k^g \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] \\
\frac{d}{dt} \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] &= k^g \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] - k^d \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] \\
\frac{d}{dt} \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] &= k^g \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right] + k^d \cdot \left[ \begin{smallmatrix} \text{Red Ball} \\ \text{Blue Ball} \\ \text{Green Ball} \end{smallmatrix} \right].
\end{aligned}
\right.
\tag{c) Système d'équations différentielles induit.}
$$

Figure 4.4: Un exemple jouet. Une protéine contient trois sites qui peuvent être phosphorylés ou non. En 4.4(a), la carte de contacts annotée indique que l'état du site du haut, en rouge, peut influencer la modification de l'état du site gauche, en vert, et l'état du site droit, en bleu. Par contre, l'état du site gauche n'a pas d'influence sur la capacité à modifier l'état du site droit, et réciproquement, l'état du site droit n'a pas d'influence sur la capacité à modifier l'état du site gauche. Ceci se traduit au niveau des règles d'interactions (voir en 4.4(b)). Une fois le site du haut phosphorylé (par la première réaction). Le site gauche peut se faire phosphoryler avec la constante de réaction, $k^g$, que le site droit soit déjà phosphorylé ou non. De même, le site droit peut se faire phosphoryler avec la constante de réaction, $k^d$, que le site gauche soit déjà phosphorylé ou non. Ce modèle ne contient que des étapes de phosphorylation pour garder le système différentiel de taille raisonnable. En appliquant le principe de la loi d'action de masse, ces règles-réactions induisent le système différentiel donné en 4.4(c).
<figure><img src="image_40.png" /><figcaption>(a) Carte de contacts pour la portion gauche de la protéine.</figcaption></figure>

$$ \left\{ \begin{array}{l} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \end{array} \right. $$

<caption>(c) Fonction d'abstraction function pour la portion gauche de la protéine.</caption>

$$ \left\{ \begin{array}{l} \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = -k^c \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = -k^g \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + k^c \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = k^g \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \end{array} \right. $$

<figure><img src="image_41.png" /><figcaption>(b) Carte de contacts pour la portion droit de la protéine.</figcaption></figure>

$$ \left\{ \begin{array}{l} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] := \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \end{array} \right. $$

<caption>(d) Fonction d'abstraction function pour la portion droite de la protéine.</caption>

$$ \left\{ \begin{array}{l} \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = -k^c \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = -k^d \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] + k^c \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \\ \\ \displaystyle \frac{d}{dt} \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] = k^d \cdot \left[ \begin{smallmatrix} \text{Red} \\ \text{Green} \end{smallmatrix} \right] \end{array} \right. $$

<caption>(f) Système d'équations différentielles pour la portion droite de la protéine.</caption>

Figure 4.5: Réduction de la sémantique différentielle de l'exemple jouet (voir en figure 4.4). En utilisant le fait que l'état du site gauche de la protéine n'influence pas l'évolution de l'état du site droit et que réciproquement, l'état du site droit n'influence pas l'état du site gauche, il est possible de découper la protéine en deux parties. La quantité d'un motif est définie comme la combinaison linéaire de la quantité des configurations de la protéine compatible avec ce motif en 4.5(c) et 4.5(d). En 4.5(e) et 4.5(f) sont exprimées les dérivées de la quantité des différents motifs en fonction de la quantité de ces motifs.
Il est possible d'exploiter l'absence de flot d'information du site vert vers le site bleu, et du site bleu vers le site vert. Ceci revient à découper chaque occurrence de protéines en deux portions. Comme l'état du site rouge contrôle à la fois l'évolution de l'état du site vert et celle du site bleu, ces deux portions devront se chevaucher sur le site rouge. Ainsi, les portions gauches de la protéine documenteront l'état du site rouge et du site vert alors que les portions droites documenteront l'état du site rouge et du site bleu. Le flot d'information entre les sites de ces portions de protéines est donné en 4.5(a) et 4.5(b).

Pour utiliser les différentes configurations de portions de la protéine comme des variables, il faut leur donner un sens formel. Celui-ci provient du principe de dualité entre leurs significations intensionnelles et extensionnelles. De manière intensionnelle, la configuration d'une portion de la protéine peut être comprise comme le sous-graphe d'une configuration complète de la protéine. De manière extensionnelle, la configuration d'une portion de la protéine peut être vue comme le multi-ensemble de toutes les configurations complètes de la protéine qui contiennent cette portion, multipliées par le nombre de plongement de cette portion dans chaque configuration complète. Sous cette angle, la quantité la configuration d'une portion de la protéine peut se définir comme la combinaison linéaire des quantités des configurations complètes de la protéine qui contiennent cette portion. Ceci permet d'obtenir les définitions en figures 4.5(c) et 4.5(d). En particulier, la quantité d'une portion de protéine dont aucun site n'est phosphorylé est égal à la quantité des protéines entièrement déphosphorylées (puisque le site rouge doit être phosphorylé en premier). La quantité des autres portions est obtenue en sommant la quantité des configurations obtenues selon l'état du site non documenté.

Les équations qui décrivent l'évolution des quantités décrites en figures 4.5(c) et 4.5(d) peuvent ensuite être dérivées. Elles sont données en figures 4.5(e) et 4.5(f) et peuvent être vérifier analytiquement à partir des équations en figure 4.4(c).

Réduire un système d'équations différentielles à 5 variables en un système à 6 variables n'est guère impres-
sionnant. Toutefois, en regardant de plus près, les 5 variables du système initial correspondent à 1 variable pour
la configuration avec le site rouge déphosphorylé et à 2 × 2 variables pour les autres configurations, selon que
le site vert soit phosphorylé ou non, et selon que le site bleu soit phosphorylé ou non. Dans le modèle réduit,
la variable pour la configuration avec le site rouge déphosphorylé est représentée de manière redondante par
deux variables du système réduit (leur valeur restera donc égale au cours de l'éxécution du système réduit). Les
variables pour les autres configurations correspondent à 2 + 2 variables, car il y a deux côtés et pour chaque côté
le site vert ou bleu peut être phosphorylé ou non. La réduction du modèle a donc remplacé une multiplication
par une somme, ce qui aura un impact important lorsque le nombre de combinaisons possibles sera plus grand.

En guise de consclusion sur cet exemple, il est dont possible d'exploiter l'absence de flot d'information entre
des sites des occurrences de protéines, afin de détecter des corrélations entre les états de plusieurs sites qui
peuvent être ignorées. Cela revient à découper les configurations des espèces biochimiques en configuration
de portions d'espèces biochimiques, et ainsi casser la combinatoire du système différentiel sous-jacent. Bien
entendu, cette abstraction perd de l'information. Il n'est plus possible d'exprimer les corrélations qui ont été
oubliées. Par contre, l'évolution de la quantité des configurations de portions d'espèces biochimiques qui auront
été gardées se décrit de manière autonome, c'est à dire uniquement à partir de la quantité des configurations
de portions d'espèces biochimiques elles-mêmes.

4.3 Réduction de systèmes d'équations différentielles

En section 4.3 est proposé un cadre formel pour réduire la dimension des systèmes d'équations différentielles ordinaires.

Les systèmes d'équations différentielles décrivent des quantités qui évoluent au cours du temps selon des contraintes sur la valeur de leurs dérivées. Une réduction de modèle consiste à trouver des changements de variables pour lesquels l'évolution de nouvelles quantités, appelées observables, peut se décrire de manière autonome. Ainsi la dérivée des observables doit pouvoir s'exprimer uniquement à partir de la valeur des observables.

Plus formellement, un système d'équations différentielles est donné par un ensemble fini de variables, $V$, qui
représentent ici la quantité de chacune des configurations des espèces biochimiques et par une fonction, $F$, de
l'ensemble des fonctions réelles positives ou nulles sur l'ensemble des variables $V$ vers l'ensemble des fonctions
réelles sur l'ensemble des variables $V$. La fonction $F$ est supposée dérivable et sa dérivée est continue. Une
fonction réelle positive ou nulle sur l'ensemble $V$ est appelée un état potentiel. En effet, un état associe à chaque
variable, la quantité de l'espèce biochimique correspondante, qui ne peut pas être négative. Une fonction réelle
sur l'ensemble $V$ est appelée un incrément. Une telle fonction définit comment la quantité de chaque espèce
coefficient stœchiométrique 1), ne diverge pas. De ce fait, leurs sémantiques sont définies sur $\mathbb{R}^+$ quel que soient leurs états initiaux. En particulier, seul le comportement des systèmes ouverts (avec introduction externe de composants) est susceptible de diverger. Un exemple minimal de système dont le comportement diverge est donné en Exe. 4.3.3.

**Exemple 4.3.3** Soit le réseau réactionnel défini par l'unique réaction suivante :

$$A, A \xrightarrow{k} A, A, A$$

portant sur une seule sorte de protéines, A.

La quantité de la protéine A est régie par l'équation différentielle suivante :

$$\frac{d[A]}{dt} = k \cdot [A]^2,$$

dont les solutions sont de la forme suivante :

$$[A] = \frac{[A]_0}{k - [A]_0 \cdot t}.$$

Chaque solution maximale diverge donc en $t = \frac{k}{[A]_0}$.

Réduire un système d'équations différentielles ordinaires consiste à changer de perspective en trouvant un ensemble de quantités d'intérêt, appelées les observables, dont l'évolution peut s'exprimer de manière autonome. Cela signifie que la dérivée des observables est entièrement définie par leurs valeurs. Pour formaliser ces notions, il faut d'une part, relier la valeur des observables aux variables du système d'équations différentielles initial et d'autre part, définir la fonction qui décrit l'évolution temporelle de ces valeurs.

Formellement, une réduction de modèle est définie par la donnée d'un ensemble fini d'observables, $V^!$, une fonction d'abstraction, $\psi$, qui associe à chaque état du système initial un état du nouveau système (c'est à dire une fonction de l'ensemble des fonctions positives ou nulles sur l'ensemble des observables $V^!$), et d'une fonction $F^!$ de l'ensemble des fonctions positives ou nulles sur l'ensemble des observables $V^!$ vers l'ensemble des fonctions réelles sur l'ensemble de observables $V^!$.

Des hypothèses supplémentaires sont requises pour garantir la correction de la réduction de modèle.

1. La fonction d'abstraction $\psi$ doit être choisie linéaire à coefficients positifs. Elle doit de plus préserver les suites qui divergent, ce qui signifie que pour toute suite divergente de fonctions positives ou nulles $(\rho_i)_{i \in \mathbb{N}}$ sur l'ensemble des variables initiales $V$, la suite $(\psi(\rho_i))_{i \in \mathbb{N}}$ diverge également.

2. Les fonctions d'abstraction $\psi$, la fonction de dynamique concrète $F$ et la fonction de dynamique abstraite $F^!$ sont reliées par le diagramme commutatif suivant :

$$(V \to \mathbb{R}^+) \xrightarrow{F} (V \to \mathbb{R})$$

$\psi$

$$(V^! \to \mathbb{R}^+) \xrightarrow{F^!} (V^! \to \mathbb{R})$$

ce qui signifie que $\psi \circ F = F^! \circ \psi$.

Prendre la fonction d'abstraction $\psi$ linéaire permet de la faire commuter avec la somme et l'intégrale utilisées pour définir la sémantique des systèmes différentiels. La prendre à coefficients positifs assure que l'image d'une fonction positive ou nulle est une fonction positive ou nulle, et donc que l'image d'un état concret sera un état abstrait. L'intérêt de l'hypothèse de préservation de la divergence des suites d'états sera expliqué plus tard. On peut toutefois remarquer que cette hypothèse revient à supposer que toute variable concrète apparaît au moins une fois avec un coefficient non nul dans la combinaison linéaire associée à au moins un des observables. Enfin le diagramme commutatif permet à la fonction d'abstraction et à la fonction de dynamique concrète de commuter, au prix de transformer la dynamique concrète — sur les variables du système initiale — en dynamique abstraite — sur les observables. Dit autrement, partant d'un état concret, le même résultat est obtenu en calculant la dérivée du système dans cet état, puis en calculant l'abstraction de cette dérivée ; ou en calculant l'abstraction de l'état d'abord, puis en calculant la dérivée du système réduit dans l'état abstrait obtenu.
$$
\nu^{\sharp} := \left\{ \begin{array}{c} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \\ \text{[orange square]} \\ \text{[purple circle]} \\ \text{[green circle]} \\ \text{[blue circle]} \\ \text{[purple circle]} \\ \text{[orange circle]} \end{array} \right\} \\
\text{(a) Ensemble des observables.}
$$

$$
\psi(\rho) := \left\{
\begin{array}{c}
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture} \mapsto \rho \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture} \mapsto \rho \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \end{pmatrix} + \rho \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture} \mapsto \rho \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \end{pmatrix} + \rho \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \\ \text{[blue square]} \\ \text{[purple square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\end{array}
\right.
\quad
\text{(b) Abstraction function.}
$$

$$
\mathbb{F}^{\sharp}(\rho^{\sharp}) := \left\{
\begin{array}{ll}
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & -k^c \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & -k^g \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} + k^c \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & k^g \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & -k^c \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & -k^d \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} + k^c \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}]
\node[circle, fill=red, inner sep=1pt] (top) at (0,0) {};
\node[circle, fill=red, inner sep=1pt] (bottom) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (left) at (0,0) {};
\node[circle, fill=green, inner sep=1pt] (right) at (0,0) {};
\node[circle, fill=blue, inner sep=1pt] (topleft) at (0.5,0) {};
\node[circle, fill=blue, inner sep=1pt] (topright) at (-0.5,0) {};
\node[circle, fill=purple, inner sep=1pt] (bottomleft) at (0,0.5) {};
\node[circle, fill=bottomleft, fill=white, inner sep=1pt] (bottomright) at (0,0.5) {};
\draw[thick] (top) -- (bottom);
\draw[thick] (topleft) -- (bottomleft);
\draw[thick] (top) -- (topright);
\draw[thick] (bottom) -- (bottomright);
\end{tikzpicture}
\mapsto & k^d \cdot \rho^{\sharp} \begin{pmatrix} \text{[red square]} \\ \text{[green square]} \end{pmatrix} \\
\text{(c) Équations différentielles.}
\end{array}
\right.
$$

<caption>Figure 4.7: Reduction de la sémantique différentielle pour l’exemple jouet.</caption>

**Exemple 4.3.4** *En figure 4.7 est donnée une réduction pour le système différentiel défini en figure 4.4. Les observables sont formés des motifs obtenus en prenant le site rouge, en haut, et en oubliant l'état du site vert, à gauche, ou l'état du site bleu, à droite. Ils sont donnés en figure 4.7(a).*

La quantité des observables est définie en fonction de la quantité des différentes configurations de la protéine en figure 4.7(b). En particulier, la quantité des motifs avec le site rouge non phosphorylé est définie comme la quantité de la configuration de la protéine dont aucun site n’est phosphorylé. Pour les autres motifs, cette quantité est définie comme la somme de la quantité des deux configurations qui contiennent ce motif. Il s’agit bien d’une fonction linéaire à coefficients positifs. Il faut remarquer que la concentration de chaque configuration d’espèces biochimiques apparaît au moins une fois dans la fonction $\psi$ ce qui assure que cette fonction préserve la divergence des suites d’états.

Enfin, la dérivée des observables est donnée en figure 4.7(c). On peut vérifier par le calcul que $\psi \circ F = F^{\sharp} \circ \psi$, ce qui assure que le diagramme commute.

Il est maintenant possible d'appliquer la fonction d'abstraction $\psi$ à gauche et à droite de l'égalité de Cauchy-Lipschitz qui avait servi à définir la sémantique du système initial.

Ainsi, pour $X_0$ un état initial (une fonction positive ou nulle sur l'ensemble $V$) et pour $T$ un instant de l'intervalle $[0, T_{X_0}^{\max}]$, l'équation suivante est vérifiée :

$$
\psi(X_{X_0}(T)) = \psi \left( X_0 + \int_{t=0}^{T} \mathbb{F}(X_{X_0}(t)) \cdot dt \right).
$$
Par linéarité de la fonction d'abstraction $\psi$, elle se distribue sur l'addition, ce qui donne l'équation suivante :

$$ \psi(X_{X_0}(T)) = \psi(X_0) + \psi\left(\int_{t=0}^{T} \mathbb{F}(X_{X_0}(t)) \cdot dt\right). $$

Toujour par linéarité, elle commute avec l'intégrale, ce qui donne l'équation suivante :

$$ \psi(X_{X_0}(T)) = \psi(X_0) + \int_{t=0}^{T} \psi(\mathbb{F}(X_{X_0}(t))) \cdot dt. $$

Enfin, en utilisant le fait que $[\psi \circ \mathbb{F}] = [\mathbb{F}^{\sharp} \circ \psi]$, il vient l'équation suivante :

$$ \psi(X_{X_0}(T)) = \psi(X_0) + \int_{t=0}^{T} \mathbb{F}^{\sharp}(\psi(X_{X_0}(t))) \cdot dt. $$

De ce fait, la fonction qui, à tout instant $T$ dans l'intervalle $[0, T_{X_0}^{\max}]$, associe l'état abstrait $\psi(X_{X_0}(T))$ est solution de l'équation différentielle suivante :

$$ Y_{Y_0}(T) = Y_0 + \int_{t=0}^{T} Y_{Y_0}(t) \cdot dt, $$

pour $Y_0 = \psi(X_0)$.

C'est en fait une solution maximale de cette équation. En effet, c'est clair lorsque $T = +\infty$. Dans le cas contraire, l'expression $X_{X_0}(T)$ diverge quand $T$ tend vers $T_{X_0}^{\max}$. Puis comme la fonction $\psi$ préserve la divergence des suites et qu'elle est continue, l'expression $\psi(X_{X_0}(T))$ diverge aussi quand $T$ tend vers $T_{X_0}^{\max}$. Ainsi la fonction qui à tout instant $T$ dans l'intervalle $[0, T_{X_0}^{\max}]$ associe l'état abstrait $\psi(X_{X_0}(T))$ ne peut pas être prolongée.

**Exemple 4.3.5** Pour finir cette partie, voici un exemple qui explique l'importance de l'hypothèse sur la pré serv-

Soit le réseau réactionnel défini par les deux réactions suivantes :

$$ \begin{cases} A, A \xrightarrow{k_A} A, A, A \\ B \xrightarrow{k_B} B, B \end{cases} $$

portant sur deux sortes de protéines A et B.

La quantité de ces protéines est régie par l'équation différentielle suivante :

$$ \begin{cases} \frac{d[A]}{dt} = k_A \cdot [A]^2 \\ \frac{d[B]}{dt} = k_B \cdot [B] \end{cases} $$

dont la solution maximale est donnée ci-dessous :

$$ \begin{cases} [A] = \frac{[A]_0}{k - [A]_0 \cdot t} \\ [B] = [B]_0 \cdot e^{kt} \end{cases} $$

pour $t$ variant dans l'intervalle de temps $[0, \frac{k}{[A]_0}]$.

En ignorant la contrainte sur la préservation de la divergence des suites d'états, il est possible d'oublier la quantité de la protéine A. Il suffit pour cela de prendre le singleton $\{B\}$ comme ensemble des observables et la fonction qui à chaque état du système associe sa restriction à l'ensemble $\{B\}$ comme fonction d'abstraction.

Le système réduit suivant est alors obtenu :

$$ \frac{d[B]}{dt} = k_B \cdot [B]. $$