Un calcul de réécriture de graphes : applications à la biologie et aux systèmes autonomes, A rewriting calculus for graphs : applications to biology and autonomous systems

Oana-Maria Andrei

Description

Sous la direction de Hélène Kirchner
Thèse soutenue le 05 novembre 2008: INPL
L'objectif de cette thèse est d'explorer des descriptions formelles pour la structure et le fonctionnement des systèmes biologiques, ainsi que des outils formels pour raisonner au sujet de leur comportement. Cette thèse s'inscrit dans les travaux étudiant les modèles informatiques sûrs où les calculs sont exprimés par l'intermédiaire de la réécriture, et où nous pouvons compter sur la vérification formelle pour exprimer et valider les propriétés des modèles. Dans cette thèse nous développons un calcul de réécriture d'ordre supérieur pour décrire des molécules, des règles de réaction, et la génération des réseaux biochimiques. Le calcul est basé sur la métaphore chimique en décrivant les calculs en termes de solutions chimiques dans lesquelles les molécules représentant des données agissent l'une sur l'autre librement selon des règles de réaction. Ainsi nous avons obtenu un Calcul Biochimique Abstrait étendant le modèle chimique d'ordre supérieur en considérant des molécules structurées. Le calcul est équipé d'une spécification naturelle de la concurrence et des mécanismes de contrôle grâce à l'expression des stratégies de réécriture sous forme de molécules. La description des complexes moléculaires ou des réactifs chimiques appartient à une classe spécifique de graphes. Nous définissons la structure des graphes avec ports et nous montrons que les principes du calcul biochimique instanciés pour les graphes avec ports sont assez expressifs pour modéliser des systèmes autonomes et des réseaux biochimiques. En plus, les techniques de la réécriture stratégique ouvrent la voie au raisonnement basé sur les calculs et à la vérification des propriétés des systèmes modélisés
-Calcul de réécriture
-Réseaux biochimiques
-Systèmes autonomes
-Stratégies de réécriture
-Réécriture de graphes
The objective of this thesis is to explore formal descriptions for the structure and functioning of biological systems, as well as formal tools for reasoning about their behavior. This work takes place in the overall prospective to study safe computational models where computations are expressed via rewriting, and where we can rely on formal verification to express and validate suitable properties. In this thesis we develop a higher-order calculus rewriting for describing molecules, reaction patterns, and biochemical network generation. The calculus is based on the chemical metaphor by describing the computations in terms of chemical solutions in which molecules representing data freely interact according to reaction rules. This way we obtained an Abstract Biochemical Calculus as an extension of the higher-order chemical model by considering structured molecules. The calculus is provided with a natural specification of concurrency and of controlling mechanisms by expressing rewrite strategies as molecules. The description of molecular complexes or chemical reactants belong to specific classes of graphs. We define the structure of port graphs and we show how the principles of the biochemical calculus instantiated for port graphs are expressive enough for modeling autonomous systems and biochemical networks. In addition, strategic rewriting techniques open the way to reason about the computations and to verify properties of the modeled systems
-Rewriting calculus
-Autonomous system
-Biochemical networks
-Graph rewriting
-Strategic rewriting
Source: http://www.theses.fr/2008INPL058N/document

Sujets

• Autonomous System

Informations

• Publié par: Thesee
• Nombre de lectures: 80
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL : [e-mail]




LIENS




