HDR PDF
HDR PDF
HDR PDF
présentée devant
L’Université de Rennes 1
Spécialité : Mathématiques et Informatique
par
Anne Siegel
au vu des rapports de :
Ce travail est avant tout le fruit de huit années de rencontres variées... Remercier tous
les gens qui y ont contribué en peu de mots est une tâche ardue.
Mes premiers et plus sincères remerciements doivent aller à Pierre Arnoux, Valérie
Berthé et Jacques Nicolas.
Pierre Arnoux m’a fait découvrir les systèmes dynamiques et a encadré mes premiers
pas dans la recherche ; il a gardé un oeil sur moi depuis ma thèse, même si les pistes que j’ai
explorées (biologie, topologie ou théorie des nombres) ne sont pas ses thèmes préférés. En
plus des règles du métier, il m’a appris à prendre le temps d’identifier l’essentiel derrière une
problématique (ce que je ne fais pas encore assez). Il est pour moi un modèle d’intégrité,
et je reste admirative de sa capacité à décrire l’essentiel d’un article obscur de 30 pages en
moins de 10 lignes limpides.
Valérie Berthé a elle aussi encadré mes premiers pas de chercheuse ; elle est devenue
une amie très proche. Son imagination, son immense culture dans différents domaines, ses
qualités d’écoute et de communicante font d’elle une grande scientifique dont j’espère être
un jour à la hauteur.
Jacques Nicolas m’a accueillie dans le projet Symbiose, à une époque où j’étais une
jeune mathématicienne très culottée récemment recrut ée en informatique au CNRS. J’étais
tentée par la biologie via l’informatique, alors que mes compétences dans ces deux domaines
étaient très limitées. Il m’a laissé ma chance... En plus de ses qualités de chercheur, son
soutien constant, ses conseils avisés, sa vision de la science et sa gestion tout en doigté de
l’équipe, en respectant la personnalité de chacun (y compris la mienne !) m’ont offert un
cadre rare pour m’épanouir en canalisant mon enthousiasme quelque peu débordant.
Mon plus grand respect et mes profonds remerciements vont aux rapporteurs qui ont
accepté de s’attaquer à ce document, dont les contours sont bien variés. Par leurs résultats
à l’interface de différents domaines, ils sont pour moi des modèles : Alejandro Maass dont
le parcours scientifique et les thèmes de recherches font le grand écart entre la théorie
ergodique et la bioinformatique ; Hidde de Jong, si grand nom de la modélisation des
systèmes biologiques ; Marie-Pierre Béal si grand nom de l’informatique théorique ; Boris
Solomyak, dont les travaux et la gentillesse ont inspiré tant de chercheurs... Je suis aussi
très honorée que Jérome Buzzi et Elisabeth Pécou (quand trouvera-t-on donc le temps de
travailler ensemble ?) aient accepté de participer à mon jury.
Je dois ensuite remercier le groupe de systémiciens avec qui tout le projet autour
de la biologie a été développé, et tous essentiels à sa réalisation : Michel Le Borgne qui
m’a beaucoup appris en informatique et biologie (entre autre que je suis allergique à la
programmation) ; Ovidiu Radulescu, à l’intuition débordante ; Philippe Veber, toujours
prêt à explorer de nouvelles voies avec enthousiasme, même quand il s’agit de relire ce
1
2
mémoire (et sauf quand il s’agit de rédiger sa thèse) ; Carito Guziolowski, venue du bout
du monde, à la volonté de fer, et imbattable pour faire parler des données de manière
intelligente ; Pierre Blavy, toujours bricoleur, mais d’une rigueur absolue lorsqu’il s’agit de
proposer une conclusion biologique ; François Moreews, expert en Java et en interactions,
Annabel Bourdé et Gregory Ranchy, toujours présents pour trouver une solution logicielle à
mes “ce serait bien si...” ; Sandrine Laguarrigue et Nathalie Théret, nos biologistes préférées
qui ont eu la patience de nous transmettre leurs intuitions et leurs connaissances en biologie
pour que nous essayions de produire des résultats exploitables ; Et les derniers arrivés,
Tatiana Bauromatova et Sylvain Blachon, qui n’hésitent pas depuis leur arrivée à nous
titiller sur l’applicabilité réelle de nos travaux ce qui oblige (heureusement) à réfléchir
encore et encore !
Au sein de ce groupe, les caractères ont toujours été bien trempés, les opinions ont
pu diverger, et les relations ont été parfois houleuses. Mais l’énergie, l’enthousiasme et
globalement la bonne humeur ne se sont jamais démenties et sont au coeur du travail
présenté ici.
Je dois encore mentionner les collaborateurs qui m’ont fait découvrir de nouveaux hori-
zons scientifiques et géographiques : Joerg Thuswaldner, qui m’a introduit à la topologie et
m’a permis de découvrir l’opéra viennois ; Shigeki Akiyama et ses numérations non entières,
ainsi que l’équipe de Japonais (Shunji Ito, Maki Furukado, Hiromi Ei) grâce auxquels le
Japon est un univers un peu moins fermé ; Arnaud Hilion et la géométrie des groupes
libres (même si décidément j’ai du mal avec la géométrie) ; Boris Adamczewski (frère ou
demi-frère selon la généalogie scientifique ?) qui m’a toujours impressionnée par sa rigueur
et ses intuitions ; Wolfgang Steiner, lui aussi d’une rigueur bien nécessaire pour recadrer
mes rédactions un peu brouillonnes.Tous ont contribué à élargir mon champ scientifique,
et ont ainsi laissé leur trace dans ce document.
Ensuite, mon amitié va à toute l’équipe Symbiose et son ambiance incroyable avec ses
pots, pauses café, repas, groupes de travail, séminaire Aubade, et activités musicales (cette
année, je me mets à la batucada). Chose fascinante, cette ambiance n’a jamais empiété
sur le sérieux et le professionalisme de l’équipe. Avec une attention particulière à François
Coste (mon alter ego dans l’équipe - souvent en opposition mais toujours amicalement)
qui porte une grande partie de cette animation (sociale et scientifique). Prochain sur la
liste des HDR ?
Ces longs remerciements ne seraient pas complets sans y inclure l’IRISA, le CNRS et
l’INRIA. Ces six dernières années, je n’ai pu que m’incliner devant l’efficacité des personnels
de l’IRISA, dont j’ai profité voire abusé (très chère Marie-Noëlle...), ainsi que devant la
bonne humeur qui règne dans ce laboratoire. J’espère sincèrement que l’alchimie (si rare
ailleurs !) entre les personnels de différentes structures et cultures résistera aux mouvements
actuels. Le CNRS a toujours soutenu mes recherches et mes prises de risque ; l’INRIA m’a
permis de profiter de son dynamisme. Là encore, je croise les doigts pour que ces deux
instituts puissent continuer à se développer en toute complémentarité.
Enfin, Stéphane, ma moitié, père et époux (presque) parfait... Depuis plus de quinze
ans, il s’est adapté un peu partout à mes envies de nouveautés. Son soutien, son équilibre,
sa disponibilité, et la joie de vivre au sein de notre famille ont été des piliers de ce travail
(son dos en sait quelque chose). Sans parler de sa patience, ces derniers mois de rédaction
en particulier. Je lui suis infiniment redevable de supporter mes lubies parfois excessives.
A mes loulous Quentin, Eymeric et Alexandre
(Toujours en forme, jamais épuisés...)
3
4
Table des matières
Avant-propos 9
5
6
2.2.2 Des multiplications par une matrice vers des additions sur un
tore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.2.3 Additions sur un tore . . . . . . . . . . . . . . . . . . . . . . 58
2.2.4 Les fractals de Rauzy : différentes approches . . . . . . . . . 60
2.2.5 Construction du fractal de Rauzy . . . . . . . . . . . . . . . . 61
2.2.6 Propriété topologique fondamentale : autosimilarité . . . . . 63
2.2.7 Retour à la dynamique symbolique . . . . . . . . . . . . . . . 67
2.3 Obtenir (enfin) une bonne dynamique symbolique . . . . . . . . . . . 70
2.3.1 Des pavages périodiques aux pavages autosimilaires . . . . . . 71
2.3.2 Différentes conditions de pavage . . . . . . . . . . . . . . . . 73
2.3.3 Graphes de frontière et condition décidable de pavage . . . . 77
2.3.4 Description de la frontière . . . . . . . . . . . . . . . . . . . . 80
2.4 Perspectives de travail : le cas non Pisot . . . . . . . . . . . . . . . . 82
Bibliographie 200
Résumé 222
Avant-propos
9
10
bon candidat pour ces partitions est donné par une structure dont la base
est fractale, introduit par Rauzy dans les années 1980. Le chapitre 1 porte
sur mon travail pour unifier les formalismes existant autour de ce fractal, et
introduire une approche décidable pour s’assurer que ce fractal est un bon
domaine pour un codage dans le cas où l’automorphisme du tore considéré
admet une unique direction dilatante (le cas Pisot).
Dans le cas où le domaine considéré induit un bon codage, nous verrons au
chapitre 2 (section 2.1) comment les approches que j’ai développées permettent
de caractériser les propriétés topologiques du fractal. La fin du chapitre 2
détaille comment ces propriétés topologiques s’exploitent dans les différents
domaines d’informatique théorique où les automorphismes et les additions sur
un tore peuvent être considérés :
– en théorie des nombres, les propriétés topologiques du domaine de Mar-
kov permettent de caractériser les propriétés des développements finis ou
purement périodiques de rationnels en base non entière.
– en géométrie discrète, ces propriétés s’interprètent en termes de conditions
pour l’engendrement de plans discrets par des méthodes itératives.
2. L’étude de systèmes dynamiques de grande échelle en biologie moléculaire. Il
s’avère que les données et les connaissances sur les modèles relatifs aux régu-
lations transcriptionnelles dans une cellule sont souvent trop partielles pour
leur appliquer les méthodes usuellement utilisées pour la modélisation de sys-
tèmes expérimentaux. Je travaille sur l’élaboration d’un formalisme permet-
tant effectivement d’interpréter les observations en biologie moléculaire dans
un cadre dynamique pour aider à la correction de modèles, et, dans le futur,
à la mise en place de plans expérimentaux. Au vu de la qualité des données,
les aspects dynamiques sont alors remplacés par des considérations sur les dé-
placements d’états stationnaires, et analyser les données revient à formaliser
des contraintes (accessibles pour les méthodes actuelles de résolutions de con-
traintes) portant sur des ensembles discrets ; ces contraintes doivent décrire
les questions des biologistes sur leurs systèmes. Au sein du projet Symbiose,
nous avons ainsi montré comment les notions de corrections de modèles et de
diagnostic de réseaux grande échelle peuvent être abordées.
Plan du document Par contre, la diversité des applications visées implique que
les travaux présentés ne sont pas du tout homogènes quant à la formalisation des
concepts abordés. En fait, la formalisation va aller en décroissant, depuis l’étude de
systèmes dynamiques en théorie ergodique (chapitre 2) à une discussion sur l’aide
à l’expérimentation que peut apporter la résolution de contraintes.
Le premier chapitre est un chapitre de revue bibliographique sur les méthodes de
discrétisation pour l’étude de systèmes dynamiques, axée sur les enjeux des systèmes
symboliques : rechercher une partition de l’espace des états qui permette de décrire
les trajectoires des points avec des suites symboliques qui vérifient une contrainte
la plus simple possible. Ces enjeux sont d’abord discutés autour de l’existence de
partitions de Markov pour certains systèmes, et ses conséquences en géométrie, théo-
rie des nombres, physique théorique et en informatique (via la géométrie discrète).
Ensuite, on évoquera la manière dont les systèmes dynamiques sont effectivement
utilisés en biologie moléculaire, où les codages symboliques associés à une approche
de vérification de modèle ont apporté des résultats substantiels.
Le second chapitre aborde la problématique de la dynamique symbolique dans le
cadre des automorphismes et des endomorphismes du tore. Nous expliquons pour-
quoi la recherche d’une bonne partition pour décrire ces applications (domaine de
Markov) est intimement liée à des questions de pavages par des compacts autosimi-
laires sur lesquels existe une dynamique d’échange de morceaux. Nous commence-
rons par résumer les connaissances sur ce domaine, et présenterons finalement une
contribution à la détermination explicite de partitions de Markov, via l’étude des
voisinages de pièces fractales dans un pavage.
Le troisième chapitre porte sur les applications des représentations des auto-
morphismes du tore par des domaines de Markov à bord fractal. Nous discuterons
en quoi des résultats précis sur la topologie des fractals permettent de répondre à
des questions en théorie des nombres, en géométrie discrète, et en perspective, en
géométrie des groupes libres.
Dans le quatrième chapitre, nous changeons de domaine d’application. On sup-
pose maintenant que l’on dispose d’observations sur un système régi par une dy-
namique au sujet de laquelle on dispose d’informations très partielles. On souhaite
exploiter au maximum cette information. La question qui se pose est donc de com-
prendre le comportement d’un système biologique à partir de connaissances et d’ob-
servations limitées. Nous montrons qu’en s’appuyant sur des méthodes algébriques
combinées avec des études de déplacements d’états stationnaires, il est possible
d’élucider la fonction de différentes régulations génétiques et de faire des prédic-
12
tions sur les effets de mutations spécifiques. Dans ce chapitre, la question biologique
étudiée est la régulation du métabolisme des acides gras. Nous utilisons différents
niveaux d’abstraction et différentes méthodes algébriques pour comprendre ce sys-
tème dynamique.
Dans le cinquième chapitre, nous formalisons et étendons les raisonnements du
chapitre 4 pour étudier la question de la correction de modèle. Ici, la probléma-
tique n’est plus de comprendre le fonctionnement d’un système mais de s’inspirer
des approches dynamiques développées au chapitre 4 pour tester si l’ensemble des
connaissances disponibles sur un système est suffisant pour expliquer un compor-
tement observé. La démarche consiste à construire un système de contraintes qui
sont vérifiées par les variations des concentrations des molécules du système, et
d’interpréter différentes questions des biologistes sur un système comme des pro-
priétés spécifiques des solutions du système de contraintes. En perspective, nous
discutons des futures applications de cette méthode pour l’élaboration d’un plan
expérimental en fonction des différents objectifs de l’expérimentateur : valider un
modèle, contrôler un système, et comprendre son fonctionnement.
13
14
et ces lois peuvent amener à des comportements cycliques qui sont identifiables par
une bonne connaissance de l’ensemble du passé.
Galilée et Newton ont révolutionné ce point de vue : en mécanique classique,
pour prévoir la trajectoire d’un point, il suffit de connaître sa position, sa vitesse
initiale, et l’ensemble des forces auquel il est soumis. Il n’est pas nécessaire de
connaître tout son passé. Des succès spectaculaires comme la prédiction du retour
de la comète de Halley ont validé cette approche. L’hypothèse implicite est ici
qu’à chaque système en évolution, on peut associer un état, qui contient toutes
les informations pertinentes sur le système, et qui permet de prévoir son évolution
future dès lors qu’on utilise des lois. Une des ambitions majeures de la physique est
ainsi d’exhiber des lois d’évolution pertinentes.
Poincaré et les systèmes dynamiques Les prévisions sur le futur d’un système
se font en général au moyen d’équations différentielles, que les mathématiciens ont
cherché à résoudre de manière toujours plus complexe. Or, à la fin du 19ème siècle,
Poincaré s’est aperçu que dans certains cas, il est impossible de trouver des solutions
explicites à ces équations [Poi87, BG97]. Un nouveau point de vue a alors été pro-
posé : connaissant l’état du système à un moment donné, on veut connaître l’état de
ce système une unité de temps plus tard. Formellement, on considère l’ensemble de
tous les états possibles, souvent appelé X et une règle d’évolution, T : X → X, qui
à un état x (par exemple, la donnée de la position et la vitesse du soleil, la terre et
la lune) associe un état T (x) (la position des astres un jour plus tard). On obtient
ainsi le concept de système dynamique (X, T ). Formellement, le futur d’un point x
est décrit par les points x, T (x), T (T (x)), T (T (T (x)))... On l’appelle orbite de x.
Étudier un système dynamique est bien différent de l’étude des fonctions apprise
au lycée. Dans ce dernier cadre, nous avons tous recherché la manière dont T (x)
varie avec x : le principal objet d’étude est alors le graphe de la fonction T , en
particulier ses variations, ses points d’inflexion ou son comportements aux points
limites. Dans le cadre des systèmes dynamiques, on étudie l’évolution d’un point x,
en recherchant des régularités dans la suite des futurs T (x), T (T (x)), T (T (T (x))).....
C’est cette orbite de points qui constitue l’objet principal d’une étude dynamique.
Les questions typiques sont alors : les éléments d’une orbite restent-ils dans un sous-
ensemble de X ? Peuvent-ils y revenir régulièrement ? Si deux points x1 et x2 sont
proches, leurs orbites restent-elles proches ? Peuvent-elles même se rejoindre ?
Les systèmes linéaires sur un espace vectoriel Un peu plus complexes sont
les systèmes dynamiques linéaires, où X est un espace euclidien Rn et T est don-
née par l’action d’une matrice M sur Rn . Dans ce cas, une classification complète
des dynamiques existe : le comportement du système dépend essentiellement des
valeurs propres de la matrice M, qui permettent de décomposer l’espace en diffé-
rents sous-espaces sur lesquels M agit de manière simple (contraction, dilatation
ou rotation) ; on parle de théorie spectrale des applications linéaires. Concrètement,
on peut dans de nombreux cadres approximer une application quelconque par une
application linéaire (via le théorème d’Hartman-Grobman et ses différentes géné-
ralisations) ; dans ce cas, la théorie spectrale permet de comprendre la dynamique.
Ces dynamiques sont assez simples : l’origine est toujours fixe, et dans la plupart
des cas, l’orbite d’un point soit devient périodique après un certain temps, soit se
rapproche d’un point périodique, soit s’éloigne vers l’infini, en suivant éventuelle-
ment une spirale [HP05, BDV05]. Comme ce sont les dynamiques les plus simples à
comprendre et à calculer, on a longtemps cru qu’il s’agissait des seules dynamiques
possibles.
Les systèmes chaotiques Et pourtant, force a été de constater que les cas les
plus fréquents dans la nature sont hautement non-linéaires. On entre alors dans
16
Applications en théorie des nombres L’exemple le plus naturel est donné par
la multiplication par 2 ramenée sur le tore R/Z, en bijection avec l’intervalle [0, 1[
(notée T2 ) : on considère un réel x ∈ [0, 1[, on le multiplie par 2 et on ne retient
finalement que la partie après la virgule de cette quantité, c’est-à-dire T2 (x) =
2x − E(2x) (où E(y) désigne la partie entière de y). Même si cette application
semble proche de la multiplication par 2, dont la dynamique est bien comprise et
prévisible, sa dynamique n’est absolument pas prévisible : elle est d’entropie non
nulle et markovienne.
Cette application, et ses cousines (où 2 est remplacé par un réel positif β) a fait
l’objet de nombreuses études combinatoires, dynamiques ou ergodiques. La raison
en est simple : cette application est le fondement de la numération binaire, ses
généralisations sont liées aux beta-numérations. En effet, si on décompose l’espace
des états (ici l’intervalle [0, 1[) en deux parties naturelles : [0, 1/2[ et [1/2, 1[, et on
code sa dynamique comme expliqué précédemment, on montre que le codage d’un
point x n’est rien d’autre que son développement binaire. L’espace des codages est
bien markovien, puisqu’il n’y a aucun mot interdit dans les développements binaires
des réels, et on en déduit que l’application T2 est d’entropie log 2. Nous discuterons
ce point plus en détails dans les sections 2.1.4 et 2.1.5.
On peut cependant se demander quel est l’apport réel de ce point de vue dyna-
mique dans les systèmes de numération. En fait, un certain nombre de théorèmes
de type probabilistes ont été établis concernant les systèmes dynamiques, portant
en particulier sur les propriétés de retour près d’un point de départ (on est alors
dans le domaine de la théorie ergodique). Ces théorèmes, associés à la vision dy-
namique des systèmes de numération, produisent des propriétés statistiques sur les
écritures de nombres. On montre par exemple que dans le développement binaire
de presque tous les nombres réels, la fréquence de 0 et de 1 est égale à 1/2 ; en
fait, cette fréquence est uniforme quelle que soit la base (entière) dans laquelle on
développe pratiquement tous les réels [Bor09, Lan94]. de manière plus concrète,
ces approches sont aussi utilisées pour l’analyse dynamique d’algorithmes arithmé-
tiques, en considérant de l’analyse spectrale basée sur de opérateurs de transfert
[Val03].
Notons cependant qu’un piège se trouve dans le terme
√ presque tous : déterminer
si la fréquence de 1 dans le développement binaire de 2 est uniforme dans n’importe
quelle base est une question toujours ouverte [K06, Bor50, Wal06].
19
Mn x mod Tn ) et son orbite dans le passé (M−n x mod Tn ) convergent toutes les
deux exponentiellement vite vers 0 [ES97, KV98]. Cependant, les domaines ainsi
construits ne sont pas tout à fait exacts, dans la mesure où on ne sait pas montrer
qu’ils séparent les points (au sens où les orbites de deux points doivent avoir des
codages différents). Nous rediscuterons ce point dans la section 2.2.
Des pavages aux additions sur un tore Un “détail” a été passé sous silence
jusqu’à maintenant : comment construire précisément un domaine autosimilaire
21
Induction La méthode utilisée par Morse et Hedlund pour montrer que toutes les
suites de complexité n+1 sont des codages de rotation fait appel à une méthode assez
classique en systèmes dynamiques, qui consiste à induire sur un sous-ensemble du
système, ce qui revient à étudier la manière dont une trajectoire revient sur un sous-
ensemble bien choisi de l’espace des états. Dans l’esprit de la dynamique symbolique,
la première étape est toujours de partitionner le système un nombre de morceaux
finis. Cependant, au lieu de chercher les trajectoires d’un point, on s’intéresse ensuite
à la manière dont l’orbite d’un point x de la première pièce de la partition revient
dans cette pièce (on parle d’application de premier retour). Lorsque l’application
de premier retour a une forme semblable à l’application considérée initialement, on
procède à une partition du nouveau système, et on calcule une nouvelle application
de premier retour. À chaque étape, l’information qui est conservée est le lien entre
l’application et son application de premier retour ; il s’agit des noms des pièces de
la partition traversées avant de revenir dans la pièce de départ.
Avec cette méthode d’induction, Morse et Hedlund ont ainsi montré que tous
les mots sturmiens s’obtiennent en composant des applications élémentaires sur
des mots, appelées substitutions ou morphismes itérés, qui consistent à remplacer
les lettres d’un alphabet par des mots finis, comme par exemple la substitution
σ0 (0) = 01, σ0 (1) = 1. Plus précisément, le langage d’un mot sturmien de pente α
est déterminé par les mots finis de la forme σ0a1 σ1a2 σ0a3 . . . σ0 a2n+1 (0), où a1 , a2 , . . .
sont donnés par l’algorithme d’Euclide appliqué sur α (il s’agit de son développement
en fractions continues) et σ0 , σ1 sont deux substitutions qui décrivent le lien entre
une addition et son application de premier retour. Nous reviendrons en détail sur
ces concepts dans la section 2.1.4.
Cette décomposition en substitutions a été abondamment exploité dans la litté-
rature ; elle est à la base d’algorithmes rapides (en O(log n)) pour retrouver les n
premiers termes du codage discret d’une droite à partir de son angle [MH38, MH40,
Fog02].
stitution dès lors que la substitution a des propriétés algébriques (condition Pisot)
et que le recouvrement périodique est un pavage.
Il existe une pléthore de conditions de pavages. Elles sont détaillées dans la sec-
tion 2.3. Ces conditions ont été proposées par différents auteurs en fonction des
points de vues considérés : ces conditions s’expriment en termes combinatoires
[BK06, IR06, Liv87], de beta-developpements [Hol96, Aki02], d’annulations sur
des approximations de la frontière [EI05] ou de propriété d’autosimilarité [Mes98,
FFIW06]. J’ai moi-même utilisé cette dernière méthode pour montrer que des sys-
tèmes substitutifs sont à spectre purement discret dans (Ann. Inst. Fourier, 2004).
Il faut cependant noter que toutes ces approches ont finalement été développées
de manière ad hoc sans prendre en compte les différents points de vue existant sur
les fractals de Rauzy. En particulier, aucune n’est réellement décidable, et le cas des
recouvrements périodiques est souvent laissé de côté.
Vers des applications autres que dynamiques ? Il faut insister sur le fait
que ces codages symboliques ont des applications externes dans différents champs
en mathématiques, informatique, ou physique, répondant par là aux ambitions de
Poincaré et Hadamard. Nous avons déjà évoqué comment des résultats substantiels
en géométrie ont été obtenus en exploitant la combinatoire de points fixes de sys-
tèmes d’itération [Mor21] ou l’existence de partitions de Markov [Sma67, Adl98]. De
même, en théorie des nombres, les systèmes symboliques, via des aspects ergodiques
et combinatoires, ont nourri des conjectures, et des constructions à base de substi-
tutions ont fourni des exemples non-triviaux pour ces conjectures [AS02, ABD06,
AB07, Roy03, HM06]. Dans cet esprit, nous allons voir maintenant comment les
graphes de frontière peuvent être utilisés dans les domaines d’applications des frac-
tals de Rauzy, ou plus précisément, comment exploiter les propriétés topologiques
de fractals pour aborder des questions liées à un processus d’autosimilarité.
drement et extension). Dans la section 3.3.4, nous détaillons comment il est possible
de vérifier ces deux propriétés pour plusieurs algorithmes d’engendrement. Le point-
clé est de faire appel à un critère topologique sur motifs images de substitutions
multidimensionnelles pour vérifier la propriété d’engendrement.
La perspective finale de ce travail rejoint les questions dynamiques discutées
dans la section 1.2.3 : il va s’agir de construire une suite de domaines fondamentaux
qui permettraient de représenter symboliquement la dynamique n’importe quelle
addition sur un tore par la composition de substitutions (conjecture S-adique).
géométriques ou arithmétiques pour relier la propriété (F) au fait que 0 est point
intérieur du fractal.
Pour traiter ce cas, j’ai proposé dans la publication (Erg. Th. Dyn. Sys, 2003)
de construire un nouveau fractal de Rauzy qui tient compte de l’arithmétique sous-
jacente à β. Puisque β est un nombre non unitaire, il existe des corps locaux (exten-
sions finies de corps p-adiques) dans lesquels β n converge exponentiellement vite, et
dans ces corps on peut faire converger des séries basées sur des systèmes de numéra-
tion. J’ai donc introduit des fractals de Rauzy complets, incluant des composantes
p-adiques, et j’ai montré en collaboration avec G. Barat, V. Berthé, et S. Akiyama
dans (Monas. Math., 2008) que ces fractals induisent un pavage autosimilaire d’un
espace constitué de corps euclidiens et locaux dès que la propriété (F) est vérifiée.
En fait, 0 est un point intérieur du fractal complet et du fractal de Rauzy original,
même si ce dernier ne pave pas l’hyperplan dans lequel il vit. Des détails sont donnés
dans la section 3.2.
Ainsi, la mécanique céleste a consisté à proposer des lois raisonnables pour dé-
crire les trajectoires des planètes [Arn99]. De la même manière, les lois d’action
de masse, ou de Michaelis-Mentens ont été proposées pour décrire le comporte-
ment de systèmes chimiques [CB04, HS96]. Des modèles spécifiques ont été intro-
duits pour décrire le comportement de systèmes économiques, ou la dynamique des
populations [Tur03]. Les chaînes de régulations transcriptionnelles avec une retro-
régulation négative sont bien décrites par un modèle de Goodwin [Goo63, Goo65].
Plus globalement, des sigmoïdes de type “loi de Hill” décrivent bien les observations
expérimentales faites sur des régulations transcriptionnelles [Yag75]. Chaque loi fait
intervenir des paramètres, que des observations variées permettent d’estimer avec
une précision plus ou moins grande.
Dans tous ces cadres, en plus de la question dynamique de l’étude du futur
des éléments, se pose la question de la fiabilité des prédictions ou des simulations.
En effet, même si le nombre d’observations sur un système peut-être important
(il suffit de considérer la quantité phénoménale d’observations intégrées dans des
modèles météorologiques [Pie01, Hol04]), ces observations sont toujours limitées. Or,
ce sont ces observations qui définissent les états du système. Cependant, lorsqu’on
a à faire à des dynamiques chaotiques, on sait que, par essence, la moindre erreur
dans la définition d’un état générera impérativement une erreur importante dans les
prédictions. Il est ainsi fondamental de prendre en compte le niveau de fiabilité à la
fois dans l’estimation des paramètres du modèle et dans la qualité des observations,
pour évaluer le caractère prédictif des modèles.
de réplicats pour déterminer les paramètres des lois est très coûteuse. Dans ce
contexte, il est extrêmement complexe de construire des modèles quantitatifs et
fiables à assez grande échelle. Les modèles quantitatifs restent ainsi exceptionnels
(on notera la régulation du cycle cellulaire [TCN01, CCCN+ 04] ou les voies de
transduction de signal associées à EGF [SEJGM02] et NFκB [NIE+ 06]).
Partant de ce constat, différentes approches ont été explorées pour simuler et
modéliser la dynamique des réseaux de régulation génétique. Certaines restent dif-
férentielles (en se focalisant sur des réseaux de petite taille), d’autre discrètes (voir
section suivante) ; d’autres encore adoptent un point de vue probabiliste, voire sto-
chastique [RWA02, KEBC05]. La revue de référence en la matière est [DJ02].
luées (ou les fonctions linéaires par morceaux), l’approche devient non-déterministe
puisque plusieurs états peuvent être les successeurs d’un état donné, puisque ces
successeurs sont déterminés en fonction des attracteurs de la dynamique. De plus,
l’approche booléenne est plus simple que l’approche multivaluée car le nombre de
valeurs qu’une variable peut prendre est limité à 2, ce qui n’est pas suffisant pour
décrire la complexité des régulations entre de multiples molécules.
Des simulations sur ces réseaux ont montré que les réseaux booléens ne sont pas
assez précis pour décrire la dynamique : il peut manquer des trajectoires observées
dans la réalité. Ils sont donc peu employés pour décrire la trajectoire des réseaux
de régulation. Par contre, ils ont montré leur intérêt pour l’étude des propriétés
globales des réseaux grande-échelle, avec des approches probabilistes [Kau93, SL98]
illustrées principalement sur le réseau de la levure S. cerevisiae [KPBT03, KPST03].
de réactions revient à proposer des analyses robustes d’un modèle, c’est-à-dire in-
dépendantes de la valeur exacte des paramètres et ne prenant en compte que les
informations connues sur ces paramètres. Un exemple couramment utilisé dans ce
domaine est la règle de Thomas , qui dit que si un système admet plusieurs états
stationnaires non dégénérés, alors son graphe d’interactions contient au moins un
cycle positif [Tho81]. On a ici une information globale sur le système, ayant un sens
biologique important (la bistabilité du système, induisant des phénomènes d’hys-
téresis), sans une étude détaillée de la dynamique. Cette règle, proposée dans les
années 1980, a été prouvée pour les différents formalismes existants (logique, mul-
tivalué, différentiel...) dans les années 2000 [Sou06], en faisant appel à un résultat
général sur l’univalence de flots différentiel, le théorème de Gale-Nikaido [Par83].
Plus généralement, les travaux mathématiques existant sur les prédictions de sys-
tèmes à partir d’informations qualitatives se concentrent pour la plupart sur l’étude
de signes de déterminants : les informations au sujet de l’existence ou l’unicité d’at-
tracteurs et leur stabilité sont principalement contenues dans la matrice jacobienne
de la dynamique (en particulier ses sous-déterminants), qui est précisément donnée
par le graphe d’interaction du réseaux [HKG]. Comme nous le détaillerons dans
la section 4.1.3, les approches qui se distinguent à ce sujet sont les réductions par
échelles de temps et les réductions de systèmes monotones [Son07].
des gras dans leur métabolisme. Des raisonnements sur les observations pendant un
jeûne suggèrent que cette voie admet un régulateur inconnu. Or, nous montrons que
cette voie est en fait contrôlée par une boucle positive qui fausse les raisonnements
intuitifs et enlève les incohérences.
Enfin, à un niveau dynamique beaucoup plus précis (quantitatif en particulier),
avec une analyse de données temporelles sur les différentes classes d’acides gras pen-
dant un jeûne chez des souris mutées, P. Blavy a illustré pourquoi la boucle positive
n’est pas active, et comment la modélisation de procédés dynamiques de transfor-
mation inter acides gras est suffisante pour conclure à l’existence de régulations
inconnues (JOBIM, 2008).
Diagnostic et règle causale Différentes analyses [FMS+ 07] ont montré qu’au-
cune méthode n’est convaincante prise isolément, et les réseaux grande-échelle qui
apparaissent actuellement sont finalement une compilation d’interactions déduites
de différentes méthodes et expérimentations sous différentes conditions. Il a été né-
cessaire de proposer des méthodes pour concilier différentes données hétérogènes,
repérer les incohérences pour raffiner et améliorer les modèles. Pour répondre à ces
deux questions, différentes méthodes ont été proposées. Elles diffèrent par le type de
règles sur lesquelles s’appuient la notion de cohérence ou les prédictions. Cependant,
on retrouve dans la plupart une règle implicite, appelée règle causale, qui affirme
que la modification de l’expression d’une protéine lorsque un gène est supprimé ou
sur-exprimé implique qu’une régulation (au moins indirecte) existe entre le gène
41
Validité de la règle causale ? Comme nous l’avons déjà mentionné, les modèles
causaux avaient d’ailleurs été proposés dans les années 80 [Kau69] pour étudier la
dynamique de systèmes ; ils ont été abandonnés au profil de modèles de régulation
par seuil quand il a été montré que l’ensemble des trajectoires obtenus pour les mo-
dèles causaux n’englobaient pas tous les comportements observés. Leur utilisation
pour le diagnostic de réseau est donc à priori plus que sujette à caution. Comme
nous le détaillerons dans la section 5.1.2, nous avons d’abord étudié le cadre de
validité de la règle causale ((Biosystems, 2006) et (Roy. Soc. Inter, 2006)). Même
si elle est largement utilisée, nous avons montré que cette règle n’a un sens que
lorsqu’on décrit les variations de produits entre un état de départ (stable) et l’état
stationnaire consécutif à une perturbation du système (qui peut être génétique ou
un stress environnemental). Ainsi, même si d’un point de vue dynamique les mo-
dèles causaux sont trop restrictifs, ils ont toute légitimité pour être utilisés pour
étudier des données portant sur les comparaisons d’états stationnaires.
Ainsi, une “simple” considération sur les déplacements d’états stationnaires per-
met de répondre à des questions relatives à la construction de réseaux biologiques.
Cependant, on constatera que la démarche pour répondre à ces question a surtout
consisté à aider le biologiste à formaliser ses questions sous forme de requêtes réso-
lubles avec des algorithmes adaptés. Le cadre d’application des méthodes présentées
au chapitre 5 s’avère donc bien plus large que la question de la reconstruction de
réseau, et nous discutons dans la section 5.4 des différentes questions biologiques
auxquelles il est envisageable d’apporter une réponse dans le futur, en gardant à
l’esprit la notion de systèmes dynamiques (voir aussi (Biofutur, 2007)).
Discrétiser de (simples ?)
additions ou multiplications
Dans ce chapitre, nous allons détailler les problématiques encore actuelles posées
par le codage symbolique des applications les plus simples possibles, c’est-à-dire les
additions et les multiplications sur des tores.
La section 2.1 présente une synthèse des principaux résultats de dynamique sur
ces applications sur les tores unidimensionnels.
Dans la section 2.2, nous rappellerons les différentes directions étudiées pour
passer du cas unidimensionnel au cas multidimensionnel, et les difficultés qui sont
apparues pour obtenir une bonne dynamique symbolique. Nous y montrerons que
l’obtention d’une bonne dynamique symbolique se ramène finalement à la vérifica-
tion d’une propriété de pavage.
Enfin, dans la section 2.3, nous proposerons une méthode qui englobe tous les
cas traités dans la littérature et répond à la question de la recherche des partitions
de Markov de manière décidable : il va s’agir de coder par un graphe l’ensemble des
points de recouvrement entre des tuiles, pour vérifier explicitement la condition de
pavage. Le résultat principal ici sera le Théorème 2.3.4.
Les résultats présentés dans ce chapitre seront exploités dans le chapitre suivant
pour des applications dans différents domaines des mathématiques et de l’informa-
tique théorique.
43
44
– soit par une évolution continue dans le temps (une équation différentielle).
Mathématiquement, le système T : X × M → X est déterminé par une loi T ,
définie sur un espace des états X et un espace de paramètres temporels M .
Cette définition est la plus naturellement d’un point de vue physique ou biolo-
gique, puisque la notion de temps y est continue. Nous utiliserons ces modèles
dans les chapitres 4 et 5 pour les applications des systèmes dynamiques en
biologie moléculaire.
– soit par une évolution discontinue dans le temps, qui correspond à modéliser
l’état du système après un pas de temps donné. Le système est alors donné
par une application T : X → X. Ces modèles, moins naturels, sont toute-
fois d’une grande utilité pour mettre en évidence des résultats importants qui
se généralisent ensuite aux systèmes différentiels. Dans les systèmes disconti-
nus, l’application T peut être un homéomorphisme sur un espace topologique
(système dynamique topologique), un difféomorphisme sur une variété diffé-
rentielle (système dynamique différentiel) ou une application qui préserve la
mesure sur un espace mesurable (système dynamique mesuré).
Dans le cas où le système (X, T ) est minimal, toutes les orbites de points ont le
même langage et le système symbolique contient exactement l’ensemble des mots
infinis qui admettent ce langage.
Toutes les substitutions n’admettent pas un point fixe (il suffit de considérer la
substitution 1 → 21, 2 → 12). Par contre, on sait que toute substitution admet au
moins un point périodique : il existe n et un mot u infini tel que σ n (u) = u.
La question naturelle qui se pose alors est de savoir plusieurs points périodiques
peuvent avoir des langages différents. Pour éviter cela, on introduit la condition de
primitivité : il s’agit de s’assurer que chaque lettre de A apparaît au bout d’un mo-
ment dans l’image de toutes les autres lettres. Ceci implique qu’un point périodique,
dont le langage contient tous les mots de la forme σ mk (u0 ), contiendra des bouts
de longueur croissante σ mk (u1 ) de tous les autres points périodiques ; les langages
seront donc globalement les mêmes.
Plus formellement, on dit que la substitution est primitive lorsqu’elle sa matrice
linéarisée Mσ estprimitive : il existe m tel que Mm σ ne „
contient«que des coefficients
1 1
strictement positifs. Par exemple, la matrice de σ est (la i-ème colonne
1 0
indique la composition en lettres de σ(i)). Cette substitution est primitive puisque
M2σ n’a aucun coefficient nul.
Sous la condition de primitivité, on sait que tous les points périodiques d’une
substitution ont même langage [Que87]. On construit un système dynamique sym-
bolique Xσ en considérant tous les mots infinis qui admettent ce langage. L’action
naturelle sur Xσ est donnée par le décalage S, qui préserve bien entendu le lan-
gage d’un mot infini. Il s’agit du système dynamique symbolique engendré par la
substitution. En utilisant l’hypothèse de primitivité, on montre que ce système dy-
namique est minimal : pour n’importe quel mot infini u ∈ Xσ , on sait que u permet
d’engendrer entièrement l’ensemble Xσ par décalage (son orbite par S est dense) :
Xσ = {S n (u), n ∈ N}.
De plus, l’ensemble AN dans lequel vit Xσ est muni d’une topologie naturelle, et
est donc un espace mesurable. Toujours sous l’hypothèse de primitivité, on montre
qu’il existe une unique mesure invariante par S pour cette topologie, et le système
dynamique est donc uniquement ergodique [Que87].
Multiplier par 2 modulo 1 Plutôt que de travailler sur l’intervalle [0, 1[, on
préfère travailler sur le tore de dimension 1 T = R/Z, qui peut-être vu comme
l’intervalle fermé [0, 1] dans lequel 0 et 1 sont identifiés comme égaux. Ces deux
ensembles sont en bijection, mais le tore est un compact alors que [0, 1[ ne l’est pas.
Un des systèmes dynamiques les plus simples est l’application sur le tore de
dimension 1 : T2 : x ∈ T 7→ 2x mod 1 ∈ T. Pour cette application, le schéma
d’étude proposé plus haut s’applique très naturellement :
– Une partition naturelle est donnée par ses intervalles de continuité [0, 1/2[,
qui sera noté par l’indice 0, et [1/2, 1[, qui sera désigné par l’indice 1.
– On montre facilement que le codage de l’orbite d’un réel x ∈ T vis-à-vis de
cette partition est le développement binaire du réel x. On en déduit que tous
les mots infinis de {0, 1}N sont des codages, à part ceux qui se terminent
par un infinité de 1. Le système dynamique symbolique associé est donc tout
l’ensemble {0, 1}N. Il est bien de type fini.
– Le développement binaire détermine entièrement un nombre réel de [0, 1[, donc
de T. Cette partition est donc génératrice.
– Les propriétés métriques du système ont été fortement exploitées dans di-
vers travaux pour proposer différentes conjectures sur les développements
des nombres. On montre par exemple que dans le développement binaire de
presque tous les nombres réels, la fréquence de 0 et de 1 est égale à 1/2 ; en
49
fait, pour n’importe quelle base entière, la fréquence de chaque chiffre est uni-
forme dans le développement de presque tous les réels [Bor09, Lan94]. Notons
cependant qu’un piège se trouve dans le terme presque √ tous : déterminer si la
fréquence de 1 dans le développement binaire de 2 est égale à 1/2 est une
question toujours ouverte [Bor50, Wal06].
– Les informations sur les fréquences se traduisent naturellement en termes pro-
babilistes : la probabilité de revenir dans un intervalle de longueur donnée est
déterminée uniquement par la longueur de l’intervalle. On en déduit aussi que
T2 est d’entropie log 2.
– Enfin, les points périodiques pour ce système sont les rationnels dont le déno-
minateur est impair. Les points ultimement périodiques sont tous les nombres
rationnels.
– En fait, le système dynamique est fondamentalement imprévisible puisque
des réels proches (dont le développement binaires commence par les mêmes
chiffres) peuvent avoir des futurs sans sans aucun rapport après un certain
temps (puisque les futurs sont déterminés par les fins du développement bi-
naire, qui peuvent être très variées). L’existence d’un ensemble dense de points
périodiques et l’imprévisibilité sont des caractéristiques habituelles de chaos.
Des résultats identiques s’appliquent en fait pour les multiplications par un
rationnel modulo 1. Par contre, si on considère un nombre irrationnel, les choses se
compliquent un peu.
où la suite des chiffres ai ne contient pas deux 1 consécutifs. Ces chiffres sont obtenus
par algorithme glouton à partir de Tφ ; il s’agit précisément du codage de l’orbite
de φ−i0 x choisi tel que φ−i0 x ∈ [1/φ, 1|.
Là encore, les propriétés métriques (sur les probabilités de retour dans un inter-
valle) ont des incidences sur les développements. On montre par exemple que pour
presque tout réel, la fréquence du chiffre 0 dans le développement en base φ est
égale à 1/φ tandis que la fréquence de 1 est égale à 1/φ2 . On remarquera qu’ici,
les fréquences existent encore, mais, contrairement aux bases entières, elles ne sont
plus uniformes.
L’ensemble des mots infinis qui vérifie cette condition étendue au cas fermé ≤lex
est appelé beta-shift. Il s’agit du système symbolique qui code Tβ pour la partition
précisée plus haut.
Notons que dans le cas du nombre d’or, on a dφ (1) = 110000000..., et donc
d∗φ = (10)∞ .On retrouve ici la condition selon laquelle le motif 11 est interdit dans
le codage.
tn
0, · · · , tm+1 − 1
0, · · · , tm+2 − 1
0, · · · , tn − 1
Fig. 2.1 – Graphe qui décrit les codages des orbites de la multiplication par β
modulo 1, notée Tβ , dans le cas où β est un nombre de Parry. Pour construire
ce graphe, on considère le mot infini obtenu à partir du codage de 1 d∗β (1) =
t1 · · · tm (tm+1 · · · tn )∞ .
(qui se terminent sur 0) et celles qui sont purement périodiques font aussi l’objet
de nombreuses études, que nous détaillerons dans la section 3.2. Nous proposerons
des extensions, en particulier quand β n’est pas un nombre unitaire.
Les nombres entiers pour la beta-numération sont les réels qui n’admettent pas
de partie fractionnaire.
X
Int(β) = z = ui β i ∈ Z[β]; uK . . . u0 = dβ (β −K−1 z) . (2.1)
0≤i≤K
Ces nombres forment un ensemble discret de R+ . Dans le cas Parry, ces nombres
présentent une régularité puisque deux éléments consécutifs ne diffèrent que par un
nombre fini de valeurs, en fait les nombres Tβa−1 (1), a ∈ {1, . . . , n} [Aki07, Thu89].
Cependant, les régularités de cet ensemble ne sont pas évidentes. On montre que
les intervalles sont ordonnés suivant l’ordre des lettres dans le point fixe d’une
substitution naturellement associée à β, qui est définie à partir de dβ (1)∗ , aussi
appelée beta-substitution [Thu89] (voir aussi (Integers, 2005)).
Rα : x ∈ T 7→ x + α mod 1.
sont d’orbite dense dans T (autrement dit, le système dynamique est minimal). De
plus, les transformations Rα préservent la métrique circulaire. La distance sur le
cercle entre les éléments des orbites de deux points est donc constante. Il y a donc
prévisibilité à long terme.
minimales, d’entropie nulle, sans orbite périodique ; mais ceci se montre directement,
sans besoin de codages...
L’intérêt de cette approche réside dans la réciproque : tout système dynamique
qui est codé par des suites de complexité minimale (c’est-à-dire n+1) sera finalement
isomorphe à une addition sur un tore, et du fait de cette caractérisation, la dyna-
mique symbolique sera engendrée par la composition de substitutions. Ainsi, une
importante littérature a été consacrée à l’identification de systèmes de complexité
n + 1, et à exploiter les relations entre complexité et dynamique. Ces propriétés ont
été utilisées par exemple dans le cadre de l’optimisation de l’allocation de ressources
dans les réseaux de télécom [GHVdL07].
ploités. Ces travaux ont ouvert la voie à des recherches très actuelles dans le cas
multidimensionnel.
Construction effective ? Précisons ici ce que signifie ici une partition de Markov.
On sait qu’un codage de type fini est associé à un ensemble de mots interdits. En
raffinant la partition (et en augmentant donc le nombre N de pièces dans cette
partition), on montre qu’un codage markovien est en fait caractérisé par un ensemble
M de paires de lettres (i, j), où, i, j ≤ N qui sont autorisées dans le codage d’une
trajectoire, tandis que les paires (i, j) qui n’appartiennent pas à M ne doivent
jamais apparaître dans un codage [LM95]. Notons bien que ici, les paires (i, j) sont
ordonnées : la lettre i peut ou non être suivie de j dans le codage. On définit ainsi
un graphe orienté sur les sommets {1, . . . N } en posant une arête de i vers j si
(i, j) ∈ M.
Rechercher une partition de Markov pour un automorphisme M consiste fina-
lement à trouver un domaine fondamental X du réseau Zn et une partition de ce
domaine en N pièces X = ∪ni=1 Xi tels que l’image par M des points d’une pièce Xi
respectent les contraintes données par l’ensemble M. Ceci revient à dire que MXi
mod Zn est exactement égal à l’union des pièces Xj , pour les j tels que (i, j) ∈ M.
La condition pour que la partition soit markovienne est donc
[
MXi = Xj mod Zn .
i→j
Le cas des automorphismes avec une seule valeur propre dilatante Après
les résultats de Bowen sur l’existence de partitions de Markov, un certains nombre de
travaux ont cherché à construire explicitement ces partitions. La dynamique arith-
métique a été développée par différents auteurs en suivant un article fondateur de
56
Vershik [Ver92], qui a étudié le cas du nombre d’or puis étendu ses travaux au cas
quadratique Pisot [SV98]. Suivant la définition de [Sid03], le but de cette approche
est de construire des codages explicites pour des automorphismes hyperboliques
de tores ou de solenoïdes, de sorte que les propriétés géométriques de l’automor-
phisme sont clairement transposées dans le cadre dynamique. L’approche de Vershik
[Ver92, SV98] et poursuivie dans [Sch00a, KV98, Sid01, Sid02, BK05, LS05] est de
considérer des automorphismes du tore avec une seule valeur propre dilatante, et
de décomposer les points du tore sous la forme de séries entières dont la base est
donnée par un point homocline, c’est-à-dire un point qui se trouve à l’intersection
des variétés stable et instable de la dynamique.
Avec ces constructions, on obtient un codage symbolique de l’automorphisme
du tore par un système markovien. Cependant, ce codage n’est pas générateur : on
dit qu’il s’agit d’une extension finie-à-un de la transformation, ce qui signifie que le
nombre de points de l’espace de départ admettant le même codage est constant : on
ne sait pas s’il est égal à un, ce qui est nécessaire pour obtenir une vraie partition
de Markov. Plus précisément, on sait que le domaine X qui est construit contient
un nombre entier de copies d’un domaine fondamental du tore, mais on ne sait
pas montrer qu’il s’agit réellement d’un domaine fondamental ; il faudrait pour cela
montrer qu’il est de volume 1. La question de la généricité du codage n’est donc pas
résolue dans ces travaux.
Sections des partitions de Markov dans le cas Pisot : une intuition géomé-
trique La dynamique arithmétique étudie une classe spécifique d’automorphismes
hyperboliques : il s’agit des automorphismes du tore hyperbolique admettant une
seule valeur propre dilatante. La valeur propre dominante est alors un nombre de
Pisot et on montre que le polynôme caractéristique est irréductible (Trans. AMS,
2001). On appelle ces automorphismes Pisot irréductibles. Géométriquement, ces
automorphismes se dilatent selon une unique direction, ce qui simplifie amplement
la dynamique.
On en déduit des propriétés géométriques intéressantes sur le pavage donné
par une partition de Markov du tore. Ces propriétés
sont
bien visibles dans le cas
1 1
bi-dimensionnel (voir Fig. 2.2 pour la matrice ), mais elle sont vérifiées
2 1
57
Fig. 2.2 – Une partition de Markov pour un automorphisme du tore T2 . Les sections
du domaine fondamental induisent un pavage périodique de la droite x + y = 0 et
un pavage stable par la contraction par −1/φ de la direction dilatante de la matrice
tore revient donc à comprendre les propriétés spectrales des systèmes symboliques
engendrés par une substitution. Cette question a occupé une large partie de la
littérature du domaine dans les années 1970 et 1980 : j’ai écrit une synthèse sur
ce sujet dans l’ouvrage collectif Pytheas-Fogg dans la collection Lectures Notes
in Mathematics (Pytheas Fogg, LNM, 2002). En tout état de cause, il s’avère que
même avec un alphabet à deux lettres, caractériser les systèmes substitutifs à spectre
purement discret, et plus globalement déterminer le spectre d’un système dynamique
substitutif est une tâche ardue.
Le cas des substitutions Pisot sur deux lettres Il ressort de l’analyse spec-
trale des années 1980 que de bons candidats pour les systèmes à spectre purement
discret sont ceux qui sont engendrés par une substitution dont la matrice d’inci-
dence a une valeur propre Pisot dont le degré algébrique est égal à la taille de
l’alphabet (comme pour les automorphismes du tore, on parlera de substitution
Pisot irréductible).
Pour cette classe de substitutions, on connaît explicitement le spectre [BK06].
On sait aussi maintenant que, si l’alphabet ne contient que deux lettres, le système
engendré par une substitution Pisot unitaire est systématiquement le codage d’une
addition sur un tore [BD02]. Le cas des substitutions sur deux lettres est donc bien
maîtrisé.
Espace de pavage associé à une substitution Pisot Pour ce qui est du cas
général, l’école américaine a publié ces dernières années un certains nombre de
travaux concernant l’étude spectrale des systèmes substitutifs. Leur approche est
la suivante : à partir d’une substitution (réductible ou irréductible) Pisot, on peut
définir un flot de translation sur un espace de pavage engendré par n’importe mot
infini qui est un point fixe (ou éventuellement périodique) pour la substitution
[BBK06, BK05]. Les valeurs propres de ce flot de translation ne dépendent que de
la matrice de la substitution [BBK06]. Une première question ouverte est de savoir
si, dans le cas Pisot unitaire, ce flot de translation dont on connaît le spectre est
effectivement à spectre purement discret.
Dans cette construction d’espaces de pavages, deux dynamiques coexistent : la
première est celle du flot de translation sur l’espace de pavage (dont on connaît ex-
plicitement le spectre), la seconde est l’application de premier retour sur une section
adéquate. Un autre résultat de Barge et Kwaplicz montre que symboliquement, une
substitution code la deuxième dynamique [BBK06].
En travaillant sur la coexistence de ces deux dynamiques, il devient possible de
montrer que le système symbolique engendré par la substitution σ(1) = 162111,
σ(2) = 435211, σ(3) = 35211, σ(4) = 435444, σ(5) = 162544, σ(6) = 62544 n’est
pas à spectre purement discret [BBK06]. Par contre, le flot de translation qui lui
est associé est à spectre purement discret. Ainsi, les systèmes substitutifs Pisot
unitaires ne sont pas tous à spectre purement discret.
On pourra cependant remarquer que si la valeur propre dominante de σ est bien
un nombre de Pisot de degré 3, elle n’est pas irréductible puisqu’elle admet des
valeurs propres de degré 2. La question reste donc entière de savoir si le système
60
associé à une substitution Pisot irréductible unitaire est à spectre discret. On sait
simplement que dans ce cas irréductible, cette propriété est équivalente au spectre
discret de la première dynamique par flot de translation.
Dans le contre-exemple de la substitution σ, même si le système substitutif n’est
pas explicitement le codage d’une addition, Barge et Kwapicz ont quand obtenu un
résultat dynamique intéressant, qui formalise et généralise des observations sur des
substitutions provenant de beta-numérations [EI05]. En effet, ils ont montré que
dès qu’un flot de translation est à spectre purement discret, le système symbolique
associé peut ne pas être une addition sur un tore, mais il sera toujours le codage de
l’application de premier retour d’une addition sur un tore. Autrement dit, il existe
toujours un réseau lié à ce système et une addition qui permet de le décrire. Dans
ce contexte, plusieurs questions ressortent :
– Vérifier que le flot de translation sur un espace de pavage engendré par une
substitution Pisot unitaire est à spectre purement discret.
– Vérifier que le système dynamique symbolique associé à la substitution est à
spectre purement discret, ou, si ça n’est pas le cas, est conjugué à l’application
de premier retour d’une translation. Cela revient à trouver un bon domaine
fondamental pour un réseau pour représenter le système.
– Étant donnée une translation sur un tore, trouver (s’il en existe) une substi-
tution qui décrit les orbites de cette translation dans une partition adéquate.
Répondre à ces questions revient aussi à répondre à la question de la construction
d’une partition de Markov. Les approches arithmétiques discutées à la section 2.2
ayant montré leurs limites, nous allons voir comment il est possible de répondre
partiellement à ces questions en adoptant un point de vue algorithmique sur les
constructions géométriques inspirées par Rauzy.
à 1).
– La seconde approche s’appuie sur les propriétés d’autosimilarité du fractal et
des substitutions généralisées pour le construire par approximations succes-
sives ; elle a été introduite par l’école japonaise [IK91, AI01, AIS01, IR06]. Elle
a d’abord été définie pour les substitutions Pisot unitaires irréductibles, avant
d’être étendue à toutes les substitutions Pisot unitaires. Même si le point de
vue est plus dynamique, la construction d’un fractal de Rauzy par espace de
pavage développée par l’école américaine [BK06, BBK06] entre dans ce cadre.
– La troisième approche suivie à partir des beta-numérations dans [Thu89]
consiste à représenter de manière compacte l’ensemble des entiers pour une
beta-numération (voir Eq. (2.1)). Cette approche a particulièrement été étu-
diée dans [Aki98, AS98, Aki99, BBLT06] On peut associer à ce nombre de
Pisot une substitution, mais sa matrice d’incidence peut admettre des va-
leurs propres dilatantes autres que β, on s’éloigne donc des deux premiers cas
(on dit qu’on se trouve alors dans le cas Pisot réductible, éventuellement non
unitaire).
Contribution Il s’avère que le lien entre ces trois approches se repose que sur une
seule propriété : les ensembles obtenus vérifient les mêmes relations d’autosimilarité,
ce qui permet de montrer qu’ils sont égaux (nous reviendrons sur ce point en détail
dans la section suivante).
Pendant et après ma thèse, j’ai travaillé sur l’unification de ces approches, en
étendant la première construction de Rauzy à différentes classes de substitutions
Pisot, ce qui a permis d’englober dans un même formalisme les classes traitées par
les autres méthodes de construction.
– La classe des substitutions irréductibles unitaires est étudiée dans (Trans.
AMS, 2001) et (JTN Bordeaux, 2001), en collaboration avec V. Canterini.
– La classe des substitutions réductibles est étudiée dans (Integers, 2005) et
(JNT, 2007), en collaboration avec Valérie Berthé, créant un pont avec les
approches de numérations.
– La relation entre la construction par beta-numération et celle par approxi-
mation successive est étudiée dans (Integers, 2005) : nous y montrons que les
nombres remarquables du point de vue de la beta-numération (beta-entiers)
ne sont rien d’autre que les coordonnées des sommets de plans discrets, qui
sont remarquables du point de vue des approximations successives.
– Le cas non unitaire est introduit dans (Erg. Th. Dyn. Sys, 2004) et repris dans
(JNT, 2007). Il s’agit de la seule représentation connues pour des substitutions
non unitaires.
Nous allons maintenant détailler la première construction, et rapidement men-
tionner pourquoi les autres constructions permettent d’obtenir le même ensemble.
géométrique développé par l’école japonais. Cette construction est détaillée dans une
monographie écrite en collaboration avec J. Thuswaldner en cours de soumission.
Ligne brisée et fractal Puisque la substitution est supposée primitive, elle ad-
met au moins un mot périodique bi-infini, noté u = . . . u−k ...u−1 u0 u1 u2 . . . [Que87].
On plonge ce mot bi-infini en une ligne brisée de Rn en remplaçant chaque lettre
de u par le vecteur canonique correspondant.
63
Dans le cas irréductible, selon l’hypothèse Pisot, la ligne brisée reste à une
distance bornée de la droite dilatante [AI01]. Dans le cas réductible, la projection
sur le beta-espace contractant reste toujours un ensemble borné. À partir de cette
projection, on définit le fractal de Rauzy (Trans. AMS, 2001).
Dans cette écriture, on sait que le couple (k, w) est unique [Mos96, DHS99].
Notons que cette unicité est loin d’être évidente, il s’agit de la principale raison
pour laquelle le système symbolique considéré contient des mots bi-infinis et pas des
mots infinis à droite seulement (en fait, pour certaines substitutions, cette unicité
est fausse si on ne considère que des mots infinis à droite).
Dans cette écriture, on peut considérer w comme le quotient de v par σ et k
comme le reste de cette division. Plutôt que k, on préférera souvent le préfixe de
longueur k de σ(w0 ). Cette écriture permet de décomposer les éléments d’une sous-
tuile en fonction de leur origine : pour tout mot bi-infini v qui commence par la
lettre i, il existe, un unique mot w et une décomposition de l’image de la lettre
centrale σ(w0 ) sous la forme σ(w0 ) = pis, avec p de longueur k, tel que v coïncide
avec σ(w) modulo un décalage de la longueur de p.
Ainsi, le fractal de Rauzy d’une substitution primitive est la solution d’un GIFS
dirigé par un graphe orienté appelé graphe des préfixes-suffixes.
65
Définition 2.2.1 Les sommets du graphe des préfixes-suffixes sont les éléments de
l’alphabet A.
Il y a une arête de i vers j dans ce graphe, étiquetée par la décomposition (p, i, s)
si et seulement si σ(j) = pis.
Vincent Cantérini et moi-même avons proposé ce graphe dans (JTN Bordeaux,
2001). D’autres versions avaient été introduites antérieurement. Ainsi, dans ses
travaux sur la substitution de Tribonacci, Rauzy travaillait avec un graphe des
suffixes (les arêtes ne contiennent que le suffixe s) [Rau82]. Dans le cadre des
beta-numérations, un graphe similaire apparaît, étiqueté seulement par des préfixes
[DT93]. Or, ces deux formalismes (préfixes ou suffixes uniquement) ne conviennent
pas pour un système substitutif d’un point de vue dynamique : la principale raison
est que les étiquettes de chemins du graphe ne sont pas en bijection avec les chemins
eux-mêmes ; il peut exister deux chemins étiqueté de manière semblable qui partent
de différents sommets. Avec Vincent Canterini, nous avons donc proposé le graphe
des préfixes-suffixes, et nous avons ainsi pu généraliser les résultats de Rauzy sur la
description du système engendré par la substitution de Tribonacci.
Théorème 2.2.2 (JTN Bordeaux, 2001) Soit σ une substitution primitive Pi-
sot. Le système symbolique constitué de mots bi-infinis engendré par σ est isomorphe
en mesure à un odomètre sur l’ensemble des étiquettes de chemins infinis reconnus
par le graphe des préfixes-suffixes.
Tuiles disjointes Dans [Rau82], Rauzy montrait facilement que l’aire des inter-
sections entre les sous-tuiles est nulle : ces tuiles ne s’intersectent que sur leur fron-
tière. Il s’appuyait fortement sur cette propriété pour obtenir ses résultats, comme
nous le détaillerons plus loin.
Cependant, lors de la construction d’autres fractals, il est vite apparu que cette
propriété de sous-tuiles disjointes en mesure n’était pas prouvée. Après différents
tâtonnements, une condition combinatoire a été introduite dans [AI01] pour assurer
cette propriété (voir le survol (Pytheas Fogg, LNM, 2002)). Grossièrement, on dit
qu’une substitution vérifie la condition de fortes coïncidences dès que toutes les
paires de mots bi-infini périodiques pour la substitution partagent un segment en
commun lorsqu’elles sont représentées sous la forme d’une ligne brisée dans Rn .
Cette condition combinatoire, simple à priori, est en fait assez frustrante : on
sait que toutes les substitutions Pisot sur deux lettres la vérifient [BD02], on ne
connaît aucun contre-exemple sur des alphabets plus gros, mais on ne sait pas pour
l’instant démontrer que toutes les substitutions Pisot la vérifient.
Cette condition est cependant fondamentale, dans la mesure où elle assure que
les fractals pour les substitutions qui la vérifient sont bien la solution unique du
GIFS donné par le graphe des préfixes-suffixes.
Théorème 2.2.3 ([AI01, SW02], (Trans. AMS, 2001), (JNT, 2007)) Soit σ
une substitution primitive, unitaire et Pisot. Si σ satisfait la condition de fortes coïn-
cidences, alors les sous-tuiles de son fractal de Rauzy ont leurs intérieurs disjoints.
Ces sous-tuiles sont l’unique solution du GIFS donné par le graphe des préfixes-
suffixes.
66
Ce théorème a une histoire assez longue. Il a d’abord été démontré par Rauzy
pour la substitution de Tribonacci [Rau82]. Ensuite, ce résultat a été prouvé par
Arnoux et Ito dans [AI01] pour le cas des substitutions irréductibles, avec une
construction du fractal basée sur des approximations successives. Sirvent et Wang
ont insisté sur l’aspect GIFS, toujours pour le cas des substitutions irréductibles
[SW02].
La preuve de ce résultat pour les fractals obtenus par la méthode arithmétique
de Rauzy [Rau82] a été donnée par V. Canterini et moi-même dans (Trans. AMS,
2001), en s’appuyant sur la notion de désubstitution étudiée dans (JTN Bordeaux,
2001). Nous en déduisons des résultats sur les facteurs topologiques des systèmes
substitutifs. L’intérêt de cette construction par rapport à celle de [AI01] était que
nous pouvions envisager de travailler sur des substitutions non unitaires, comme
nous aurons l’occasion d’en discuter plus tard.
Surtout, la généralisation de ces résultats au cas réductible (où le polynôme
caractéristique de la matrice n’est plus irréductible) a été proposée dans (JNT,
2007), par Valérie Berthé et moi-même, pour considérer les problèmes liés aux beta-
substitutions. Cela a en particulier d’expliciter le lien entre les fractals de Rauzy et
les systèmes de numération. Le cas des substitutions non unitaires a aussi été traité
dans (JNT, 2007), nous en rediscutons au chapitre 3.
T (2) = h(T (1) + 2π(e1 )) T (3) = h(T (2) + 2π(e1 )) T (4) = h(T (3)).
chaque tuile T (i), il y a autant de sous-tuiles que de flèches qui partent du sommet i
dans le graphe. De plus, le vecteur de translation associé à la sous-tuile T (j) dans la
décomposition de T (i) est donné par le préfixe apparaissant dans l’étiquette. Ainsi,
puisqu’une seule arête part des sommets 2, 3 et 4, on sait que les tuiles T (2), T (3)
et T (4) ne se décomposeront qu’en une seule sous-tuile.
Le fractal et sa décomposition sont montrés dans la figure 2.4. Dans cette figure,
la contraction h est la composée d’une homothétie contractante et d’une rotation
d’environ π/2 : l’image des tuiles (qui ont la forme de rectangles horizontaux) est
alors des rectangles pratiquement verticaux.
Là encore, ce résultat a été montré par étapes. D’abord dans le cas irréductible
dans [AI01]. Avec Vincent Canterini, nous avons redémontré ce résultat avec les
approches de séries entières dans (Trans. AMS, 2001). Cette nouvelle approche m’a
permis d’introduire le cas non unitaire dans (Erg. Th. Dyn. Sys., 2003). Le cas
réductible a été traité par Valérie Berthé et moi-même dans (JNT, 2007).
−→
Fig. 2.5 – Le fractal de Rauzy pour la substitution σ(1) = 12, σ(2) = 13, σ(3) = 1
et l’échange de morceaux défini à partir de ses trois sous-tuiles.
Ainsi, savoir si un système substitutif est un codage générateur pour une addition
sur un tore est ramené à une question de pavage.
Le recouvrement est ici périodique parce que la condition surPles tuiles est indé-
pendante du nom des tuiles : pour tout point γ dans la grille nk=2 Z(π(eB(k) ) −
π(eB(1) )), on place une copie de toutes les tuiles. Un exemple est illustré à la Figure
2.6 pour la substitution σ0 qui vérifie bien la condition de quotient.
Théorème 2.3.1 ([IR06, EIR06, BK06]) Soit σ une substitution primitive Pi-
sot unitaire. Alors les conditions suivantes sont équivalentes :
– Les sous-tuiles du fractal de Rauzy pavent l’espace contractant Hc de manière
autosimilaire.
– Le fractal de Rauzy est la base d’une partition de Markov pour l’action de
la matrice d’incidence de la substitution sur un tore obtenu en quotientant
l’espace engendré par les espaces propres associés à sa valeur propre dominante
et à ses conjugués algébriques.
Si, de plus, la substitution est irréductible, alors ces conditions sont équivalentes
au fait que le système symbolique engendré par la substitution est un codage d’une
translation sur un tore de dimension d − 1, pour une partition génératrice donnée
par les sous-tuiles du fractal. La partition de Markov représente alors l’action de la
matrice sur le tore Tn .
1 1 1
Ainsi, pour la matrice M = 1 0 0 , qui correspond à la substitution
0 1 0
de Tribonacci, une partition de Markov est donnée à partir du fractal de Rauzy,
comme montré Fig. 2.7. Cette pièce pave l’espace selon un Z3 , et elle montre que
73
l’orbite de tout point de l’espace est caractérisé par des chemins dans un graphe à
trois états. Les arêtes de ce graphe ayant des étiquettes toutes distinctes, le graphe
est déterministe et la représentation symbolique est markovienne.
actuellement une synthèse sur ce sujet (CANT, 2009) à paraître chez Cambridge
University Press.
des entiers d’une numération. Il suffit pour cela d’étendre la définition des beta-
numérations aux numérations de Dumont-Thomas. En effet, selon [DT93], pour
toute substitution sur un alphabet A et pour chaque lettre a de P A, il est possible de
développer les réels de l’intervalle [0, hvβ , ea i[ sous la forme x = i≥1 hvβ , l(qi )iβ −i ,
où les qi sont des suites de préfixes lus dans le graphe des préfixes-suffixes à partir
du sommet a. On note dσ,a (x) la suite des préfixes qi . Dans (Integers, 2005), Valérie
Berthé et moi-même montrons que les chiffres qi de ce nouveau développement
peuvent être produits de manière gloutonne à partir d’un système dynamique sur
une suspension d’intervalles.
Proposition 2.3.2 (Integers, 2005) Soit σ une substitution primitive Pisot uni-
taire. Soit a une lettre de l’alphabet. Soit vβ un vecteur propre dominant de la
transposée le la matrice d’incidence de σ.
Pour tout x ∈ [0, hvβ , ea i[, on note q1 , q2 , . . . les préfixes d’images de lettres
qui constituent
P le développement de Dumont-Thomas de x : x peut s’écrire sous la
forme x = i≥1 hvβ , l(qi )iβ −i où les qi sont les étiquettes d’un chemin du graphe
des préfixes-suffixes qui part de a.
Alors les qi sont obtenus par codage de la dynamique suivante, qui étend les
beta-transformations.
S S
Tσ : a∈A [0, hvβ , ea i) × {a} → a∈A [0, hvβ , ea i) × {a}
(x, b) 7→ (βx − hv β , l(q)i, c)
(2.6)
σ(b) = qcs
avec
βx − δσ (q) ∈ [0, hvβ , ec i).
Nous en avons déduit que pour toute substitution primitive, le fractal de Rauzy
est la représentation des réels qui sont des entiers pour cette nouvelle numération
(Integers, 2005). Ceci a permis d’expliciter définitivement pourquoi les approches
par représentation des entiers et par représentation des points fixes sont strictement
équivalentes.
Du point de vue des beta-numération, la condition de pavage autosimilaire s’ap-
pelle propriété (W) pour weak finiteness condition [Hol96, Aki02]. Elle spécifie que
Pour vérifier cette condition, un algorithme est donné par [ARS04] ; Il a été
utilisé pour caractériser tous les nombres cubiques qui la vérifient. Dans (CANT,
2009), nous donnons une généralisation de cette condition à toutes les substitutions,
à l’aide de géométrie discrète. On ne sait pas encore si un algorithme permet de la
vérifier.
Dans ce cadre, pour vérifier que la condition de pavage autosimilaire est satis-
faite, il suffit de montrer que le bord des approximations successives converge vers
un ensemble de mesure nulle [IR06]. Pour vérifier cela, l’école japonaise propose
d’utiliser une description des approximations de la frontière par un morphisme de
groupe libre, et lorsqu’il y a peu d’annulation dans cette description, en déduit qu’il
y a effectivement pavage [IK91, EI05].
Cette méthode est intéressante pour certaines substitutions, mais aucun travail
à ce jour n’en a déduit des critères généraux de pavage.
Idée générale On considère l’intersection entre une sous-tuile T (i) et une autre
tuile du recouvrement, notée T (j) + γ. Il est possible de décomposer les deux sous-
tuiles selon le GIFS qui gouverne le fractal, on obtient alors
[
T (i) ∩ (T (j) + γ) = (hT (i1 ) + πP(p1 )) ∩ (hT (j1 ) + πP(p2 ) + γ).
σ(i1 )=p1 is1
σ(j1 )=p2 js2
[
=h (T (i1 ) + h−1 πP(p1 )) ∩ (T (j1 ) + h−1 πP(p2 ) + h−1 γ).
σ(i1 )=p1 is1
σ(j1 )=p2 js2
on obtient finalement
[
T (i) ∩ (T (j) + γ) = h e + T (i′ ) ∩ (T (j ′ ) + γ ′ ) (2.7)
σ(i1 )=p1 is1
σ(j1 )=p2 js2
3. Définir les arêtes du graphe : inclusion dans la décomposition par GIFS. Les
arêtes du graphes sont définies par la relation (2.7). Un travail technique
est nécessaire pour identifier les représentants dans D des intersections qui
apparaissent dans la partie droite de (2.7) (voir (Monographie S. & T., 2008)).
4. S’adapter au pavage considéré : considérer des chemins infinis. C’est seule-
ment à cette étape que le graphe est spécifié en fonction du recouvrement
considéré (périodique ou autosimilaire). Pour un ensemble de translation don-
né Γ, le graphe de frontière est l’ensemble des chemins infinis dans le graphe
précédent issus des sommets [i, γ, j] tels que [γ, j] ∈ Γ. On montre dans (Mo-
nographie S. & T., 2008) que les conditions qui définissent ce graphe en font
un graphe fini.
Théorème 2.3.3 (Monographie S. & T., 2008) Soit σ une substitution primi-
tive Pisot unitaire. Soit Γ ⊂ π(Zn ) × A un ensemble de translations localement fini
qui permet de recouvrir l’espace beta-contractant à l’aide des sous-tuiles du fractal
de Rauzy.
L’intersection d’une sous-tuile T (i) avec une autre tuile T (j)+γ du recouvrement
est non vide si et seulement si [i, γ, j] ou [j, −γ, i] est un noeud du graphe de frontière
associé à Γ.
Théorème 2.3.4 (Monographie S. & T., 2008) Soit σ une substitution primi-
tive Pisot et β la valeur propre dominante de sa matrice d’incidence.
– Le recouvrement autosimilaire associé à σ est un pavage si et seulement si la
valeur propre dominante de la matrice du graphe de frontière pour l’ensemble
de translation autosimilaire Γsrs est strictement inférieure à β.
80
Exemple Dans la figure 2.8, nous donnons le graphe de frontière pour le recou-
vrement autosimilaire de σ0 . En considérant tous les sommets qui sont de la forme
[1, γ, j], on peut ainsi retrouver toutes les tuiles du recouvrement qui sont adja-
centes à la tuile centrale T (1). Ainsi, on montre que T (1) intersecte les trois autres
sous-tuiles T (2), T (3) and T (4) (puisque les sommets [1, 0, 2], [1, 0, 3] and [1, 0, 4]
apparaissent dans le graphe).
Cette tuile intersecte aussi cinq autres tuiles du recouvrement : T (1) + π(0, 0,
1, 0), T (2) + π(0, 0, 1, 0), T (1) + π(0, 1, −1, 0), T (1) + π(0, 1, 0, 0) et T (1) + π(1, −1,
1, 0), qui correspondent aux sommets du graphe [1, π(0, 0, 1, 0), 1], [1, π(0, 0, 1, 0), 2],
[1, π(0, 1, −1, 0), 1], [1, π(0, 1, 0, 0), 1], [1, π(1, −1, 1, 0), 1].
En étudiant la valeur propre maximale de la matrice d’incidence de ce graphe,
on montre que le recouvrement autosimilaire est bien un pavage, comme illustré
Figs. 2.6 et 2.8.
tous positifs. Pour étudier des automorphismes avec des coefficients négatifs, une
piste consiste à considérer non plus des substitutions mais des automorphismes du
groupe libre, c’est-à-dire des règles de transformations qui autorisent des annulations.
Par exemple, dans [AFHI07], les auteurs exploitant les constructions de frac-
tals à l’aide d’approximations polygonales ainsi que les formalismes d’itérations
définis dans [SAI01]. Cela permet de construire une partition de Markov pour un
automorphisme du tore T4 admettant deux directions dilatantes et deux directions
contractantes, avec certains coefficients négatifs. La généralisation de cette approche
et la définition de graphes de frontière pour les pièces de la partition de Markov
obtenue dans[AFHI07] est le prochain travail à effectuer dans cette direction.
L’étude des automorphismes du groupe libre présente des intérêts plus généraux
que la construction de partition de Markov. Dans cette direction, dans la section
3.4.3, nous discuterons de la dynamique symbolique pour les laminations attractives
de classes d’automorphismes du groupe libre et ses applications pour la définition
d’invariants à conjugaison près.
Représentation des additions sur un tore Dans le cas non algébrique, pour
les additions, la principale question concerne la description de la dynamique sym-
bolique des additions sur un tore, quelles qu’elles soient. Cela nécessite de trouver
une partition du tore convenable vis-à-vis de l’addition. S’inspirant du cas unidi-
mensionnel, on cherche à construire ce domaine fondamental par itération et re-
normalisations successives de différentes substitutions, reliées à un développement
en fractions continues du vecteur de translation. On entre alors dans le monde des
fractions continues multidimensionnelles et des substitutions généralisées, que nous
aborderons dans le chapitre 3 (section 3.3).
Si la construction d’un tel domaine fondamental est réalisée, on peut espérer
pouvoir en déduire des propriétés pour construire des partitions de Markov pour
des automorphismes du tore moins spécifiques.
84
Chapitre 3
85
86
être simplement connexes, 0 peut ne pas être point intérieur [Aki02]. Les méthodes
utilisées pour mettre en évidence des phénomènes sont très peu généralisables et
concernent des exemples fixés.
frontière n’est pas une courbe de Jordan). Par contre, 0 est point intérieur du
fractal.
σ5 Cette substitution est définie par σ5 (1) = 123, σ5 (2) = 1, σ5 (3) = 31. Le groupe
fondamental du fractal est non dénombrable. 0 se trouve sur la frontière du
fractal : même si cela est peu visible sur le dessin, il existe en fait un isthme
très fin qui part de l’extérieur du fractal et se termine en 0.
σ6 Cette substitution est définie par σ6 (1) = 12, σ6 (2) = 31, σ6 (3) = 1. Le groupe
fondamental du fractal est non dénombrable. 0 se trouve sur la frontière du
fractal.
Dire que la frontière d’un compact est une courbe de Jordan est équivalent à
dire que le compact lui-même est homéomorphe à une disque. Pour vérifier cette
propriété sur un fractal de Rauzy, on utilise les propriétés d’autosimilarité du bord :
on sait que le bord se décompose de manière autosimilaire, en considérant le graphe
de la frontière par exemple. De plus, chaque morceaux du bord admet lui-même
une décomposition. En considérant les points triples du fractal, on peut vérifier si,
topologiquement, le bord peut se décomposer sous forme de cercle.
Fig. 3.2 – Les graphes de connexité pour les sous-tuiles du fractal de la substitution
σ0 . Chaque sommet des graphes correspond à une intersection de la forme T (i) ∩
T (j)+γ qui apparaît dans la décomposition de la frontière de T (i). Un sommet entre
deux arêtes signifie que les morceaux de la frontière correspondant s’intersectent.
composent sous forme de lignes brisées (leurs graphes de connexité doivent être
des lignes). En appliquant le processus d’autosimilarité, on va ainsi construire des
lignes polygonales qui convergent vers le bord du fractal en maîtrisant le processus
de décomposition, et obtenir finalement le bord d’un disque.
Théorème 3.1.1 (Monographie S. & T., 2008) Soit σ une substitution primi-
tive Pisot unitaire dont la valeur propre dominante est de degré 3. On suppose que
le recouvrement auto-similaire est un pavage.
Alors chaque sous-tuile T (i) (i ∈ A) est homéomorphe à un disque si les condi-
tions suivantes sont vérifiées.
1. Tous les graphes de connexité des sous-tuiles T (i) sont des boucles.
2. Tous les graphes de connexité des éléments qui apparaissent dans la décompo-
sition des sous-tuiles T (i) sont des lignes ou réduits à un noeud.
3. Les intersections entre trois tuiles du pavage autosimilaires sont vides ou ré-
duites à un point.
Groupe fondamental Nous avons exhibé des compacts du plan euclidien dont
le groupe fondamental est non libre et non dénombrable, ce qui est pathologique
d’un point de vue topologique. Il serait intéressant de décrire la structure du groupe
fondamental.
Comme déjà mentionné, le fait que le groupe fondamental est non dénombrable
implique que l’intérieur du fractal n’est pas simplement connexe. Or, des exemples
de structures qui ne sont pas simplement connexes existent (tapis de Sierpinski,
Hawaiian Earring) et leur groupe fondamental est décrit par des mots [CL08, EK98].
Cependant, les méthodes ne sont pas tout à fait transposables ici dans la mesure
où les exemples qui ont été considérés jusqu’à maintenant étaient de dimension
topologique 1 alors que nos fractals sont de dimension topologique 2.
suites [ABD06]. Dans le même esprit, les nombres irrationnels dont le développe-
ment binaire est le point fixe d’une substitution sont transcendants [AB07].
En approximation diophantienne enfin, les substitutions ont montré leur utilité :
leurs points fixes produisent des nombres transcendants qui sont très mal approxi-
mables par des entiers algébriques cubiques [Roy03, HM06].
Te = φβ (Int(β)) ⊂ Kβ
Pour différencier ce fractal du fractal construit au chapitre 2, le fractal de Rauzy
usuel est appelé fractal euclidien.
– Les sous-tuiles Te (a) sont disjointes en mesure dans l’espace complet de repré-
sentation, de mesure non nulle et elles sont l’adhérence de leurs intérieurs.
– On obtient un recouvrement de l’espace en considérant les translatés des sous-
tuiles selon un ensemble autosimilaire et localement fini (ici, l’ensemble des
(a−1)
paires (x, a) telles que x ∈ Z[1/β] ∩ [0, Tβ (1))) :
[
Kβ = Te (a) + φβ (x). (3.2)
(a−1)
x∈Z[1/β]∩[0,Tβ (1))
Une des questions qui vont nous intéresser va être de donner des conditions
explicites pour que ce recouvrement de Kβ soit un pavage.
97
Familles qui vérifient cette propriété Dans [FS92], les auteurs montrent que
dès que β est une racine dominante d’un polynôme du type X n = an−1 X n−1 + · · ·+
a0 , avec an−1 ≥ an−2 ≥ . . . a0 ≥ 1, alors β vérifie la propriété (F). Si on considère
la β-substitution engendrée par β, lorsque le polynôme X n − an−1 X n−1 + · · · − a0
est irréductible, le système dynamique symbolique est à spectre purement discret :
il est mesurablement isomorphe à une addition sur un groupe compact [Sol92].
Une caractérisation des nombres de Pisot de degré 2 ou 3 qui vérifient (F) est
explicitement donnée dans [Aki00].
∀a ∈ A = {1 . . . n},
∀z ∈ Z[hvβ , ek i, · · · , hvβ , ek i] ∩ [0, hvβ , ea i), d(σ,a) (z) est fini. (3.3)
point intérieur du fractal de Rauzy. On obtient ainsi un résultat plus général que
[Aki02] puisque notre preuve, basée sur la géométrie des plans discrets, englobe
toutes les substitutions unitaires Pisot (y compris les substitutions réductibles). De
plus, on en déduit un critère algorithmique pour vérifier cette propriété, inspiré par
les graphes de frontière.
Le cas non unitaire Les preuves de (Monographie S. & T., 2008) et [Aki02]
sont valables seulement dans le cas unitaire : dans le cas non-unitaire, le fractal de
Rauzy euclidien ne vérifie pas de propriété de pavage, puisque l’ensemble produit
par approximation de plan n’est pas un ensemble localement fini ; pour la même
raison, ses sous-tuiles ne sont pas disjointes. Ceci empêche d’utiliser les approches
géométriques ou arithmétiques pour relier la propriété (F) au fait que 0 est point
intérieur du fractal.
Dans ce cadre, le fractal de Rauzy complet (intégrant des places non-archimé-
diennes) est d’une large utilité. En effet, nous prouvons que sous la condition (F), les
sous-tuiles sont disjointes et des propriétés de pavages sont vérifiées. Dans (Monas.
Math., 2008), en collaboration avec Shigeki Akiyama, Valérie Berthé et Guy Barat,
nous exploitons ces propriétés de pavages dans l’espace complet de représentation
pour en déduire que si β vérifie la propriété (F), alors 0 est point intérieur du fractal
de Rauzy complet et du fractal de Rauzy euclidien.
en base b est ultimement périodique sont les nombres rationnels. Plus généralement,
lorsque β est un nombre de Pisot, les nombres dont le β-développement est ultime-
ment périodique sont tous les éléments de Q(β) [Ber77, Sch80].
Base non-entière unitaire Pour comprendre le cas non quadratique (au moins
cubique), Akiyama a montré que dès que la propriété (F) est vérifiée, il existe un
intervalle non vide de la forme [0, ǫ[ dont tous les rationnels ont un β-développement
purement périodique [Aki98]. Ceci est assez inattendu, dans la mesure où on attend
que la répartition des développements périodiques en base β soit aléatoire, en tout
cas indépendante de la position par rapport à 0.
Ce résultat est moins surprenant lorsqu’on considère le point du vue du fractal
de Rauzy. En effet, Ito et Rao ont proposé d’utiliser le fractal de Rauzy et ses
propriétés d’extension naturelle [IR05]. Puisque l’extension naturelle respecte la
structure algébrique de Z[β] dans le cas unitaire, on en déduit qu’un élément x de
Q(β) a un développement purement périodique si et seulement s’il existe une lettre
a telle que
– x < T (a) (1),
– La tuile T (a) du fractal euclidien contient le point du plan contractant dont
les coordonnées sont données par les conjugués de Galois de −x.
Si on suppose que la propriété (F) est vérifiée, on sait que 0 est point intérieur
du fractal, en particulier d’une de ses tuiles T (a). Cette tuile T (a) contient donc
un voisinage de 0. Si on considère maintenant un rationnel x suffisamment petit,
tous ses conjugués de Galois sont égaux à x et sont donc petits. Tout point ayant
(−x, . . . , −x) pour coordonnées dans l’espace contractant sera donc près de 0 et
appartiendra ainsi à T (a), ce qui implique que le développement de x est purement
périodique.
101
Bases non-unitaires Dans le cas non-unitaire, comme nous l’avons déjà discuté,
les propriétés d’extension naturelle de la tuile euclidienne ne sont plus vérifiées. Dans
(JNT, 2007), avec Valérie Berthé, nous utilisons le fractal complet pour caractériser
les points au développement purement périodique dans le cas non-unitaire. Nous
généralisons le résultat de [IR05] au cas non-unitaire, en remplaçant le fractal de
Rauzy euclidien par le fractal complet. Nous donnons aussi une preuve plus simple
que celle de [IR05] et qui fait ressortir la structure d’extension naturelle proposée
par le fractal de Rauzy.
Théorème 3.2.7 (A., F., S. & S., en cours) Soit β un nombre de Pisot cubique
et unitaire. Soit T le fractal de Rauzy associé. Alors tous les points de ∂T ∩ R sont
des nombres irrationnels. En particulier, γ(β) 6∈ Q.
Le cas non unitaire Dans le cas non unitaire, un calcul assez simple montre que
tous les rationnels de la forme 1/N (β)n n’ont pas un développement périodique. On
a donc γ(β) = 0.
On introduit alors la quantité suivante, qui évite les nombres dont le dénomina-
teur est certain de générer un développement non périodique.
γ̃(β) = sup{ε, ∀p/q < ε, pgcd(q, N (β)) = 1, dβ (p/q) est purement périodique}.
Nous montrons dans (Monas. Math., 2008) que contrairement au cas unitaire,
cette quantité n’est pas liée à la propriété (F). En effet, dans le cas quadratique non-
unitaire, la proposition 3.2.6 se généralise pour montrer que γ̃(β) est intimement
lié à la description de la frontière du fractal de Rauzy complet (incluant les places
locales). En décrivant cette frontière par un GIFS, on parvient à calculer cette
quantité dans des cas particuliers.
Théorème 3.2.8 (Monas. Math., 2008) Les rationnels ont un comportement
inattendu vis à vis des développements purement périodiques en base β non unitaire
et de la propriété
√ de finitude.
– γ̃(2 + 7) = 0 alors que ce nombre vérifie la propriété (F) (il s’agit de la
2
racine de
√ X − 4X√− 3).
– γ̃(5 + 2 7) = (7 − 7)/12, qui vérifie toujours la propriété (F) (il s’agit de la
racine de X 2 − 10X − 3).
Dans (A., F., S.& S., en cours), nous montrons aussi que dans le cas quadratique
non ramifié, γ̃(β) appartient toujours à Q(β), et nous proposons un algorithme pour
calculer cette valeur à partir de la notion de graphe de frontière.
103
Fig. 3.5 – Illustration des trois cas de calcul des quantités γ(β) et γ̃(β). L’illustra-
tion est faite dans un cas unitaire, mais la démonstration reste valable dans le cas
non unitaire. La quantité γ̃(β) est donné par la partie la plus large de la diagonale
S (a−1)
qui est entièrement inclus dans l’extension naturelle a∈A (−Te (a) ) × [0, Tβ (1)).
e
Cette extension naturelle est représentée par les sous-tuiles −T (a) dans la direction
horizontale et par l’intervalle [0, 1) sur l’axe vertical. Ainsi, l’extension naturelle
est une union de cylindres à base fractale et de hauteur verticale. La hauteur du
cylindre dépend de la sous-tuile considérée.
En fonction du premier endroit où la diagonale sort de cette extension naturelle,
on obtient différentes situations pour γ̃(β), décrites dans (Monas. Math., 2008) et
dans la proposition 3.2.6.
La première situation correspond au cas où la diagonale part de 0 et sort de l’exten-
(a−1)
sion naturelle sur un plateau de hauteur Tβ (1). Alors, γ̃(β) appartient à l’orbite
de 1 sous l’action de Tβ .
La deuxième situation signifie que la diagonale sort de l’extension naturelle en tra-
versant une verticale entre deux plateaux. Le point d’intersection se situe alors au
dessus de l’intersection entre deux sous-tuiles (−Te (a)) ∩ (−Te (b)).
La dernière situation signifie que la diagonale traverse complètement l’extension
naturelle et sort au dessus d’une nouvelle tuile du pavage autosimilaire.
À partir de cette caractérisation et d’une description par graphe des intersections
entre les tuiles du pavage, on obtient un calcul exact de γ̃(β) pour certains β et des
informations sur son irrationalité.
104
Théorème 3.2.9 (A., F., S.& S., en cours) Supposons que β est un nombre
quadratique non unitaire,
√ solution de β 2 = aβ + b. Soit d l’entier sans facteur carré
tel que Q(β) = Q( d). Si
– b est sans facteur carré,
– b est premier avec le discriminant de Q(β),
– d est un résidu quadratique pour tout les diviseurs premiers impairs de b,
– d ≡ 1 (mod 8) si b est pair.
Alors γ̃(β) est un élément de Q(β). De plus, il existe un algorithme pour le calculer
à partir du graphe de frontière du fractal de Rauzy associé à la β-numération.
Transcendance de γ(β) Une question difficile est d’aller plus loin dans l’étude
de γ(β), au moins dans le cas unitaire cubique.
En effet, nous savons montrer que γ(β) n’est alors pas un nombre rationnel (A.,
F., S.& S., en cours). Nous utilisons pour cela le fait que cette quantité est décrite
par l’intersection d’un courbe fractale et d’une droite. Cependant, on n’utilise pas
la description explicite du fractal par son graphe de frontière. La connaissance de
ce graphe peut-elle permettre de déterminer la valeur de γ(β) (comme c’est le cas
dans le cas quadratique), ou au moins montrer qu’il ne s’agit pas d’un élément de
Q(β) ?
Dans le cas quadratique non-unitaire, on obtient l’algébraicité de γ̃(β) en étu-
diant la frontière du fractal par une description autosimilaire. Dans le cas cubique,
il faut se restreindre à l’intersection du fractal avec une droite, qui n’est pas décrite
par un IFS à priori. Pour avancer dans cette direction, il faudra décrire explicite-
ment l’intersection du fractal et la droite, sans doute avec un arbre infini du type
diagramme de Bratelli.
En effet, dans [HM06, IFHY03a], en suivant les idées de [Rau82], les auteurs
considèrent des nombres de Pisot β cubiques unitaires avec un conjugué de Galois
non réel. Ils montrent que les meilleures approximations du (1/β, 1/β 2 ) pour une
norme euclidienne décrite par β sont données par la suite récurrence associée à β, et,
en tout état de cause,
√ que ces nombres sont très mal approximés par des nombres
rationnels (puisque N kN (1/β, 1/β 2)k la quantité est minorée par une quantité
indépendante de N ).
La preuve s’appuie sur le fractal de Rauzy, en particulier ses propriétés de pa-
vages, sur le fait que 0 est point intérieur, et l’étude des ellipses incluses dans ce
fractal.
Pour généraliser cette approche, il faut être capable de déterminer le rayon du
fractal de Rauzy, c’est-à-dire la taille maximale de la boule incluse dans le fractal,
éventuellement pour différentes topologies. Ensuite, il faudra déterminer la valeur
du rayon de cette boule ; sans doute en la décrivant par un arbre pondéré.
même que les suites sturmiennes sont caractérisées comme les codages d’additions
sur le tore de dimension 1. Il faut ensuite être capable de définir un développement
en fraction continue multidimensionnel d’un vecteur (qui sera le vecteur orthogonal
au plan approximé). Il faut enfin définir des substitutions multidimensionnelles qui
permettront d’engendrer le codage de l’approximation de plan.
Dans cette direction, un procédé d’extension des substitutions en grande dimen-
sion a été développé par Arnoux et Ito [AI01], et il semble très prometteur. Nous
allons dans cette section détailler comment il est possible de l’utiliser pour répondre
partiellement à la question de l’engendrement des plans discrets, et quelles sont les
perspectives dans ce domaine.
Faces du plan discret Le plan discret P(a,b,c) est naturellement recouvert par
différentes faces de cubes placées en des points à coordonnées entières. Pour décrire
un plan discret, on recherche donc les couples de la forme
[ point à coordonnées entières , orientation de la face de cube ]
qui permettent de recouvrir P(a,b,c) . On introduit donc trois faces de cubes qui vont
permettre de reconstruire P(a,b,c) .
Selon [ABI02], une face x + Fi de P(a,b,c) sera alors désignée par la notation [x, i∗ ].
L’ensemble des faces de P(a,b,c) est appelé Γ(a,b,c) ; c’est cet ensemble qu’il faut
déterminer. [
P(a,b,c) = x + Fi .
[x,i∗ ]∈Γa,b,c
– L’ensemble x+F3 est une face du plan discret si et seulement 0 ≤ ax+by+cz <
c.
On obtient donc une description arithmétique de P(a,b,c) :
Γa,b,c = {[x, i∗ ], hx, (a, b, c)i ≥ 0 et hx, (a, b, c)i < hei , (a, b, c)i}. (3.5)
7→
[0, 1∗ ]
7→
[0, 2∗ ]
7→
[0, 3∗ ]
Fig. 3.6 – Images des faces du cube unité par la substitution généralisée de la
substitution σ(1) = 3, σ(2) = 13, σ(3) = 233. La face [0, 1∗ ] est représentée par la
face du cube orthogonale à l’axe des x (similairement pour les autres faces).
E1 (σ)∗ Γx ⊂ Γt Mx .
U ⊂ E1 (σ)∗ U.
7→
Fig. 3.7 – Image du cube unité par la substitution généralisée de σ(1) = 3, σ(2) =
13, σ(3) = 233. Chaque couleur dans la figure de droite correspond à l’image de la
même de la dite couleur dans le cube unité à gauche. On remarquera que les images
des différentes faces du cube unité ne se superposent pas. De plus, l’image du cube
unité contient le cube unité lui-même. Ces deux propriétés sont vérifiées par toutes
les substitutions généralisées.
x = M1 M2 . . . Mn xn . (3.7)
déduire que le plan discret Γx contient un motif généré par des substitutions géné-
ralisées
E1 (σ1 )∗ . . . E1 (σn )∗ (U) ⊂ Γx . (3.8)
En particulier, selon la section 3.2.2, ceci est équivalent au fait que 0 est un point
intérieur du fractal de Rauzy associé à σ. Cette propriété peut donc se vérifier en
construisant un graphe de frontière. Cependant, une telle vérification sort du cadre
de la géométrie discrète et est difficilement généralisable au cas où on composera
des substitutions différentes. Nous allons donc introduire un nouveau critère pour
l’engendrement du plan Γx .
Proposition 3.3.2 (CANT, 2009) Soit σ une substitution unitaire de type Pisot.
Soit x le vecteur propre dilatant à gauche de la matrice d’incidence M de σ. La
valeur propre dilatante est notée β. On note aussi vβ (2) , . . . , vβ (r+s) les vecteurs
propres contractants de M pour les conjugués de β. On introduit les constantes
Kk = max{|hl(S), vβ (k) i| pour s suffixe propre de l’image d’une lettre par σ} et
Kk′ = min{|hl(S), vβ (k) i| pour s suffixe propre de l’image d’une lettre par σ}.
La constante d’itération associée à la substitution est
( Kk ′
)
log(2 1−|β (k) | ) − log(Kk )
N = min , 2≤k ≤r+s .
− log(|β (k) |)
Alors σ satisfait la propriété de finitude étendue, c’est-à-dire que le plan discret
Γx est engendré à partir des itérations du cube unité si et et seulement si le motif
E1 (σ)∗ N (U) recouvre le motif V défini par :
0 ≤ hx, uβ i < hei , uβ i
V= [x, i∗ ] ∈ Zn × A, Kk .
|hx, vβ (k) i| < 1−|β (k) | , ∀ 1 < k ≤ r + s
Cette approche a été développée dans les années 1990 par l’école japonaise portée
par S. Ito [IO94] à partir des outils définis plus haut, en se basant sur l’algorithme de
fractions continues de Jacobi-Perron. Avec P. Arnoux et V. Berthé (Jour. Montoises,
2006), et dans un travail en cours avec V. Berthé et J. Bourdon (B., B. & S.,
en cours), nous travaillons sur la généralisation l’automatisation de l’approche de
[IO94] pour l’appliquer à d’autres algorithmes de fractions continues et étudier plus
précisément les différentes approximations de plans discrets. Avant de discuter des
apports, il est nécessaire de détailler un peu les points principaux de l’approche de
Ito et Ohtsuki.
7→ 7→
7→
Fig. 3.8 – Images des faces du cube unité par la substitution généralisée d’une
substitution de Jacobi-Perron σ3,5 . Il y a B faces de type 2 dans l’image des faces
de type 3 par σB,C , et C faces de type 3.
Fig. 3.9 – Un anneau et son image par une substitution généralisée, qui n’est pas
un anneau
généralisée ? Le premier cas non trivial dans ce cadre est de considérer des suites
infinies bidimensionnelles, c’est-à-dire des suites Ui,j indicées par Z2 . Dans ce cadre,
la notion de motifs bi-dimensionnel est naturelle : il s’agit d’un motif purement géo-
métrique, qui ne contient aucune information de localisation dans Z2 . Par exemple,
un motif peut être constitué d’un 1, placé à gauche d’un 3 et en dessous d’un 2. On
ne précise par à quel endroit de Z2 ce motif se trouve.
2
3 1
Cette notion de motif (positionné ou non positionné) est discutée dans la publi-
cation (TCS, 2004).
Une substitution définie par règle de placement ? Dans ce cadre, une sub-
stitution bidimensionnelle le devrait être une application qui associe à chaque lettre
un motif bi-dimensionnel non vide. Considérons par exemple :
2
Σ0 : 1 7→ 2 7→ 3 3 7→ 1.
1
Pour être un morphisme, il faut que cette application puisse s’appliquer sur les
motifs et non pas sur les lettres. Pour cela, il est nécessaire de savoir placer les images
de lettres les unes par rapport aux autres. Le problème ici est qu’il n’existe pas de
structure de monoïde sur Z2 : il n’y a pas de manière naturelle pour positionner
2 3
deux motifs l’un à côté de l’autre. Ainsi, l’image de 12 doit-elle être ou
1
2
, or autre chose ?
3 1
En fait, on ne sait même pas si des motifs peuvent se positionner correctement
pour recouvrir tout Z2 , sauf dans le cas particulier des motifs rectangulaires de même
taille ou des opérations canoniques existent (mettre deux motifs l’un au dessus de
l’autre ou sur leur côté) [GA97].
Même si cette question du placement est résolue, il faut aussi vérifier que ces
règles de placement sont compatibles, c’est-à-dire qu’en appliquant différentes règles
de placement les éléments ne se recouvrent pas. Là encore, ces questions se résolvent
bien dans le cas où les images de lettres sont des rectangles de même taille (la
substitution se découpe dans ce cas en deux substitutions unidimensionnelles).
2 2 2
2 2 1 1 2 1
7→ 3 1 7→ 1 7→ 2 1 2 1 7→ 1 7→
1 3 1 1 3 1
1 1 3
2
2
2 2 2 1
1 7→ 7→ 7→ 3 1 7→
1 3 1 3 1
1
1
2 2
2 2 3 1 2 1
3 1 2 1 3 1
7→ 7→ .
3 1 2 1
1 3 1
1
sont bornés. Il reste aussi à proposer des jeux de règles locales explicites dans ce
cas.
7→ 7→
7→ 7→
7→ 7→
7→
puis les images de ces règles locales par de nouvelles règles, jusqu’à ne plus produire
de nouvelles règles).
Ainsi, pour la substitution de Jacobi-Perron σ(2,3) , on obtient le jeu de règles
locales montré Fig. 3.11.
Fig. 3.12 – L’anneau présenté à la figure 3.9 n’était pas recouvert par règles locales
pour les substitutions de Jacobi-Perron. Par contre il est inclus dans un anneau
recouvert par règles locales, dont l’image est elle-même recouverte par règles locales.
Partie (1). Le lemme de l’anneau couvert par des règles locales Dans
notre travail en cours, V. Berthé, J. Bourdon et moi-même introduisons une nouvelle
définition pour les anneaux, qui intègrent la combinatoire de la substitution :
Définition 3.3.3 ((B., B. & S., en cours)) un sous-ensemble A d’un plan dis-
cret est un anneau couvert par un jeu de règles locales s’il existe une suite de motifs
primaires dans le jeu de règles locales qui recouvrent l’anneau et tels que chaque
motif intersecte exactement deux autres motifs du recouvrement.
Avec cette notion qui prend en compte la combinatoire des substitutions, nous
montrons dans (B., B. & S., en cours) que les substitutions généralisées respectent
les anneaux. Cette proposition est illustrée à la figure 3.12.
Il faut noter que la preuve de ce résultat n’est pas purement topologique mais fait
intervenir la combinatoire des substitutions. Il s’agit de considérer les préimages de
chaque règle locale du jeu et vérifier qu’elles ne se déconnectent pas, par une étude
de cas. Le point principal est que cette vérification est automatique et se fait en un
temps fini.
Il faut noter ici que le sens des arcs est inversé par rapport à la notion de
substitution : les flèches représentent les préimages des motifs par une substitution
et non leurs images.
Ce graphe est fini puisqu’il s’agit de sous-motifs d’un nombre fini de motifs (les
configurations terminales). D’un point de vue algorithmique, la difficulté consiste
à identifier l’ensemble des configurations terminales pour le jeu de règles locales.
Pour cela, on utilise la notion de motif admissible défini plus haut et un critère
topologique pour s’assurer que les configurations considérées sont bien minimales.
Il s’agit du point le plus long en terme de calcul dans cette approche.
Théorème 3.3.6 (B., B. & S., en cours) Soit σi des substitutions associées à
un algorithme de fractions continues en dimension 3. On considère un jeu de règles
locales pour lesquelles les substitutions généralisées vérifient le lemme de l’anneau
par règles locales.
On considère un vecteur x dont le développement en fractions continues est décrit
par les indices i0 , . . . , in , . . . . Si le développement est tel que pour tout n il existe
′
n tel que in in+1 . . . in+n′ indice un chemin qui part d’une configuration terminale
vers le cube unité, alors le plan discret Γx est engendré à partir du cube unité :
Premières constructions Nous avons vérifié que cette approche généralise exac-
tement le résultat de [IO94] dans la mesure où le graphe d’engendrement relatif aux
configurations terminales pour le lemme de l’anneau donné dans [IO94] est exacte-
ment celui qui est décrit dans [IO94]. De plus, la condition (3.9) décrit exactement
les chemins du graphe qui partent d’une configuration terminale mais ne reviennent
jamais vers le cube unité.
122
3.3.7 Perspectives
Nous avons finalement proposé une approche qui permet de décrire les développe-
ments en fractions continues de vecteurs en dimension 3 pour lesquels le plan discret
qui leur est orthogonal est engendré à partir du cube unité. Cette approche combine
des vérifications de contraintes, des constructions de graphes et des vérifications
topologiques. À partir de cette approche théorique, plusieurs perspectives sont à
l’étude.
Topologie des motifs qui engendrent les plans Un objectif sera de choisir
le meilleur algorithme de génération de plan discret en fonction de la topologie des
morceaux engendrés. Dans le cas substitutif Pisot, la non-connexité du fractal de
Rauzy implique que les itérations successives ne sont pas connexes à partir d’un
certain rang. Ainsi, il sera intéressant de déterminer quels sont les meilleurs algo-
rithmes de fractions continues qui engendrent des plans discrets à partir de pièces au
moins connexes, si possible simplement connexes, et avec un volume équitablement
réparti.
En relation avec cette question, des approches basées sur les substitutions gé-
néralisées et l’algorithme de fractions continues de Brun fournissent des bases pour
la reconnaissance de plans discrets [ABFJ07, BF08, Fer08]. La reconnaissance de la
topologie de ces motifs est maintenant une question qu’on peut espérer comprendre
en combinant les approches topologiques présentées au début de ce chapitre avec
les questions d’engendrement de plans discrets décrites ici.
Echange de morceaux dans des espaces p-adiques J’ai montré que les résul-
tats dynamiques connus dans le cas unitaire se généralisent au cas non unitaire : en
particulier, un système substitutif code les trajectoires d’un échange de morceaux
dans un espace un peu surprenant.
Théorème 3.4.1 (Erg. Th. Dyn. Sys, 2003) Soit σ une substitution irréductible
Pisot sur d lettres, qui vérifie la condition de fortes coïncidences. Soit Mσ la matrice
124
Avec des méthodes identiques au cas unitaire, on peut aller plus loin dans l’étude
de la dynamique du système substitutif : l’échange de morceaux peut se quotienter
sur un groupe abélien compact en une translation.
Proposition 3.4.2 (Erg. Th. Dyn. Sys, 2003) Tout système substitutif de type
Pisot est une extension finie presque partout de son facteur équicontinu maximal,
qui est une translation sur un groupe compact.
Avant cette approche, les seuls résultats connus sur le spectre discret des systè-
mes substitutifs non unitaires concernaient les substitutions sur deux lettres [BD02].
On voit ici que les graphe de pavages peuvent être exploités dans des contextes très
généraux.
Partition de Markov pour l’action d’une matrice sur des corps locaux
On considère donc une substitution Pisot irréductible non unitaire sur n lettres.
Comme nous venons de le rappeler, nous pouvons définir un fractal de Rauzy,
qui est un sous-ensemble de l’espace complet de représentation Kβ . La matrice
de la substitution M agit naturellement sur cet espace (via la multiplication par la
représentation de β dans chaque composante de l’espace Kβ ). Sous des conditions
125
naturelles (qui généralisent la condition Pisot) données dans (Erg. Th. Dyn. Sys,
2003), la matrice agit aussi naturellement sur un groupe compact obtenu comment
quotient de Kβ . Comme pour le cas unitaire, l’extension naturelle introduite à la
section 3.2 est alors un bon candidat pour une partition de Markov pour cette
action. Il faut pour cela qu’une extension de la condition de pavage exprimée par
des graphes de frontière soit vérifiée, comme illustré au théorème 3.4.3 (voir (Ann.
Inst. Fourier, 2004) et (Erg. Th. Dyn. Sys, 2003)).
La différence fondamentale entre les cas unitaire et non-unitaire est que cette
partition de Markov décrit l’action de la matrice sur l’espace de représentation
complet Kβ , qui inclut des parties non-archimédiennes. Dans cet espace, l’action de
M est inversible et peut donc être décrite par un sous-shift de type fini inversible :
il va s’agit du décalage sur l’ensemble des étiquettes de chemins bi-infinis du graphe
des préfixes-suffixes (notons bien que sur un ensemble de mots bi-infinis, ce décalage
est bien inversible). Rajouter les composantes non-archimédiennes nous ramène ainsi
à un cas équivalent à l’action d’une matrice inversible sur un tore.
Recherche d’un candidat Un bon candidat pour ces points consiste à repré-
senter la partie non-archimédienne de l’espace de représentation comme une limite
inverse d’anneaux d’entiers. Dans ce cadre, l’élément z = hx, vβ i considéré au départ
admet plusieurs préimages dans le quotient O(Q(β))/βO(Q(β)). On peut sélection-
ner la seule préimage z1 qui appartient Z[β], puis recommencer cette opération. La
126
suite des représentations dans l’espace complet des zn , notée φβ (zn ) converge alors
dans le fractal de Rauzy complet vers un point z∞ qui admet z pour représentation
euclidienne.
Intuitivement, cela revient à sélectionner dans le fractal de Rauzy représenté
Fig. 3.3 la ligne horizontale d’ordonnée y = 1. Formellement, on peut définir ce
nouvel ensemble en considérant une généralisation des beta-numérations.
Un cas plus spécifique : le cas non unitaire Cependant, dans le cas non
unitaire, les applications τr apparaissent comme une restriction injective de la dy-
namique de la beta-transformation ; en fait, cette dynamique procède exactement
à la sélection de points dans O(Q(β))/βO(Q(β)) : nous démontrons ceci dans un
travail en cours de rédaction avec Paul Surer, Joerg Thuswaldner et Valérie Berthé
(B., S., S. & T., en cours).
L’intérêt de ce processus de sélection est que, avec les SRS, on peut, y compris
dans le cas non unitaire, définir un ensemble compact qui représente les entiers pour
ces systèmes de numération. Par contre, contrairement au cas unitaire, l’ensemble
compact ainsi obtenu ne coïncide pas avec le fractal de Rauzy euclidien : il s’agit
d’un sous-ensemble de ce fractal euclidien.
Une manière de visualiser cet ensemble est la suivante. On considère le frac-
tal de Rauzy complet (incluant les parties p-adique associé au nombre β.PChaque
composante
P p-adique de ce fractal se plonge dans [0, 1[ par l’application ai p i ∈
Zp → ai p ∈ [0, 1[. Comme nous l’avons déjà mentionné, ce plongement respecte
−i
la mesure du fractal, ainsi que ses parties compactes. L’image du fractal complet
dans le fractal est alors un sous ensemble de Rd−1 croisé avec un produits d’inter-
valles [0, 1]N . Le fractal obtenu avec les SRS correspond aux éléments x de Rd−1
tels que (x, 1, . . . 1) appartient au plongement du fractal. Autrement dit, ce sont les
préimages dans le fractal euclidien des éléments qui se trouvent au bout de Zp .
127
Fig. 3.13 – Tuile centrale pour le shift radix system associée à la beta-substitution
du nombre de Pisot non unitaire beta3 = 7β2 + 3β + 2.
Les propriétés de ce nouveau compact sont complexes. Nous avons montré que
0 est un point intérieur de ce fractal. Par contre, il n’est plus autosimilaire mais
décrit par un graphe infini. La dimension de Haussdorf de son bord n’a pas encore
été calculée.
Théorème 3.4.4 (B., S., S. & T., en cours) Soit β défini par β 3 = 7β 2 −3β +2.
Les tuiles associées au shift radix system défini à partir de β forment un pavage du
plan R2 .
-1
-2
-3
-3 -2 -1 0 1 2
Une condition suffisante pour limiter les annulations Pour régler ce prob-
lème, Bestvina et Handel ont proposé de coder un automorphisme Φ du groupe libre
par un représentant topologique, plus formellement une application sur un graphe
marqué f : G → G qui induit l’automorphisme Φ sur le groupe fondamental de G,
en l’occurrence un groupe libre Fn . Un tel représentant est appelé un train-track
si les itérations de f ne contiennent aucune annulation. Elles se comportent donc
comme une substitution.
Betsvina et Handel se concentrent sur les équivalents algébriques des homéo-
morphismes pseudo-Anosov des surfaces, appelés iwip (irreducible with irreducible
power). Formellement, ces automorphismes sont tels qu’aucun facteur libre n’est
envoyé par l’automorphisme et ses puissances sur un conjugué de ce facteur.
Le résultat fondamental dit que tout automorphisme iwip, à conjugaison par un
automorphisme intérieur près, admet un train-track pour représentant topologique
[BFH97]. La construction de ce train-track est en plus proposée sous une forme
proche d’un algorithme.
Lien avec les substitutions Dans (Ann. Inst. Fourier, 2006), avec V. Berthé, P.
Arnoux et A. Hilion, nous nous intéressons aux laminations attractives d’un point
de vue purement symbolique. Nous étudions d’abord le lien entre la propriété iwip
et la propriété de primitivité. Il s’avère que, même si elles sont reliées, ces deux
propriétés ne sont pas équivalentes.
Nous montrons ensuite que la lamination attractive d’un automorphisme ex-
térieur iwip dans les coordonnées données par un représentant train-track f est
un système dynamique symbolique associé à un substitution double σf , obtenue en
doublant l’alphabet constitué par les arêtes sur lequel le train-track est défini.
En particulier, nous montrons que ce système est minimal et invariant par le
flip si et seulement si la substitution double σf est non-orientable, c’est-à-dire qu’il
n’existe pas de sous-ensemble de l’alphabet qui le partitionne en deux et est stable
ou disjoint de son image par la substitution.
Ainsi, tout automorphisme extérieur Φ iwip non-orientable contient une dyna-
mique substitutive minimale, qui représente la lamination attractive de Φ du bord
du groupe libre.
Fig. 3.15 – Fractals de Rauzy pour deux paires (τ4 , σ4 ), et (τ2 , σ2 ) de substitutions
Pisot unitaires irréductibles. Dans chaque paire, les substitutions sont conjuguées
par un automorphisme du groupe libre. Ces fractals semblent avoir des propriétés
topologiques communes
132
Chapitre 4
Appréhender le
fonctionnement d’un système
dynamique en biologie
moléculaire
Dans les deux chapitres précédents, nous avons vu comment on pouvait tirer
parti de la connaissance d’une application pour considérer ses propriétés dynamiques
et en extraire des informations sur les codages de cette application. Cependant, cela
nécessite d’une part de connaître explicitement l’application, d’autre part d’étudier
une application dont les régularités sont assez importantes. Dorénavant, nous allons
discuter des approches de systèmes dynamiques dans un autre domaine, la biologie
moléculaire.
La situation est dans ce cas là vraiment orthogonale à ce que nous avons consi-
déré jusqu’alors : on dispose d’observations sur un système ; on suppose simplement
que ce système suit une loi dynamique, au sujet de laquelle on dispose d’informa-
tions très partielles. Le but est d’exploiter les observations disponibles sur le système
de manière optimale.
Un des points qui frappe dans ce nouveau domaine est son manque de contours ;
il s’agit là d’un contraste frappant avec la théorie des systèmes dynamiques symbo-
liques où les enjeux sont bien déterminés. La raison principale de ce flou en biologie
des systèmes est la jeunesse de ce domaine : mis à part quelques articles précur-
seurs et fondateurs des années 1960 (le travail de Jacob et Monod en particulier),
l’importance des concepts de dynamique est réellement discutée en biologie molé-
culaire depuis seulement une quinzaine d’années : l’intérêt des biologistes croît avec
l’amélioration des techniques d’observation à grande échelle dans une cellule. Mais
finalement, ce domaine n’en est qu’à ses balbutiements. Il est donc caractérisé par
une profusion de propositions de méthodes d’analyses de réseaux et de données. A
long terme, la sélection entre les différentes approches se fera sans doute par leur
133
134
Visualiser les régularités Une méthode pour visualiser des régularités consiste
à représenter une séquence par une image de dimension 2, avec des techniques de
jeu de chaos.
Pn Il s’agit là de représenter une séquence u1 . . . un ... par l’ensemble de
points { i=1 l(ui )/2i }, où les vecteurs l(A), l(C), l(G) et l(T ) sont quatre points
135
du plan (typiquement, (1, 1), (1, −1), (−1, 1), (−1, −1) [Jef90]. En considérant de
cette manière des génomes d’espèces différentes, on observe à l’oeil nu que les re-
présentations obtenues sont bien distinctes, et qu’elles présentent des régularités,
qui font penser à des fractals. Lors d’un stage de Master 2, T. Hénin a montré
que ces régularités sont expliquées par la présence de mots interdits dans les sé-
quences d’ADN, ces mots interdits étant liés à des faits bien connus en biologie des
séquences. Ainsi, la représentation par jeu du chaos est d’autant plus fractale que
le langage du génome considéré est proche d’un langage régulier [Hén06].
Fig. 4.1 – Gauche : schéma des mécanismes transformant un gène en une pro-
téine. Droite : les différents rôles des protéines (Sources : http ://www.hbcprotocols.com/,
http ://www.hon.ch/Dossier/Ageing/)
sur des réseaux de petite taille), d’autre discrètes, d’autres encore adoptent un point
de vue probabiliste, voire stochastique [DJ02]. Les questions posées sont variées :
citons entre autres l’atteignabilité, l’existence d’états stationnaires ou d’oscillations,
l’enchaînement de réactions pour produire une molécule [MRM+ 08].
simple de la stationnarité.
Contributions J’ai axé mes recherches sur des méthodes permettant des prédic-
tions robustes pour un réseau, dans des modèles assez peu renseignés et de grande
taille. Du fait de l’absence de connaissances sur la valeur numérique des paramètres,
les méthodes de prédiction vont s’appuyer sur la comparaison de différents états sta-
tionnaires. Nous allons cependant voir que cette restriction permet quand même de
mieux comprendre le fonctionnement d’un système, en particulier de détecter les
zones qui méritent une modélisation fine.
– Les premiers résultats portent sur des réseaux formalisés sous la forme de
modèles de réactions élémentaires. Nous verrons que l’étude des sous-déter-
minants de la jacobienne du système issu du modèle de réactions permet de
caractériser les effets de certains régulations.
– La seconde classe de résultats étudie la réponse d’un système à des paramètres
extérieurs. Les systèmes sont alors décrits seulement par leur graphe d’interac-
tion, aussi appelé graphe d’influence. Lorsqu’ils sont taille moyenne, on arrive
à comprendre le rôle de boucles positives dans le comportement du système.
– La troisième classe de système comprend des réseaux de grande échelle couplés
avec des données de puces à ADN. On entre alors dans une problématique de
correction de modèles avec des méthodes de diagnostic. Cette troisième classe
de modèle sera considérée dans le chapitre suivant.
Pour toutes ces questions, une question biologique reviendra régulièrement : il
s’agit de la modélisation des régulations du métabolisme des acides gras. Nous al-
lons en particulier présenter différents modèles pour ce système, avec un niveau
d’abstraction plus ou moins important. Avec ce fil conducteur, nous allons illus-
140
trer pourquoi la biologie systémique doit adopter une démarche progressive pour
comprendre un système dans ses différentes composantes : considérer d’abord des
données qualitatives avec un graphe d’influence, puis un modèle défini par des réac-
tions mais sans spécifier ses coefficients, pour enfin se concentrer sur l’analyses de
données numériques sur une toute petite partie du modèle. Chaque type d’abstrac-
tion correspond à une classe de questions et engendre des méthodes spécifiques de
résolution. Pour revenir à ce qui a été écrit au début de ce chapitre, on pourra ainsi
illustrer l’une des principales causes de la difficulté à poser des contours pour la
biologie systémique, à savoir, la complémentarité entre les différents degrés d’abs-
traction pour l’étude d’un même système et l’impossibilité d’en préférer une par
rapport aux autres.
Proposition 4.2.1 ((Roy. Soc. Inter, 2006) et (R., S., P., C.& L. en cours))
Soit Φ(X) = G(X) − Λ(X) un champ de vecteurs différentiable sur Rn+ tel que
– G est borné,
141
Tab. 4.1 – Un modèle différentiel abstrait pour la synthèse des acides gras et ses
régulations.
On obtient un résultat d’existence d’un état stationnaire pour ce modèle dès que
les hypothèses biologiques associées à la Proposition 4.2.1 sont vérifiées.
143
Gly
DegA Krebs
Kout
A T DegT
Oxi1
E4
E1 Syn Oxi2
Fin2
F1 F2
L E2 E3
Fin1
DegF2
DegF1
PP
Fig. 4.2 – Un modèle du métabolisme des acides gras et ses régulations, sous la
forme d’un graphe qui schématise un modèle différentiel défini par des réactions
élémentaires (voir 4.1). Les flèches en pointillés désignent des régulations génétiques.
Les flèches pleines désignent des flux métaboliques. Les flèches pointillées/traits
désignent des régulations énérgétiques impliquant l’ATP (T ).
∂Ri
Tab. 4.2 – Table des signes des dérivées ∂Xj pour le modèle de la régulation du
métabolisme des acides gras.
Ceci est en fait un résultat assez général : dans le cas des réseaux transcription-
nels, on est capable de déterminer les signes de la matrice jacobienne de Φ, et on
peut s’appuyer sur cette connaissance pour appliquer la règle de Thomas et en dé-
duire des conditions d’unicité d’états d’équilibre. Pour les réseaux qui incluent des
flux métaboliques, ce processus se passe généralement mal : les signes de la matrice
jacobienne ne sont plus constants, ou, lorsqu’ils le sont, ils introduisent des cycles
positifs superflus liés à la présence de réactions réversibles. Par contre, les signes
∂Ri
des dérivées des réactions élémentaires ∂X j
peuvent être identifiés à partir de la
littérature. La question que nous allons aborder maintenant est de savoir comment
on peut s’appuyer sur cette connaissance pour proposer des études d’unicité d’états
stationnaires et de prédictions sur les modèles.
Comme l’a fait remarqué C. Soulé, ce théorème est en fait une généralisation
de la règle de Thomas qui dit qu’une condition suffisante pour qu’un système ait
un unique état stationnaire est que son graphe d’interaction ne contienne pas de
145
boucle positive [Tho81, Sno98, Gou98, Sou03]. En effet, le graphe d’interaction d’un
système biologique est intimement lié à la matrice jacobienne du champ de vecteur
associé : ses arêtes correspondent aux coefficients non nuls de la matrice jacobienne ;
les signes du graphe sont donnés par les signes des coefficients de la matrice. Or, les
mineurs principaux de la matrice peuvent être exprimés comme sommes d’éléments
dont les signes sont déterminés par les cycles dans le graphe d’interaction. Si ces
cycles sont tous négatifs, on peut en déduire que tous les mineurs sont positifs et
appliquer le théorème de Gale-Nikaido (voir (R., S., P., C.& L. en cours)).
Cependant, ce résultat est trop restrictif pour la majeure partie des applica-
tions, en particulier dans le cas des réseaux métaboliques, du fait de la présence de
réactions réversibles, qui induisent des cycles positifs inactifs dans les réseaux.
Dans (R., S., P., C.& L. en cours), nous montrons comment il est possible d’ap-
pliquer itérativement le théorème de Gale Nikaido pour obtenir une condition pour
avoir un unique état stationnaire pour le système du métabolisme des lipides. Nous
allons détailler maintenant cet aspect.
Coefficients de contrôle Puisque les réactions dans le modèle sont des éléments
symboliques, au sujet desquels on connaît seulement les signes des variations par
rapport aux variables du modèle, on introduit des coefficients de contrôle pour
interpréter le rôle des réactions dans la dynamique du système.
Usuellement, les coefficients de contrôle et d’élasticité comparent l’importance
∂Ri
des variations de flux. Nous appelons ainsi coefficients de contrôle les dérivées | ∂Xj
|
qui sont non nulles dans la Table 4.2. Pour les réseaux métaboliques, ces coefficients
sont utilisés pour quantifier et étudier le rôle des enzymes régulatrices des flux
[CB04]. Ici, vu le rôle particulier joué par les métabolites que sont les PUFA et
l’ATP, on considère des coefficients de contrôles pour les variables F2 et T.
L’intérêt de cette approche est qu’elle est explicite. Finalement, on obtient une
condition d’unicité d’état stationnaire qui est donnée par une fonction polynomiale
des coefficients de contrôle.
Proposition 4.2.4 (R., S., P., C.& L. en cours) Il existe quatre fonctions
∂Ri
f, g, h, l, dont les variables sont les coefficients de contrôle | ∂Xj
|, et qui sont toutes
positives telles que le modèle abstrait du métabolisme des lipides admet un unique
état stationnaire dès que les conditions suivantes sont vérifiées pour tout X :
f (X)( ∂Fin1
∂T (X) −
∂Oxi1
∂T(X) ) + h(X) > l(X), (4.2)
|g(X)( ∂Fin2 ∂Oxi2 ∂Fin1
∂T (X) − ∂T (X))| <<< f (X)| ∂T (X) −
∂Oxi1
∂T (X)| (4.3)
αS < αO1 < n1 αG , n2 αO1 < n1 αO2 . (4.4)
Perspective : effectivité de la méthode Dans (R., S., P., C.& L. en cours), les
calculs pour obtenir la condition d’équilibre sont fait manuellement. Une question
naturelle est d’identifier automatiquement les boîtes sur lesquelles des réductions
sont possibles, puis d’opérer ces réductions avec des méthodes de calcul algébrique.
Nos premiers essais ont abouti à une explosion combinatoire lors du calcul des signes
de mineurs, même en utilisant des propriétés de stabilité de signes.
Dans une autre direction, Ovidiu Radulescu a proposé avec Vincent Noël de
faire appel à la notion de réaction pendante [GR07] pour classer les variables en
fonction de leurs effets, ce qui permet de vérifier la condition de Gale-Nikaido sur
un plus petit sous-ensemble de déterminant. L’applicabilité de cette approche est
en cours d’étude actuellement.
Rôle des régulations génétiques Pour appréhender le rôle des régulations gé-
nétiques dans un modèle, on compare la valeur de son état stationnaire à celle
de l’état stationnaire du même modèle dans lequel les régulations génétiques sont
supposées constantes. L’état stationnaire de ce deuxième modèle est en fait l’état
quasi-stationnaire du modèle général. La réduction des variables génétiques per-
met d’intégrer au niveau métabolique l’effet des régulations génétiques. Les deux
modèles réduits sont montrés dans la figure 4.3.
On peut aller plus loin que cette étude graphique. En considérant les expressions
des flux après réduction, on montre dans (R., S., P., C.& L. en cours) que la valeur
à l’état quasi-stationnaire de dGdT
est strictement supérieure à sa valeur à l’état
stationnaire.
Biologiquement, on interprète cette relation algébrique comme suit : un des rôles
des régulations génétiques est de renforcer l’effet tampon sur la quantité d’ATP :
les variations d’ATP pour une variation fixée de nutriment sont moins importantes
quand les régulations génétiques sont présentes.
Avec des comparaisons similaires entre les états quasi-stationnaires et station-
naires, on prédit aussi que les courbes qui représentent la concentration des PUFA
pendant le jeûne devraient montrer un pic : l’augmentation de la concentration des
PUFA est plus importante à court terme qu’à long terme.
Ainsi, avec un modèle extrêmement abstrait et non paramétré, une étude fine des
signes de la matrice de dérivation permet d’obtenir des informations non triviales
sur le comportement dynamique du modèle, en particulier de comparer les états
quasi-stationnaires et stationnaires.
148
G
−
G
−
Gly
Gly
DegA Krebs −
DegA Krebs − A T DegT
Kout
+
A T DegT
Kout −
+ + Oxi1
− −
Oxi1 + − Oxi2 + −
Syn +
− −
+ − Oxi2 + − Fin2
Syn F1 F2
Fin2 Fin1
F1 F2
Fin1
DegF2
DegF1
DegF2
DegF1
Cette relation signifie qu’une mutation des PPAR diminue l’effet tampon sur la
quantité de PUFA : l’augmentation de la concentration des PUFA pendant le jeûne
est plus important dans les cellules mutée en PPAR que dans les cellules sauvages.
Ceci est en accord avec des observations de [BLC+ 04, LCL+ 04].
4.2.4 Discussion
Avec ces travaux, nous avons ainsi pu montrer qu’un modèle extrêmement abs-
trait reproduit le principal comportement connu du métabolisme, c’est-à-dire le
passage d’un régime de synthèse à un régime d’oxydation qui stabilise la quantité
d’énergie en remplaçant les apports de nourriture par des réserves. A des échelles de
temps courtes, ce passage est assuré par des contrôles métaboliques. A des échelles
de temps longues, l’effet de régulation des PUFA renforce le contrôle par les facteurs
de transcription LXR et PPAR.
149
Limites Les limites du modèle sont bien entendu données par son degré d’abs-
traction. En particulier, les données de [LCL+ 04] montrent que les PUFA ne se
comportent pas tous de la même manière pendant un jeûne chez des souris dans
lesquelles PPAR a été muté : en particulier, la concentration de l’acide linoléique
(PUFA avec un petit nombre de carbones) est amplifiée, tandis que la concentra-
tion des acides gras avec un grand nombre de carbones devient quasiment nulle.
Cette observation sous-entend que la désaturation qui permet de passer des PUFA
à courtes chaînes aux PUFA à longues chaînes doit être mieux comprise, ce que nous
allons faire dans la section suivante en nous plaçant à un autre niveau d’abstraction.
Fig. 4.4 – Gauche : Quelques interactions chez la bactérie Echerischia coli : les
sommets sous forme de cercles représentent des protéines, les sommets sous forme
de cercle plein sont des complexes protéiques, les rectangles représentent des gènes,
c’est-à-dire des portions d’une séquence d’ADN.
Droite : les relations entre les molécules permettent de créer un graphe d’influence
dont les flèches représentent des actions positives (+) ou négatives (–).
151
EXT
PPAR [+]
FADS1 [0]
PUFA [+]
LXRa
SREBPa
FADS2 [0] FAS [-] ACL [+] ACC [-] SCD1 [-]
Fig. 4.5 – Graphe d’influence réduit pour les régulations du métabolisme des acides
gras. Les boucles d’auto-régulation négatives sont omises. Les flèches qui se ter-
minent par − > signifient que l’interaction est positive tandis que les flèches qui
se terminent par −| correspondent à des interactions négatives. Le symbole Ext
signifie que les produits cibles sont régulés par des éléments qui ne sont pas intégrés
au graphe. Les signes placés entre crochets correspondent aux variations d’ARN
observées pendant un jeûne.
publiés dans (Biosystems, 2006) et (Roy. Soc. Inter, 2006), et nous allons maintenant
en détailler les principaux résultats.
in
– La notation k G désigne l’ensemble des sommets qui se trouvent sur la fron-
tière de G (supposés connectés à un sommet extérieur). L’ensemble PG̊ ras-
154
semble les chemins inclus dans G qui partent de la frontière et n’y reviennent
pas.
∂Fk
– aj i désigne le produit des coefficients d’interaction ∂Xl
parcourus en suivant
le chemin de j vers i. l(j− > i) désigne la longueur du chemin de j vers i.
˚
– C̊j i = (−1)lk(j) i +1 ∆
˚
∆
désigne le module du chemin k(j) i où k(j) ∈
k(j) i
˚ k(j) i
G̊ est le successeur de j sur le chemin considéré aj i . Les quantités ∆
sont les mineurs du jacobien obtenu en supprimant les lignes et les colonnes
qui correspondant aux sommets parcourus sur le chemin j i.
˚
∆
– Si k(j) = i, on pose alors C̊j i = C̊i = − ∆
˚ i
L’intérêt de cette approche réside dans la détermination des signes des modules
Ci et C̊j i . En effet, comme nous l’avons mentionné et utilisé en appliquant le
théorème de Gale-Nikaido, les mineurs d’une matrice se décomposent en produits
dont les signes sont liés au nombre d’éléments dans les partitions en cycles disjoints
du graphe d’influence :
P |L|
L∈L(G) (−1) lp(L)
Cj i = P |L|
(4.6)
L∈L(Gj i ) (−1) lp(L)
P |L|
L∈L(G) (−1) lp(L)
Ci = P |L|
, (4.7)
L∈L(Gi ) (−1) lp(L)
Il faut alors modifier l’équation 4.8 en y ajoutant un saut fini (voir discussion dans
(Roy. Soc. Inter, 2006) pour éclairer la question de la robustesse et des conditions
de changement d’états.).
Si Li croît en fonction de Le, on obtient une contrainte non triviale sur les
différentes contribution des boucles du système à son fonctionnement :
X3 X3
∂XLi ˜ 1+ ) < 1 − ˜ i− ) − lp(l
˜ 2+ )lp(l
˜ 4− ) + lp(l
˜ 1+ )lp(l
˜ 3− ).
> 0 ssi lp(l lp(l
∂Le i=1 i=1
L’intensité du flux de lactose entrant sera alors moins importante que chez la bac-
térie sauvage. Si l’inégalité inverse est vraie, le flux de lactose augmentera.
157
Des boucles et des chemins... Pour cela, on considère les boucles du modèle
donné dans la Figure 4.5.
l1− = {P U F A, SCAP, SREBP a, F ADS2, P U F A},
l2− = {P U F A, SREBP a, F ADS2, P U F A},
l3− = {P U F A, LXRa, SREBP, SREBP a, F ADS2, P U F A},
l4− = {P U F A, F ADS2, P U F A},
l+ = {P U F A, P P ARa, F ADS2, P U F A}.
On considère aussi des chemins qui passent par les produits P U F A, F ADS2 et LXR :
p = {P U F A, LXR − a, SREBP },
p′ = {LXR, LXR − a, SREBP },
p1 = {P U F A, F ADS2},
p2 = {P U F A, SCAP, SREBP a, F ADS2},
p3 = {F ADS2, P U F A},
p4 = {P U F A, LXRa, SREBP, SREBP a, F ADS2},
p5 = {LXR, LXRa, SREBP, SREBP a, F ADS2},
p6 = {P P AR, P P ARa, F ADS2},
p7 = {P U F A, P P ARa, F ADS2},
p8 = {P U F A, SREBP a, F ADS2},
p9 = {P P AR, P P ARa, F ADS2, P U F A},
p10 = {LXR, LXRa, SREBP, SREBP a, F ADS2, P U F A}.
Dans ces équations, les quantités ãp sont obtenues comme des produits des
éléments de la matrice jacobienne qui correspondent aux arêtes parcourues par le
chemin p.
L’équation (4.10) permet de mieux comprendre le rôle de la régulation duale
de F ADS1 et F ADS2 par P P AR et SREBP . En effet, la boucle positive l+ qui
158
Modèle abstrait des entrées des acides gras L’approche adoptée a consisté
à partir d’un modèle volontairement abstrait pour les mécanismes actifs pendant le
jeûne. Pour les souris mutées pendant le jeûne, seule la bêta-oxydation est active. De
plus, les désaturations pour l’obtention des PUFA sont inactives, puisqu’elles sont
régulées par FADS1 et FADS2 qui sont elles-mêmes régulées par PPARα et SREBP
(or PPARα n’est pas présent chez les souris mutées et l’activité de SREBP décroît
pendant le jeûne). Le modèle abstrait qui a été considéré contient donc simplement
– une entrée des acides gras dans le foie à partir du tissus adipeux,
– des bêta-oxydations,
– différentes transformations métaboliques entre les acides gras (sauf les désa-
turations qui sont inactivées).
La question principale était de savoir si ce modèle différentiel extrêmement gé-
nérique pouvait se coupler avec les données, les paramètres pour le taux d’entrée
159
Régulation des désaturases Les données pour les souris mutées montrent que
la production de l’acide gras C22 :6ω3 par désaturation du C18 :3ω3 est active
chez ces espèces, avec un taux d’accumulation constant. Or, si les désaturations
étaient inactives dans le modèle, on devrait observer une diminution de la production
de C22 :6ω3 chez les souris mutées. On aboutit ici à une contradiction puisque
les données indiquent que l’activité de FADS1 et FADS2 est non nulle chez les
souris mutées pendant le jeûne, ce qui suggère fortement l’existence d’un régulateur
additionnel pour ces deux protéines.
Pour vérifier cette hypothèse, nos collaborateurs à l’INRA (Pascal Martin et
Hervé Guillou, Toulouse) ont procédé à des mesures additionnelles (PCR quantita-
tive) sur les ARNs de FADS1 et FADS2. Comme nous l’avions prédit, les concen-
trations d’ARN sont non nulles, et il existe donc sans doute un régulateur inconnu
aux désaturases.
D’un point de vue méthodologique, ce résultat illustre l’importance du niveau
de modélisation et du choix de l’expérimentation pour obtenir une conclusion sur
le comportement d’un système. Dans la section précédente, nous avions expliqué
que des données de jeûne chez des souris sauvages ne suffisaient pas pour conclure à
l’existence de ce régulateur inconnu pour FADS1 et FADS2, à cause de la présence de
boucles de régulations positives dans le système qui faussent les analyses intuitives
du comportement du système. Ici, l’expérimentation s’est faite chez des souris mu-
tées, et la construction d’un modèle qui prend en compte toutes les transformations
entre les acides gras a permis de conclure positivement.
4.4 Conclusion
Dans ce chapitre, nous avons donc illustré certaines spécificités de la modélisa-
tion de systèmes biologiques au sujet desquels l’obtention de paramètres ne peut
être réalisée que sur une très petite portion.
Les questions principales qui se sont posées ont été
– Une étude globale de l’unicité des états stationnaires du système.
160
De la dynamique à l’aide au
raisonnement par l’analyse
de contraintes
Dans le chapitre précédent, nous avons montré comment des approches algé-
briques associées à différents niveaux d’abstraction de modèles permettent de mieux
comprendre le rôle de certains éléments d’un réseau. Dans ce chapitre, nous allons
nous intéresser à l’automatisation des raisonnements pour étudier un réseau. Il
va donc s’agir d’identifier différentes questions fondamentales du point de vue de
l’expérimentateur, et d’apporter un cadre de réponse générique à ces questions en
s’appuyant le théorème 4.3.1 qui décrit la réponse linéaire d’un système.
161
162
que pour une très petite partie du système. La question qui se pose est donc d’aider
le biologiste à identifier, au sein de l’ensemble des molécules qui sont actives dans
son système, un tout petit nombre de produits sur lesquels une modélisation fine
pourra être appliquée.
Ce domaine ne fait a priori plus partie de l’étude de systèmes dynamiques. Il
s’agit de travailler à partir des observations et des connaissances sur un système pour
suggérer l’existence d’interactions que des expérimentations précises permettront
de valider. Cependant, puisqu’on recherche des régulateurs à partir d’observations
sur un système, les systèmes dynamiques offrent un cadre utile à la production
d’hypothèses.
Diagnostic Les réseaux grande échelle qui apparaissent actuellement sont fina-
lement une compilation d’interactions déduites de différentes méthodes et expéri-
mentations sous différentes conditions. Ainsi, les différentes sources utilisées pour
construire ces réseaux introduisent des erreurs, ce qui rend les biologistes dubita-
tifs sur les études faites sur ces systèmes. Depuis quelques années, différents au-
teurs mettent ainsi en avant le besoin de méthodes pour concilier différentes don-
nées hétérogènes, repérer les incohérences pour raffiner et améliorer les modèles
[IGH01, Pal00, Kit02b]. L’objectif est alors double :
– Vérifier que le modèle est cohérent avec les observations disponibles, et sinon,
proposer des corrections.
– Proposer des prédictions pour le comportement du système. Ces prédictions
peuvent ensuite être validées par la littérature. Elles peuvent aussi mener à la
proposition d’expérimentation, dans une boucle qui alimente le modèle avec
de nouvelles données pouvant potentiellement l’invalider à nouveau.
Pour répondre à ces deux questions, différentes méthodes ont été proposées. Elles
diffèrent par le type de règles sur lesquelles s’appuient la notion de cohérence ou les
prédictions. Cependant, on retrouve dans la plupart une règle implicite, appelée règle
causale, qui affirme que la modification de l’expression d’une protéine lorsque un
gène est supprimé ou sur-exprimé implique qu’une régulation (au moins indirecte)
existe entre le gène manipulé et la protéine observée [DWFS99]. Cette règle a ainsi
été utilisée pour procéder à des test globaux de compatibilité [GRRL+ 03], pour vé-
rifier la cohérence de systèmes avec des raisonnements logiques [BSPL03, JDSZ05],
pour suggérer des voies de régulations actives en s’appuyant sur les connaissances
d’interaction protéines-protéines [YIJ04, YMM+ 05, Ide04] ou pour analyser la co-
hérence de données d’activités des voies métaboliques [HLPP06].
et la prédiction [HLPP06] mais peuvent de plus être appliquées sur des réseaux de
taille bien plus grande.
Nous avons ensuite cherché à étendre le cadre d’application de ces systèmes de
contraintes, en particulier à la recherche du mode de régulation (activation ou inhi-
bition) des facteurs de transcription. Nous travaillons maintenant sur l’élaboration
de plans expérimentaux.
Ces résultats sont vraiment le fruit de la complémentarité entre divers chercheurs
de cultures différentes. Ma propre contribution a porté sur l’identification des ques-
tions qui pouvaient se poser en fonction des connaissances et des données disponibles
sur un réseau et son comportement. Nous allons donc maintenant détailler les ré-
sultats rapidement mentionnés ici en insistant sur le processus de formalisation des
questions sur un système et des approches de résolution.
Règle intuitive Nous avons travaillé sur les raisonnements intuitifs des biolo-
gistes et cherché à les formaliser. Après une lecture approfondie de la littérature et
de nombreuses discussions avec des biologistes, il nous est apparu que les raison-
nements utilisés implicitement par les biologistes pour conclure à l’invalidité d’un
modèle (et donc à l’existence de régulations additionnelles) ou faire des prédictions
étaient basées sur une simple règle causale très intuitive : la variation d’un élément
doit être qualitativement expliquée par la variation d’au moins un prédécesseur dans
le graphe d’influence.
Un exemple est donné dans la figure 5.1, où A et B sont deux protéines qui
activent la transcription de C. Plusieurs cas peuvent se produire lors d’un stress
environnemental :
– Si la concentration de A et B augmentent lors du stress, alors C doit néces-
sairement augmenter. Ou plutôt il ne peut pas diminuer...
– En particulier, si A et B augmentent et qu’une observation établit que C
diminue simultanément, la règle de cohérence n’est pas respectée et on doit
conclure que soit les observations sont erronées, soit il manque une interaction
dans le réseau. Dans tous les cas, nous détectons un conflit dans le réseau.
– Si la concentration de A augmente et celle de B diminue, alors C peut aussi
bien augmenter que diminuer, et on ne peut rien conclure.
ne varient pas pendant un jeûne peut être expliqué par des influences indirectes
dans le réseau, alors qu’on s’attend intuitivement à l’existence d’une régulation
additionnelle. Dans ce cas là, d’autres expérimentations appuient la thèse de la
régulation additionnelle, mais cet exemple est intéressant pour illustrer les erreurs
de raisonnement qu’on peut faire si on ne formalise pas les raisonnements utilisées
et les hypothèses sous-jacentes.
Ainsi, les modèles causaux ont été utilisés puis abandonnés dans les années
1990 pour modéliser la dynamique de réseaux de régulation, parce que non adaptés
à un cadre dynamique. Nous avons souhaité reprendre ces modèles causaux dans
un cadre plus restreint. En effet, même si les modèles causaux ne sont pas adaptés
pour étudier la dynamique des réseaux biologiques, nous avons cherché à savoir si ces
modèles peuvent être utilisés dans un cadre de déplacements d’états stationnaires.
On ne cherche plus alors à décrire l’état d’un molécule au moment n + 1 en fonction
de son état au temps n, mais à poser une contrainte globale sur les variations entre
deux états stationnaires. Nous allons expliquer maintenant pourquoi que cette règle
est vraie sous des conditions raisonnables d’un point de vue biologique.
Alors les signes des variations entre deux états stationnaires consécutifs à un stress
environnemental vérifient la contrainte suivante :
X
∂FX(i)
signe(∆X(i) ) ≃ signe × signe(∆X(k) ).
∂X(k)
k6=i,k→i
Algèbre de signes Pour comprendre ces équations, il faut réaliser que les élé-
ments signe(∆X(i) ) ne sont pas des réels mais doivent plutôt être lus dans l’algèbre
de signes. Cette algèbre est définie par l’ensemble {+, –, ?, 0}. Le symbole + désigne
les variations positives, – désigne les variations négatives et 0 désigne les variations
nulles. Le symbole ? désigne les variations sur lesquelles on n’a pas d’information
précise.
Sur cette algèbre de signes, on définit des opérations d’addition et de multipli-
cation ainsi qu’une relation de compatibilité ≃. On peut voir cette algèbre comme
un codage des relations ensemblistes sur R, R+ , R− et {0}. Cette algèbre de signe
a été introduite dans les années 80 pour étudier des questions de raisonnements
qualitatifs à partir de règles causales ; le point de vue était plutôt dynamique que
statique [Kui84, dKB84, dKB82].
+ + – ? 0 × + – ? 0 ≈ + – ? 0
+ + ? ? + + + – ? 0 + V F V V
– ? – ? – – – + ? 0 – F V V V
? ? ? ? ? ? ? ? ? 0 ? V V V V
0 + – ? 0 0 0 0 0 0 0 V V V V
Validité pour des modèles non différentiels ? Dans (Biosystems, 2006), nous
avons étudié la validité de ces contraintes en supposant que les systèmes étaient régis
par des modèles différentiels. Cependant, cette hypothèse peut s’étendre. Ainsi, en
collaboration avec A. Richard, nous avons travaillé sur la validité des contraintes
dans le cadre des modèles logiques multivalués. Là encore, cette règle s’avère assez
générale [Veb07].
Contraintes entre les variables Jusqu’à maintenant, nous n’avons fait que
transcrire la connaissance et les observations, mais nous n’avons pas relié les va-
riables entre elles. Pour cela, nous utilisons les règles décrites dans la section pré-
cédente. En fonction du type d’interaction sur la molécule Mj et du type d’expéri-
(l)
mentation, on introduit une contrainte sur chaque variable xj , qui fait intervenir
171
(l)
les variables xi pour lesquels si,j est non nul ou inconnu.
Dans le cas de l’opéron-lactose, on obtient le système de contraintes suivant.
LacI ≈ −A
(1)
A ≈ LacZ (2)
LacZ ≈ cAM P − LacI (3)
Li ≈ Le + LacY − LacZ (4)
G ≈ Li + LacZ (5)
cAM P ≈ −G (6)
LacY ≈ cAM P − LacI (7)
Solution Une solution dans {+, –} d’un système de contraintes associé à un mo-
dèle biologique est une affection de toutes les variables du système avec les valeurs
+ et – qui satisfait simultanément toutes les équations du système.
Une solution à valeur dans {+, –, 0} introduit la valeur 0 pour les variables et
permet de distinguer des sous-ensembles de variables pertinents.
Ces solutions correspondent aux différents observations qu’il est possible d’obte-
nir avec un stress.
Pour le cas de l’opéron-lactose (voir Fig. 4.6), il est possible d’énumérer l’en-
semble des solutions du système dans {+, –}, décrites dans la Table 5.1. Il y a une
symétrie dans l’ensemble des solutions puisque le système est linéaire. On voit ici que
les contraintes associées au système restreignent fortement l’espace des possibilités,
puisqu’on passe de 256 jeux d’observations possibles à priori à 18 jeux réellement
admissibles.
Tab. 5.1 – Liste des 18 jeux expérimentaux (parmi les 28 =256 possibles) compatibles
avec le réseau modélisant l’opéron lactose.
De même, les observations sur la mise à jeûn des poulets décrites à Fig. 4.5 sont
cohérentes avec le réseau. On retrouve ainsi de manière automatique que la variation
nulle des désaturases FADS1 et FADS2 n’est absolument pas une contradiction du
système, comme nous l’avons déjà discuté à la section 4.3.4.
(l)
Prédictions On dit que la variable si,j ou xj est une prédiction du système
lorsque la valeur de cette variable est invariante dans toutes les solutions du système
de contraintes.
Par exemple, si nous revenons sur le système de l’opéron-lactose, et si on ob-
serve que Le est sous-exprimé et LacZ est sur-exprimé, on peut déduire de la liste
des solutions que, nécessairement, LacI sera sous-exprimé et A sera sur-exprimé,
puisque toutes les solutions telles que Le = – et LacZ = + sont aussi telles que
LacI = – et A = +.
pas en compte les contraintes successives apportées par les sommets éloignés d’un
nœud). L’apport du point de vue global est d’abord de contraindre plus fortement
le système, et surtout de localiser les modules à corriger (quelle que soit leur taille)
pour orienter le modélisateur dans sa construction de réseau.
Fig. 5.2 – Deux réseaux qui sont cohérents respectivement seulement par chemin
et pour les équations qualitatives.
Énumérer les solutions Une première stratégie pour identifier des diagnostics et
répondre à la question des prédictions consiste à explorer l’ensemble des solutions.
Pour cela, il faut résoudre deux questions distinctes.
1. Réduire le système de contraintes à un système de taille plus petite mais équi-
valent en terme de cohérence. Plus précisément, un certain nombre d’équations
ne contraignent en fait pas le système. Il s’agit typiquement des successions
de transcriptions de gènes non observés. On obtient alors des équations de la
forme xi+1 = xi qui n’apportent rien à la cohérence du système.
Ainsi, nous montrons dans (Complex Us, 2005) que la question de la cohérence
globale du système est équivalente à la cohérence du système construit pour le
graphe d’influence qui correspond à l’image inverse des états observés et des
cycles du système (voir aussi la discussion dans la thèse de P. Veber [Veb07]).
Sur les réseaux transcriptionnels, cette opération de réduction diminue consi-
dérablement la taille du système de contraintes, et permet d’envisager une
étude de l’ensemble des solutions.
2. Représenter efficacement l’espace des solutions. Le système étant réduit à un
système de taille plus raisonnable équivalent pour la question de la cohérence,
il devient possible de représenter l’espace des solutions sous la forme d’un
arbre de décision binaire (BDD pour Binary Decision Diagram). Il s’agit d’une
structure de données dans laquelle toute formule logique (booléenne) peut
être représentée par un graphe orienté acyclique avec une racine consistant
en nœuds de décisions, et deux nœuds terminaux pour les valeurs 0 et 1.
Un chemin de la racine au nœud 1-terminal représente un modèle admissible
pour la formule considérée. Ces BDD sont très utilisés par les programmes de
conception assistée par ordinateur, pour générer des circuits (synthèse logique)
et en vérification de modèles [Bry92].
Concrètement, Michel Le Borgne, Philippe Veber et Carito Guziolowski ont
ainsi proposé une implémentation sous la forme de BDD et des algorithmes
efficaces pour les parcourir, qui permettent de rechercher des diagnostics et
procéder à des prédictions pour les graphes d’influence. Une suite logicielle
(Pyquali et Bioquali) a été développée à ce propos [LBV07], et une interface
web a été développée (http ://www.irisa.fr/symbiose/bioquali) ainsi qu’un
plugin pour la suite logicielle Cytoscape dédiée à la représentation de réseaux
biologiques [SMO+ 03].
Rechercher au moins une solution Une autre stratégie consiste non pas à
étudier l’ensemble des solutions mais à rechercher s’il existe au moins une solution
à différents problèmes. La question de la cohérence d’un système entre naturellement
dans ce cadre. La recherche des prédictions est aussi abordable en considérant la
recherche des éléments qui ne sont pas invariants (pour chaque sommet, existe-t-il
deux solutions pour le système qui prennent des valeurs opposées ?). On entre ici
dans le cadre de la résolution de contraintes.
176
Complémentarité Nous avons ainsi à notre disposition deux approches bien dif-
férentes mais tout aussi efficaces pour résoudre les questions biologiques qui ont
été identifiées en début de chapitre. On pourra se demander pourquoi les conserver
toutes les deux : en fait, ces approches sont complémentaires, et doivent être étu-
diées en parallèle pour pouvoir répondre à des questions plus précises que celle du
diagnostic et des prédictions.
Ces questions seront abordées plus en détail à la fin de ce chapitre, mais nous
pouvons déjà insister sur les apports des deux méthodes :
– La spécificité du parcours de l’ensemble des solutions via les BDD est qu’il
permet d’énumérer les solutions à des questions variées, même s’il ne s’agit
pas d’invariants. Ceci nous permettra en particulier d’assouplir les contraintes
sur les prédictions en recherchant non pas des variables qui sont invariantes
pour l’ensemble des solutions du système, mais des variables dont la valeur est
identique pour un pourcentage assez élevé de solutions. Ceci est impraticable
par une approche directe la programmation par ensembles réponses.
– La spécificité de la programmation par ensembles réponses est de pouvoir
interroger des systèmes de contraintes de très grande taille sans les réduire
préalablement, et d’agrandir le spectre de questions posées. En particulier,
la notion de détermination de plans expérimentaux et la recherche de causes
communes à un évènement semblent abordables en ASP mais pas avec des
algorithmes de parcours de BDD. Nous en rediscuterons plus précisément
dans la dernière section du chapitre.
Schéma général Le processus que nous mettons en place pour analyser un réseau
est illustré dans la figure 5.3 :
177
−→
−→
distingue les ARN des protéines actives, et est présenté Fig. 5.6.
Avec ce deuxième graphe, les incohérences ont été résolues.
Prédictions Nous avons ensuite procédé à des calculs de prédictions sur le réseau.
Nous avons ainsi obtenu 20 prédictions sur des sommets non-observés. En particu-
lier, les prédictions ont porté principalement sur des protéines actives. À partir d’une
nouvelle analyse des données, nous avons orienté nos recherches sur des protéines
actives dont la variation est prédite mais pour lesquelles les ARN ne varient pas
significativement. Selon notre interprétation, cela signifie qu’un phénomène post-
transcriptionnel renverse l’effet naturel de la transcription sur cette protéine. Des
expérimentations sont programmées à l’automne 2008 pour rechercher la pertinence
des prédictions.
tions trouvées sont des optimums globaux plutôt que locaux. Dans les faits, comme
nous l’avons déjà mentionné, les différentes approches probabilistes de reconstruc-
tion de réseaux ne coïncident pas sur les organismes modèles ; elles coïncident encore
moins pour la question de l’inférence des signes.
La difficulté est accrue pour l’inférence de signes en comparaison avec la problé-
matique de la reconstruction de modèle dans la mesure où les modèles prédits sont
difficilement validables. À cause des jeux de données disponibles, l’organisme mo-
dèle habituellement étudié dans ce cadre est la levure S. cerevisiae, mais il n’existe
pas, comme pour E. coli, de base qui référence les différentes interactions entre les
molécules de cet organisme dans la littérature. Un travail considérable a été fait
pour élaborer la baseSGD intégrant les données génétiques sur la levure [HBC+ 01].
Cependant les relations protéine-protéine y sont fournies sans détailler les influences
transcriptionnelles et en particulier leur sens. Le seul travail de référencement des
publications concernant les interactions chez la levure que nous connaissons ac-
tuellement a été fait dans [GBBK02]. Malheureusement, les informations proposées
alors ne sont pas disponibles sous la forme de base de données ni actualisées.
On se retrouve donc dans une situation où la communauté propose des méthodes
pour inférer les réseaux de régulation mais n’a pas la possibilité de valider ses travaux
par une référence commune.
non pas global. L’approche par contrainte permet donc d’identifier la partie qui
devrait faire consensus entre les différentes approches probabilistes.
Fig. 5.7 – Les différents types de modules incohérents quand au mode de régulation
retrouvés chez des réseaux transcriptionnels
Fig. 5.8 – Les modules du réseau transcriptionnel de E. coli pour lesquels soit une
interaction est manquante, soit une protéine peut agir à la fois comme activateur
et inhibiteur de sa cible en fonction du contexte expérimental. Les flèches pleines
représentent des modules de Type 2, les flèches pointillées des modules de Type 1.
187
sur cette espèce. La plupart de ces réseaux ont été construits à partir d’un tra-
vail expérimental phénoménal qui a consisté à rechercher par immuno-précipitation
l’ensemble des protéines qui se fixent sur la plupart des facteurs de transcrip-
tions connus chez la levure [LRR+ 02]. Ces données ont permis à différents auteurs
de proposer des réseaux transcriptionnels orientés mais non-signés pour la levure
[HGL+ 04, MWG+ 06, SSR+ 03, NTIM05, BBAIdB07]. À partir de ces sources, nous
avons sélectionné différents réseaux :
– Le premier est le cœur du réseau directement déduit des données chIP-chip
de [LRR+ 02], et déjà introduit dans [KPST03]. Il contient 31 nœuds et 52
interactions.
– Le deuxième réseau contient toutes les interactions entre les facteurs de trans-
cription testés dans l’étude de [LRR+ 02]. Dans ce réseau, les interactions sur
les protéines qui ne sont pas des facteurs de transcription sont omises du
réseau.
– Le troisième est le réseau étendu à l’ensemble des facteurs de transcription de
la levure, publié dans [MWG+ 06].
– Le dernier réseau considéré, grande-échelle, consiste en l’ensemble des régu-
lations obtenues par chIP-chip dans [LRR+ 02]. Il contient 2419 sommets et
4344 nœuds.
Concernant la phase de diagnostic, il faut constater que le nombre de modules
pour lesquels des interactions avec de multiples effets apparaissent est très important
pour l’ensemble des quatre réseaux considérés. Ces modules ainsi que nos prédictions
ont été listés et proposés à la communauté (voir le matériel supplémentaire de (BMC
bioinfo, 2008)). Nous espérons pouvoir travailler avec des expérimentateurs pour
prouver en particulier les phénomènes de régulations dépendante du contexte.
un taux de faux-positif de 2,5% (voir (BMC bioinfo, 2008) pour plus de précisions).
Ainsi, la redondance permet de faire des prédictions sur les signes des régulations
malgré l’incertitude des données et les incohérences contenues dans le réseau.
Fig. 5.9 – Signes inférés dans le réseau transcriptionnel de la levure proposé dans
[MWG+ 06]
d’optimisation [YMM+ 05, SSR+ 03] pour qu’ils prennent en compte ce type
de données plutôt que des données de perturbations génétiques.
– En fonction des réseaux, le taux d’inférence est compris entre 19% et 37%. Ce
taux est similaire au taux théorique pour une vingtaine d’expériences calculé
dans le cas de E. coli.
– Comme dans le cas de E. coli, l’opération de filtrage (prédictions obtenues
à partir de jeux expérimentaux différents) permet de diminuer significative-
ment le nombre de prédictions invalidées par les références bibliographiques
de [GBBK02], sans doute dues à des interactions manquantes.
0.35
fraction of inference
0.3
0.25
0.2
0.15
20 40 60 80 100 120 140 160 180 200
number of expression profiles
avons supprimé les signes des régulations et calculé la proportion de signes déduc-
tibles. Cette proportion dépend du nombre de jeux d’observations disponibles pour
procéder à l’inférence des signes. Les courbes obtenues montrent qu’il semble exis-
ter un taux maximal de signes de régulation inférables, qui semble proche de 40%.
Les trois cinquièmes restant du réseau ne sont pas inférables à partir de méthodes
causales (voir Fig 5.10).
Cependant, rien n’indique que le palier visible sur la courbe est effectivement
un maximum. En mêlant les diagrammes de décision, des notions d’élimination de
variables et une partition des contraintes, (voir l’algorithme 2 dans (BMC bioinfo,
2008)), P. Veber a montré que le pourcentage maximal de signes inférables dans le
réseau de E. coli à partir de données de stress expérimentaux est effectivement de
40.8%.
Nous pouvons également conclure que 30 expériences distinctes sont en moyenne
suffisantes pour inférer la moitié des signes inférables ; ceci sous-entend que multi-
plier les expérimentations au delà de quelques dizaines ne permet pas d’obtenir un
gain significatif dans la problématique de l’inférence des modes de régulation avec
notre approche.
pour laquelle les aspects dynamiques jouent peu : le graphe d’influence y ressemble
à un graphe acyclique. Sur cette partie du réseau, des analyses causales avec peu
d’expérimentations sont largement suffisantes pour comprendre la structure et le
fonctionnement du système ; la dynamique du système entre peu en jeu.
val(X1 , . . . Xp )
τ (X1 , . . . Xp ) = 1 − ,
2p
où val(X1 , . . . Xp ) désigne le nombre de valeurs de (X1 , . . . Xp ) dans {+, −}p qui
s’étendent en une solution globale du système de contraintes associé au réseau consi-
déré.
Nous nous sommes appuyés sur une observation là encore naïve : certains jeux de
données n’apportent en fait aucune information sur un système, dans la mesure où
toute variation de leurs composants peut s’étendre en une solution globale du sys-
tème qualitatif. Par exemple, en étudiant la Table 5.1, on constate que pour chaque
valeur du triplet (Le, G, A), il existe une valuation de (Li, LacY, LacZ, LacI, cAM P )
qui est solution du système associé à l’opéron lactose. Une observation du système
limitée aux nœuds (Le, G, A) ne peut donc pas mettre en défaut le modèle proposé.
Notons par ailleurs qu’il ne s’agit pas d’un cas isolé : il y a 56 possibilités d’observer
3 nœuds dans le graphe, et 22 d’entre elles ont un pouvoir de validation nul.
Inversement, parmi les huit valeurs possibles du triplet (LacI, A, LacZ), seuls
les jeux (+, −, −) et (−, +, +) s’étendent en une solution du système. Ainsi, ce jeu
196
de données s’avère très contraignant pour la validité du modèle. Parmi les groupes
de trois composants, il s’agit du jeu qui est le plus astreignant.
connaissances sur les régulations entre les gènes liés au métabolisme des acides gras.
Il s’agit de rassembler à la fois les connaissances des experts sur des protéines iden-
tifiées comme importantes (LXR, P P AR, SCD1, . . . ), et de les comparer aux in-
formations qui existent au sujet des gènes variant significativement dans les e-QTL,
disponibles soit dans la base PathwayCommons soit dans les services des sociétés In-
genuity et Biobase. À la fin de ce travail, nous aurons un ensemble de connaissances
dans lequel nous pourrons rechercher les origines du facteur d’engraissement.
décider quels sont les jeux d’expérimentations nécessaires peuvent être inté-
ressants.
201
202
[BF08] V Berthé and T Fernique. Brun expansions of stepped surfaces. preprint, 2008.
[BFH97] M Bestvina, M Feighn, and M Handel. Laminations, trees, and irreducible automorphisms
of free groups. GAFA, 7 :215–244, 1997.
[BFH00] M Bestvina, M Feighn, and M Handel. The Tits alternative for Out(Fn ), I : Dynamics of
exponentially growing automorphisms. Ann. Math., 151 :517–623, 2000.
[BFZ05] V Berthé, S Ferenczi, and LQ Zamboni. Interactions between dynamics, arithmetics and
combinatorics : the good, the bad, and the ugly. In Algebraic and topological dynamics,
volume 385 of Contemp. Math., pages 333–364. Amer. Math. Soc., Providence, RI, 2005.
[BG97] J Barrow-Green. Poincaré and the three body problem, volume 11 of History of Mathe-
matics. American Mathematical Society, Providence, RI, 1997.
[BK05] M Barge and J Kwapisz. Elements of the theory of unimodular Pisot substitutions with an
application to β-shifts. In Algebraic and topological dynamics, volume 385 of Contemp.
Math., pages 89–99. Amer. Math. Soc., 2005.
[BK06] M Barge and J Kwapisz. Geometric theory of unimodular Pisot substitutions. Amer. J.
Math., 128(5) :1219–1282, 2006.
[BKS91] T (ed.) Bedford, M (ed.) Keane, and C (ed.) Series. Ergodic theory, symbolic dynamics,
and hyperbolic spaces. Lectures given at the workshop "Hyperbolic geometry and ergodic
theory", held at the International Centre for Theoretical Physics in Trieste, Italy, 17-28
April, 1989. Oxford University Press, 1991.
[Bla] F Blanchard. Topological chaos : what may this mean ? arXiv :0805.0232v1.
[Bla89] F Blanchard. β-expansions and symbolic dynamics. Theoret. Comput. Sci., 65 :131–141,
1989.
[BLC+ 04] S Barnouin, F Lassere, M Cantiello, H Guillou, T Pineau, and P Martin. A kinetic view
of coordinate modulations of gene expresion and metabolism in wild-type and pparα-/-
mice during fasting. In Conference of the Paul Hamel Institute, Monaco, 2004.
[BM86] A Bertrand-Mathis. Développement en base θ ; répartition modulo un de la suite
(xθ n )n≥0 ; langages codés et θ-shift. Bull. Soc. Math. France, 114(3) :271–323, 1986.
[BMO+ 01] CH Bryant, SH Muggleton, SG Olivier, DB Kell, P Reiser, and RD King. Combining
inductive logic programming, active learning and robotics to discover the function of
genes. Electronic Transaction in Artificial Intellingence, 5 :1–36, 2001.
[BMOH97] BM Bakker, PAM Michels, FR Opperdoes, and Westerhoof HV. Glycolysis in bloodstream
from trypanasoma brucei can be understood in terms of the kinetics of the glycotic en-
zymes. J. Biol. Chem., 272 :3207–3215, 1997.
[Bor09] E Borel. Les probabilités d´enombrables et leurs applications arithmétiques. Rend. Circ.
Mat. Palermo, 1909.
√
[Bor50] E Borel. Sur les chiffres décimaux de 2 et divers problèmes de probabilités en chaîne.
C. R. Acad. Sci. Paris, 230 :591–593, 1950.
[Bow75] R Bowen. Equilibrium states and the ergodic theory of Anosov diffeomorphisms.
Springer-Verlag, Berlin, 1975. Lecture Notes in Mathematics, Vol. 470.
[Bow78] R Bowen. Markov partitions are not smooth. Proc. Amer. Math. Soc., 71(1) :130–132,
1978.
[Boy96] DW Boyd. On beta expansions for Pisot numbers. Math. Comput., 65(214) :841–860,
1996.
[BP97] MP Béal and D Perrin. Symbolic dynamics and finite automata. In Grzegorz Rozenberg
and Arto Salomaa, editors, Handbook of Formal Languages, volume 2, pages 463–503.
Springer, 1997.
[BRdJ+ 05] G Batt, D Ropers, H de Jong, J Geiselmann, R Mateescu, M Page, and D Schneider. Va-
lidation of qualitative models of genetic regulatory networks by model checking : Analysis
of the nutritional stress response in escherichia coli. Bioinformatics, 21(Suppl 1) :i19–i28,
2005.
[Bre81] AJ Brentjes. Multidimensional continued fraction algorithms. Mathematisch Centrum,
Amsterdam, 1981.
[Bro96] A Broise. Transformations dilatantes de l’intervalle et théorèmes limites. Astérisque,
238 :1–109, 1996.
[Bry92] RE Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM
Comput. Surv., 24(3) :293–318, 1992.
[BSPL03] SD Bay, J ; Shrager, A Pohorille, and P Langley. Revising regulatory networks : from
expression data to linear causal models. Journal of Biomedical Informatics, 35(289-297),
2003.
204
[BT86] E Bombieri and JE Taylor. Which distributions of matter diffract ? An initial investiga-
tion. J. Physique, 47(7, Suppl. Colloq. C3) :C3–19–C3–28, 1986. International workshop
on aperiodic crystals (Les Houches, 1986).
[BV00] V Berthé and L Vuillon. Tilings and rotations on the torus : a two-dimensional generali-
zation of sturmian sequences. Discrete Math., 223 :27–53, 2000.
[BV03] F Boyer and A Viari. Ab initio reconstruction of metabolic pathways. Bioinformatics,
19(supp. 2), 2003.
[BYBW07] G Batt, B Yordanov, C Belta, and R Weiss. Robustness analysis and tuning of synthetic
gene networks. Bioinformatics, 23(18) :2415–2422, 2007.
[Cal80] AP Calderon. On an inverse boundary value problem. In Soc. Braziliera de Mathematica,
editor, Seminar on Numerical Analysis and its applications to Continuum Physics,
pages 65–73, Rio de Janeiro, 1980.
[Can03] V Canterini. Connectedness of geometric representation of substitutions of Pisot type.
Bull. Belg. Math. Soc. Simon Stevin, 10(1) :77–89, 2003.
[Caw91] E Cawley. Smooth Markov partitions and toral automorphisms. Ergodic Theory Dynam.
Systems, 11(4) :633–651, 1991.
[CB88] A Casson and S Bleiler. Automorphisms of surfaces after Nielsen and Thurston, vo-
lume 9 of London Mathematical Society Student Texts. Cambridge University Press,
Cambridge, 1988.
[CB04] A Cornish-Bowden. Fundamentals of Enzyme Kinetics (third edition). Portland Press,
Londres, 2004.
[CBJS05] A Cornish-Bowden, M Jamin, and V Saks. Cinétique enzymatique. EDP Sciences, 2005.
[CCCN+ 04] K Chen, L Calzone, A Csikasz-Nagy, FR Cross, B Novak, and JJ Tyson. Integrative
analysis of cell cycle control in budding yeast. Molecular Biology of the Cell, 15(8) :3841–
3862, 2004.
[CFLM06] R Coutinho, B Fernandez, R Lima, and A Meyroneinc. Discrete time piecewise affine
models of genetic regulatory networks. J. Math. Biol., 52(4) :524–570, 2006.
[CFS06] L Calzone, F Fages, and S Soliman. Biocham : An environment for modeling biological
systems and formalizing experimental knowledge. Bioinformatics, 22 :1805–1807, 2006.
[CFZ00] J Cassaigne, S Ferenczi, and LQ Zamboni. Imbalances in Arnoux-Rauzy sequences. Ann.
Inst. Fourier, 50(4) :1265–1276, 2000.
[CHL06] T Coulbois, A Hilion, and M Lustig. R-trees and laminations for free groups. Preprint,
2006.
[CKR+ 04] MW Covert, EM Knight, JL Reed, MJ Herrgard, and BO Palsson. Integrating high-
throughput and computational data elucidates bacterial networks. Nature, 429(6987) :92–
6, 2004.
[CL08] GR Conner and JW Lamoreaux. On the existence of universal covering spaces for metric
spaces and subsets of the euclidean plane. preprint, 2008.
[CM00] EB Curtis, , and JA Morrow. Inverse problems for electrical networks. World Scientific,
2000.
[CMPS93] D Crisp, W Moran, A Pollington, and P Shiue. Substitution invariant cutting sequences.
J. Théor. Nombres Bordeaux, 5(1) :123–137, 1993.
[Coa59] CL Coates. Flow-graph solutions of linear algebraic equations. IRE Trans. Circuit
Theory, CT-6 :170–187, 1959.
[Cob72] A Cobham. Uniform tag sequences. Math. Systems Theory, 6 :164–192, 1972.
[CP02] MW Covert and BO Palsson. Transcriptional regulation in constraints-based metabolic
models of escherichia coli. J biol chem, 277(31) :28058–28064, 2002.
[CRCD+ 04] N Chabrier-Rivier, M Chiaverini, V Danos, F Fages, and V Schächter. Modeling and
querying biomolecular interaction networks. Theor. Comput. Sci., 325(1) :25–44, 2004.
[CSR93] T Chevalier, T Schreiber, and J Ross. Toward a systematic determination of complex
reaction mechanisms. J. Phys. Chem., 97 :6776 – 6787, 1993.
[Dev86] RL Devaney. An introduction to chaotic dynamical systems. The Benjamin/Cummings
Publishing Co. Inc., Menlo Park, CA, 1986.
[DGV+ 99] PJ Deschavanne, A Giron, J Vilain, G Fagot, and B Fertil. Genomic signature : characte-
rization and classification of species assessed by chaos game representation of sequences.
Molecular Biology and Evolution, 16 :1391–1399, 1999.
[DHS99] F Durand, B Host, and C Skau. Substitutional dynamical systems, Bratteli diagrams and
dimension groups. Ergodic Theory Dynam. Systems, 19(4) :953–993, 1999.
[DJ02] H De Jong. Modeling and simulation of genetic regulatory systems : A literature review.
Journal of Computational Biology, 9(1) :67–103, 2002.
205
[dJGHP03] H de Jong, J Geiselmann, Céline Hernandez, and Michel Page. Genetic network analyzer :
qualitative simulation of genetic regulatory networks. Bioinformatics, 19(3) :336–344,
2003.
[dJRCT05] H de Jong, D Ropers, C Chaouiya, and D Thieffry. Modélisation, analyse et simulation
de réseaux de régulation génique. Biofutur, 252(36-40), 2005.
[dKB82] J de Kleer and JS Brown. Foundations of envisioning. In Proceedings of the National
Conference of the American Association for Artificial Intelligence, 1982.
[dKB84] J de Kleer and JS Brown. A qualitative physics based on confluences. In Qualitative
Reasoning about Physical Systems. Elsevier Science Publishers, 1984.
[DKS96] K Dajani, C Kraaikamp, and B Solomyak. The natural extension of the β-transformation.
Acta Math. Hungar., 73(1-2) :97–109, 1996.
[DL04] V Danos and C Laneve. Formal molecular biology. Theoretical Computer Science,
325(1) :69 – 110, 2004.
[Dor88] JL Dormoy. Controlling qualitative resolution. In Proceedings of the seventh National
Conference on Artificial Intelligence, AAAI88’, Saint-Paul, Minn., 1988.
[DPLR72] E Dubois and R Paysan-Le Roux. Approximations simultanées dans un corps de séries
formelles. (Simultaneous approximation in a formal power series field). C. R. Acad. Sci.,
Paris, Sér. A , 274 : 437–440, 1972.
[DR04] O Delgrange and E Rivals. Star : an algorithm to search for tandem approximate repeats.
Bioinformatics, 20(16) :2812–20, 2004.
[DT93] JM Dumont and A Thomas. Digital sum moments and substitutions. Acta Arith., 64 :205–
225, 1993.
[DWFS99] P D’haeseleer, X Wen, S Fuhrman, and R Somogyi. Linear modeling of mrna expression
levels during cns development and injury. In Pacific Symposium on Biocomputing, pages
41–52, 1999.
[ECB98] R Eisenthal and A Cornish-Bowden. Propsects for antiparasitic drugs : the case of trypa-
nasoma brucei, the causative agent of african sleeping sickness. J. Biol. Chem, 272 :5500–
5505, 1998.
[EI05] H Ei and S Ito. Tilings from some non-irreducible, Pisot substitutions. Discrete Math.
Theor. Comput. Sci., 7(1) :81–121, 2005.
[EIR06] H Ei, S Ito, and H Rao. Atomic surfaces, tilings and coincidences II. reducible case. Ann.
Inst. Fourier, 56 :2285–2313, 2006.
[EK98] K Eda and K Kawamura. The fundamental groups of one-dimensional spaces. Topology
Appl., 87(3) :163–172, 1998.
[EP00] JS Edwards and BO Palsson. The escherichia coli mg1655 in silico metabolic genotype : its
definition, characteristics, and capabilities. Proc Natl Acad Sci U S A, 97(10) :5528–33,
May 2000.
[ES97] M Einsiedler and K Schmidt. Markov partitions and homoclinic points of algebraic Zd -
actions. Tr. Mat. Inst. Steklova, 216(Din. Sist. i Smezhnye Vopr.) :265–284, 1997.
[Far06a] E Farcot. Geometric properties of a class of piecewise affine biological network models.
J. Math. Biol., 52(3) :373–418, 2006.
[Far06b] E Farcot. Symbolic numeric analysis of attractors in randomly generated piecewise affine
models of gene networks. In ISSAC 2006, pages 79–86, New York, 2006. ACM.
[Fel97] D Fell. Understanding the Control of Metabolism. Portland Press, 1997.
[Fer05] T Fernique. Bidimensional sturmian sequences and substitutions. In DLT’05, volume
Lecture Notes in Computer Science 3572, pages 236–247, 2005.
[Fer08] T Fernique. Generation and recognition of digital planes using multi-dimensional conti-
nued fractions. In DGCI’08 : International Conference on Discrete Geometry for Com-
puter Imagery, 2008.
[FFIW06] DJ Feng, M Furukado, S Ito, and J Wu. Pisot substitutions and the Hausdorff dimension
of boundaries of atomic surfaces. Tsukuba J. Math., 30(1) :195–223, 2006.
[FHT+ 07] JJ Faith, B Hayete, JT Thaden, I Mogno, J Wierzbowski, and al,˙ Large-scale map-
ping and validation of Escherichia coli transcriptional regulation from a compendium of
expression profiles. PLoS Biol, 5(1) :e8, 2007.
[Fie02] O Fiehn. Metabolomics : the link between genotypes and phenotypes. Plant Molecular
Biology, 48(1-2) :155–171, 2002.
[FIKO96] T Fujita, S Ito, M Keane, and M Ohtsuki. On almost everywhere exponential convergence
of the modified Jacobi-Perron algorithm : A corrected proof. Ergodic Theory Dyn. Syst.,
16(6) :1345–1352, 1996.
206
[FMS+ 07] F Ferrazzi, P Magni, L Sacchi, A Nuzzo, U Petrovic, and R Bellazzi. Inferring gene
regulatory networks by integrating static and dynamic data. Int J Med Inform, Epub
2007 Sept 6, 2007.
[Fog02] N. Pytheas Fogg. Substitutions in dynamics, arithmetics and combinatorics, volume
1794 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002. Edited by V.
Berthé, S. Ferenczi, C. Mauduit and A. Siegel.
[FP54] E Frank and O Perron. Remark on a certain class of continued fractions. Proc. Am.
Math. Soc., 5 :270–283, 1954.
[Fri04] N Friedman. Inferring cellular networks using probabilistic graphical models. Science,
303 :799–805, 2004.
[FS92] C Frougny and B Solomyak. Finite beta-expansions. Ergodic Theory Dynamical Systems,
12 :45–82, 1992.
[FS08] F Fages and S Soliman. From reaction models to influence graphs and back : a theorem. In
Formal Methods in Systems Biology, Lectures Notes in Bio-Informatics, Springer-Verlag,
2008.
[GA97] D Giammaressi and Restivo A. Two-dimensional languages. Springer-Verlag, Berlin,
1997.
[GA04] R Ghoshn and C Andomlin. Symbolic reachable set computation of piecewise affine hybrid
automata and its application to biological modelling : Delta-notch protein signalling.
Systems Biology, 1(1) :170–183, 2004.
[GBBK02] N Guelzim, S Bottani, P Bourgine, and F Képès. Topological and causal structure of the
yeast transcriptional regulatory network. Nature Genetics, 31 :60–63, 2002.
[GBC+ 04] J Guespin, G Bernot, J-P Comet, A Mérieau, A Richard, C Hulen, and B Polack. Epi-
genesis and dynamic similarity in two regulatory networks in pseudomonas aeruginosa .
Acta Biotheoretica, 52(4) :379–390, 2004.
[GCT08] A Gonzalez, C Chaouiya, and D Thieffry. Logical modelling of the role of the hh pathway
in the patterning of the drosophila wing disc. Bioinformatics, to appear, 2008.
[GDZ+ 06] A Ghazalpour, S Doss, B Zhang, S Wang, C Plaisier, Ruth Castellanos, Alec Brozell, Eric E
Schadt, Thomas A Drake, Aldons J Lusis, and Steve Horvath. Integrating genetic and
network analysis to characterize genes related to mouse weight. PLoS Genet, 2(8) :e130,
2006.
[GHVdL07] B Gaujal, A Hordijk, and D Van der Laan. On the optimal open-loop control policy for
deterministic and exponential polling systems. Probability in Engineering and Informa-
tional Sciences, 21 :157–187, 2007.
[GKNS07] M Gebser, B Kaufmann, A Neumann, and T Schaub. clasp : A conflict-driven answer set
solver. In Proceedings of the Ninth International Conference on Logic Programming
and Nonmonotonic Reasoning (LPNMR’07), pages 260–265. Springer, 2007.
[Goo63] BC Goodwin. Temporal organization in cells. Academic Press, 1963.
[Goo65] BC Goodwin. Oscillatory behavior in enzymatic control processes. In G. Weber, editor,
Advances in Enzyme Regulation, pages 425–438. Pregamon Press, Oxford, 1965.
[Gou98] JL Gouzé. Positive and negative circuits in dynamical systems. J.Biol.Syst., 6 :11–15,
1998.
[GR07] A Gorban and O Radulescu. Dynamical robustness of biological networks with hierarchical
distribution of time scales. IET Systems Biology, 1(238-246), 2007.
[Gra92] DJ Grabiner. Farey nets and multidimensional continued fractions. Monatsh. Math.,
114(1) :35–61, 1992.
[Grm01] M Grmela. Complex fluids subjected to external influences. J. Non-Newtonian Fl. Mech.,
96 :221–254, 2001.
[GRRL+ 03] RM Gutierrez-Rios, DA Rosenblueth, JA Loza, AM Huerta, JD Glasner, FR Blattner, and
J Collado-Vides. Regulatory network of Escherichia coli : consistency between literature
knowledge and microarray profiles. Genome Res, 13(11) :2435–2443, 2003.
[GS98] C Goodman-Strauss. Matching rules and substitution tilings. Ann. of Math. (2),
147(1) :181–223, 1998.
[GS02] JL Gouzé and T Sari. A class of piecewise linear differential equations arising in biological
models. Dynamical Systems, 17(4), 2002.
[GST+ 08] M Gebser, T Schaub, S Thiele, B Usadel, and P Veber. Detecting inconsistencies in large
influence networks with answer set programming. In Workshop on Constraint Based
Methods for Bioinformatics, 2008.
[GVG04] JP Gazeau and JL Verger-Gaugry. Geometric study of the beta-integers for a Perron
number and mathematical quasicrystals. J. Théor. Nombres Bordeaux, 16(1) :125–149,
2004.
207
[GW02] B Grunenfelder and EA Winzeler. Treasures and traps in genome-wide data sets : case
examples from yeast. Nat Rev Genet, 3(9) :653–661, Sep 2002.
[Had98] J Hadamard. Les surfaces à courbures opposées et leurs lignes géodésiques. Journal de
Mathématiques Pures & Appliquées, 4, 1898.
[Han00] CW Hansen. Dynamics of multi-dimensional substitutions. PhD thesis, George Wa-
shington University, 2000.
[HBC+ 01] EL Hong, R Balakrishnan, KR Christie, MC Costanzo, SS Dwight, and al,˙Saccharomyces
genome database. http ://www.yeastgenome.org/, 2001.
[HCP03] MJ Herrgard, MW Covert, and BØ Palsson. Reconciling gene expression data with known
genome-scale regulatory network structures. Genome Res, 13(11) :2423–34, Nov 2003.
[HGH01] J Hartman, G Garvik, , and L Hartwell. Principles for the buffering of genetic variation.
Science, 291 :1001–1004, 2001.
[HGL+ 04] CT Harbison, DB Gordon, TI Lee, NJ Rinaldi, K Macisaac, and al ,˙ Transcriptional
regulatory code of a eukaryotic genome. Nature, 431(7004) :99–104, 2004.
[HI97] M Hama and T Imahashi. Periodic β-expansions for certain classes of Pisot numbers.
Comment. Math. Univ. St. Paul., 46(2) :103–116, 1997.
[HKG] JW Helton, I Klep, and R Gomez. Determinant expansions of signed matrices and of
certain jacobians. arXiv :0802.4319v1.
[HLPP06] MJ Herrgard, BS Lee, V Portnoy, and BO Palsson. Integrated analysis of regulatory
and metabolic networks reveals novel regulatory mechanisms in Saccharomyces cerevisiae.
Genome Res, 16(5) :627–35, 2006.
[HM06] P Hubert and A Messaoudi. Best simultaneous Diophantine approximations of Pisot
numbers and Rauzy fractals. Acta Arith., 124(1) :1–15, 2006.
[HMJ+ 00] T Hughes, M Marton, A Jones, C Roberts, R Stoughton, and ,˙ Functional discovery via
a compendium of expression profiles. Cell, 102(1) :109–126, 2000.
[HMPL+ 04] H Hermjakob, L Montecchi-Palazzi, C Lewington, S Mudali, S Kerrien, and al ,˙ In-
tAct : an open source molecular interaction database. Nucleic Acids Res, 32(Database
issue) :D452–5, 2004.
[Hol96] M Hollander. Linear numeration systems, finite beta expansions, and discrete spectrum
of substitution dynamical systems. PhD thesis, Washington University, 1996.
[Hol04] JR Holton. An Introduction to Dynamic Meteorology. Academic Press, 2004.
[HP05] D Hinrichsen and AJ Pritchard. Mathematical systems theory. I, volume 48 of Texts
in Applied Mathematics. Springer-Verlag, Berlin, 2005. Modelling, state space analysis,
stability and robustness.
[HR74] R Heinrich and TA Rapoport. A linear steady-state treatment of enzymatic chains. general
properties, and effector strength. Eur. J. Biochem., 42 :89–95, 1974.
[HS96] R Heinrich and S Schuster. The Regulation of Cellular Systems. Chapman and Hall,
1996.
[HSG+ 06] S Hoops, S Sahle, R Gauges, C Lee, J Pahle, N Simus, M Singhal, L Xu, P Mendes,
and U Kummer. Copasi–a complex pathway simulator. Bioinformatics, 22(24) :3067–74,
2006.
[Hén06] T Hénin. Représentation par jeux du chaos de séquences d’adn. Master’s thesis, IRISA,
Université de Rennes 1, 2006. présenté à "Algorithmique, combinatoire du texte et appli-
cations en bio-informatique", Chessy France.
[Ide04] T Ideker. A systems approach to discovering signaling and regulatory pathways–or, how to
digest large interaction networks into relevant pieces. Adv Exp Med Biol, 547(NIL) :21–30,
2004.
[IFHY03a] S Ito, J Fujii, H Higashino, and S Yasutomi. On simultaneous approximation to (α, α2 )
with α3 + kα − 1 = 0. J. Number Theory, 99(2) :255–283, 2003.
[IFHY03b] S Ito, J Fujii, H Higashino, and SI Yasutomi. On simultaneous approximation to (α, α2 )
with α3 + kα − 1 = 0. J. Number Theory, 99(2) :255–283, 2003.
[IGH01] T Ideker, T Galitski, and L Hood. A new approach to decoding life : systems biology.
Annu Rev Genomics Hum Genet., 2 :343–72, 2001.
[IK91] S Ito and M Kimura. On Rauzy fractal. Japan J. Indust. Appl. Math., 8(3) :461–486,
1991.
[IK02] M Iosifescu and C Kraaikamp. Metrical theory of continued fractions. Mathematics and
its Applications, Kluwer Academic Publishers, 2002.
[IO93] S Ito and M Ohtsuki. Modified Jacobi-Perron algorithm and generating Markov partitions
for special hyperbolic toral automorphisms. Tokyo J. Math., 16(2) :441–472, 1993.
208
[IO94] S Ito and M Ohtsuki. Parallelogram tilings and Jacobi-Perron algorithm. Tokyo J. Math.,
17(1) :33–58, 1994.
[IR05] S Ito and H Rao. Purely periodic β-expansion with Pisot base. Proc. Amer. Math. Soc.,
133 :953–964, 2005.
[IR06] S Ito and H Rao. Atomic surfaces, tilings and coincidences I. Irreducible case. Israel J.
Math., 153 :129–155, 2006.
[IS98] Ingenuity-Systems. Ingenuity pathways knowledge base. Avalaible : www.ingenuity.com,
1998.
[IY07] S Ito and SI Yasutomi. On simultaneous diophantine approximation to periodic points
related to modified Jacobi-Perron algorithm. Advanced Studies in Pure Mathematics,
49 :171–184, 2007.
[Jac68] CGJ Jacobi. General theory of continued-fraction-like algorithms in which each number
is formed from three previous ones. (From the posthumous papers communicated by E.
Heine.). (Allgemeine Theorie der kettenbruchänlichen Algorithmen, in welche jede Zahl
aus drei vorhergehenden gebildet wird.). Borchardt J., LXIX : 29–64, 1868.
[Jam04] D Jamet. On the language of discrete planes and surfaces. In Proceedings of the Tenth In-
ternational Workshop on Combinatorial Image Analysi, pages 227–241. Springer-Verlag,
2004.
[JDSZ05] P Juvan, J Demsar, G Shaunlsky, and B Zupan. Genepath : from mutations to genetic
networks and back. Nucleic Acids Research, 33(Web Server issue) :W749–W752, 2005.
[Jef90] J Jeffrey. Chaos game representation of gene structure. Nucleic Acids Research,
18(8) :2163–2170, 1990.
[JM61] F Jacob and J Monod. Genetic regulatory mechanisms in the synthesis of proteins. J Mol
Biol., 3 :318–56, 1961.
[JP06] Andrew R Joyce and Bernhard O Palsson. The model organism as a system : integrating
’omics’ data sets. Nat Rev Mol Cell Biol, 7(3) :198–210, 2006.
[Jum04] DB Jump. Fatty acid regulation of gene transcription. Crit. Rev. Clin. Lab. Sci.,
41(1) :41–78, 2004.
[JVEGS02] R Jansen, JDA Van Embden, W Gaastra, and LM Schouls. Identification of genes that
are associated with dna repeats in prokaryotes. Mol Microbiol, 43(6) :1565–1575, 2002.
[K06] Davar K. Normal numbers are normal. Clay Mathematics Institute Annual Report 2006,
pages 15 ;27–31, 2006.
[Kal03] E Kalnay. Atmospheric Modeling, Data Assimilation and Predictability. Cambridge
University Press, 2003.
[Kan06] K Kaneko. An Introduction to Complex Systems Biology. Springer-Verlag, 2006.
[Kau69] SA Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets.
Journal of Theoretical Biology, 22 :437–467, 1969.
[Kau93] SA Kauffman. The origins of Order : Self-Organization and Selection in Evolution.
Oxford University Press, 1993.
[KB73] H Kacser and JA Burns. The control of flux. Symp. Soc. Exp. Biol., 27 :65–104, 1973.
[Kea75] M Keane. Interval exchange transformations. Math. Z., 141 :25–31, 1975.
[KEBC05] M Kaern, TA Elston, WJ Blake, and JJ Collins. Stochasticity in gene expression : from
theories to phenotypes. Nature Rev.Genet., 6 :451–464, 2005.
[Kel04] DB Kell. Metabolomics and systems biology : making sense of the soup. Current Opinion
in Microbiology, 7(3) :296–307, 2004.
[KGC05a] RD King, SM Garrett, and GM Coghill. On the use of qualitative reasoning to simulate
and identify metabolic pathways. Bioinformatics, 21(9) :2017–26, 2005.
[KGC05b] RD King, SM Garrett, and GM Coghill. On the use of qualitative reasoning to simulate
and identify metabolic pathways. Bioinformatics, 21(9) :2017–2026, 2005.
[KGK+ 04] M Kanehisa, S Goto, S Kawashima, Y Okuno, and M Hattori. The KEGG resource for
deciphering the genome. Nucleic Acids Res, 32(Database issue) :D277–80, 2004.
[Khi63] AY Khintchine. Continued fractions. P. Noordhoff, Ltd., Groningen, 1963.
[Kit01] H Kitano, editor. Foundations of Systems Biology. MIT Press, 2001.
[Kit02a] H Kitano. Systems biology : A brief overview. Science, 295(5560) :1662 – 1664, 2002.
[Kit02b] H Kitano. Systems biology : A brief overview. Science, 295(5560) :1662–1664, Mar 2002.
[KKB+ 02] BN Kholodenko, A Kiyatkin, FJ Bruggeman, E Sontag, HV Westerhoff, and JB Hoek.
Untangling the wires : a strategy to trace functional interactions in signaling and gene
networks. PNAS, 99(20) :12841–12846, 2002.
209
[KP00] J Kellendonk and I Putnam. Tilings, C ∗ -algebras, and K-theory. In M. Baake et al.,
editor, Directions in mathematical quasicrystals, volume 13 of AMS CRM Monogr. Ser.,
pages 177–206, Providence, RI, 2000.
[KPBT03] S Kauffman, C Peterson, Samuelsson B, and C Troein. Random boolean network models
and the yeast transcriptional network. PNAS, 100 :14796–14799, 2003.
[KPE03] K Kauffman, P Prakash, and J Edwards. Advances in flux balance analysis. Current
Opinion in Biotechnology, 2003.
[KPST03] S Kauffman, C Peterson, B Samuelsson, and C Troein. Random boolean network models
and the yeast transcriptional network. PNAS, 100(25) :14796–14799, 2003.
[KTH98] R Kubo, M Toda, and N Hashitsume. Statistical Physics II. Nonequilibrium Statistical
Mechanics. Springer, 1998.
[Kui84] BJ Kuipers. Commonsense reasoning about causality : Deriving behaviour from structure.
In Qualitative Reasoning about Physical Systems. Elsevier Science Publishers, 1984.
[Kur68] K Kuratowski. Topology. Vol. II. New edition, revised and augmented. Translated from
the French by A. Kirkor. Academic Press, New York, 1968.
[KV98] R Kenyon and A Vershik. Arithmetic construction of sofic partitions of hyperbolic toral
automorphisms. Ergodic Theory Dynam. Systems, 18(2) :357–372, 1998.
[Lag94] JC Lagarias. Geodesic multidimensional continued fractions. Proc. Lond. Math. Soc.,
III. Ser., 69(3) :464–488, 1994.
[Lan94] S Lang. Algebraic number theory, volume 110 of Graduate Texts in Mathematics.
Springer-Verlag, New York, second edition, 1994.
[Lap86] PS Laplace. Essai philosophique sur les probabilités. Collection Epistémè. [Epistémè
Collection]. Christian Bourgois Éditeur, Paris, fifth edition, 1986.
[Lar88] RG Larson. Constitutive Equations for Polymer Melts and Solutions. Butterworths :
Boston, 1988.
[LB06] Abdelhalim Larhlimi and Alexander Bockmayr. A new approach to flux coupling analysis
of metabolic networks. In Computational Life Sciences II, CompLife’06, LNBI, number
= 4216, pages 205–215. Springer-Verlag, 2006.
[LBV07] M Le Borgne and P Veber. Decision diagrams for qualitative biological models. Technical
Report RR-6182, INRIA, 2007.
[LCL+ 04] SS Lee, WY Chan, CK Lo, DC Wan, DS Tsang, and WT Cheung. Requirement of ppa-
ralpha in maintaining phospholipid and triacylglycerol homeostasis during energy depri-
vation. J Lipid Res., 45(11) :2025–37, 2004.
[LGJJ93] JM Luck, C Godrèche, A Janner, and T Janssen. The nature of the atomic surfaces of
quasiperiodic self-similar structures. J. Phys. A, 26(8) :1951–1999, 1993.
[Liv87] AN Livshits. On the spectra of adic transformations of Markov compact sets. Uspekhi
Mat. Nauk, 42(3(255)) :189–190, 1987. In Russian. English translation in Russian Math.
Surveys 42 (1987), 222–223.
[LM95] D Lind and B Marcus. An introduction to symbolic dynamics and coding. Cambridge
University Press, Cambridge, 1995.
[LMS02] JY Lee, RV Moody, and B Solomyak. Pure point dynamical and diffraction spectra. Ann.
Henri Poincaré, 3(5) :1003–1018, 2002.
[Lot05] M Lothaire. Applied combinatorics on words, volume 105 of Encyclopedia of Mathema-
tics and its Applications. Cambridge University Press, 2005.
[LPCal06] S Lagarrigue, F Pitel, W Carré, and al ,˙ Mapping quantitative trait loci affecting fatness
and breast muscle weight in meat-type chicken lines divergently selected on abdominal
fatness. Genet. Sel. Evol., 38 :85–97, 2006.
[LRR+ 02] TI Lee, NJ Rinaldi, F Robert, DT Odom, Z Bar-Joseph, and al,˙ Transcriptional regula-
tory networks in Saccharomyces cerevisiae. Science, 298(5594) :799–804, 2002.
[LRT02] J Luo, H Rao, and B Tan. Topological structure of self-similar sets. Fractals, 10 :223–227,
2002.
[LS05] E Lindenstrauss and K Schmidt. Symbolic representations of nonexpansive group auto-
morphisms. Israel J. Math., 149 :227–266, 2005.
[LT06] J Luo and JM Thuswaldner. On the fundamental group of self-affine plane tiles. Ann.
Inst. Fourier (Grenoble), 56(7) :2493–2524, 2006. Numération, pavages, substitutions.
[LU06] R Lima and E Ugalde. Dynamical complexity of discrete-time regulatory networks. Non-
linearity, 19(1) :237–259, 2006.
[Luo02] J Luo. A note on a self-similar tiling generated by the minimal Pisot number. Fractals,
10(3) :335–339, 2002.
[LW96] JC Lagarias and Y Wang. Self affine tiles in Rn . Adv. Math., 121 :21–49, 1996.
210
[LW00] D Lockhart and E Winzeler. Genomics, gene expression and dna arrays. Nature, 405 :827–
836, 2000.
[LZ04] J Luo and ZL Zhou. Disk-like tiles derived from complex bases. Acta Math. Sin. (Engl.
Ser.), 20(4) :731–738, 2004.
[Mac70] AGJ MacFarlane. Dynamical Sytems Models. Harap : London, 1970.
[Mas53] SJ Mason. Feedback theory - some properties of signal flow graphs. Proc. IRE, 41 :1144–
1156, 1953.
[Mes98] A Messaoudi. Propriétés arithmétiques et dynamiques du fractal de Rauzy. J. Théor.
Nombres Bordeaux, 10(1) :135–162, 1998.
[Mes00] A Messaoudi. Frontière du fractal de Rauzy et système de numération complexe. Acta
Arith., 95(3) :195–224, 2000.
[Mes06] A Messaoudi. Propriétés arithmétiques et topologiques d’une classe d’ensembles fractales.
Acta Arith., 121(4) :341–366, 2006.
[MH38] M Morse and GA Hedlund. Symbolic Dynamics. Amer. J. Math., 60(4) :815–866, 1938.
[MH40] M Morse and GA Hedlund. Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.,
62 :1–42, 1940.
[Moo00] RV Moody. Model sets : a survey. In F. Axel and eds J.-P. Gazeau, editors, From Quasi-
crystals to More Complex Systems, pages 145–166. Les Editions de Physique, Springer-
Verlag, Berlin, 2000.
[Mor21] HM Morse. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math.
Soc., 22(1) :84–100, 1921.
[Mos96] B Mossé. Reconnaissabilité des substitutions et complexité des suites automatiques. Bull.
Soc. Math. France, 124(2) :329–346, 1996.
[Moz89] S Mozes. Tilings, substitution systems and dynamical systems generated by them. J.
Anal. Math., 53 :139–186, 1989.
[MRM+ 08] PT Monteiro, D Ropers, R Mateescu, AT Freitas, and H de Jong. Temporal logic patterns
for querying dynamic models of cellular interaction networks. Bioinformatics, to appear,
2008.
[MW88] RD Mauldin and SC Williams. Hausdorff dimension in graph directed constructions.
Trans. Amer. Math. Soc., 309(2) :811–829, 1988.
[MWG+ 06] KD MacIsaac, T Wang, DB Gordon, DK Gifford, G Stormo, and E Fraenkel. An improved
map of conserved regulatory sites for Saccharomyces cerevisiae. BMC Bioinformatics,
7(NIL) :113, 2006.
[NAT+ 04] S Nicolay, F Argoul, M Touchon, Y d’Aubenton Carafa, C Thermes, and A Arneodo. Low
frequency rhythms in human dna sequences : a key to the organization of gene location
and orientation ? Phys. Rev. Lett., 93 :108101, 2004.
[Nic08] J Nicolas. Habibitation à Diriger des Recherches : Syntaxe et Raisonnement sur les
génomes. PhD thesis, Université de Rennes 1, 2008.
[Nie99] I Niemela. Logic programs with stable model semantics as a constraint programming
paradigm. Annals of Mathematics and Artificial Intelligence, 25 :241–273, 1999.
[NIE+ 06] DE Nelson, AE Ihekwaba, M Elliot, JR Johnson, CA Gibnet, Foreman BE, and al,˙Oscil-
lations in nf-κb signaling control the dynamics of gene expression. Science, 22(5696) :704
– 708, 306.
[NN03a] MT Nakamura and TY Nara. Essential fatty acid synthesis and its regulation. Prostglan-
dins, Leukotrienes and Essential Fatty Acids, 68 :145–150, 2003.
[NN03b] SM Ngai and N Nguyen. The Heighway dragon revisited. Discrete Comput. Geom.,
29(4) :603–623, 2003.
[Nog95] A Nogueira. The three-dimensional Poincaré continued fraction algorithm. Isr. J. Math.,
90(1-3) :373–401, 1995.
[NT04] SM Ngai and TM Tang. A technique in the topology of connected self-similar tiles.
Fractals, 12(4) :389–403, 2004.
[NTC07] A Naldi, D Thieffry, and C Chaouiya. Decision diagrams for the representation and
analysis of logical models of genetic networks. In Conference on Molecular Systems
Biology 2007, number 4695 in LNCS/LNBI, pages 233–247. Springer-Verlag, 2007.
[NTIM05] N Nariai, Y Tamada, S Imoto, and S Miyano. Estimating gene regulatory networks and
protein-protein interactions of Saccharomyces cerevisiae from multiple genome-wide data.
Bioinformatics, 21 Suppl 2(NIL) :ii206–ii212, 2005.
[OG04] N Oiwa and J Glazier. Self-similar mitochondrial dna. Cell Biochemistry and Biophysics,
41 :41–62, (2004.
211
[SAI01] Y Sano, P Arnoux, and S Ito. Higher dimensional extensions of substitutions and their
dual maps. J. Anal. Math., 83 :183–206, 2001.
[Sau04] U Sauer. High-throughput phenomics : experimental methods for mapping fluxomes.
Current Opinion in Biotechnology, 15(1) :58–63, 2004.
[SCG+ 01] F Schacherer, C Choi, U Gotze, M Krull, S Pistor, and E Wingender. The TRANS-
PATH signal transduction database : a knowledge base on signal transduction networks.
Bioinformatics, 17(11) :1053–7, 2001.
[Sch80] K Schmidt. On periodic expansions of Pisot numbers and Salem numbers. Bull. London
Math. Soc., 12(4) :269–278, 1980.
[Sch00a] K Schmidt. Algebraic coding of expansive group automorphisms and two-sided beta-shifts.
Monatsh. Math., 129(1) :37–61, 2000.
[Sch00b] F Schweiger. Multidimensinal Continued Fraction. Oxford Univ. Press, New York, 2000.
[SEJGM02] B Schoeberl, C Eichler-Jonsson, ED Gilles, and G Müller. Computational modeling of the
dynamics of the map kinase cascade activated by surface and internalized egf receptors.
Nature Biotechnology, pages 370 – 375, 2002.
[Sel78] ES Selmer. Unit fraction expansions and a multiplicative analog. Nordisk Mat. Tidskr.,
25-26 :91–109, 1978.
[Sen06] M Senechal. What is. . .a quasicrystal ? Notices Amer. Math. Soc., 53(8) :886–887, 2006.
[SFD00] S Schuster, DA Fell, and T Dandekar. A general definition of metabolic pathways useful
for systematic organization and analysis of complex metabolic networks. Nature Biotech-
nology, 18 :326–332, 2000.
[SGCPG+ 06] H Salgado, S Gama-Castro, M Peralta-Gil, E Diaz-Peredo, F Sanchez-Solano, A Santos-
Zavaleta, and al.,˙ RegulonDB (version 5.0) : Escherichia coli K-12 transcriptional regu-
latory network, operon organization, and growth conditions. Nucleic Acids Res, 34(Da-
tabase issue) :D394–7, 2006.
[Sid01] N Sidorov. Bijective and general arithmetic codings for Pisot toral automorphisms. J.
Dynam. Control Systems, 7(4) :447–472, 2001.
[Sid02] N Sidorov. An arithmetic group associated with a Pisot unit, and its symbolic-dynamical
representation. Acta Arith., 101(3) :199–213, 2002.
[Sid03] N Sidorov. Arithmetic dynamics. In S. Bezuglyi et al., editor, Topics in dynamics
and ergodic theory, volume 310 of Lond. Math. Soc. Lect. Note Ser., pages 145–189.
Cambridge University Press, 2003.
[SKB+ 02] J Stelling, S Klamt, K Bettenbrock, S Schuster, , and ED Gilles. Metabolic network
structure determines key aspects of functionality and regulation. Nature, 420 :190–193,
2002.
[SL98] Z Szallasi and S Liang. Modeling the normal and neoplastic cell cycle with "realistic boo-
lean genetic networks" : their application for understanding carcinogenesis and assessing
therapeutic strategies. In Proc. Pacific Symposium on Biocomputing, volume 3, pages
66–76, 1998.
[Sma67] S Smale. Differentiable dynamical systems. Bull. Amer. Math. Soc., 73 :747–817, 1967.
[SMO+ 03] P Shannon, A Markiel, O Ozier, NS Baliga, JT Wang, and al ,˙ Cytoscape : a software
environment for integrated models of biomolecular interaction networks. Genome Res.,
13(11) :2498–504, 2003.
[Sno89] EH Snoussi. Qualitative dynamics of piecewise-linear differential equations : a discrete
mapping approach. Dyn. Stab. Syst., 4(3-4) :189–207, 1989.
[Sno98] EH Snoussi. Necessary conditions for multistationarity and stable periodicity. J. Biol.
Syst., 6(3-9), 1998.
[Sol92] B Solomyak. Substitutions, adic transformations, and beta-expansions. In Symbolic dy-
namics and its applications (New Haven, CT, 1991), volume 135 of Contemp. Math.,
pages 361–372. Amer. Math. Soc., Providence, RI, 1992.
[Sol94] B Solomyak. Conjugates of beta-numbers and the zero-free domain for a class of analytic
functions. Proc. Lond. Math. Soc., III. Ser., 68(3) :477–498, 1994.
[Sol06] B Solomyak. Tilings and dynamics. In EMS Summer School on Combinatorics, Auto-
mata and Number Theory, Liege, 2006.
[Son07] ED Sontag. Monotone and near-monotone biochemical networks. Systems and Synthetic
Biology, 1 :59–87, 2007.
[Sou03] C Soulé. Graphic requirements for multistationarity. ComPlexUs, 1 :123–133, 2003.
[Sou06] C Soulé. Mathematical approaches to differentiation and gene regulation. C.R. Paris
Biologies, 329, 2006.
[SRN07] JA Sepulchre, S Reverchon, and W Nasser. Modeling the onset of virulence in a pectino-
lytic bacterium. J. of Theor. Biol., 244 :239–257, 2007.
213
[SSR+ 03] E Segal, M Shapira, A Regev, D Pe’er, D Botstein, and al,˙Module networks : identifying
regulatory modules and their condition-specific regulators from gene expression data. Nat
Genet, 34(2) :166–76, 2003.
[ST02] K Scheicher and JM Thuswaldner. Canonical number systems, counting automata and
fractals. Math. Proc. Cambridge Philos. Soc., 133(1) :163–182, 2002.
[STV04] B Scholkopf, K Tsuda, and J-P Vert, editors. Kernel Methods in Computational Biology.
MIT Press, 2004.
[SV98] N Sidorov and A Vershik. Bijective arithmetic codings of hyperbolic automorphisms of
the 2-torus, and binary quadratic forms. J. Dynam. Control Systems, 4(3) :365–399,
1998.
[SVC02] D Segrè, D Vitkup, and GM Church. Analysis of optimality in natural and perturbed
metabolic networks. PNAS, 99(23) :15112–15117, 2002.
[SW02] VF Sirvent and Y Wang. Self-affine tiling via substitution dynamical systems and Rauzy
fractals. Pacific J. Math., 206(2) :465–485, 2002.
[TCN01] JJ Tyson, K Chen, and B Novak. Network dynamics and cell physiology. Nat Rev Mol
Cell Biol, 2 :908–916, 2001.
[Tho79] R Thomas, editor. Kinetic logic : a boolean approach to the analysis of complex regula-
tory systems, volume 29 of ecture Notes in Biomathematics. Springer-Verlag, 1979.
[Tho81] R Thomas. On the relation between the logical structure of systems and their ability
to generate multiple steadt states or sustained oscillations. Springer Ser. Synergetics,
9 :180–193, 1981.
[Tho91] R Thomas. Regulatory networks seen as asynchronous automata : a logical description.
J. Theor. Biol., 153 :1–23, 1991.
[THT+ 99] M Tomita, K Hashimoto, K Takahashi, TS Shimuzu, Y Matsuzaki, and al,˙E-cell :software
environment of whole-cell simulation. Bioinformatics, 15 :72–84, 1999.
[Thu88] W Thurston. On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Amer.
Math. Soc. (N.S.), 19(2) :417–431, 1988.
[Thu89] WP Thurston. Groups, tilings and finite state automata. Lectures notes distributed in
conjunction with the Colloquium Series, in AMS Colloquium lectures, 1989.
[Thu06] JM Thuswaldner. Unimodular Pisot substitutions and their associated tiles. J. Théor.
Nombres Bordeaux, 18(2) :487–536, 2006.
[TMD03] L Travé-Massuyès and P Dague, editors. Modèles et raisonnements qualitatifs. Hermes
sciences, 2003.
[TS01] D Thieffry and L Sanchez. A logical analysis of the drosophila gap-gene system. Journal
of Theoretical Biology, 211(2) :115–141, 2001.
[Tur03] P Turchin. Complex Population Dynamics : a Theoretical/Empirical Synthesis. NJ :
Princeton University Press, 2003.
[Val03] B Vallée. Dynamical analysis of a class of Euclidean algorithms. Theoret. Comput. Sci.,
297(1-3) :447–486, 2003. Latin American theoretical informatics (Punta del Este, 2000).
[Var03] F Varenne. La simulation informatique face à la méthode des modèles. le cas de la crois-
sance des plantes. Nature Sciences Sociétés, 11 :16–28, 2003.
[VAR04] MO Vlad, A Arkin, and J Ross. Response experiments for nonlinear systems with appli-
cation to reaction kinetics and genetics. PNAS, 101(19) :7223–7228, 2004.
[Veb07] P Veber. Modélisation grande échelle de réseaux biologiques : vérification par con-
traintes booléennes de la cohérence des données. PhD thesis, Université de Rennes 1,
2007.
[Vee78] WA Veech. Interval exchange transformations. J. Anal. Math., 33 :222–272, 1978.
[Ver92] AM Vershik. Arithmetic isomorphism of hyperbolic automorphisms of a torus and of sofic
shifts. Funktsional. Anal. i Prilozhen., 26(3) :22–27, 1992.
[vK35] ER van Kampen. On some characterizations of 2-dimensional manifolds. Duke Math. J.,
1(1) :74–93, 1935.
[Wal82] P Walters. An introduction to ergodic theory. Springer-Verlag, New York, 1982.
[Wal06] M Waldschmidt. Diophantine analysis and words. In Diophantine analysis and related
fields 2006, volume 35 of Sem. Math. Sci., pages 203–221. Keio Univ., Yokohama, 2006.
[Yag75] G Yagil. Quantitative aspects of protein induction. In BL Horecker and ER Stadtman,
editors, Current topics in Cell regulation, pages 183–237. Academic Press, 1975.
[Yas99] SI Yasutomi. On Sturmian sequences which are invariant under some substitutions. In
Kanemitsu, Shigeru (ed.) et al., Number theory and its applications. Proceedings of the
conference held at the RIMS, Kyoto, Japan, pages 347–373. Kluwer Academic Publishers,
1999.
214
5.6 Publications
Livres et ouvrages
– N. Pytheas-Fogg. Substitutions in Dynamics, Arithmetics and Combinatorics. Lec-
tures Notes in Mathematics 1794, Springer-Verlag, 2002. V. Berthé, S. Ferenczi, C.
Mauduit and A. Siegel, editors.
– Journées Montoises d’Informatique Théorique (Rennes, 2006), Theoretical Informa-
tics and Applications, Vol 42 (3), 2008. D. Caucal and A. Siegel, guest editors.
215
216
Soumissions
(Repeat, submitted, 2008) J. Nicolas ; C. Rousseau ; A. Siegel ; P. Peterlongo ; F. Cos-
te ; P. Durand ; S. Tempel ; A.-S. Valin and F. Mahé, Local and Maximal Repeats,
2008.
217
Travaux en cours
(R., S., P., C.& L. en cours) O. Radulescu, A. Siegel, E. Pécou, C. Chatelain and S.
Lagarrigue, Algebraic mddules and qualitative constraints for the study of equilibria
of biochemical models
(A., F., S.& S., en cours) B. Adamczewski, C. Frougny, A. Siegel, W. Steiner, Alge-
braicity of the length of the largest interval [0, ε[∩Q containing only purely periodic
beta-expansions.
(B., B. & S., en cours) V. Berthé, J.Bourdon, A. Siegel Génération de plan discret par
des algorithmes de fractions continues.
(B., S., S. & T., en cours) V. Berthé, A. Siegel, P. Surer, J. Thuswaldner Fractal tiles
associated to generalized radix representations and shift radix systems.
(CANT, 2009) V. Berthé, A. Siegel, J. Thuswaldner Tilings, substitutions and Rauzy
fractals : effectivity and complexity, Chapter of Combinatorics, Automata and Num-
ber Theory, Cambridge University Press.
(A., G. & S., en cours) P. Arnoux, S. Giabicani, A. Siegel Dynamique du nombre d’or.
Divers
– A. Siegel, Représentations géométrique, combinatoire et arithmétique des systèmes
substitutifs de type Pisot, Thèse de troisième cycle, Université de la Méditérranée,
2000.
5.7 Communications
Congrès, symposium
– Workshop “Number Theory and Ergodic Theory 2008 April”, Kanazawa, Japan
(04/2008) Topological properties of central tiles and boundary graphs
– Journée annuelle du Groupe de Travail « Systèmes Dynamiques, Automates et Al-
gorithmes » (GT SDA2) du GDR Informatique Mathématique, Paris (10/2007) Pro-
priétés topologiques des fractals de Rauzy
– ICIAM’07 : International Conference on Applied and Industrial Mathematics, Zurich
(07/2007). Minisymposium : new reasearch in bioinformatics Qualitative response of
interaction networks : application to the validation of biological models.
218
– Groupe d’étude sur la numération, CIRM, Marseille, mars 1999. Automate des
préfixes-suffixes et représentation des substitutions
Séminaires
– Station biologique de Roscoff, séminaire (10/2008)
– Université de Rennes I, Séminaire de systèmes dynamiques (02/2008)
– Laboratoire Systèmes Navals Complexes, Toulon (12/2007)
– Université de Rennes, groupe de travail application des mathématiques en biologique
(12/2007)
– Université de Nice (03/2007)
– Université Paris XI, groupe de travail Systèmes Dynamiques (05/2006)
– ENS Lyon, séminaire de mathématiques, (04/2006)
– Université de Montpellier, LIRMM, groupe de travail d’info. théorique (02/2006)
– University of Neuchâtel, colloquium de mathématiques, (01/2006)
– University of Vienna, séminaire de mathématiques (11/2005)
– Université de Rennes I, séminaire de systèmes dynamiques (11/01, 02/05)
– Université de Brest, séminaire de systèmes dynamiques , (11/04)
– ENS-Cachan, antenne Bretagne, séminaire des élèves (05/04)
– Université Paris XI, séminaire de systèmes dynamiques (06/01)
– Dijon, séminaire de systèmes dynamiques (03/01)
– Université de Montpellier, séminaire de mathématiques (03/01)
– Université Paris VII, séminaire d’informatique du LIAFA (02/01)
– Université de Marne-la-Vallée, séminaire d’informatique (12/00)
– Université Paris VI, séminaire de théorie ergodique (11/00)
– Ecole Polytechnique, séminaire de géométrie ergodique (11/00)
– Université de Bordeaux, séminaire de théorie des nombres (10/00)
– Université de Turku (Finlande), séminaire de mathématiques (09/98)
– Université de la méditérannée, séminaire de théorie ergodique (04/98, 04/00)
– Université d’Amiens, séminaire d’informatique (03/98)
– Université de Provence, séminaire de dynamique symbolique (10/97, 03/99, 04/00)
Stages de master
– Laurent Chamoin, Master 2 bio-informatique, 2006-2007. Recherche de modules dans
le réseau MAPK.
220
Enseignements
– Master 2 Modélisation de Systèmes Biologiques, Rennes. Construction et exploitation
de réseaux biomoléculaires (2008) [24h]
– Formation interne Inria, Liffré. Modélisation de réseaux biologiques (2005) [2h]
– Master 1 de bio-informatique, Rennes. (2005) [4h]
– Université d’été Sciences Mathématiques et Modélisation, Bordeaux. Dynamique du
nombre d’or (2004) [6h]
– Niveau Licence : Premier degré universitaire, Préparation concours (Mathématiques,
Marseille et Rennes) (1998, 1999, 2000, 2001) [202h]
Relations internationales
– programme Egide Sakura (Franco-japonais), 2007-2008. Number theory and discrete
dynamical systems
– programme Egide Amadeus (franco-autrichien), 2008-2009. Fractals and topological
structures arising from dynamics
– relation bilatérales avec le CMM, université du Chili (visite d’un mois en 2005).
221
Séjours à l’étranger
– Laboratoire de mathématiques de l’université de Kanazawa, Japon. Visite d’une
semaine, 2008.
– Laboratoire de mathématiques de Keio university, Japon. Visite de 3 jours, 2008.
– Laboratoire de mathématiques de l’université de Leoben, Autriche. Visite d’une
semaine, 2005.
– Centre de modélisation mathématiques, Université du Chili, Santiago du Chili. Visite
de 5 semaines, 2005.
– Laboratoire de Mathématiques de l’université du North Texas, Denton, USA. Visite
de 2 semaines, 2000.
– Laboratoire de mathématiques de l’Université de Turku, Finlande. Visite de 2 se-
maines, 1999.
Animation de la recherche
Mathématiques et informatique
– Organisation de la conférence internationale Numeration : Mathematics and Com-
puter Science, March 23-27, 2009, CIRM, Marseille. (70 participants attendus)
– Organisation de la conférence internationale Journées montoises d’informatique théo-
rique, Rennes, août 2006. (70 participants)
– J’organise régulièrement des ateliers de travail sur le thème Generalized substitution
and tilings and numeration, avec V. Berthé. Ces ateliers rassemblent une quaran-
taine de chercheurs ; la moitié sont étrangers. Des sessions ont eu lien en Juin 2007
(porquerolles), Mars 2006 (CIRM, Marseille), Avril 2005 (CIRM, Marseille), Mars
2004 (CIRM, Marseille), Mars 2003 (CIRM, Marseille),
222
Bioinformatique
– Organisation du séminaire de bioinformatique de l’IRISA depuis 2002.
– Organisation de 14 journées thématiques de bioinformatique depuis 2002, dans le
cadre de l’animation de Ouest-Génopole.
– Supervision de l’animation sur les réseaux biologiques dans le cadre du projet ACI
VICANNE (programme IMPBio, 2004-2007).
– Organisation de deux journées satelites de la conférence de bioinformatique française
JOBIM :
– Modélisation dynamique et simulation des réseaux biologiques Lille, 2008
– Modélisation dynamique et simulation des réseaux biologiques Où en est-on ?, Mar-
seille, 2007.
– Organisation d’ateliers sur les réseaux biologiques. Ces réunions ont rassemblé de 20
à 50 participants français.
– Réseaux booléens et automates cellulaires pour la modélisation de systèmes biolo-
giques, Rennes, 2007 (organisé avec P. Veber).
– Aspects stochastiques de la modélisation des réseaux de régulation, Nice 2005 (or-
ganisé avec J.A. Sepulchre).
– Modélisation de réseaux de gènes, Dijon 2004 (organisé avec E. Pécou).
Résumé
223
224
léculaire, pour aider à la correction de modèles, et, dans le futur, à la mise en place de
plans expérimentaux. Au vu de la qualité des données, les aspects dynamiques sont
alors remplacés par des considérations sur les déplacements d’états stationnaires,
et analyser les données revient à formaliser puis résoudre des contraintes portant
sur des ensembles discrets. Nous montrons ainsi comment aborder les notions de
corrections de modèles et de diagnostic de réseaux grande échelle.
Mots clés : systèmes dynamiques discrets. Fractal. Numération. Biologie des
systèmes. Diagnostic. Contraintes.