J. Alber, J. Gramm, J. Guo, and R. Niedermeier, Towards Optimally Solving the Longest Common SubsequenceProblem for Sequences with Nested Arc Annotations in Linear Time, Proc. 13th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.99-114, 2002.
DOI : 10.1007/3-540-45452-7_10

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

A. M. Ambalath, R. Balasundaram, H. , C. R. Koppula, V. Misra et al., On the Kernelization Complexity of Colorful Motifs, Accepted at the 5th International Symposium on Parameterized and Exact Computation, 2010.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

A. Amir, L. Gasieniec, S. , and R. , Improved approximate common interval, Information Processing Letters, vol.103, issue.4, pp.142-149, 2007.
DOI : 10.1016/j.ipl.2007.03.006

S. Angibaud, G. Fertin, I. Rusu, A. Thévenin, and S. Vialette, A Pseudo-boolean Programming Approach for Computing the Breakpoint Distance Between Two Genomes with Duplicate Genes, Proc. 5th RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG), pp.16-29, 2007.
DOI : 10.1007/978-3-540-74960-8_2
URL : https://hal.archives-ouvertes.fr/hal-00417902

S. Angibaud, G. Fertin, I. Rusu, A. Thévenin, and S. Vialette, On the Approximability of Comparing Genomes with Duplicates, Journal of Graph Algorithms and Applications, vol.13, issue.1, pp.19-53, 2009.
DOI : 10.7155/jgaa.00175
URL : https://hal.archives-ouvertes.fr/hal-00159893

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

A. Bergeron, C. Chauve, F. De-montgolfier, and M. Raffinot, Permutations, with Applications to Modular Decomposition of Graphs, SIAM Journal on Discrete Mathematics, vol.22, issue.3, pp.1022-1039, 2008.
DOI : 10.1137/060651331
URL : https://hal.archives-ouvertes.fr/hal-00159580

A. Bergeron, C. Chauve, and Y. Gingras, Bioinformatics Algorithms: Techniques and Applications, pp.177-202, 2008.

A. Bergeron, S. Corteel, and M. Raffinot, The Algorithmic of Gene Teams, Proceedings of WABI 2002, pp.464-476, 2002.
DOI : 10.1007/3-540-45784-4_36

A. Bergeron, S. Heber, and J. Stoye, Common intervals and sorting by reversals: a marriage of necessity, Bioinformatics, vol.18, issue.Suppl 2, pp.54-63, 2002.
DOI : 10.1093/bioinformatics/18.suppl_2.S54

A. Bergeron and J. Stoye, 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

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

G. Blin, E. Blais, P. Guillon, M. Blanchette, and N. Mabrouk, Inferring Gene Orders from Gene Maps Using the Breakpoint Distance, Proc. 4th RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG), pp.99-112, 2006.
DOI : 10.1007/11864127_9
URL : https://hal.archives-ouvertes.fr/hal-00620364

G. Blin, E. Blais, D. Hermelin, P. Guillon, M. Blanchette et al., Gene Maps Linearization Using Genomic Rearrangement Distances, Journal of Computational Biology, vol.14, issue.4, pp.394-407, 2007.
DOI : 10.1089/cmb.2007.A002
URL : https://hal.archives-ouvertes.fr/hal-00619755

G. Blin, P. Bonizzoni, R. Dondi, R. Rizzi, F. M. Sikora et al., Complexity Insights of the Minimum Duplication Problem, 38th International Conference on Current Trends in Theory and Practice of Computer Science Spindler?vSpindler?Spindler?v Mí yn, pp.153-164, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00629047

G. Blin, P. Bonizzoni, R. Dondi, and F. Sikora, On the parameterized complexity of the repetition free longest common subsequence problem, Information Processing Letters, vol.112, issue.7, 2012.
DOI : 10.1016/j.ipl.2011.12.009
URL : https://hal.archives-ouvertes.fr/hal-00637255

G. Blin, L. Bulteau, M. Jiang, P. Tejada, and S. Vialette, Longest common subsequences for bounded run lengths, Proc. 23th Annual Symposium on Combinatorial Pattern Matching (CPM), 2012.
DOI : 10.1007/978-3-642-31265-6_11
URL : https://hal-upec-upem.archives-ouvertes.fr/hal-00683311/file/hal.pdf