Code de la propriété intellectuelle. Articles L 122.4
Code de la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
Departement de formation doctorale en informatique
Institut National Ecole doctorale IAEM Lorraine
Polytechnique de Lorraine
Un calcul de reecriture de graphes :
applications a la biologie et aux systemes
autonomes
THESE
presentee et soutenue publiquement le 5 Novembre 2008
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
(specialite informatique)
par
Oana Andrei
Composition du jury
Rapporteurs : Jean-Pierre Ban^atre Professeur, Universite de Rennes 1, France
Jean-Louis Giavitto Directeur de Recherche, IBISC, CNRS, France
Examinateurs : Paolo Baldan Professeur, Universite de Padova, Italie
Horatiu Cirstea Ma^ tre de Conferences, Universite Nancy 2, France
Marie-Dominique Devignes Chargee de Recherche CNRS, Habilitee, Nancy, France
Helene Kirchner Directeur de Recherche, INRIA Bordeaux, France
Dorel Lucanu Professeur, Universite \Al.I.Cuza", Iasi, Roumanie
Jean-Yves Marion Ecole des Mines de Nancy, France
Laboratoire Lorrain de Recherche en Informatique et ses Applications | UMR 7503T
Mis
L
en
X
page
A
a
E
v
ecOb
T
.
able
3.5
des
Abstrait
mati?res
.
In
.
tro
.
duction
.
1
.
I
.
U
.
n
.
Calcul
.
Bio
.
c
.
himique
.
Abstrait
.
13
.
1
.
Notions
Substitutions,
Pr?liminaires
.
15
.
1.1
taxe
Relations
de
binaires
43
et
Au
leurs
.
propri?t?s
V
.
.
.
Structure
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.6
.
.
.
ue
.
.
.
P
.
.
.
.
15
.
1.2
.
Graphes
.
.
.
.
.
.
.
.
Calcul
.
.
.
.
.
.
.
artie
.
.
.
.
.
.
.
Syn
.
.
.
.
.
.
.
.
.
3.2
.
.
.
.
.
.
.
.
.
Abstraites
.
.
.
.
.
.
.
3.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ou
.
.
.
.
.
.
16
la
1.3
Calcul
Syst?mes
.
de
4
R?du
43
c
.
ti
.
o
.
n
.
Abstraits
Explicite
.
.
.
.
.
.
.
Conuence
.
.
.
.
.
.
.
.
.
.
.
.
.
30
.
rs
.
c
.
.
.
.
.
.
.
.
.
.
.
32
.
la
.
.
.
.
.
.
17
.
1.4
.
R??criture
.
de
.
T
33
ermes
35
.
structur?s
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
jets,
.
.
.
.
18
.
1.4.1
.
Alg?bre
.
de
.
termes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
ers
.
.
.
.
.
.
.
.
.
.
.
3.7
.
ble
.
y
.
Base
.
.
.
.
.
.
.
.
.
tique
.
P
.
S?man
.
.
.
.
18
.
1.4.2
.
Th?ories
.
?quationelles
.
.
.
.
.
.
Rendre
.
.
.
.
.
.
.
.
.
.
.
.
.
44
.
de
.
cale
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19
2.3
1.4.3
e
R??criture
un
de
Bio
T
himique
ermes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.4
.
de
.
P
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
.
1.5
.
?l?men
3
ts
taxe
de
3.1
Th?orie
jets
d
.
es
.
Cat?gories
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
.
Abstractions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
.
1.6
.
T
.
rans
.
fo
.
rmation
.
de
.
Graphe
.
.
.
.
.
.
36
.
Mol?cules
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
.
Sous-ob
.
Sous-mol?cules,
.
Filtrage
.
.
.
.
.
.
.
.
23
.
1.7
.
R??criture
38
Strat?gique
Mondes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
.
Structures
.
Mondes
.
Multiv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
.
2
.
Motiv
.
ation
.
et
41
V
V
ue
d'Ensem
d'Ensem
de
ble
S
du
n
Calcul
de
29
du
2.1
.
Le
.
i
.
-calcul
.
et
.
HOCL
.
.
.
.
41
.
S?man
.
?
.
etit
.
as
.
4.1
.
tique
.
Base
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2
.
l'Application
.
.
.
.
.
.
.
.
29
.
2.2
.
Le
.
45
.
-calcul
.
.
.
.
.
.
.
.
.
.
4.3
.
sujet
.
la
.
Lo
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
T
d
able
.
des
.
mati?res
P
4.4
.
D'ab
.
ord
.
refroid
.
ir,
.
puis
ec
r?c
.
hauer
.
.
.
.
74
.
.
.
Graphes
.
.
.
v
.
.
.
Un
.
.
.
.
.
.
.
.
.
R?gle
.
.
.
.
.
.
.
.
.
.
.
a
.
.
.
.
.
.
.
la
45
.
4.5
.
V
.
u
.
e
.
d'ensem
r
ble
.
de
.
la
.
S?man
.
tique
.
du
l
Calcul
.
a
.
v
92
ec
P
Application
.
Explicite
.
.
.
.
.
46
.
5
.
Ajouter
R??criture
des
.
Strat?gies
.
au
.
Calcul
R??criture
47
orts
5.1
.
Des
.
Strat?gies
P
sous
.
F
.
ormes
.
d'Abstractions
Sur
.
a
.
.
.
80
.
R?actif