?. S-'il-existe-i-insertions-pour-une-couleur-c, IsDel c = IsExact c = 0 Les contraintes (6.12) et (6.13) assurent qu'il existe un i = 0 tel que nins c [i] = 1. La contrainte (6.14) est vraie car IsDel c = 0. Les contraintes (6.15) et (6.16) sont toutes les deux vraies si et seulement si nins c [i] = 1 (i ? i et i ? i)

L. Alors and . Contrainte, 18) est vraie Comme IsDel c = 0, alors la contrainte (6.19) est vraie. Ensuite, les contraintes (6.21) (?i ? 0) et (6.22) (?i + N ins ? 0)

. Premièrement and . Qu, une protéine du motif n'ayant aucun homologue dans le réseau (c'est-à-dire une couleur présente dans le motif mais qui n'apparaît pas dans le graphe) sera considérée comme une délétion dans n'importe quelle solution

D. Soit, G. De-couleurs-de-m-n-'apparaissant-pas-dans, |. Si, and . Del, alors aucune solution n'est possible pour ce motif. Sinon, les couleurs de D sont obligatoirement des délétions dans n'importe quelle solution. Par conséquent, le programme pseudo-booléen peut être lancé

C. Ensuite and G. Montré-dans, il est possible d'élaguer le graphe en supprimant certains sommets, p.14

T. Gramofone, Comparaison des temps de calculs moyens entre l'implémentation de la Proposition 4, p.152

G. .. Motif, Étude de la complexité paramétrée (sans prendre en compte les contributions de cette thèse) pour le problème EXACT, p.95

K. , L. , L. , M. Common, .. Graph et al., 110 MAXIMUM INDEPENDENT, 161 MINIMUM SUBSTITUTIONS GRAPH MOTIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 INDEX DES PROBLÈMES MINIMUM TRAVELLING SALESMAN PROBLEM, vol.185, issue.157, pp.31-43

A. Eric and P. Adam, ARKIN : Biological Networks, Current Opinion in Structural Biology, vol.13, issue.74, pp.193-202, 2003.

. Stein, B. Heather, J. Michael, C. , A. P. Davis et al., Ontology : tool for the unification of biology, Gene Nature genetics, vol.25, pp.25-29, 2000.

A. Giorgio, C. Pierluigi, G. Giorgio, K. Viggo, M. Alberto et al., Complexity and Approximation : Combinatorial Optimization Problems and Their Approximability Properties, 1999.

A. Noga, D. Phuong, H. Iman, H. Fereydoun, C. Süleyman et al., Biomolecular network motif counting and discovery by color coding, Proceedings of the 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), pp.241-249, 2008.

A. Sébastien, F. Guillaume, R. Irena, T. Annelyse, and V. Stéphane, A Pseudo-boolean Programming Approach for Computing the Breakpoint Distance Between Two Genomes with Duplicate Genes, Glenn TESLER et Dannie DURAND, éditeurs : BIBLIOGRAPHIE Proceedings of the RECOMB International Workshop Comparative Genomics (RECOMB-CG), volume 4751 de Lecture Notes in Computer Science, pp.16-29, 2007.

A. Sébastien, F. Guillaume, and R. Irena, On the Approximability of Comparing Genomes with Duplicates, Shin-Ichi NAKANO et Md. Saidur RAHMAN, éditeurs : Proceedings of the Second International Workshop Algorithms and Computation (WALCOM), volume 4921 de Lecture Notes in Computer Science, pp.34-45, 2008.

A. Sébastien, F. Guillaume, R. Irena, T. Annelyse, and V. Stéphane, On the Approximability of Comparing Genomes with Duplicates, Journal of Graph Algorithms and Applications, vol.13, issue.1, pp.19-53, 2009.

A. Jochen, G. Jens, G. Jiong, and N. Rolf, Computing the similarity of two sequences with nested arc annotations, Theoretical Computer Science, vol.312, issue.2-3, pp.337-358, 2004.

A. Noga, Y. Raphael, and Z. Uri, Color coding, Journal of the ACM, vol.42, issue.4, pp.844-856, 1995.

D. Gary and . Bader, Design and use of the Biomolecular Interaction Network Database (BIND) for Storing and Analyzing Protein-Protein Interaction Data

B. Guillaume, B. Paola, D. Riccardo, R. Romeo, and S. Florian, Complexity Insights of the Minimum Duplication Problem, Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'12), Lecture Notes in Computer Science, pp.15-181, 2012.

