La recherche de motifs dans les réseaux d'interactions

Florian Sikora

Un réseau d'interaction peut-être représenté par un graphe coloré. Une grande partie de la littérature est dédiée à la recherche de motifs dans ces graphes, avec une topologie donnée sur le motif (chemin, arbre, graphe,...).

Récemment, Lacroix et al. ont établi un nouveau problème où le motif n'a pas de topologie mais est simplement un (multi) ensemble de couleurs. On cherche alors une composante connexe dans le graphe contenant cet ensemble. On présentera lors de cet exposé différentes variantes de ce problème, des résultats de complexité paramétrée et d'approximation, ainsi qu'un plugin pour Cytoscape.