Caractérisation de la stéréoisomérie et mesure de similarité stéréo 

Télécharger le fichier pdf d’un mémoire de fin d’études

Modèles de représentation des molécules

Une molécule est un assemblage chimique d’atomes, liés entre eux par des liaisons covalentes. Si des atomes ont le même numéro atomique (c’est-à-dire un même nombre de protons), ils représentent un même élément chimique. Les liaisons covalentes ont un ordre, identifiant le nombre d’électrons impliqués dans la liaison. Selon cet ordre, les liaisons sont appelées liaisons simples, doubles, triples ou aromatiques.
Un graphe est un ensemble de sommets liés entre eux par des arêtes. Ces sommets et ces arêtes peuvent avoir des étiquettes. Ainsi, une molécule peut être naturellement représentée par un graphe. Dans ce cas, le graphe est appelé graphe moléculaire.
Définitions et notations
Afin de définir formellement un graphe moléculaire, nous allons dans un premier temps donner les définitions qui seront utilisées au cours de ce manuscrit.
Définition 1. Graphe orienté
Un graphe orienté G = (V, E ) est un couple composé de deux ensembles. Un premier ensemble V de sommets et un second ensemble E ⊂ V ×V d’arcs entre ces sommets. Les arcs sont des couples ordonnés de sommets (u, v) ∈ V × V indiquant une liaison de u vers v.
Définition 2. Graphe non orienté
Un graphe non orienté G = (V, E ) est un couple composé de deux ensembles. Un premier ensemble V de sommets et un second ensemble E ⊂ P2(V ) d’arêtes entre ces sommets, où P2(V ) est l’ensemble des parties de taille 2 de V . Les arêtes sont des ensembles non ordonnés de deux sommets {u, v} ∈ P2(V ) indiquant une liaison entre u et v.
Dans tout ce manuscrit, un ensemble non ordonné sera entouré par des accolades {a1, . . . , an} et un ensemble ordonné sera entouré par des parenthèses (a1, . . . , an).
Les prochaines définitions sont données pour un graphe non orienté, mais sont aussi applicables aux graphes orientés. Le terme arête est réservé aux graphes non orientés et celui d’arc aux graphes orientés.
Définition 3. Arête incidente
Soit un graphe G = (V, E ). Une arête e ∈ E est dite incidente à un sommet v ∈ V si v ∈ e. On dit alors que v est une des extrémités e.
Définition 4. Adjacence de sommets
Soit un graphe G = (V, E). Un sommet v ∈ V est dit adjacent à un sommet u ∈ V , s’il existe une arête e ∈ E telle que e = {u, v}.
Définition 5. Boucle
Soit un graphe G = (V, E). Une boucle est une arête e ∈ E reliant un sommet v ∈ V à lui-même : e = {v, v}.
Définition 6. Arête multiple
Soit un graphe G = (V, E). Une arête multiple est un ensemble d’arêtes {e1, . . . , en} ⊂ E tel que chaque arête possède les mêmes extrémités {u, v} ∈ V 2 : e1 = {u, v}, . . . , en = {u, v}.
Définition 7. Graphe fini
Un graphe G = (V, E) est dit fini si son nombre de sommets |V | est fini.
Définition 8. Graphe simple
Un graphe G = (V, E) est dit simple si il ne possède ni boucle ni arête multiple.
Définition 9. Graphe étiqueté
Un graphe étiqueté G = (V, E, µ, ν) est un graphe (V, E) avec deux fonctions d’étiquetage µ et ν. La fonction µ : V → LV associe à chaque sommet v du graphe une étiquette µ(v) et la fonction ν : E → LE associe à chaque arête e du graphe une étiquette ν(e).
Les ensembles d’étiquettes LV et LE peuvent être de n’importe quel type (chaîne de caractères, entier, vecteur …).
Sauf mention contraire, dans la suite de ce manuscrit on désignera un graphe simple, fini, non orienté et étiqueté par le terme de graphe.
Définition 10. Voisinage
Soit un graphe G = (V, E, µ, ν). Le voisinage d’un sommet v ∈ V , dénoté N(v), est l’ensemble des sommets adjacents à v : N(v) = {u ∈ V |∃e = {u, v} ∈ E}
Étant donné un ensemble de sommets S ⊆ V , on note N(S) l’ensemble des voisins des sommets de S :
[
N(S) = N(u)
u∈S
Définition 11. Degré d’un sommet
Soit un graphe G = (V, E, µ, ν). Le degré dv d’un sommet v ∈ V est la taille de son voisinage.
dv = |N(v)|
Définition 12. Chemin
Soit un graphe G = (V, E, µ, ν). Un chemin p est une séquence ordonnée de sommets (v1, . . . , vn) telle qu’il existe une arête entre deux sommets consécutifs : ∀i ∈ {1 . . . , n − 1}, ∃e ∈ E t.q e = {vi, vi+1}
La longueur d’un chemin est définie par son nombre d’arêtes. Le chemin p = (v1, . . . , vn) est donc de longueur n − 1.
Définition 13. Distance entre sommets
Soit un graphe G = (V, E, µ, ν). La distance d(u, v) entre deux sommets u ∈ V et v ∈ V est la longueur du plus court chemin entre u et v.
Définition 14. Chemin simple
Soit un graphe G = (V, E, µ, ν). Un chemin p = (v1, . . . , vn) est dit simple si toutes ses arêtes sont distinctes : ∀(i, j) ∈ {1, . . . , n − 1}2, i 6= j ⇐⇒ ei = {vi, vi+1} 6= ej = {vj, vj+1} Définition 15. Chemin élémentaire
Soit un graphe G = (V, E, µ, ν ). Un chemin p = (v1, . . . , vn) est dit élémentaire si tous ses sommets sont distincts : ∀(i, j) ∈ {1, . . . , n}2, i 6= j ⇐⇒ vi 6= vj
Tout chemin élémentaire est aussi un chemin simple.
Définition 16. Cycle
Soit un graphe G = (V, E, µ, ν ). Un cycle est un chemin simple p = (v1, . . . , vn) dont les deux extrémités sont identiques : v1 = vn.
Si le chemin est élémentaire (sauf pour les extrémités), alors le cycle est appelé cycle élémentaire.
Un graphe ne possédant aucun cycle est dit acyclique.
Définition 17. Sous-graphe
Soit un graphe G = (V, E, µ, ν). Un graphe H = (VH , EH , µH , νH ) est un sous-graphe de G si H est contenu dans G, c’est-à-dire VH ⊂ V , EH ⊂ E, µH = µ VH et νH = ν EH .
Dans tout ce manuscrit la notation VH désignera l’ensemble des sommets du sous-graphe H.
Définition 18. Sous-graphe induit
Soit un graphe G = (V, E, µ, ν) et H = (VH , EH , µH , νH ) un sous-graphe de G. On dit que H est un sous-graphe induit de G si pour tout couple de sommets de H une arête existe entre ces sommets dans H si et seulement si elle existe dans G : EH = E ∩ P2(VH)
L’ensemble des sommets VH d’un sous-graphe induit H de G suffit à le décrire. On dit alors que H est le sous-graphe induit de G par VH .
Soit H un sous-graphe de G (ou V 0 un sous-ensemble de V ). La notation G − H (ou G − V 0) désigne le sous-graphe induit de G obtenu en supprimant l’ensemble des sommets de H (ou en supprimant les sommets de V 0).
Définition 19. Isomorphisme de graphes Soit deux graphes G1 = (V1, E1, µ1, ν1) et G2 = (V2 , E2, µ2, ν2). Une fonction f est un isomorphisme entre G1 et G2 si c’est une bijection entre les sommets qui préserve les arêtes et les étiquettes. Formellement, f est une fonction de V1 vers V2 respectant les conditions suivantes :
1. ∀u ∈ V2, ∃!v ∈ V1 t.q u = f(v)
2. ∀v ∈ V1, µ1(v) = µ2(f(v))
3. {u, v} ⊆ V1, {u, v} ∈ E1 ⇐⇒ {f(u), f(v)} ∈ E2
4. {u, v} ∈ E1, ν1({u, v}) = ν2({f(u), f(v)})
S’il existe un isomorphisme f entre deux graphes G1 et G2, ces graphes sont dit isomorphes. On note Isom(G1, G2 ) l’ensemble des isomorphismes entre G1 et G 2. La relation “G1 est isomorphe à G2” est une relation d’équivalence. On note cette relation G1 ‘ G 2.
Étant donné un ensemble de sommets S ⊆ V1, et un isomorphisme f entre deux graphes G1 et G2, on note f(S) l’ensemble des sommets associés à des sommets de S par f :
f(S) = {f(u)|u ∈ S}
Définition 20. Graphe connexe
Un graphe G = (V, E, µ, ν) est dit connexe si pour tout couple de sommets {u, v} ∈ P2(V ) il existe un chemin entre u et v.
Définition 21. Arbre
Un arbre est un graphe acyclique et connexe.
Définition 22. Arbre enraciné
Un arbre enraciné est un arbre dont l’un des sommets est distingué et appelé racine de l’arbre.
Un arbre étant connexe et acyclique, il existe pour tout sommet v un unique chemin élémentaire p = (v1 , . . . , vn) reliant r = v1 à v = vn. Si v est différent de la racine, le père de v est l’unique sommet vn−1 situé avant v dans le chemin le reliant à la racine (ce sommet peut être la racine elle-même). Le sommet v est appelé fils de vn−1.
Définition 23. Permutation
Soit X un ensemble. Une permutation ϕ sur X est une bijection de X sur lui-même.
L’orbite Oϕ(x) d’un élément x selon une permutation ϕ est l’ensemble de ses images successives obtenues par applications répétées de ϕ : Oϕ(x) = {ϕk(x) | k ∈ N}
Si l’ensemble X est fini, alors pour tout élément x de X l’orbite de x est fini et donc il existe k tel que ϕk(x) = x. De plus les orbites des éléments de X forment une partition (X1, X2, . . . , Xk ) de X. Pour chaque sous-ensemble Xi de cette partition on note xi un de ses éléments et li sa taille. La restriction de ϕ sur chaque Xi définit une permutation notée xi, ϕ(xi), ϕ2(x i), . . . , ϕli (xi) appelée un cycle. La permutation ϕ peut donc être définie comme la composition de ses cycles sur chacun des Xi : ϕ = Y xi, ϕ(xi), ϕ2(xi), . . . , ϕli (xi)
Une permutation uniquement composée d’un cycle de taille 2 est appelée transposition.
Définition 24. Parité et signature d’une permutation
Soit ϕ une permutation de n éléments. La permutation ϕ est dite paire si elle peut être exprimée comme le produit d’un nombre pair de transpositions. De la même manière, ϕ est dite impaire si elle peut être exprimée comme le produit d’un nombre impair de transpositions. La signature (ϕ) d’une permutation paire est 1, et celle d’une permutation impaire est -1.
Définition 25. Groupe
Un groupe est un couple composé d’un ensemble G et d’une loi de composition •, qui associe à deux éléments a et b de G un autre élément noté a • b, respectant les quatre axiomes suivant :
• ∀{a, b} ⊂ G, a • b ∈ G.
• ∀{a, b, c} ⊂ G, (a • b) • c = a • (b • c).
• Il existe un élément e dans G, appelé élément neutre, tel que pour tout a de G on ait : e • a = a • e = a.
• Soit e l’élément neutre de G, pour tout a de G il existe b dans G tel que : a • b = b • a = e.
On dit que G est un groupe pour la loi de composition •.

Graphe moléculaire

Le graphe moléculaire d’une molécule (page 8) est défini comme un graphe simple, non orienté et étiqueté où :
1. Chaque atome de la molécule est représenté par un sommet.
2. Chaque liaison chimique reliant une paire d’atomes est représentée par une arête incidente aux deux sommets représentant ces deux atomes.
3. Chaque sommet est étiqueté par une chaîne de caractères (par ex. “C”,“H”,“Br”, …) représentant l’élément chimique de l’atome qu’il représente.
4. Chaque arête est étiquetée par un caractère représentant son ordre.
Pour représenter graphiquement un graphe moléculaire, plusieurs conven-tions sont utilisées (Figure 1.1).
Figure 1.1 – Représentation graphique de la molécule : C17H24N2O2. Les extrémités des lignes brisées représentent les atomes de carbone. Les atomes d’hydrogène sont implicitement représentés par les liaisons manquantes. Les trois traits parallèle incident à l’atome d’azote (en haut à gauche) représentent une triple liaison. De même les deux traits parallèle à droite représentent une double liaison. Finalement, le cercle à l’intérieur de l’hexagone représente des liaisons aromatiques.
2. Les atomes d’hydrogène ne sont pas représentés lorsqu’ils sont liés à un carbone. Leur présence est déduite du nombre de liaisons du carbone. Si un hydrogène est lié à un autre atome qu’un carbone, la liaison entre l’hydrogène et cet atome n’est pas représentée (voir l’oxygène à droite de la Figure 1.1).
3. Les arêtes encodant des liaisons simples, doubles et triples sont respecti-vement représentées par un, deux ou trois traits.
4. Les liaisons aromatiques sont toujours présentes dans des cycles. Elles peuvent être représentées de deux façons. Soit par une alternance de trait simple et double, soit par un cercle à l’intérieur du cycle. Dans ce manuscrit nous utiliserons la seconde notation.
Autres représentations
D’autres modèles permettent de représenter les molécules. On peut par exemple représenter une molécule par sa formule brute. Ce modèle est constitué de la liste des atomes composant une molécule, accompagnée du nombre d’occurrences de ceux-ci. Cette représentation est plus simple que le graphe moléculaire, mais code moins d’informations.
Au sein d’une molécule, les atomes peuvent subir des rotations autour des liaisons simples. Les différentes formes que peut prendre une molécule grâce à ces rotations sont appelées conformères. Parmi les conformères d’une molécule, il y en a des plus stables que d’autres. Les méthodes de modélisation moléculaire [Lea01] permettent de calculer les coordonnées cartésiennes des atomes d’une molécule pour une conformation donnée. On peut donc représenter une molécule par la liste de ses atomes, accompagnés de leurs coordonnées dans la conformation la plus stable. Cette représentation peut être couplée au graphe moléculaire, afin d’avoir la position des atomes ainsi que leurs relations d’adjacence.

Table des matières

Introduction générale 
1 Description du contexte applicatif 
1.1 Prédiction des propriétés moléculaires
1.1.1 Modèles de représentation des molécules
1.1.2 Descripteurs moléculaires
1.1.3 Noyaux sur graphes
1.1.4 Méthodes de classification/régression
1.2 Stéréochimie
1.2.1 Description du problème
1.2.2 Représentations de la stéréochimie
1.2.3 Méthodes de prédiction existantes
1.3 Conclusion
2 Graphes Localement Ordonnés 
2.1 Introduction
2.2 Structures localement ordonnées
2.2.1 Définition des structures localement ordonnées
2.2.2 Fonctions de réordonnancement
2.2.3 Structures localement ordonnées avec des ordres équivalents
2.3 Graphes localement ordonnés appliqués aux molécules
2.3.1 Graphes localement ordonnés
2.3.2 Graphes localement ordonnés pour représenter et différencier les stéréoisomères
2.3.3 Stéréo sommets
2.4 Lien avec la définition de la chiralité
2.5 Conclusion
3 Caractérisation de la stéréoisomérie et mesure de similarité stéréo 
3.1 Introduction
3.2 Stéréo sous-graphes minimaux
3.3 Preuve d’algorithme
3.3.1 Convergence et caractérisation du stéréo sommet
3.3.2 Minimalité du stéréo sous-graphe “minimal”
3.4 Complexité
3.5 Définition du noyau
3.6 Expérimentations
3.7 Conclusion
4 Extensions 
4.1 Introduction
4.2 Recouvrements
4.2.1 Graphes de recouvrements
4.2.2 Expérimentations
4.3 Voisinage des stéréo sous-graphes minimaux
4.3.1 Construction des voisinages
4.3.2 Expérimentations
4.4 Noyau entre différents stéréo sous-graphes
4.4.1 Comparaison de stéréo sous-graphes minimaux
4.4.2 Expérimentations
4.5 Conclusion
Conclusion et Perspectives 
5 Annexes 
5.1 Preuves des théorèmes et propositions du chapitre 2
5.1.1 Preuve de la Proposition 5
5.1.2 Preuve du Théorème 2
5.1.3 Preuve de la Proposition 6
5.1.4 Preuve du Théorème 3
5.1.5 Preuve de la Proposition 7
5.2 Lemmes utilisés pour prouver le théorème 4 du chapitre 3
5.3 Noyaux définis positifs
5.3.1 Preuve de la Proposition 10
5.3.2 Preuve de la Proposition 11
5.3.3 Preuve de la Proposition 12
5.3.4 Preuve de la Proposition 13
Liste des publications 143
Références

Télécharger le rapport complet