S. Mukul, J. Bansal, B. Gordon, E. Oliver, and W. André, Heuristics for the Gene-Duplication Problem : A ?(n) -Speed-Up for the Local Search, éditeurs : Proceedings of the 11th Annual International Conference Research in Computational Molecular Biology (RECOMB), volume 4453 de Lecture Notes in Computer Science, pp.238-252, 2007.

B. Prosenjit, J. F. Buss, and L. Anna, Pattern Matching for Permutations, Information Processing Letters, vol.65, issue.5, pp.277-283, 1998.

B. Guillaume, C. Cedric, F. Guillaume, R. Romeo, and V. Stéphane, Comparing Genomes with Duplications : A Computational Complexity Point of View, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.4, issue.4, pp.523-534, 2007.

B. Anne, C. Cedric, F. De, M. Mathieu, and R. , Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs, SIAM Journal on Discrete Mathematics, vol.22, issue.3, pp.1022-1039, 2008.

B. Anne, C. Sylvie, and R. Mathieu, The Algorithmic of Gene Teams, Proceedings of the Second International Workshop Algorithms in Bioinformatics (WABI), volume 2452 de Lecture Notes in Computer Science, pp.464-476

L. Hans, R. G. Bodlaender, M. R. Downey, . Fellows, and H. Danny, On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, pp.423-434, 2009.

S. Mukul, . Bansal, E. Oliver, and W. André, The Gene- Duplication Problem : Near-Linear Time Algorithms for NNI-Based Local Searches, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), vol.6, issue.2, pp.221-231, 2009.

B. Nadja, M. R. Fellows, K. Christian, and N. Rolf, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, Paolo FERRAGINA et Gad M. LANDAU, éditeurs : Proceedings of the 19th Annual Symposium Combinatorial Pattern Matching (CPM), pp.31-43, 2008.

B. Guillaume, F. Guillaume, M. Hafedh, R. Irena, S. Florian et al., Algorithmic Aspects of Heterogeneous Biological Networks Comparison, Weifan WANG, Xuding ZHU et Ding-Zhu DU, éditeurs : Proceedings of the 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11), volume 6831 de Lecture Notes in Computer Science, pp.272-286, 2011.

B. Guillaume, F. Guillaume, S. Florian, V. Stéphane, B. Jaroslaw et al., The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated New results on optimizing rooted triplets consistency, Sandip DAS et Ryuhei UEHARA, éditeurs : Proceedings of the Third International Workshop Algorithms and Computation (WALCOM), pp.357-368, 2009.

B. Andreas, H. Thore, K. Petteri, and K. Mikko, Fourier meets möbius : fast subset convolution

R. E. Bixby, Solving Real-World Linear Programs: A Decade and More of Progress, Operations Research, vol.50, issue.1, pp.3-15, 2002.
DOI : 10.1287/opre.50.1.3.17780

B. Sebastian, J. Katharina, M. Julia, and S. Jens, Computation of median gene clusters, Journal of Computational Biology, vol.16, issue.8, pp.1085-1099, 2009.

L. Norman, E. Biggs, L. Keith, and R. J. Wilson, Graph theory, pp.1736-1936, 1986.

B. Johannes, L. Michael, and W. Andreas, Structure and evolution of protein interaction networks : a statistical model for link dynamics and gene duplications, BMC Evolutionary Biology, vol.4, p.51, 2004.

B. Frédéric, M. Anne, L. Laurent, P. Joël, and V. Alain, Syntons, metabolons and interactons : an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data, Bioinformatics, vol.21, issue.23, pp.4209-4215, 2005.

L. Hans and . Bodlaender, Kernelization : New Upper and Lower Bound Techniques, Proceedings of the Parameterized and Exact Computation, 4th International Workshop (IWPEC), pp.17-37, 2009.

B. Sebastian, R. Florian, and S. Tamara, Annotating Fragmentation Patterns, Steven SALZBERG et Tandy WARNOW, éditeurs : Proceedings of the 9th International Workshop Algorithms in Bioinformatics (WABI), pp.13-24, 2009.

B. Guillaume, R. Romeo, S. Florian, and V. Stéphane, Minimum Mosaic Inference of a Set of Recombinants, Alex POTANIN et Taso VIGLAS, éditeurs : Proceedings of the 17th Computing : the Australasian Theory Symposium (CATS), volume 119 de CRPIT, pp.23-30, 2011.

