Mercedes est un projet exploratoire 2017 du LabEx PERSYVAL-Lab.

Dans ce projet une technique permettant la réécriture parallèle de graphe est proposée. Un logiciel permettant la mise en pratique de cette théorie est en cours de finalisation. Enfin un problème biologique très concret est en cours de développement.

Réécriture parallèle de graphes

Le travail que nous menons porte sur les systèmes de réécriture simultanée avec recouvrement dans un contexte de transformation de graphes. Etant donné un ensemble de règles de réécriture R= {l_i → r_i, 1 ≤ i ≤ n } , un système de règles de réécriture appliqué à un état initial s est tel que toutes les occurrences des l_i dans s doivent être remplacées par une occurrence de r_i en un pas de réécriture. Les membres gauches de règles peuvent se chevaucher. Certaines parties droites de la règle peuvent également se chevaucher. Décider de la manière de réécrire nécessite alors une stratégie de réécriture qui dépend du cadre de l'application de ces règles. Nous proposons donc une définition formelle pour ces transformations de graphes en s'inspirant des techniques de réécriture modulo. Cette modélisation assure un résultat déterministe à condition que la réécriture soit déterministe. L'importance du déterminisme est double. Il prouve que la gestion des chevauchements est bien faite et permet une analyse théorique du comportement du système dans son ensemble. Comme illustration, voici l'exemple d'un raffinement d'un maillage triangulaire. Considérons la règle de réécriture l → r définie graphiquement comme suit :

Une étape de réécriture se fait en deux temps : les occurences de l sont remplacées par des occurences de r. Par suite, la réécriture modulo identifie des ensembles de ports et des ensembles de noeuds.

Le logiciel GPaR

Le logiciel GPaR est la mise en oeuvre de ce travail théorique. Il est implémenté en C++. Il dispose de fenêtres graphiques permettant de définir le graphe initial, l'ensemble des règles de réécriture et la stratégie d'application parallèle des règles de réécriture. Ce logiciel peut être utilisé pour le calcul de systèmes dynamiques discrets très variés. Les applications en physique et en biologie sont nombreuses. Le logiciel traite les automates cellulaires et les L-systèmes, sans être restreint à ces seuls concepts. Dans l'example proposé ci-dessous, le raffinement parallèle de maillages est utilisé pour la localisation d'une fonction implicite.

Modèle pour la biologie : La meiose chez la souris mus musculus domesticus 2n=40

Dans cette partie, nous nous intèressons à la modélisation de comportements biologiques encore au stade d'observation : L'étude algorithmique et probabiliste des associations entre chromosomes de cellules d'une souris particulière appelée mus musculus domesticus 2n=40 . L'association entre les chromosomes (bivalents) d'une spermatocyte en état de Pachitène (Méiose) a été étudiée d'un point de vue expérimental à la Faculté de Médecine, Universidad de Chile, (Santiago, Chili). Un ensemble d'observations a montré que pendant la prophase précoce des noyaux, les complexes centromères - télomères (CTC) sont groupés et forment une structure dite bouquet. Puis les CTC glissent sur la surface du noyau et des sous ensembles connexes de CTC se forment. Nous disposons donc d'une base de données expérimentales sur les ensembles connexes de CTC des cellules de souris. Voici un extrait des observations biologiques du bouquet et de la migration des CTC :

Nous proposons une modélisation de la cellule obéissant à des contraintes de forme et de taille en relation avec les données expérimentales. Puis, nous proposons une dynamique stochastique d'évolution des CTC's. Les résultats obtenus sont très similaires à ceux observés.

Puis nous modélisons le nuage de chromatine induit par cette migration des CTC. Ci-dessous est présenté une observation biologique de nuages de chromatique à l'intérieur d'un noyau et une simulation.