Dominique Barth, PRiSM-UVSQ

Petite introduction thématique à la théorie des graphes; quelques applications à la

modélisation moléculaire

Dominique Barth, PRiSM-UVSQ

Journées Simulation Numérique 2013 15/11/2013

1. Type de modèle : discret (combinatoire, graphes, proc. Stochastique) ou continu (EDP,…)

2. Approche : statique (structure, architecture, états) ou dynamique (évolution temporelle)

3. Granularité : fine (élément de base = niveau atomique ou petite molécule) ou élevée (élément de base =molécule de grande taille)

4. Simulation : le but est il de calculer un modèle ou de simuler in silico un phénomène réel?

5. Application : en biologie, en pharmacologie ou autre (matériaux,…)

Quelques questions concernant la modélisation moléculaire…

Dominique Barth, PRiSM, UVSQ 15/11/2013

1. Type de modèle : discret (combinatoire, graphes, proc. Stochastique) ou continu (EDP,…)

2. Approche : statique (structure, architecture, états) ou dynamique (évolution temporelle)

3. Granularité : fine (élément de base = niveau atomique ou petite molécule) ou élevée (élément de base =molécule de grande taille)

4. Simulation : le but est il de calculer un modèle ou de simuler in silico un phénomène réel?

5. Application : en biologie, en pharmacologie ou autre (matériaux,…)

Quelques réponses par la théorie et l’algorithmique des graphes…


« Il peut ne pas être entièrement sans intérêt pour les lecteurs de Nature d'être au courant d'une analogie qui m'a récemment fortement impressionné entre des branches de la connaissance humaine apparemment aussi dissemblables que la chimie et l'algèbre moderne. […] Chaque invariant et covariant devient donc exprimable par un graphe précisément identique à un diagramme Kékuléan ou chemicograph. »

James Joseph Sylvester (1814-1897)


http://commons.wikimedia.org/wiki/File:James_Joseph_Sylvester.jpg

http://commons.wikimedia.org/wiki/File:Historic_Benzene_Formulae_Kekul%C3%A9_%28original%29.png

Axe T1 du Labex CHARMMMAT : Modélisation, Caractérisation et Simulation

Axe T1 du Labex CHARMMMAT : Modélisation, Caractérisation et Simulation

Fonctions, objectifs

Caractérisation

Modélisation

Identification

Prédiction

. Comportement stat/dyn

. Granularité

. RMN

. Spectro…

Propriétés, structuresRésolution de systèmes, Algorithimique de graphes

1


Plan

• Introduction et concepts de base

• Coloration de graphes

• Planarité

• Comparaison de graphes

• Application à la modélisation moléculaire

• Conclusion


Introduction et concepts de base


Graphes : relation (application de V*V dans {Vrai,Faux})

(vrai) graphe orienté

Graphe orienté symétrique Graphe non-orienté

- Degrés- Distances, diamètre- Chaine, chemin, cycle, circuits- Connexité, forte-connexité, k-connexité- pondération, étiquetage

Graphe de la relation, matrice d’adjacence, listes par extension



http://www.google.fr/imgres?start=100&client=firefox-a&hs=Sv8&sa=X&rls=org.mozilla:fr:official&channel=np&biw=1227&bih=1026&tbm=isch&tbnid=5jCKQ408kepxpM:&imgrefurl=http://images.math.cnrs.fr/Representer-les-mondes-II.html&docid=2q-qfbq2EWvaDM&imgurl=http://images.math.cnrs.fr/IMG/jpg/Proteine.jpg&w=567&h=427&ei=IS1FUp_vLvL50gX8o4GoDg&zoom=1

http://www.google.fr/imgres?client=firefox-a&hs=rNo&sa=X&rls=org.mozilla:fr:official&biw=1227&bih=1026&tbm=isch&tbnid=R5poEJiFJgiQBM:&imgrefurl=http://www.cndp.fr/crdp-orleans-tours/lettre-dinformation-janvier-2009-acrolire.html&docid=QJLeRogcK9s8EM&imgurl=http://www.cndp.fr/crdp-orleans-tours/images/stories/CRDP_ORLEANS_TOURS_20090529/CDDP_INDRE_ET_LOIRE/img/SocialNetworkAnalysis_Graph.gif&w=600&h=619&ei=_y5FUuLeLObt0gXpqYBY&zoom=1&iact=hc&vpx=660&vpy=196&dur=4807&hovh=228&hovw=221&tx=100&ty=123&page=1&tbnh=143&tbnw=139&start=0&ndsp=39&ved=1t:429,r:10,s:0,i:111