G. Blin, C. Chauve, and G. Fertin, The breakpoint distance for signed sequences, Proc. 1st Algorithms and Computational Methods for Biochemical and Evolutionary Networks (Comp- BioNets), pp.3-16, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00620356

G. Blin, C. Chauve, and G. Fertin, Genes Order and Phylogenetic Reconstruction: Application to ??-Proteobacteria, Proc. 3rd RECOMB Comparative Genomics Satellite Workshop, pp.11-20, 2005.
DOI : 10.1007/11554714_2
URL : https://hal.archives-ouvertes.fr/hal-00620362

G. Blin, C. Chauve, G. Fertin, R. Rizzi, and S. Vialette, 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.
DOI : 10.1109/TCBB.2007.1069
URL : https://hal.archives-ouvertes.fr/hal-00417720

G. Blin, M. Crochemore, S. Hamel, and S. Vialette, Finding the median of three permutations under the Kendall-Tau distance, Proc. 7th annual international conference on Permutation Patterns, p.6, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00620459

G. Blin, A. Denise, S. Dulucq, C. Herrbach, and H. Touzet, Alignments of RNA Structures, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.7, issue.2, pp.309-322, 2010.
DOI : 10.1109/TCBB.2008.28
URL : https://hal.archives-ouvertes.fr/hal-00506348

G. Blin, D. Faye, and J. Stoye, Finding Nested Common Intervals Efficiently, Journal of Computational Biology, vol.17, issue.9, pp.1183-1194, 2010.
DOI : 10.1089/cmb.2010.0089
URL : https://hal.archives-ouvertes.fr/hal-00620365

G. Blin, G. Fertin, D. Hermelin, and S. Vialette, Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints, Proc. 31st International Workshop International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.271-282, 2005.
DOI : 10.1007/11604686_24
URL : https://hal.archives-ouvertes.fr/hal-00620363

G. Blin, G. Fertin, D. Hermelin, and S. Vialette, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Journal of Discrete Algorithms, vol.6, issue.4, pp.618-626, 2008.
DOI : 10.1016/j.jda.2008.03.004
URL : https://hal.archives-ouvertes.fr/hal-00620363

G. Blin, G. Fertin, G. Herry, and S. Vialette, Comparing RNA Structures: Towards an Intermediate Model Between the Edit and the Lapcs Problems, 1st Brazilian Symposium on Bioinformatics, pp.101-112, 2007.
DOI : 10.1007/978-3-540-73731-5_10
URL : https://hal.archives-ouvertes.fr/hal-00417918

G. Blin, G. Fertin, G. Herry, and S. Vialette, Comparing RNA Structures: Towards an Intermediate Model Between the Edit and the Lapcs Problems, 1st Brazilian Symposium on Bioinformatics (BSB), pp.101-112, 2007.
DOI : 10.1007/978-3-540-73731-5_10
URL : https://hal.archives-ouvertes.fr/hal-00417918

G. Blin, G. Fertin, H. Mohamed-babou, I. Rusu, F. Sikora et al., Algorithmic Aspects of Heterogeneous Biological Networks Comparison, 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11), pp.272-286, 2011.
DOI : 10.1007/978-3-642-22616-8_22
URL : https://hal.archives-ouvertes.fr/hal-00606375

G. Blin, G. Fertin, R. Rizzi, and S. Vialette, What makes the arc-preserving subsequence problem hard ? T, Comp. Sys. Biology, vol.2, pp.1-36, 2005.

G. Blin, G. Fertin, R. Rizzi, and S. Vialette, What Makes the Arc-Preserving Subsequence Problem Hard?, Proc Int. Workshop on Bioinformatics Research and Applications (IWBRA), pp.860-868, 2005.
DOI : 10.1007/11428848_110
URL : https://hal.archives-ouvertes.fr/hal-00417738

G. Blin, G. Fertin, I. Rusu, and C. Sinoquet, Extending the Hardness of RNA Secondary Structure Comparison, 1st intErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental methodologies, pp.140-151, 2007.
DOI : 10.1007/978-3-540-74450-4_13
URL : https://hal.archives-ouvertes.fr/hal-00418248

