F Nous contacter


0

Post-edited Le problème Graph Motif - Partie 1

Auteurs : Fertin, Guillaume (Auteur de la Conférence)
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 :
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 : Français
    Date de publication : 30/03/17
    Date de captation : 22/03/17
    Collection : Research School
    Format : MP4 (.mp4) - HD
    Durée : 01:08:53
    Domaine : Computer Science ; Combinatorics ; Mathematics in Science & Technology
    Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctorants , Post - Doctorants
    Download : http://videos.cirm-math.fr/2017-03-22_Fertin_part1.mp4

Informations sur la rencontre

Nom du congrès : ALEA Days / Journées ALEA
Organisteurs Congrès : Gerin, Lucas ; Pierrot, Adeline ; Gittenberger, Bernhard
Dates : 20/03/17 - 24/03/17
Année de la rencontre : 2017
URL Congrès : http://scientific-events.weebly.com/1590.html

Citation Data

DOI : 10.24350/CIRM.V.19145503
Cite 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

Voir aussi

Bibliographie

  1. 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

  2. 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

  3. 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

  4. 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. <hal-00425661> - https://hal.archives-ouvertes.fr/hal-00425661

  5. 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

  6. 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

  7. 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

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

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

  10. 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

  11. 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

  12. 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

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

  14. 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

  15. 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

  16. 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

  17. 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&#

  18. 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

  19. 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



Z