CIRM - Videos & books Library - Le problème Graph Motif

Multi angle

Auteurs : Fertin, Guillaume (Auteur de la conférence)
CIRM (Editeur )

Loading the player...

Résumé : Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.

Codes MSC :
05C15 - Coloring of graphs and hypergraphs
05C85 - Graph algorithms
05C90 - Applications of graph theory
68Q17 - Computational difficulty of problems
68Q25 - Analysis of algorithms and problem complexity
68R10 - Graph theory in connection with computer science
92D20 - Protein sequences, DNA sequences
92C42 - Systems biology, networks

Ressources complémentaires :
http://gt-alea.math.cnrs.fr/alea2017/slides/GuillaumeFertinCours-ALEA2017.pdf
http://fpt.wikidot.com/

Informations sur la Vidéo

Réalisateur :

Hennenfent, Guillaume

Langue :

Date de Publication :

Date de Captation :

Sous Collection :

Catégorie arXiv :

Domaine(s) :

Format :

Durée :

Audience :

Download :

https://videos.cirm-math.fr/2017-03-23_Fertin_part2.mp4

Informations sur la Rencontre

Nom de la Rencontre : ALEA Days / Journées ALEA
Organisateurs de la Rencontre : Gerin, Lucas ; Pierrot, Adeline ; Gittenberger, Bernhard
Dates : 20/03/17 - 24/03/17
Année de la rencontre : 2017
URL de la Rencontre : http://conferences.cirm-math.fr/1590.html

Données de citation

DOI : 10.24350/CIRM.V.19146003
Citer cette vidéo: Fertin, Guillaume (2017). Le problème Graph Motif - Partie 2. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19146003
URI : http://dx.doi.org/10.24350/CIRM.V.19146003

Voir Aussi

[Multi angle] Random cubic planar graphs revisited / Auteur de la conférence Rué, Juanjo.
[Multi angle] Une histoire de mots inattendus et de génomes / Auteur de la conférence Schbath, Sophie.
[Multi angle] Processus de Pólya à valeur mesure / Auteur de la conférence Mailler, Cécile.
[Post-edited] Le problème Graph Motif - Partie 1 / Auteur de la conférence Fertin, Guillaume.

Bibliographie

Betzler, N., van Bevern, R., Fellows, M.R., Komusiewicz, C., & Niedermeier, R. (2011). Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5), 1296-1308 - https://doi.org/10.1109/TCBB.2011.19

Betzler, N., Fellows, M.R., Komusiewicz, C., & Niedermeier, R. (2008). Parameterized algorithms and hardness results for some graph motif problems. In P. Ferragina, & G.M. Landau (Eds.), Proccedings of the 19th Annual Symposium on Combinatorial pattern matching (pp. 31-43). Berlin: Springer - http://dx.doi.org/10.1007/978-3-540-69068-9_6

Björklund, A., Kaski, P. & Kowalik, L. (2016). Constrained multilinear detection and generalized graph motifs. Algorithmica, 74(2), 947-967 - http://dx.doi.org/10.1007/s00453-015-9981-1

Blin, G., Sikora, F., & Vialette, S. (2010). GraMoFoNe: a cytoscape plugin for querying motifs without topology in protein-protein interactions networks. In Hisham Al-Mubaid (Ed.), Proceedings of the 2nd International Conference on Bioinformatics and Computational Biology (pp. 38-43). International Society for Computers and their Applications. - https://hal.archives-ouvertes.fr/hal-00425661

Böcker, S., & Rasche, F. (2008). Towards de novo identification of metabolites by analyzing tandem mass spectra. Bioinformatics, 24(16), 49-55 - https://doi.org/10.1093/bioinformatics/btn270

Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., & Sharan, R. (2010). Topology-free querying of protein interaction networks. Journal of Computational Biology, 17(3), 237-252 - https://doi.org/10.1089/cmb.2009.0170

Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Cham: Springer - http://dx.doi.org/10.1007/978-3-319-21275-3

Downey, R.G., & Fellows, M.R. (2013). Fundamentals of parameterized complexity. London: Springer - http://dx.doi.org/10.1007/978-1-4471-5559-1

Downey, R.G., & Fellows, M.R. (1998). Parameterized complexity. Berlin: Springer - http://dx.doi.org/10.1007/978-1-4612-0515-9

Fellows, M.R., Fertin, G., Hermelin, D., & Vialette, S. Upper and lower bounds for finding connected motifs in vertex-colored graphs. Journal of Computer and System Sciences, 77(4), 799-811 - http://dx.doi.org/10.1016/j.jcss.2010.07.003

Fernau, H. (2005). Parameterized algorithmics: A graph-theoretic approach - http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_cs_08w/Resources/fernau_habil.pdf

Fertin, G., & Komusiewicz, C. (2016). Graph motif problems parameterized by dual. In R. Grossi, & M. Lewenstein (Eds.), Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (Article No. 7; pp. 7:1-7:12). Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik - http://subs.emis.de/LIPIcs/volltexte/2016/6083/pdf/LIPIcs-CPM-2016-7_.pdf

Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer - http://dx.doi.org/10.1007/3-540-29953-X

Guillemot, S., & Sikora, F. (2013). Finding and counting vertex-colored subtrees. Algorithmica, 65(4), 828-844 - http://dx.doi.org/10.1007/s00453-011-9600-8

Koutis, I., & Williams, R. (2016). LIMITS and applications of group algebras for parameterized problems. ACM Transactions on Algorithms, 12(3), (Article No. 31; pp. 31:1-31:18) - https://doi.org/10.1145/2885499

Lacroix, V., Fernandes, C.G., & Sagot, M.-F. (2006). Motif search in graphs: Application to metabolic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4), 360-368 - https://doi.org/10.1109/TCBB.2006.55

Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press - https://global.oup.com/academic/product/invitation-to-fixed-parameter-algorithms-9780198566076?cc=fr&lang=en&#

Pinter, R.Y., Shachnai, H., & Zehavi, M. (2016). Deterministic parameterized algorithms for the graph motif problem. Discrete Applied Mathematics, 213, 162-178 - http://dx.doi.org/10.1016/j.dam.2016.04.026

Scott, J., Ideker, T., Karp, R.M., & Sharan, R. (2006). Efficient algorithms for detecting signaling pathways in protein interaction networks. Journal of Computational Biology, 13(2), 133-144 - https://doi.org/10.1089/cmb.2006.13.133

fertin.jpg

Sélection Signaler une erreur

TUTELLES

PARTENAIRES

Destination de la recherche

Raccourcis

Voir Aussi