RESEARCH IN PAIRS
The Graph Motif Problem: A Survey
Le problème Graph Motif problem: Un état de l’art
13 – 17 January 2020
Le problème Graph Motif problem: Un état de l’art
13 – 17 January 2020
Description
|
The Graph Motif problem: A survey. Our goal is to write a survey paper on the algorithmic aspects of the Graph Motif problem, a remote sibling of the famous Pattern Matching problem, in which a (small) text sequence P (the pattern) is to be retrieved in a larger text T. In the Graph Motif problem, the text T is replaced by a vertex-colored graph G, and the pattern is a multiset of colors M. The problem then consists in finding whether there exists a set of vertices V 0 ⊆ V (G) satisfying the two following conditions: (i) the multiset of colors used to color V 0 is exactly M and (ii) the subgraph of G induced by V 0 is connected.
This problem is motivated by the search for functional groups in biological networks, and has been introduced in 2006 [LFS06]: in this context, the vertices of the graph G represent biological entities (such as proteins or enzymes), and colors are biological functions corresponding to these entities. Edges in G represent biological phenomena between such entities (e.g. interactions between proteins, or metabolic reactions), and the sought motif M is a group of functionalities that one expects to be simultaneously expressed (modeled here by the connectivity requirement). The Graph Motif problem is NP-hard, even in restricted cases. However, for practical reasons, it is important to find ways of solving it, notably using fixed-parameterized tractability (or FPT) algorithms. Since 2006, the Graph Motif problem and its variants have led to an abundant literature (roughly 100 papers). Most interestingly, it has given rise to many new and insightful algorithmic techniques, mainly devoted to designing fast FPT algorithms. Besides, due to its applicative nature, several associated software have been developed. Altogether, the fact that (i) the Graph Motif problem and its variants have raised so much interest in the algorithmic community since 2006, and (ii) that it has led to original and sophisticated techniques and algorithms, calls for a survey paper on the area. References [LFS06] Vincent Lacroix, Cristina G. Fernandes, and Marie-France Sagot. Motif search in graphs: Application to metabolic networks. IEEE/ACM Trans. Comput. Biology Bioinform., 3(4):360–368, 2006. |
Le problème Graph Motif problem: Un état de l’art. Notre projet est d’écrire un article de type ”état de l’art” concernant les aspects algorithmiques du problème Graph Motif, un parent éloigné du célèbre problème Pattern Matching, dans lequel un texte (court) P (le pattern) est à rechercher dans un texte long T. Dans le problème Graph Motif, le texte T est remplacé par un graphe sommet-coloré G, et le pattern est un multi-ensemble de couleurs M. Le problème consiste alors à déterminer s’il existe un ensemble V 0 de sommets de G qui satisfait les deux conditions suivantes: (i) le multi-ensemble de couleurs utilisé pour colorier V 0 est exactement M et (ii) le sous-graphe de G induit par V 0 est connexe.
Ce problème est motivé par la recherche de motifs fonctionnels dans les réseaux biologiques, et a été introduit en 2006 [LFS06]: dans ce contexte, les sommets du graphe G représentent des entités biologiques (protéines ou enzymes, par exemple), et les couleurs sont des fonctions biologiques associées à ces entités. Les arêtes de G représentent des phénomènes biologiques reliant ces entités (e.g. interactions entre protéines ou réactions métaboliques), et le motif recherché M est un groupe de fonctionnalités que l’on s’attend àvoir exprimées simultanément (modélisé ici par la contrainte de connectivité). Contrairement au problème Pattern Matching, le problème Graph Motif est NP-difficile. Cependant, pour des raisons pratiques, il est important de trouver des moyens de le résoudre, notamment par l’utilisation d’algorithmes dits fixed-parameterized tractable (ou FPT). Depuis 2006, le problème Graph Motif et ses variantes ont donné lieu à une littérature abondante (environ 100 articles). De plus, il a donné lieu à de nombreuses techniques algorithmiques nouvelles et perspicaces, principalement dévolues à la conception d’algorithmes FPT rapides. De plus, de par sa nature applicative, plusieurs logiciels associés au problème ont été développés. En résumé, le fait que (i) le problème Graph Motif et ses variantes ont suscité tant d’intérêt au sein de la communauté algorithmique depuis 2006 et (ii) qu’il ait abouti à la création de techniques algorithmiques originales et sophistiquées, nécessite qu’un article de type ”état de l’art” existe. Références [LFS06] Vincent Lacroix, Cristina G. Fernandes, and Marie-France Sagot. Motif search in graphs: Application to metabolic networks. IEEE/ACM Trans. Comput. Biology Bioinform., 3(4):360–368, 2006. |
Participants
Guillaume Fertin (Université de Nantes)
Géraldine Jean (Université de Nantes)
Florian Sikora (Université Paris Dauphine)
Sponsor