L.P. Euler (1707 – 1783)

W.R. Hamilton (1805 – 1865)

Claude Berge (1926 – 2002)

Une veille science en informatique…


http://commons.wikimedia.org/wiki/File:Konigsberg_bridges.png

http://commons.wikimedia.org/wiki/File:7_bridges.svg

http://commons.wikimedia.org/wiki/File:Konigsburg_graph.svg

http://www.google.fr/imgres?imgurl=http://pmcdn.priceminister.com/photo/Berge-Claude-Theorie-Des-Graphes-Et-Ses-Applications-Livre-349551230_ML.jpg&imgrefurl=http://www.priceminister.com/offer/buy/1970237/Berge-Claude-Theorie-Des-Graphes-Et-Ses-Applications-Livre.html&h=270&w=270&sz=8&tbnid=S8t5kUNSLTNdOM:&tbnh=90&tbnw=90&zoom=1&usg=__JIOOkPpbReXm5gJgY5DMf-KJDWo=&docid=jvrtYdMPpQoUnM&itg=1&sa=X&ei=LBZEUueuLKrH7AbvkYGYCQ&ved=0CFEQ9QEwBA&dur=3125

http://www.google.fr/imgres?imgurl=http://www.les-mathematiques.net/p/p/b/img7.png&imgrefurl=http://www.les-mathematiques.net/p/p/b/node2.php&h=451&w=316&sz=94&tbnid=LtLcuj6C0DAd2M:&tbnh=114&tbnw=80&zoom=1&usg=__kAGFz_QAd6aSRj7w96mANrrz-Q0=&docid=8ZBK0FyuHY77YM&sa=X&ei=LBZEUueuLKrH7AbvkYGYCQ&ved=0CFoQ9QEwBw&dur=1073

http://commons.wikimedia.org/wiki/File:William_Rowan_Hamilton_painting.jpg

http://commons.wikimedia.org/wiki/File:Leonhard_Euler_2.jpg

http://commons.wikimedia.org/wiki/File:Paley9-perfect.svg

Coloration de graphes


Francis Guthrie (1831-1899)

Un problème de géographe


http://commons.wikimedia.org/wiki/File:Francis_guthrie.jpg

http://www.google.fr/imgres?client=firefox-a&hs=hHB&sa=X&rls=org.mozilla:fr:official&biw=932&bih=1026&tbm=isch&tbnid=bv-uIGB9-MJZYM:&imgrefurl=http://www.math.ucsd.edu/%7Eerdosproblems/About.html&docid=K67mGXDfUzDvWM&imgurl=http://www.math.ucsd.edu/%7Eerdosproblems/imgs/about_erdos.jpg&w=305&h=310&ei=NhpEUrmOCYXTsgaWvYCADw&zoom=1&iact=hc&vpx=4&vpy=206&dur=1101&hovh=226&hovw=223&tx=102&ty=166&page=1&tbnh=148&tbnw=146&start=0&ndsp=34&ved=1t:429,r:0,s:0,i:83


http://www.google.fr/imgres?client=firefox-a&hs=Ihq&hl=fr&rls=org.mozilla:fr:official&biw=932&bih=1026&tbm=isch&tbnid=TKdnejLYYPp4_M:&imgrefurl=http://people.ucalgary.ca/%7Elaflamme/colorful/enseignm.html&docid=kfkTbLWZSfB__M&imgurl=http://people.ucalgary.ca/%7Elaflamme/colorful/graphics/4colors.gif&w=360&h=120&ei=axtEUs-uDcmDtAa33IHADQ&zoom=1&iact=hc&vpx=475&vpy=299&dur=1312&hovh=96&hovw=288&tx=173&ty=64&page=3&tbnh=58&tbnw=174&start=54&ndsp=34&ved=1t:429,r:86,s:0,i:344

