2016 | AlCoMol


Axe :DataSense – Making Sense of Complex and heterogeneous data
Sujet : Algorithmique de graphes pour l’aide à la décision dans la construction
moléculaire
Directeurs de thèse :Dominique Barth, PRISM et Marc Antoine Wesser, LRI
Institution : David, LRI
Laboratoire gestionnaire : David
Doctorant : Stefi Nouleho
Début : 2016
Productions scientifiques : Publications en attente de validation.
Ressources :


Contexte :
De nombreuses bases de données de réactions sont proposées aux chimistes et biochimistes. Elles peuvent être considérés comme des graphes ou des hypergraphes dans lesquelles les sommets sont des molécules et les liens (ou les hyperliens) représentent les réactions permettant de ces molécules. Etant donnée une molécule cible, qui ne se trouve pas dans la ou les bases considérées, l’objectif est d’identifier le chemin réactionnel qui pourrait présider à sa synthèse à partir d’éléments existants. L’objectif de ce sujet de thèse en informatique vise donc la conception d’algorithmes d’aide à la décision pour la prédiction de chemins réactionnels, algorithmes basés sur des notions adaptées de similarités de graphes. Il s’agira donc de définir les notions de similarités les plus pertinentes (un stage de master 2 financé par le Labex CHARMMMAT va initier cette étude), d’en étudier les aspects théoriques et de complexité, de proposer des algorithmes d’évaluation et enfin de proposer des algorithmes d’aide à la décision conçus en lien avec les chimistes partenaires. Positionnement par rapport à l’état de l’art et à la concurrence nationale et internationale
Différentes approches informatiques sont actuellement proposées aux chimistes (notamment aux chimistes organiciens) pour la prédiction de réactions moléculaires, avec deux principaux points de vue, l’un basé sur la modélisation et la simulation des comportement physico-chimiques des réactions, l’autre sur la recherche de sous-graphes communs maximaux entre la molécule cible et les molécules stockées dans la base. En termes de graphes, les solutions qui sont envisagées dans les travaux préparatoires à ce projet ont pu considérer pour cet exemple le squelette générique de la figure, et les molécules sélectionnée insistait à des molécules dont les squelettes été suffisamment similaires (mais pas forcément identiques) à ce squelette générique cible.

Objectif scientifique:
L’objectif final de ce projet est la conception d’un logiciel d’aide à la décision pour la construction moléculaire. Pour ce faire, nous considérons donc des graphes, dit graphes de réactions, obtenus par union de différentes chaines de réactions enregistrées dans des bases de données (publiques ou commerciales) comme Reaxys. Il s’agit en fait de « graphes de graphes » (ou d’« hypergraphes de graphes»), c’est à dire de graphes dans lesquels les sommets sont des molécules (dont les structures sont aussi modélisées par des graphes) et les arcs des réactions entre ces molécules. D’un point de vue algorithmique, le projet scientifique global consiste, étant donnée une nouvelle molécule cible, à prédire la (ou
les) place(s) possible(s) dans un graphe de réactions existant. Le paradigme de départ est que si deux molécules sont proches (en particulier liées) dans ce graphe, alors elles ont des sous-structures de graphes communes ou similaires. On peut entendre ici bien sûr la notion de sous-structures communes au sens de l’isomorphisme de graphes partiels, mais aussi des notions déjà envisagées au sein de premiers projets de recherche menés dans CHARMMMAT comme les mineurs communs ou proches, des similarités de la décomposition en cycles, ou des propriétés des groupes d’automorphismes. Une des spécificités de ce sujet de thèse est que ces notions de similarités sont à envisager à des niveau de granularité de graphes
(de la structure complète à un squelette générique, voir figure plus haut). L’expertise du chimiste est que ce niveau de granularité dépend de l’intérêt fonctionnel ou non de chaque élément de la molécule, et que le niveau de granularité envisagé ne sera pas homogène sur toute la molécule. Enfin, chaque réaction se traduira souvent par une coupe (ou une partie d’une coupe) minimale dans le graphe considéré, ce qui induit également des choix dans le squelette finalement choisi. Le premier objectif de la thèse sera d’évaluer, sur des molécules cibles dans les graphes de réactions visées, le rapport entre la distance entre deux molécules dans ce graphe et leur similarité selon ces différents critères, pour identifier (voire redéfinir) les mieux adaptés, avec les niveaux de granularité de
graphes les plus pertinentes. Il s’agira ensuite d’étudier les propriétés structurales liées à ces paramètres, la complexité de leur calcul (en tenant compte des caractéristiques des graphes considérés) et enfin de proposer des algorithmes d’évaluation qui seront au coeur des solutions de prédiction qui seront proposées. Ces solutions opèreront, soit directement sur les graphes quand les bases de données le permettre, soit en utilisant fonctions d’accès fournies avec les bases de données commerciales (comme Reaxys). La validation des approches proposées sera faite tout au long de la thèse par une étroite collaboration avec une équipe de chimistes de l’ILV de Versailles, avec qui nous avons préparé cette proposition de thèse,
dans la cadre de CHARMMMAT.

Perspectives :