B. Guillaume, R. Romeo, S. Florian, and V. Stéphane, Minimum Mosaic Inference of a Set of Recombinants, International Journal of Foundations of Computer Science (IJFCS), 2011.

B. David, S. David, and J. H. Nadeau, The complexity of calculating exemplar distances Comparative Genomics : Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and Evolution of Gene Families, pp.207-211, 2000.

A. Bergeron and S. Jens, On the Similarity of Sets of Permutations and Its Applications to Genome Comparison, Journal of Computational Biology, vol.13, issue.7, pp.1340-1354, 2006.
DOI : 10.1089/cmb.2006.13.1340

S. Mukul, . Bansal, and S. Ron, A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), vol.8, issue.3, pp.848-850, 2011.

B. Guillaume, S. Florian, V. I. Stéphane, . Mandoiu, N. Giri et al., Querying Protein-Protein Interaction Networks, Proceedings of the 5th International Symposium Bioinformatics Research and Applications (ISBRA)

B. Guillaume, S. Florian, and V. Stéphane, GraMoFoNe : a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks, Hisham AL-MUBAID, éditeur : Proceedings of the 2nd International Conference on Bioinformatics and Computational Biology (BICoB) International Society for Computers and their Applications (ISCA), pp.38-43, 2010.

B. Guillaume, S. Florian, and V. Stéphane, Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set Special Issue-ISBRA 2009-Bioinformatics Research and Applications, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.7, issue.4, pp.628-635, 2010.

C. Michael, B. Anastasia, B. Jeremy, K. Yungil, E. D. Spear et al., The Genetic Landscape of a Cell, Science, vol.10, issue.5964, pp.327425-431, 2010.

C. Wen-chieh, J. Gordon, B. David, F. Fernández-baca, and E. Oliver, An ILP solution for the gene duplication problem, BMC Bioinformatics, vol.12, p.14, 2011.

C. Liang-hui and C. Bor-sen, Construction of a cancer-perturbed protein-protein interaction network for discovery of apoptosis drug targets, BMC systems biology, vol.2, p.56, 2008.

C. Zhixiang, F. Bin, and Z. Binhai, The Approximability of the Exemplar Breakpoint Distance Problem, Proceedings of the Second International Conferenc Algorithmic Aspects in Information and Management (AAIM), volume 4041 de Lecture Notes in Computer Science, pp.291-302, 2006.

P. David and . Clark, Molecular Biology, pp.13-69, 2005.

C. R. Cho, L. Mark, R. Mischa, O. Van-van, and C. Manuel, The application of systems biology to drug discovery, Current Opinion in Chemical Biology, vol.10, issue.4, pp.294-302, 2006.
DOI : 10.1016/j.cbpa.2006.06.025

H. Thomas, C. E. Cormen, R. L. Leiserson, . Rivest, and S. Clifford, Introduction à l'algorithmique : cours et exercices. Dunod, seconde édition, pp.29-158, 2002.

C. Jianer, L. Songjian, S. Sing-hoi, Z. Fenghui, B. Nikhil et al., Improved algorithms for path, matching, and packing problems, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.298-307

A. Stephen and . Cook, The Complexity of Theorem-Proving Procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), pp.151-158, 1971.

H. William and . Cunningham, Decomposition of directed graphs, SIAM Journal on Algebraic and Discrete Methods, vol.3, issue.2, pp.214-228, 1982.

S. E. Calvano, X. Wenzhong, D. R. Richards, R. M. Felciano, H. V. Baker et al., A network-based analysis of systemic inflammation in humans, Nature, issue.7061, pp.4371032-1037, 2005.

D. Elias, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, Journal of Algorithms, vol.36, issue.2, pp.205-240, 2000.

D. Charles, The Origin of Species by Means of Natural Selection, pp.1859-74

D. Eugene and B. Serafim, A computational model for RNA multiple structural alignment, Theoretical Computer Science, vol.368, issue.3, pp.205-216, 2006.

E. Martin, . Dyer, and M. Alan, FRIEZE : Planar 3DM is NP-Complete, Journal of Algorithms, vol.7, issue.2, pp.174-184, 1986.

D. Riccardo, F. Guillaume, V. Stéphane, F. Giuseppe, . Italiano et al., Weak pattern matching in colored graphs : Minimizing the number of connected components, éditeurs : Proceedings of the 10th Italian Conference Theoretical Computer Science (ICTCS), pp.27-38, 2007.

