Français
Le problème Graph Motif - Partie 1
Post-edited
Authors : Fertin, Guillaume (Author of the conference)
CIRM (Publisher )
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
Additional resources :
http://gt-alea.math.cnrs.fr/alea2017/slides/GuillaumeFertinCours-ALEA2017.pdf
http://fpt.wikidot.com/
CIRM (Publisher )
Loading the player...
|
| pattern matching biological networks Graph Motif problem NP-complete problem reduction (NP-hardness proof) fixed-parameter tractability computational complexity |
Abstract :
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.
MSC Codes : (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
Additional resources :
http://gt-alea.math.cnrs.fr/alea2017/slides/GuillaumeFertinCours-ALEA2017.pdf
http://fpt.wikidot.com/
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : French Available date : 30/03/17 Conference Date : 22/03/17 Subseries : Research School arXiv category : Combinatorics ; Computer Science Mathematical Area(s) : Computer Science ; Combinatorics ; Mathematics in Science & Technology Format : MP4 (.mp4) - HD Video Time : 01:08:53 Targeted Audience : Researchers ; Graduate Students Download : https://videos.cirm-math.fr/2017-03-22_Fertin_part1.mp4 
|
Information on the Event
Event Title : ALEA Days / Journées ALEAEvent Organizers : Gerin, Lucas ; Pierrot, Adeline ; Gittenberger, Bernhard Dates : 20/03/17 - 24/03/17 Event Year : 2017 Event URL : http://conferences.cirm-math.fr/1590.html
Citation Data
DOI : 10.24350/CIRM.V.19145503Cite this video as: 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 |
See Also
- [Multi angle] Random cubic planar graphs revisited / Author of the conference Rué, Juanjo.
- [Multi angle] Une histoire de mots inattendus et de génomes / Author of the conference Schbath, Sophie.
- [Multi angle] Processus de Pólya à valeur mesure / Author of the conference Mailler, Cécile.
- [Multi angle] Le problème Graph Motif - Partie 2 / Author of the conference Fertin, Guillaume.
Bibliography
- 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
