G. Blin, F. Sikora, and S. Vialette, Querying Protein-Protein Interaction Networks, 5th International Symposium on Bioinformatics Research and Applications, pp.52-62, 2009.
DOI : 10.1093/nar/30.1.303
URL : https://hal.archives-ouvertes.fr/hal-00620391

B. Dost, T. Shlomi, N. Gupta, E. Ruppin, V. Bafna et al., QNet: A Tool for Querying Protein Interaction Networks, pp.1-15, 2007.

A. Gavin and M. Boshe, Functional organization of the yeast proteome by systematic analysis of protein complexes, Nature, vol.415, issue.6868, pp.141-147, 2002.
DOI : 10.1038/415141a

Y. Ho and A. Gruhler, Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry, Nature, vol.415, issue.6868, pp.180-183, 2002.
DOI : 10.1038/415180a

P. Uetz and L. Giot, A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisae, Nature, vol.403, issue.6770, pp.623-627, 2000.

T. Reguly, A. Breitkreutz, L. Boucher, B. Breitkreutz, G. Hon et al., Comprehensive curation and analysis of global interaction networks in saccharomyces cerevisiae, Journal of Biology, 2006.

M. Pellegrini, E. Marcotte, M. Thompson, D. Eisenberg, and T. Yeates, Assigning protein functions by comparative genome analysis: Protein phylogenetic profiles, Proceedings of the National Academy of Sciences, vol.96, issue.8, pp.4285-4288, 1999.
DOI : 10.1073/pnas.96.8.4285

M. Garey and D. Johnson, Computers and Intractability: a guide to the theory of NP-completeness, 1979.

B. Kelley, R. Sharan, R. Karp, T. Sittler, D. E. Root et al., Conserved pathways within bacteria and yeast as revealed by global protein network alignment, Proceedings of the National Academy of Sciences, vol.100, issue.20, pp.11-394, 2003.
DOI : 10.1073/pnas.1534710100
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC208768

T. Shlomi, D. Segal, E. Ruppin, and R. Sharan, QPath: a method for querying pathways in a protein-protein interaction network, BMC Bioinformatics, vol.7, issue.1, p.199, 2006.
DOI : 10.1186/1471-2105-7-199

N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of the ACM, vol.42, issue.4, pp.844-856, 1995.
DOI : 10.1145/210332.210337

R. Pinter, O. Rokhlenko, E. Yeger-lotem, and M. Ziv-ukelson, Alignment of metabolic pathways, Bioinformatics, vol.21, issue.16, pp.3401-3408, 2005.
DOI : 10.1093/bioinformatics/bti554

H. Bodlaender, A tourist guide through treewidth, Acta Cybernetica, vol.11, pp.1-23, 1993.

S. Arnborg, D. Corneil, and A. Proskurowski, -Tree, SIAM Journal on Algebraic Discrete Methods, vol.8, issue.2, pp.277-284, 1987.
DOI : 10.1137/0608024

Q. Cheng, P. Berman, R. Harrison, and A. Zelikovsky, Fast Alignments of Metabolic Networks, 2008 IEEE International Conference on Bioinformatics and Biomedicine, pp.147-152, 2008.
DOI : 10.1109/BIBM.2008.75

R. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972.

J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, vol.72, issue.8, pp.1386-1396, 2006.
DOI : 10.1016/j.jcss.2006.02.001

S. Thomasse, A quadratic kernel for feedback vertex set, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
DOI : 10.1137/1.9781611973068.13
URL : https://hal.archives-ouvertes.fr/lirmm-00394595

S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman, Basic local alignment search tool, Journal of Molecular Biology, vol.215, issue.3, pp.403-410, 1990.
DOI : 10.1016/S0022-2836(05)80360-2

J. Scott, T. Ideker, R. Karp, and R. Sharan, Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks, Journal of Computational Biology, vol.13, issue.2, pp.133-144, 2006.
DOI : 10.1089/cmb.2006.13.133

S. Bruckner, F. Hüffner, R. Karp, R. Shamir, and R. Sharan, Topology-free querying of protein interaction networks, Proc. 13th Annual International Conference on Computational Molecular Biology (RECOMB), p.74, 2009.

H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal, vol.51, issue.3, 2007.
DOI : 10.1093/comjnl/bxm037

I. Xenarios, L. Salwinski, X. Duan, P. Higney, S. Kim et al., DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions, Nucleic Acids Research, vol.30, issue.1, p.303, 2002.
DOI : 10.1093/nar/30.1.303

P. Dent, A. Yacoub, P. Fisher, M. Hagan, and S. Grant, MAPK pathways in radiation responses, Oncogene, vol.22, issue.37, pp.5885-5896, 2003.
DOI : 10.1038/sj.onc.1206701

M. Kanehisa, S. Goto, S. Kawashima, Y. Okuno, and M. Hattori, The KEGG resource for deciphering the genome, Nucleic Acids Research, vol.32, issue.90001, pp.277-280, 2004.
DOI : 10.1093/nar/gkh063

F. Huffner, S. Wernicke, and T. Zichner, ALGORITHM ENGINEERING FOR COLOR-CODING TO FACILITATE SIGNALING PATHWAY DETECTION, Proceedings of the 5th Asia-Pacific Bioinformatics Conference, 2007.
DOI : 10.1142/9781860947995_0030

M. Fellows, Parameterized complexity: new developments and research frontiers, Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra: Mathematics Workshop, p.51, 2000.
DOI : 10.1515/9783110889178.51

V. Lacroix, C. Fernandes, and M. Sagot, Motif Search in Graphs: Application to Metabolic Networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.3, issue.4, pp.360-368, 2006.
DOI : 10.1109/TCBB.2006.55
URL : https://hal.archives-ouvertes.fr/hal-00427984

M. Fellows, G. Fertin, D. Hermelin, and S. Vialette, Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs, Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP), pp.340-351, 2007.
DOI : 10.1007/978-3-540-73420-8_31
URL : https://hal.archives-ouvertes.fr/hal-00417928

N. Betzler, M. Fellows, C. Komusiewicz, and R. Niedermeier, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, Proc. 19th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.31-43, 2008.
DOI : 10.1007/978-3-540-69068-9_6

R. Dondi, G. Fertin, and S. Vialette, WEAK PATTERN MATCHING IN COLORED GRAPHS: MINIMIZING THE NUMBER OF CONNECTED COMPONENTS, Theoretical Computer Science, pp.27-38, 2007.
DOI : 10.1142/9789812770998_0007
URL : https://hal.archives-ouvertes.fr/hal-00417910

G. Blin, F. Sikora, and S. Vialette, GraMoFoNe: a cytoscape plugin for querying motifs without topology in protein-protein interactions networks, 2nd International Conference on Bioinformatics and Computational Biology (BICoB-2010). International Society for Computers and their Applications (ISCA), 2010.
URL : https://hal.archives-ouvertes.fr/hal-00425661

S. Schbath, V. Lacroix, and M. Sagot, Assessing the exceptionality of coloured motifs in networks, EURASIP Journal on Bioinformatics and Systems Biology, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00428313

F. Sikora and . Ph, D. student in the LIGM at Université Paris-Est -France. He received his Master Degree from the Université Paris-Est in 2008. His research interests include algorithmics in computational biology and more especially fixed parameter tractable algorithms
URL : https://hal.archives-ouvertes.fr/ujm-00355959