G. Blin, G. Fertin, F. Sikora, and S. Vialette, The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated, Proc. 3rd Annual Workshop on Algorithms and Computation (WALCOM'09), pp.357-368, 2009.
DOI : 10.1093/bioinformatics/15.11.909
URL : https://hal.archives-ouvertes.fr/hal-00416491

G. Blin, G. Fertin, and S. Vialette, New Results for the 2-Interval Pattern Problem, Proc. 15th Annual Symposium on Combinatorial Pattern Matching (CPM), 2004.
DOI : 10.1007/978-3-540-27801-6_23
URL : https://hal.archives-ouvertes.fr/hal-00620366

G. Blin, G. Fertin, and S. Vialette, New Results for the 2-Interval Pattern Problem, Proc. 15th Combinatorial Pattern Matching (CPM), pp.311-322, 2004.
DOI : 10.1007/978-3-540-27801-6_23
URL : https://hal.archives-ouvertes.fr/hal-00620366

G. Blin, G. Fertin, and S. Vialette, What makes the arc-preserving subsequence problem hard ?, LNCS Transactions on Computational Systems Biology, vol.2, pp.1-36, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00417738

G. Blin, G. Fertin, and S. Vialette, Extracting constrained 2-interval subsets in 2-interval sets, Theoretical Computer Science, vol.385, issue.1-3, pp.1-3241, 2007.
DOI : 10.1016/j.tcs.2007.07.002
URL : https://hal.archives-ouvertes.fr/hal-00417717

G. Blin, S. Hamel, and S. Vialette, Comparing RNA Structures with Biologically Relevant Operations Cannot Be Done without Strong Combinatorial Restrictions, 4th Workshop on Algorithms and Computation (WALCOM'10), pp.149-160, 2010.
DOI : 10.1007/978-3-642-11440-3_14
URL : https://hal.archives-ouvertes.fr/hal-00620327

G. Blin and R. Rizzi, Conserved Interval Distance Computation Between Non-trivial Genomes, Proc. 11th Annual Int. Conference on Computing and Combinatorics (COCOON), pp.22-31, 2005.
DOI : 10.1007/11533719_5
URL : https://hal.archives-ouvertes.fr/hal-00620353

G. Blin, R. Rizzi, F. Sikora, and S. Vialette, MINIMUM MOSAIC INFERENCE OF A SET OF RECOMBINANTS, International Journal of Foundations of Computer Science, vol.24, issue.01, 2011.
DOI : 10.1142/S0129054113400042
URL : https://hal.archives-ouvertes.fr/hal-00679269

G. Blin, R. Rizzi, F. Sikora, and S. Vialette, MINIMUM MOSAIC INFERENCE OF A SET OF RECOMBINANTS, 17th Computing: the Australasian Theory Symposium (CATS'11), pp.23-30, 2011.
DOI : 10.1142/S0129054113400042
URL : https://hal.archives-ouvertes.fr/hal-00679269

G. Blin, R. Rizzi, and S. Vialette, A Faster Algorithm for Finding Minimum Tucker Submatrices, 6th Computability in Europe (CiE'10), pp.69-77, 2010.
DOI : 10.1007/978-3-642-13962-8_8
URL : https://hal.archives-ouvertes.fr/hal-00620380

G. Blin, R. Rizzi, and S. Vialette, A polynomial-time algorithm for finding minimal conflicting sets, Proc. 6th International Computer Science Symposium in Russia (CSR), volume 6651 of Lecture Notes in Computer Science, pp.373-384, 2011.

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

G. Blin, F. Sikora, and S. Vialette, GraMoFoNe: a cytoscape plugin for querying motifs without topology in protein-protein interactions networks, International Society for Computers and their Applications (ISCA), pp.38-43, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00425661

G. Blin, F. Sikora, and S. Vialette, Querying Graphs in Protein-Protein Interactions Networks Using Feedback Vertex Set, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.7, issue.4, pp.628-635, 2010.
DOI : 10.1109/TCBB.2010.53
URL : https://hal.archives-ouvertes.fr/hal-00619763

G. Blin and J. Stoye, Finding Nested Common Intervals Efficiently, 7th RECOMB Satellite Workshop on Comparative Genomics (RECOMB- CG'09), pp.59-69, 2009.
DOI : 10.1007/978-3-642-04744-2_6
URL : https://hal.archives-ouvertes.fr/hal-00620365

G. Blin and H. Touzet, How to Compare Arc-Annotated Sequences: The Alignment Hierarchy, 13th Symposium on String Processing and Information Retrieval, pp.291-303, 2006.
DOI : 10.1007/11880561_24
URL : https://hal.archives-ouvertes.fr/inria-00178671

G. Blin, S. Vialette, R. , and R. , A faster algorithm for finding minimum Tucker submatrices, Theory of Computing Systems, p.10, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00620380

S. 51-]-b-¨-ocker, K. Jahn, J. Mixtacki, and J. Stoye, Computation of median gene clusters, J, 2009.

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

S. C. Boulakia, A. Denise, and S. Hamel, Using Medians to Generate Consensus Rankings for Biological Data, 23rd International Scientific and Statistical Database Management, pp.73-90, 2011.
DOI : 10.1007/978-3-540-77918-6_21
URL : https://hal.archives-ouvertes.fr/inria-00584690

G. Bourque, Y. Yacef, and N. Mabrouk, Maximizing Synteny Blocks to Identify Ancestral Homologs, Proc. 3rd RECOMB Comparative Genomics Satellite Workshop, pp.21-35, 2005.
DOI : 10.1007/11554714_3

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

D. Bryant, The Complexity of Calculating Exemplar Distances, Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, pp.207-212, 2000.
DOI : 10.1007/978-94-011-4309-7_19

C. Chauve, U. Haus, T. Stephen, and V. P. You, Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction, RECOMB-CG 09, pp.48-58, 2009.
DOI : 10.1137/0208032

D. Che and G. Li, Detecting uber-operons in prokaryotic genomes, Nucleic Acids Research, vol.34, issue.8, pp.2418-2427, 2006.
DOI : 10.1093/nar/gkl294

X. Chen, J. Zheng, Z. Fu, P. Nan, Y. Zhong et al., COMPUTING THE ASSIGNMENT OF ORTHOLOGOUS GENES VIA GENOME REARRANGEMENT, Proceedings of the 3rd Asia-Pacific Bioinformatics Conference, pp.302-315, 2005.
DOI : 10.1142/9781860947322_0037

Z. Chen, R. H. Fowler, B. Fu, and B. Zhu, Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes, Lecture Notes in Computer Science, vol.4112, pp.245-254, 2006.
DOI : 10.1007/11809678_27

Z. Chen, B. Fu, and B. Zhu, The Approximability of the Exemplar Breakpoint Distance Problem, 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), pp.291-302, 2006.
DOI : 10.1007/11775096_27

G. Didier, T. Schmidt, J. Stoye, and D. Tsur, Character sets of strings, Journal of Discrete Algorithms, vol.5, issue.2, pp.330-340, 2007.
DOI : 10.1016/j.jda.2006.03.021

M. Dom, J. Guo, and R. Niedermeier, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Journal of Computer and System Sciences, vol.76, issue.3-4, pp.3-4, 2010.
DOI : 10.1016/j.jcss.2009.07.001

R. Dondi, G. Fertin, and S. Vialette, Maximum Motif Problem in Vertex-Colored Graphs, Proc. 20th Annual Symposium on Combinatorial Pattern Matching (CPM'09), pp.221-235, 2009.
DOI : 10.1073/pnas.0409522102
URL : https://hal.archives-ouvertes.fr/hal-00416463

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the tenth international conference on World Wide Web , WWW '01, pp.613-622, 2001.
DOI : 10.1145/371920.372165

P. Evans, Algorithms and Complexity for Annotated Sequences Analysis, 1999.

P. A. Evans, Finding Common Subsequences with Arcs and Pseudoknots, Proc. 10th Annual Symposium Combinatorial Pattern Matching (CPM), pp.270-280, 1999.
DOI : 10.1007/3-540-48452-3_20

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

J. Felsenstein, Phylogenies from Molecular Sequences: Inference and Reliability, Annual Review of Genetics, vol.22, issue.1, pp.521-565, 1988.
DOI : 10.1146/annurev.ge.22.120188.002513

W. M. Fitch, Homology, Trends in Genetics, vol.16, issue.5, pp.227-231, 2000.
DOI : 10.1016/S0168-9525(00)02005-9

Z. Fu, V. Vacic, Y. Zhong, and T. Jiang, A Parsimony Approach to Genome-Wide Ortholog Assignment, Research in Computational Molecular Biology, 10th Annual International Conference, pp.578-594, 2006.
DOI : 10.1007/11732990_47

M. Garey and D. Johnson, Computers and Intractability: A guide to the theory of NPcompleteness, 1979.

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

J. Gramm, J. Guo, and R. Niedermeier, Pattern matching for arc-annotated sequences, Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp.182-193, 2002.

J. Gramm, J. Guo, and R. Niedermeier, Pattern matching for arc-annotated sequences, ACM Transactions on Algorithms, vol.2, issue.1, pp.44-65, 2006.
DOI : 10.1145/1125994.1125997
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.7716

V. Guignon, C. Chauve, and S. Hamel, An Edit Distance Between RNA Stem-Loops, 12th International Conference SPIRE, pp.335-347, 2005.
DOI : 10.1007/11575832_38
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.3444

S. Guillemot and F. Sikora, Finding and Counting Vertex-Colored Subtrees, 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10), pp.405-416, 2010.
DOI : 10.1007/978-3-642-15155-2_36
URL : https://hal.archives-ouvertes.fr/hal-00455134

J. Guo, Exact algorithms for the longest common subsequence problem for arcannotated sequences, 2002.

J. Guo, J. Gramm, F. Uffner, 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.721386-1396, 2006.
DOI : 10.1016/j.jcss.2006.02.001

X. He and M. H. Goldwasser, Identifying Conserved Gene Clusters in the Presence of Homology Families, Journal of Computational Biology, vol.12, issue.6, pp.638-656, 2005.
DOI : 10.1089/cmb.2005.12.638

S. Heber and J. Stoye, Finding All Common Intervals of k Permutations, Proc. Annual Symposium on Combinatorial Pattern Matching (CPM), pp.207-218, 2001.
DOI : 10.1007/3-540-48194-X_19

Y. Ho and A. Gruhler, Systematic identification of protein complexes in Saccharomyces cerevisae by mass spectrometry, Nature, issue.6868, pp.415180-183, 2002.

R. Hoberman and D. Durand, The Incompatible Desiderata of Gene Cluster Properties, LNCS, vol.3678, pp.73-87, 2005.
DOI : 10.1007/11554714_7

K. Jahn, Approximate Common Intervals Based Gene Cluster Models, 2010.

T. Jiang, G. Lin, B. Ma, and K. Zhang, A General Edit Distance between RNA Structures, Journal of Computational Biology, vol.9, issue.2, pp.371-388, 2002.
DOI : 10.1089/10665270252935511

T. Jiang, G. Lin, B. Ma, and K. Zhang, The longest common subsequence problem for arc-annotated sequences, Journal of Dicrete Algorithms, pp.257-270, 2004.

T. Jiang, G. Lin, B. Ma, and K. Zhang, The Longest Common Subsequence Problem for Arc-Annotated Sequences, Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.154-165, 2000.
DOI : 10.1007/3-540-45123-4_15

T. Jiang, L. Wang, and K. Zhang, Alignment of trees ??? an alternative to tree edit, Theoretical Computer Science, vol.143, issue.1, pp.137-148, 1995.
DOI : 10.1016/0304-3975(95)80029-9

R. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

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, pp.11394-11399, 2003.
DOI : 10.1073/pnas.1534710100

P. Klein, G. Bilardi, G. Italiano, A. Pietracaprina, and G. Pucci, Computing the Edit-Distance Between Unrooted Ordered Trees, Proc. 6th European Symposium on Algorithms (ESA), pp.91-102, 1998.
DOI : 10.1007/3-540-68530-8_8

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

G. Lin, Z. Chen, T. Jiang, W. , and J. , The longest common subsequence problem for sequences with nested arc annotations, Journal of Computer and System Sciences, vol.65, issue.3, pp.465-480, 2002.
DOI : 10.1016/S0022-0000(02)00004-1

G. Lin, B. Ma, and K. Zhang, Edit distance between two RNA structures, Proceedings of the fifth annual international conference on Computational biology , RECOMB '01, pp.211-220, 2001.
DOI : 10.1145/369133.369214

B. Ma, L. Wang, and K. Zhang, Computing similarity between RNA structures, Theoretical Computer Science, vol.276, issue.1-2, pp.111-132, 2002.
DOI : 10.1016/S0304-3975(01)00192-X
URL : http://doi.org/10.1016/s0304-3975(01)00192-x

M. Marron, K. M. Swenson, and B. M. Moret, Genomic distances under deletions and insertions, Theoretical Computer Science, pp.537-547, 2003.
DOI : 10.1007/3-540-45071-8_54
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8269

J. H. Nadeau and B. A. Taylor, Lengths of chromosomal segments conserved since divergence of man and mouse., Proceedings of the National Academy of Sciences, vol.81, issue.3, pp.814-818, 1984.
DOI : 10.1073/pnas.81.3.814

C. Nguyen, Algorithms for calculating exemplar distances, 2005.

C. T. Nguyen, Y. C. Tay, and L. Zhang, Divide-and-conquer approach for the exemplar breakpoint distance, Bioinformatics, vol.21, issue.10, pp.2171-2176, 2005.
DOI : 10.1093/bioinformatics/bti327

S. Ohno, Evolution by gene duplication, 1970.
DOI : 10.1007/978-3-642-86659-3

A. Ouangraoua, K. Swenson, C. , and C. , A 2-Approximation for the Minimum Duplication Speciation Problem, Journal of Computational Biology, vol.18, issue.9, pp.1041-1053, 2011.
DOI : 10.1089/cmb.2011.0108
URL : https://hal.archives-ouvertes.fr/inria-00635025

S. Pasek and A. Bergeron, Identification of genomic features using microsyntenies of domains: Domain teams, Genome Research, vol.15, issue.6, pp.867-874, 2005.
DOI : 10.1101/gr.3638405

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

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

S. Rahmann and G. W. Klau, Integer Linear Programs for Discovering Approximate Gene Clusters, Proceedings of WABI 2006, pp.298-309, 2006.
DOI : 10.1007/11851561_28

T. Reguly and A. Breitkreutz, Comprehensive curation and analysis of global interaction networks in saccharomyces cerevisiae, Journal of Biology, 2006.

D. Sankoff, Genome rearrangement with gene families, Bioinformatics, vol.15, issue.11, pp.909-917, 1999.
DOI : 10.1093/bioinformatics/15.11.909
URL : http://bioinformatics.oxfordjournals.org/cgi/content/short/15/11/909

D. Sankoff and L. Haque, Power Boosts for Cluster Tests, Proc. 3rd RECOMB Comparative Genomics Satellite Workshop, pp.11-20, 2005.
DOI : 10.1007/11554714_11

D. Sankoff and B. Kruskal, Time Warps, String Edits and Macromolecules: the Theory and Practice of Sequence Comparison, 1983.

D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang et al., Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome., Proceedings of the National Academy of Sciences, pp.896575-6579, 1992.
DOI : 10.1073/pnas.89.14.6575

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

T. Schmidt and J. Stoye, Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences, Proceedings of CPM 2004, pp.347-358, 2004.
DOI : 10.1007/978-3-540-27801-6_26

D. Shasha and K. Zhang, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, vol.18, issue.6, pp.1245-1262, 1989.

T. Shlomi, D. Segal, E. Ruppin, S. , and R. , 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

F. Sikora, Aspects algorithmiques de la comparaison d'´ eléments biologiques, 2011.

C. Simillion, K. Vandepoele, and Y. V. De-peer, Recent developments in computational approaches for uncovering genomic homology, BioEssays, vol.28, issue.11, pp.261225-1235, 2004.
DOI : 10.1002/bies.20127

K. M. Swenson, M. Marron, J. V. Earnest-deyoung, and B. M. Moret, Approximating the true evolutionary distance between two genomes, ALENEX/ANALCO, pp.121-129, 2005.
DOI : 10.1145/1227161.1402297

J. Tang and B. Moret, Phylogenetic Reconstruction from Gene-Rearrangement Data with Unequal Gene Content, Proc. 8-th International Workshop on Algorithms and Data Structures (WADS), pp.37-46, 2003.
DOI : 10.1007/978-3-540-45078-8_4

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

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

T. Uno and M. Yagiura, Fast Algorithms to Enumerate All Common Intervals of Two Permutations, Algorithmica, vol.26, issue.2, 2000.
DOI : 10.1007/s004539910014

T. Uno and M. Yagiura, Fast Algorithms to Enumerate All Common Intervals of Two Permutations, Algorithmica, vol.26, issue.2, pp.290-309, 2000.
DOI : 10.1007/s004539910014

S. Vialette, Pattern Matching Problems over 2-Interval Sets, Proc. 13th Annual Symposium Combinatorial Pattern Matching (CPM), pp.53-63, 2002.
DOI : 10.1007/3-540-45452-7_6

S. Vialette, On the computational complexity of 2-interval pattern matching problems, Theoretical Computer Science, vol.312, issue.2-3, pp.223-249, 2004.
DOI : 10.1016/j.tcs.2003.08.010

B. Wang, Output-Sensitive Algorithms for Finding the Nested Common Intervals of Two General Sequences, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.9, issue.2, 2011.
DOI : 10.1109/TCBB.2011.112

X. Yang and S. Aluru, Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, chapter 32, pp.725-747, 2011.

X. Yang, F. Sikora, G. Blin, S. Hamel, R. Rizzi et al., An Algorithmic View on Multi-Related-Segments: A Unifying Model for Approximate Common Interval, 9th annual conference on Theory and Applications of Models of Computation (TAMC), p.10, 2012.
DOI : 10.1007/978-3-642-29952-0_33
URL : https://hal.archives-ouvertes.fr/hal-00630150

M. Zhang and H. W. Leong, Gene Team Tree: A Hierarchical Representation of Gene Teams for All Gap Lengths, Journal of Computational Biology, vol.16, issue.10, pp.1383-1398, 2009.
DOI : 10.1089/cmb.2009.0093

B. Zhu, Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems, Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, TAMC '09, pp.71-80, 2009.
DOI : 10.1007/978-3-642-02017-9_10

F. Guillaume, ·. Full-professor, S. Marie-france, and R. Director, Université de Lille Examinators: · Romeo RIZZI, Full-Professor, Università degli Studi di Trento (Italy) · Irena RUSU, Full-Professor, Alpes ·Héì ene TOUZET, Research Director CNRS (DR2), 2001.

T. Franky and . Associate-professor, Professional Training 2011-2012 ? 6 months of CRCT at Université de Marne la Vallée for handling the HAL project 2010-2011 ? Full Temporary CNRS Researcher at Université de Marne la Vallée From 2006 ? Associate-Professor at Université de Marne la Vallée ? Assistant-Professor at Université de Marne la Vallée 2002-2005 ? Junior-Lecturer -MENRT grant -Université de Nantes 2000-2002 ? Temporary Lecturer at Université de Nantes Scientific Duties Local duties From 2006, I am co-organizing the weekly general seminar of the Laboratoire d'Informatique Gaspard Monge, I have been one of the two organizers of the seminar, 2005.

F. With-dr, Finally, via the process of " invited months " , I have been able to provide some short terms visits to foreign collaborators to work with our team: Sylvie Hamel from Montréal, Canada (1 month in Jens Stoye from Bielefeld, Romeo Rizzi from Minghui Jiang from Utah Danny Hermelin from SaarbrückenSaarbr¨Saarbrücken Riccardo Dondi from Sylvie Hamel from Montréal, Canada (1 week in 2011) and Xiaodong Wu from Iowa, 2008.

A. Bilateral-franco-italian-project and P. Galileo-n?08484vh, A bilateral franco-quebec project from the Commission Permanente de Coopération Franco- Québécoise on " Structures conservées et duplications pour les réarrangements génomiques, 2005.

A. Peps, Traduction Automatique et Génomique Comparative, 2010.

A. Programme-jeune-chercheur and A. , Biological networks, Radiotherapy and Structures " (2010- 2014) for which I am the coordinator Member of the Laboratoire International Franco

G. Crochemore, M. Vialette, S. G. Fertin, G. Vialette, and S. , Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, chapter Algorithmic Aspects of Arc-Annotated Sequences What makes the arc-preserving subsequence problem hard ?, List of Publications Complete list of my publications Book Chapter, pp.113-1261, 2005.

G. Blin, F. Sikora, S. Vialette, G. Applications-blin, R. Rizzi et al., Querying Minimum Mosaic Inference of a Set of Recombinants. International Journal of Foundations of Computer Science (IJFCS) To appear Blin On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem A faster algorithm for finding minimum Tucker submatrices The breakpoint distance for signed sequences New results for the 2-interval pattern problem Genes order and phylogenetic reconstruction: Application to ?-proteobacteria, Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set Theory of Computing Systems, page 10 pp In proceedings Blin, Proc. 1st Algorithms and Computational Methods for Biochemical and Evolutionary Networks (CompBioNets) Proc. 15th Combinatorial Pattern Matching (CPM) Proc. 3rd RECOMB Comparative Genomics Satellite Workshop, pp.628-635, 2004.

G. Blin, G. Fertin, D. Hermelin, S. G. Vialette, R. G. Rizzi et al., Fixed-parameter algorithms for protein similarity search under mrna structure constraints Conserved intervals distance computation between non-trivial genomes What makes the arc-preserving subsequence problem hard ? How to Compare Arc-Annotated Sequences: The Alignment Hierarchy Inferring gene orders from gene maps using the breakpoint distance, Proc. 31st Proc. 11th Annual Int. Conference on Computing and Combinatorics (COCOON) 13th Symposium on String Processing and Information Retrieval Proc. 4th RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG), pp.271-282, 2005.

G. Blin, G. Fertin, I. Rusu, C. Sinoquet, C. Bo et al., Extending the Hardness of RNA Secondary Structure Comparison Comparing RNA structures: towards an intermediate model between the EDIT and the LAPCS problems Querying Protein-Protein Interaction Networks Finding the median of three permutations under the Kendall-Tau distance The exemplar breakpoint distance for non-trivial genomes cannot be approximated Finding Nested Common Intervals Efficiently GraMoFoNe: a cytoscape plugin for querying motifs without topology in protein-protein interactions networks Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions A faster algorithm for finding minimum Tucker submatrices Algorithmic aspects of heterogeneous biological networks comparison Minimum Mosaic Inference of a Set of Recombinants A polynomial-time algorithm for finding minimal conflicting sets, 1st intErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental methodologies 5th International Symposium on Bioinformatics Research and Applications (ISBRA'09), volume 5542 of LNBI Proc. 7th annual international conference on Permutation Patterns Proc. 3rd Annual Workshop on Algorithms and Computation 7th RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'09) 2nd International Conference on Bioinformatics and Computational Biology (BICoB-2010). International Society for Computers and their Applications 4th Workshop on Algorithms and Computation (WALCOM'10) 6th Computability in Europe (CiE'10) 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11) 17th Computing: the Australasian Theory Symposium (CATS'11) Proc. 6th International Computer Science Symposium in Russia (CSR), volume 6651 of Lecture Notes in Computer Science, pp.140-151, 2007.

G. Springer-blin, P. Bonizzoni, R. Dondi, R. Rizzi, F. M. Sikora et al., Complexity Insights of the Minimum Duplication Problem ? Spindler?vSpindler?Spindler?v Mí yn, Tchèque, République An Algorithmic View on Multi-related-segments: a new unifying model for approximate common interval Longest common subsequences for bounded run lengths Lecture Notes in Computer Science, 38th International Conference on Current Trends in Theory and Practice of Computer Science 9th annual conference on Theory and Applications of Models of Computation (TAMC) Proc. 23th Annual Symposium on Combinatorial Pattern Matching (CPM), pp.153-164, 2012.