D. Riccardo, F. Guillaume, V. Stéphane, D. Riccardo, F. Guillaume et al., Maximum Motif Problem in Vertex-Colored Graphs Finding Approximate and Constrained Motifs in Graphs, Proceedings of the 20th Annual Symposium Combinatorial Pattern Matching (CPM) Raffaele GIANCARLO et Giovanni MANZINI, éditeurs : Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), volume 6661 de Lecture Notes in Computer Science, pp.221-235, 2009.

D. Erik, R. A. Demaine, and . Hearn, Playing Games with Algorithms : Algorithmic Combinatorial Game Theory, de Mathematical Sciences Research Institute Publications, pp.3-56, 2009.

D. Reinhard, Graph Theory. Numéro 173 de Graduate texts in Mathematics, pp.19-84, 2005.

D. Geraldine, . Mondo, E. Damien, and R. Irena, Homogeneous decomposition of protein interaction networks : refining the description of intra-modular interactions, Bioinformatics, vol.25, issue.7, pp.926-932, 2009.

D. Irit and S. Samuel, On the Hardness of Approximating Minimum Vertex Cover, Annals of Mathematics, vol.162, 2004.

D. Banu, S. Tomer, G. Nitin, R. Eytan, B. Vineet et al., QNet : A Tool for Querying Protein Interaction Networks, éditeurs : Proceedings of the 11th Annual International Conference Research in Computational Molecular Biology (RECOMB), pp.1-15, 2007.

B. George, . Dantzig, and N. Mukund, THAPA : Linear programming 1 : introduction, pp.58-59, 1997.

D. Barbara, . Ventura, L. Caroline, M. Konstantinos, and S. Luis, From in vivo to in silico biology and back, Nature, vol.443, issue.7111, pp.527-533, 2006.

S. R. Eddy, What is dynamic programming?, Nature Biotechnology, vol.22, issue.7, pp.909-910, 2004.
DOI : 10.1038/nbt0704-909

A. M. Edwards, K. Bart, J. Ronald, G. Dov, G. Jack et al., Bridging structural biology and genomics: assessing protein interaction data with known complexes, Trends in Genetics, vol.18, issue.10, pp.529-536, 2002.
DOI : 10.1016/S0168-9525(02)02763-4

E. Evan, . Eichler, and S. David, Structural Dynamics of Eukaryotic Chromosome Evolution, Science, vol.301, issue.5634, pp.793-797, 2003.

E. Leonhard, Solutio problematis ad geometriam situs pertinentis

. A. Patricia and . Evans, Finding Common Subsequences with Arcs and Pseudoknots, Maxime CROCHEMORE et Mike PATERSON, éditeurs : Proceedings of the 10th Annual Symposium Combinatorial Pattern Matching (CPM), volume 1645 de Lecture Notes in Computer Science, pp.270-280, 1999.

. A. Patricia and . Evans, Finding Common RNA Pseudoknot Structures in Polynomial Time, Moshe LEWENSTEIN et Gabriel VALIENTE, éditeurs : Proceedings of the 17th Annual Symposium Combinatorial Pattern Matching (CPM), volume 4009 de Lecture Notes in Computer Science, pp.223-232

R. Michael and . Fellows, Parameterized Complexity : The Main Ideas and Some Research Frontiers, Peter EADES et Tadao TAKAOKA, éditeurs : Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC), volume 2223 de Lecture Notes in Computer Science, pp.291-307, 2001.

R. Michael and . Fellows, Parameterized Complexity : The Main Ideas and Connections to Practical Computing

M. , E. Meineche, and S. , Experimental Algorithmics, From Algorithm Design to Robust and Efficient Software [Dagstuhl seminar, Lecture Notes in Computer Science, pp.51-77, 2000.

R. Michael, . Fellows, F. Guillaume, H. Danny, and V. Stéphane, Sharp tractability borderlines for finding connected motifs in vertex-colored graphs, Lars ARGE, Christian CACHIN, Tomasz JURD- ZINSKI et Andrzej TARLECKI, éditeurs : Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP)

F. Jörg and G. Martin, The parameterized complexity of counting problems, SIAM Journal on Computing, vol.33, issue.4, pp.892-922, 2004.

F. Jörg and G. Martin, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, pp.37-104, 2006.

V. Fedor, . Fomin, and K. Dieter, Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, 2010.

F. Guillaume, M. Hafedh, . Babou, and R. Irena, A Patternguided Approach to compare Heterogeneous Networks, pp.2011-156

G. Serge, Exponential Time Algorithms -Structures, 2010.

