English
Le problème Graph Motif - Partie 1
Post-edited
Auteurs : Fertin, Guillaume (Auteur de la conférence)
CIRM (Editeur )
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/
CIRM (Editeur )
Loading the player...
|
| pattern matching biological networks Graph Motif problem NP-complete problem reduction (NP-hardness proof) fixed-parameter tractability computational complexity |
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 : (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.
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, GuillaumeLangue : Français Date de Publication : 30/03/17 Date de Captation : 22/03/17 Collection : Ecoles de recherche Sous Collection : Research School Catégorie arXiv : Combinatorics ; Computer Science Domaine(s) : Informatique ; Combinatoires ; Mathématiques pour les Sciences & Technologies Format : MP4 (.mp4) - HD Durée : 01:08:53 Audience : Chercheurs ; Etudiants Science Cycle 2 Download : https://videos.cirm-math.fr/2017-03-22_Fertin_part1.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : ALEA Days / Journées ALEAOrganisateurs 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.19145503Citer cette vidéo: Fertin, Guillaume (2017). Le problème Graph Motif - Partie 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19145503 URI : http://dx.doi.org/10.24350/CIRM.V.19145503 |
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.
- [Multi angle] Le problème Graph Motif - Partie 2 / 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