http://www.google.fr/imgres?client=firefox-a&hs=Ihq&hl=fr&rls=org.mozilla:fr:official&biw=932&bih=1026&tbm=isch&tbnid=cPAPRYXuLsfVnM:&imgrefurl=http://icosaweb.ac-reunion.fr/Algorithmes/Graphes/Intro.htm&docid=p6BJ8WSro8ooMM&imgurl=http://icosaweb.ac-reunion.fr/Algorithmes/Graphes/Th4Couleurs/CarteDeFrance1.gif&w=450&h=441&ei=axtEUs-uDcmDtAa33IHADQ&zoom=1&iact=hc&vpx=297&vpy=420&dur=211&hovh=222&hovw=227&tx=111&ty=104&page=1&tbnh=155&tbnw=158&start=0&ndsp=28&ved=1t:429,r:10,s:0,i:111









Paul erdos (1913-1996)


Conjecture : 4 couleurs suffisent pour chaque carte géographique





Une coloration du graphe de Petersen avec 3 couleurs.

G=(V,E), graphe non-orienté

Coloration de G: application f de V dans un ensemble de couleursColoration propre : (u,v) une arête de E implique f(u) différent de f(v)Taille d’une coloration(propre) : cardinal de f(V)Nombre chromatique de G : taille minimum d’une coloration propre de G

Problème historique des 4 couleurs


http://fr.wikipedia.org/wiki/Fichier:Petersen_graph_3-coloring.svg



Théorème : Un graphe est 2-coloriable ssi il ne contient pas de cycles de longueur impaire.




11

2

3

3

3

24

4

5

0


11

2

3

3

3

24

4

5


1

11

1

1

1

1

2

2

22

cPair/impair Pair/impair


Théorème : Décider si un graphe peut ou non être colorié avec au plus 3 couleurs est un problème NP-complet

Complexité Nombre de données processeur x 1000 traitées / 24h

Linéaire 1 million x1000Polynomial (deg. 4) 4000 x 2

Exponentielle 150 +20Factorielle 12 +2

} Classe P

Difficulté d’un problème : plus petite complexité d’un algorithme le résolvant

Taille d’un problème : nombre de sommets, de liens


Classe P: problèmes « faciles », pouvant être résolus en temps polynomial fonction du nombre de sommets et d’arêtes.

Classe NP: problèmes pour lesquels pour chaque instance, vérifier si une solution possible est une solution réalisable ou optimale est « facile » (d’où algorithme exponentiel). Contient la classe P.

Problème NP-complet : problème X de NP tel que tout autre problème de NP peut de facon « facile » se ramener à un sous-problème de X (donc, problèmes les plus durs de NP).

Hiérarchie de classes de problèmes

Question : P=NP ?

Si un des problèmes NP-complet est dans P, alors P=NP



http://inf421.files.wordpress.com/2011/10/gj2.gif




Savoir si un problème est NP-complet :« Si un problème X est au moins aussi difficile qu’un problème connucomme étant l’un des plus difficiles (NP-complet) alors X est aussiun des problèmes les plus difficiles (NP-complet). »

Que faire si un problème est NP-complet : - Heuristiques polynomiales- Approximation, garanties de performances- Liens entre invariants et complexité


Théorème : Décider si un graphe peut ou non être colorié avec au plus 3 couleurs est un problème NP-complet

3 3

5

2

47

Invariant de complexité : largeur arborescente (calcul NP-complet)

Problème : enchevêtrement de cycles


Planarité

Un graphe est planaire si et seulement si il existe une facon de le dessiner sur une sphère sans que deux arête ne se croisent



La terre est ronde







La terre est ronde





Comment décider qu’un graphe est ou non planaire sans disposer de plusieurs siècles?

Conjecture : 4 couleurs suffisent pour chaque carte géographiquegraphe planaire




K3 K4K5

K3,3

Graphe planaire : graphe que l’on peut dessiner sur un plan (une sphère) Sans que deux arêtes ne se croisent

oui ouinon

non

?


Graphe homéomorphe à

Théorème (Kuratowski ) : Un graphe est planaire ssi il n’est homéomorphe ni à K5, ni à K3,3

Décider si un graphe est planaire est dans P.

Kutlaw Kuratowski (1896-1980)Dominique Barth, PRiSM, UVSQ 15/11/2013

http://commons.wikimedia.org/wiki/File:Kazimierz_Kuratowski.jpg

Carte planaire : dessin planaire d’un graphe planaire