G. Morris, C. John, G. William, M. , A. E. Romero-herrera et al., Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences, Systematic Zoology, vol.28, issue.2, pp.132-163, 1979.

G. Jiong, G. Jens, H. Falk, N. Rolf, and W. Sebastian, 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.

G. Deborah, I. Sorin, and C. H. Papadimitriou, Algorithmic aspects of protein structure similarity, Proceedings of the 40th Annual Symposium of Foundations of Computer Science (FOCS), pp.512-522, 1999.

R. Michael, . Garey, S. David, . W. Johnson, S. Freeman et al., Computers and Intractability : A guide to the theory of NP-completeness, pp.31-93, 1979.

G. Julien, K. Roland, B. Tewis, and C. Georg, Modular decomposition of protein-protein interaction networks

G. Anthony, K. Judith, G. Anupam, and B. Ziv, Discovering pathways by orienting edges in protein interaction networks, Nucleic Acids Research, vol.39, issue.4, pp.22-155, 2011.

. Gra76 and G. Mark, Network Sampling : Some First Steps, The American Journal of Sociology, vol.81, issue.6, pp.1287-1303, 1976.

G. Mira, S. Yuval, A. Konstantin, D. Donato, and L. Nelly, Approximating the Number of Network Motifs, Proceedings of the 6th International Workshop Algorithms and Models for the Web-Graph (WAW), pp.13-24, 2009.

G. Sylvain and S. Florian, Finding and counting vertexcolored subtrees, Petr HLINENÝ et Antonín KUCERA, éditeurs : Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10), volume 6281 de Lecture Notes in Computer Science, pp.405-416, 2010.

G. Sylvain and S. Florian, Finding and counting vertexcolored subtrees. Algorithmica Accepté pour publication, pp.114-150, 2011.

G. Iftah, S. Danny, and S. Roded, Improved Orientations of Physical Networks, éditeurs : Proceedings of the 10th International Workshop on Algorithms in Bioinformatics (WABI), volume 6293 de Lecture Notes in Bioinformatics, pp.215-225

G. Dan, Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology, pp.40-79, 1997.

H. Rose and D. Dannie, The Incompatible Desiderata of Gene Cluster Properties, Aoife MCLYSAGHT et Daniel H. HUSON, éditeurs : Proceedings of the 3rd RECOMB 2005 International Workshop Comparative Genomics Cité pages 177 et 179. [Her09] Danny HERMELIN : New Results in Parameterized Complexity Thèse de doctorat, pp.73-87, 2005.

H. Michel, F. De, M. Christophe, and P. , A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), volume 3111 de Lecture Notes in Computer Science, pp.187-198, 2004.

H. Falk, W. Sebastian, and Z. Thomas, Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection, Algorithmica, vol.52, issue.2, pp.114-132, 2008.

I. Trey and S. Roded, Protein networks in disease, Genome research, vol.18, issue.4, pp.644-652, 2008.

C. J. Jeffery, Moonlighting proteins Trends in biochemical sciences, pp.8-11, 1999.

J. Minghui, The Zero Exemplar Distance Problem, Eric TANNIER, éditeur : Proceedings of the RECOMB International Workshop Comparative Genomics (RECOMB-CG), volume 6398 de Lecture Notes in Computer Science, pp.74-82, 2010.

J. Tao, L. Guohui, M. Bin, and Z. Kaizhong, The longest common subsequence problem for arc-annotated sequences, Journal of Discrete Algorithms, vol.2, issue.2, pp.257-270, 2004.

J. Hawoong, S. P. Mason, B. Albert-laszlo, and N. Zoltan, OLTVAI : Lethality and centrality in protein networks, Nature, issue.6833, pp.411-452, 2001.

J. Hawoong, B. Tombor, A. Reka, N. Zoltan, . Oltvai et al., The large-scale organization of metabolic networks, Nature, vol.407, issue.6804, pp.651-654, 2000.

M. Richard, . W. Karp-j, R. E. Thatcher, and . Miller, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972.

R. M. Karp, Dynamic programming meets the principle of inclusion and exclusion, Operations Research Letters, vol.1, issue.2, pp.49-51, 1982.
DOI : 10.1016/0167-6377(82)90044-X

K. George, A better approximation ratio for the vertex cover problem, ACM Transactions on Algorithms, vol.541, issue.4, pp.1-41

K. Maxim, B. Vineet, and S. Roded, Fast and Accurate Alignment of Multiple Protein Networks, Proceedings of the 12th Annual International Conference Research in Computational Molecular Biology (RECOMB), pp.246-256, 2008.

