Nous avons travaillé ces dernières années à la mise en place d’outils pour la comparaison de graphes hétérogènes, avec des applications en bioinformatique. Le problème traité, NP-difficile au sens fort, se pose comme suit. Soient un graphe orienté D (représentant un réseau métabolique) et un graphe non-orienté G (représentant la proximité des gènes produisant les protéines en jeu), tous deux définis sur le même ensemble de sommets. Le problème consiste à trouver un (ou plusieurs) chemin dans D, tels que le sous-graphes de G engendré par les sommets de ce chemin est connexe. On cherche donc une (ou plusieurs) voie métabolique impliquant des protéines produites par des gènes voisins. Nous nous intéressons à la recherche de chemins élémentaires et non-élémentaires, dits trails. Ces chemins constituent des marqueurs des espèces et peuvent servir à leur comparaison. Dans cette présentation nous aborderons : différentes variantes du problème, les méthodes de résolution développées, des résultats numériques obtenus sur des données synthétiques et sur des données réelles, et les critères de comparaison utilisés par les biologistes et leur modélisation.
Séminaire des groupes Symbiose:
https://www.cesgo.org/symbiose/seminars/resolution-de-problemes-combina…