= caractérisation par un graphe + parcours des arêtes décrivant les faces

a

b

c

d

e

f

(abdfec),(abc),(bdec),(dfe) (abdec),(abc),(bdfec),(def)



Question : un graphe est-il « rond » ou « long »?

1. Existe-t-il un critère mesurable pour cette question? Est-il « facile » à calculer?

2. Si non, utilisation de critères croisés : - Excentricité moyenne (calcul polynomial) - Taille de séparateur (NP-complet, critère négatif) - Heuristique de largeur de bande


Comparaisons de graphes


Morphisme d’un graphe G=(V,E) dans un graphe H=(V’,E’) :Application f de V dans V’ tel que (u,v) dans E implique (f(u),f(v)) dans E’.

f est un isomorphisme ssi f est une bijection (donc l’inverse de f est un (iso)morphisme)

Graphe G Graphe HIsomorphismeentre G et H

ƒ(a) = 1 ƒ(b) = 6ƒ(c) = 8ƒ(d) = 3ƒ(g) = 5ƒ(h) = 2ƒ(i) = 4ƒ(j) = 7


f est un automorphisme ssi f est un isomorphisme et G=H

- groupe d’automorphismes d’un graphe, - classes d’équivalence de sommets, - symétries (involutions) - graphes sommet-transitifs


f homéomorphisme ssi isomorphisme – injectivité (contraction de V dans V’) (puis notion de mineur)

Graphe homéomorphe à


Comparaison de sous-graphes : plus grand sous-graphes de GEt de H qui ont la propriété de morphisme visée.

Plongement de graphes: f:V -> V’, injectif. Critère : minimiser dist(f(u),f(v)) pour tout (u,v) de E

Transformation (édition, mineur) d’un graphe à un autre en minimisantLe nombre d’opérations élémentaires

Application de la généralisation à la notion de distance entre graphes

-Statique : comparaisons de structures a priori similaire,-Dynamique : mesure de l’évolution d’une structure dans le temps


Quelques applications ….

- Identifier la bonne structure moléculaire,- Prédire la structure tridimensionnelle d’une molécule,


1


Y VVY Y

?

Exemple d’application : génération de topologies de cages moléculaires construites à partir de motifs de base

Verrous : Faire face à l’explosion combinatoire et à la sélection sur critères

1


Y VVY Y

?



Question : un graphe est-il « rond » ou « long »?

1. Existe-t-il un critère mesurable pour cette question? Est-il « facile » à calculer?

2. Si non, utilisation de critères croisés : - Excentricité moyenne (calcul polynomial) - Taille de séparateur (NP-complet, critère négatif) - Heuristique de largeur de bande




1

2

3

7

6

5

4

8

9

10

11

Séparateur (calcul approché)

Excentricité (calcul exact)

Largeur de bande(calcul approché)

+ nombre de classes d’équivalence+ test de planarité


Conclusion

- Le choix du modèle dépend du problème (structure, granularité,..)

- Importance des caractéristiques des instances- Déterminer la difficulté intrinsèque (NP-complétude, explosion combinatoire)

- Produire la bonne approche (cout/performance)

Un des objectifs du groupe de travail transverse sur la modélisation moléculaire CHARMMMAT – LERMIT - PALM


Objectifs de l’axe :

•appréhender les structures complexes observées dans le LABEX, à la fois expérimentalement et d'un point de vue algorithmique,

•proposer des modèles et des stratégies pour la corrélation des techniques expérimentales sur un même objet étudié

•modéliser des propriétés et des fonctions identifiées par les quatre thèmes et proposer/identifier des architectures moléculaires cibles..

Axe T1 du labex CHARMMMAT: Modélisation, Caractérisation et

Simulation

Axe T1 du labex CHARMMMAT: Modélisation, Caractérisation et

Simulation


« Il peut ne pas être entièrement sans intérêt pour les lecteurs de Nature d'être au courant d'une analogie qui m'a récemment fortement impressionné entre des branches de la connaissance humaine apparemment aussi dissemblables que la chimie et l'algèbre moderne. […] Chaque invariant et covariant devient donc exprimable par un graphe précisément identique à un diagramme Kékuléan ou chemicograph. »

James Joseph Sylvester (1814-1897)


Documents

Dominique Barth, PRiSM-UVSQ