D. John, . Kececioglu, and G. Dan, Reconstructing a History of Recombinations From a Set of Sequences, Discrete Applied Mathematics, vol.88, issue.1-3, pp.239-260, 1998.

K. Mehmet, G. Ananth, S. Wojciech, M. Satoru, J. P. Mesirov et al., Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution, éditeurs : Proceedings of the 9th Annual International Conference Research in Computational Molecular Biology (RECOMB), Lecture Notes in Computer Science, pp.48-65, 2005.

K. Hiroaki, Systems Biology : A Brief Overview, Science, vol.295, issue.5560, pp.1662-1664, 2002.

K. Joachim, M. Daniel, R. Stefan, and R. Peter, Divide-and-Color, Fedor V. FOMIN, éditeur : Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 4271 de Lecture Notes in Computer Science, pp.58-67

E. Donald and . Knuth, Big Omicron and big Omega and big Theta, SIGACT News, vol.8, issue.2, pp.18-24, 1976.

K. Ioannis, A. Luca, D. Ivan, L. Ann, G. et al., Faster Algebraic Algorithms for Path and Packing Problems, éditeurs : Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp.575-586, 2008.

K. Mikko, R. Pasi, U. Esko, K. Juhani, H. A. Maurer et al., Recombination Systems éditeurs : Theory Is Forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, Lecture Notes in Computer Science, vol.3113, pp.159-169, 2004.

K. Marcin, R. Romeo, V. Stéphane, and W. Tomasz, Approximation of RNA Multiple Structural Alignment

B. P. Kelley, S. Roded, R. M. Karp, S. Taylor, 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 of the USA, pp.11394-11399, 2003.
DOI : 10.1073/pnas.1534710100
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC208768

K. Jon and T. Éva, Algorithm Design, 2005.

K. Ioannis, W. Ryan, A. Susanne, A. Marchetti-spaccamela, M. Yossi et al., Limits and Applications of Group Algebras for Parameterized Problems, éditeurs : Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP)

L. Daniel, . Berre, and P. Anne, On extending SAT solvers for PB problems, Proceedings of the 14th RCRA workshop Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA), 2007.

L. Insuk, S. V. Date, A. T. Adai, and E. M. Marcotte, A probabilistic functional network of yeast genes, Science, vol.306, pp.1555-1558, 2004.

. A. Leonid and . Levin, Universal sorting problems, Problemy Predaci Informacii, vol.9, issue.3, pp.265-266, 1973.

L. Vincent, C. G. Fernandes, and S. Marie-france, Motif search in graphs : application to metabolic networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.3, issue.90, pp.360-368, 2006.

L. Chung-shou, L. Kanghao, B. Michael, S. Rohit, and B. Bonnie, IsoRankN : spectral methods for global alignment of multiple protein networks, Bioinformatics, vol.25, issue.12, pp.253-258, 2009.

S. Mark, M. J. Longo, R. J. Neill, and . Neill, Abundant Human DNA Contamination Identified in Non-Primate Genome Databases, PLoS ONE, vol.6, issue.2, p.16410, 2011.

L. Antoni and V. Gabriel, On the Maximum Common Embedded Subtree Problem for Ordered Trees King's College London Publications, éditeurs : String Algorithmics, pp.155-169, 2004.

M. Alexander, B. Vineet, Z. Uri, and S. Roded, An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks, éditeurs : Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI), pp.222-232, 2008.

M. Bin, L. Ming, and Z. Louxin, From Gene Trees to Species Trees, SIAM Journal on Computing, vol.30, issue.3, pp.729-752, 2000.

M. David, Carl Woese and New Perspectives on Evolution, NASA Astrobiology Institute, 2003.

R. H. Möhring and F. J. Radermacher, Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization, Annals of Discrete Mathematics, vol.19, pp.257-355, 1984.
DOI : 10.1016/S0304-0208(08)72966-9

M. Hamish, V. Franck, G. Mickael, L. Weizhong, N. Menaka et al., Web services at the European Bioinformatics Institute-2009, Nucleic acids research, vol.37, pp.6-10, 2009.

M. Mathias, W. Sebastian, and B. Rolf, Lifting Prediction to Alignment of RNA Pseudoknots, Serafim BATZOGLOU, éditeur : Proceedings of the 13th Annual International Conference Research in Computational Molecular Biology (RECOMB), volume 5541 de Lecture Notes in Computer Science, pp.285-301, 2009.

M. Jochen, W. Tim, and K. Tobias, Decision support for team staffing : An automated relational recommendation approach, Decision Support Systems, vol.45, issue.3, pp.429-447, 2008.

N. Jesper, A. Susanne, A. Marchetti-spaccamela, M. Yossi, E. Sotiris et al., Fast Polynomial-Space Algorithms Using Möbius Inversion : Improving on Steiner Tree and Related Problems, éditeurs : Proceedings of the 36th International Colloquium Automata, Languages and Programming (ICALP)

H. Joseph, . Nadeau, A. Benjamin, and . Taylor, Lengths of chromosomal segments conserved since divergence of man and mouse, Proceedings of the National Academy of Sciences of the United States of America, vol.81, issue.3, pp.814-818, 1984.

O. Aïda, M. Krister, . Swenson, and C. Cedric, An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model, Eric TANNIER, éditeur : Proceedings of the RECOMB International Workshop Comparative Genomics (RECOMB-CG), volume 6398 de Lecture Notes in Computer Science, pp.290-301, 2010.

P. Christophe, Aspects algorithmiques de la décomposition modulaire. Habilitation à diriger des recherches, 2006.

P. Sophie, A. Bergeron, R. Jean-loup, L. Alexandra, O. Emmanuelle et al., Identification of genomic features using microsyntenies of domains : Domain teams, Genome Research, vol.15, issue.6, pp.867-874, 2005.

. A. Pavel and . Pevzner, Bio-informatique Moléculaire. Une approche algorithmique, pp.66-79, 2006.

P. Annick, L. Dominique, and M. Joël, La lactoferrine : une protéine multifonctionnellen, Médecine sciences, pp.361-369, 2009.

Y. Prylzu05-]-ron, . Pinter, R. Oleg, Y. Esti, and Z. Michal, Alignment of metabolic pathways, Bioinformatics, vol.21, issue.16, pp.3401-3408, 2005.

H. Christos, . Papadimitriou, and Y. Mihalis, Optimization, approximation and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.

R. Andrea, B. Christian, O. Sigeru, R. Miguel, B. José et al., Tabu Search for the Founder Sequence Reconstruction Problem : A Preliminary Study, éditeurs : Proceedings of the 10th International Work-Conference on Artificial Neural Networks (IWANN), volume 5518 de Lecture Notes in Computer Science, pp.1035-1042, 2009.

R. Sven, W. Gunnar, B. Klau-philipp, M. E. Bernard, and . Moret, Integer Linear Programs for Discovering Approximate Gene Clusters, éditeurs : Proceedings of the 6th International Workshop Algorithms in Bioinformatics (WABI), volume 4175 de Lecture Notes in Computer Science, pp.298-309, 2006.

R. Ran and S. Shmuel, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC), pp.475-484, 1997.

R. Erzsebet, A. L. Somera, D. A. Mongru, N. Zoltan, . Oltvai et al., Hierarchical Organization of Modularity in Metabolic Networks, Science, vol.297, issue.5586, pp.1551-1555, 2002.

A. Bruce, . Reed, S. Kaleigh, and V. Adrian, Finding odd cycle transversals, Operations Research Letters, vol.32, issue.4, pp.299-301, 2004.

R. Pasi and U. Esko, Haplotype Inference Via Hierarchical Genotype Parsing, Raffaele GIANCARLO et Sridhar HANNENHALLI, éditeurs : Proceedings of the 7th International Workshop Algorithms in Bioinformatics (WABI), pp.85-97, 2007.

S. David, Genome rearrangement with gene families, Bioinformatics, vol.15, issue.11, pp.909-917, 1999.

W. David, . Staple, E. Samuel, and . Butcher, Pseudoknots : RNA structures with diverse functions, PLoS biology, vol.3, issue.6, pp.956-959, 2005.

S. Damian, H. Syed, B. Benoit, H. Richard, L. Darin et al., BioMart biological queries made easy, BMC genomics, vol.10, p.22, 2009.

S. Roded and I. Trey, Modeling cellular machinery through biological network comparison, Nature biotechnology, vol.24, issue.80, pp.427-433, 2006.

S. Jacob, I. Trey, R. M. Karp, and S. Roded, Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks, Journal of Computational Biology, vol.13, issue.2, pp.133-144, 2006.

S. Steven and . Skiena, The Algorithm Design Manual Incorporated, second édition, pp.29-30, 2008.

S. Sophie, L. Vincent, and S. Marie-france, Assessing the exceptionality of coloured motifs in networks, EURASIP Journal on Bioinformatics and Systems Biology, pp.1-9, 2009.

S. Paul, M. Andrew, O. Owen, N. S. Baliga, J. T. Wang et al., Cytoscape : A Software Environment for Integrated Models of Biomolecular Interaction Networks, Genome Research, vol.13, pp.2498-2504, 2003.

S. Steffen, S. Shamil, B. Peer, and D. Thomas, Metabolites : a helping hand for pathway evolution ?, TRENDS in Biochemical Sciences, vol.28, issue.6, pp.336-341, 2003.

S. Roded, S. Silpa, R. M. Kelley, K. Tanja, M. Scott et al., Conserved patterns of protein interaction in multiple species, Proceedings of the National Academy of Sciences of the USA, pp.1974-1979, 2005.

S. Eran, S. Michael, R. Aviv, P. Dana, B. David et al., Module networks : identifying regulatory modules and their condition-specific regulators from gene expression data, Nature genetics, vol.34, issue.2, pp.166-176, 2003.

S. Tomer, S. Daniel, R. Eytan, and S. Roded, QPath : a method for querying pathways in a protein-protein interaction network, BMC Bioinformatics, vol.7, p.199, 2006.

S. Ulrike, K. H. Frank, . Dehne, G. Arvind, S. Jörg-rüdiger et al., Gene Trees and Species Trees : The Gene-Duplication Problem is Fixed-Parameter Tractable, éditeurs : Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS), volume 1663 de Lecture Notes in Computer Science, pp.288-293, 1999.

]. The11, . The, and . Consortium, Ongoing and future developments at the Universal Protein Resource, Nucleic Acids Research, vol.39

T. Stéphan, A quadratic kernel for feedback vertex set, Claire MATHIEU, éditeur : Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.115-119, 2009.

T. Cam, Y. C. Nguyen, . Tay, and Z. Louxin, Divide-and-conquer approach for the exemplar breakpoint distance, Bioinformatics, vol.21, issue.10, pp.2171-2176, 2005.

U. Takeaki and Y. Mutsunori, Fast Algorithms to Enumerate All Common Intervals of Two Permutations, Algorithmica, vol.26, issue.2, pp.290-309, 2000.

V. Vijay and . Vazirani, Algorithmes d'approximation, pp.54-57, 2007.

V. Gabriele and W. H. Mcclain, The G-U wobble base pair. A fundamental building block of RNA structure crucial to RNA function in diverse biological systems, EMBO Reports, vol.1, issue.1, pp.18-23, 2000.

M. Christian-von, K. Roland, S. Berend, C. Michael, S. G. Oliver et al., Comparative assessment of large-scale data sets of protein-protein interactions, Nature, issue.6887, pp.417399-403, 2002.

W. Yufeng and G. Dan, Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants, Bin MA et Kaizhong ZHANG, éditeurs : Proceedings of the 18th Annual Symposium Combinatorial Pattern Matching (CPM), pp.150-161, 2007.

W. Ryan, Finding paths of length k in O * (2 k ) time, Information Processing Letters, vol.109, issue.6, pp.315-318, 2009.

J. Gerhard, J. Michael, R. Gerhard, and R. Giovanni, Exact Algorithms for NP-Hard Problems : A Survey, éditeurs : Combinatorial Optimization -Eureka, You Shrink !

W. Yufeng, Bounds on the Minimum Mosaic of Population Sequences under Recombination, Amihood AMIR et Laxmi PARIDA, éditeurs : Proceedings of the 21st Annual Symposium Combinatorial Pattern Matching (CPM), volume 6129 de Lecture Notes in Computer Science, pp.152-163

Y. Xiao and A. Srinivas, An Improved Model for Gene Cluster Inference, Hisham AL-MUBAID, éditeur : Proceedings of the ISCA 2nd International Conference on Bioinformatics and Computational Biology (BICoB), pp.190-195, 2010.

Y. Xiao, S. Florian, B. Guillaume, H. Sylvie, R. Romeo et al., An Algorithmic View on Multi-relatedsegments : a new unifying model for approximate common interval, pp.15-177, 2011.

Z. Mikhail, F. R. Bach, and V. Jean-philippe, Global alignment of protein-protein interaction networks by graph matching methods, Bioinformatics, vol.25, issue.12, pp.259-267, 2009.

Z. David, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Theory of Computing, pp.103-128, 2007.