Publications and talks

International journals

• M.-F. Sagot, A. Viari, J. Pothier and H. Soldano, Finding flexible patterns in a text - An application to 3D matching. Computer Applications to the Biosciences, 11:59-70, 1995, presented at the First International IEEE Workshop on Shape and Pattern Matching in Computational Biology, Seattle, Washington, USA.

• M.-F. Sagot, A. Viari and H. Soldano, Multiple comparison - A peptide matching approach. Theoretical Computer Science, 180(1-2):115-137, 1997, extended version of a paper presented at CPM 1995.

• M.-F. Sagot and E. W. Myers, Identifying satellites and periodic repetitions in biological sequences. J. of Comput. Biol., 5(3):539-554, 1998.

• A. Vanet, L. Marsan and M.-F. Sagot, Promoter sequences and algorithmical methods for identifying them. Res. Microbiol., 150:779-799, 1999.

• A. Vanet, L. Marsan, A. Labigne and M.-F. Sagot, Inferring regulatory elements from a whole genome. An application to the analysis of the genome of Helicobacter pylori sigma 80 family of promoter signals. J. Mol. Biol., 297:335-353, 2000.

• L. Marsan and M.-F. Sagot, Algorithms for extracting structured motifs using a suffix tree with application to promoter and regulatory site consensus identification . J. of Comput. Biol., 7:345-360, 2000.

• Nadia Pisanti and M.-F. Sagot, Further thoughts on the syntenic distance between genomes. Algorithmica, 34:157-180, 2002.

• C. Mathé, M.-F. Sagot, T. Schiex and P. Rouzé, Current methods of gene prediction, their strengths and weaknesses. Nucleic Acids Research, 30:4103-4117, 2002.

• P. Blayo, P. Rouzé and M.-F. Sagot, Orphan gene finding - An exon assembly approach. Theoretical Computer Science, 290:1407-1431, 2003.

• S. Robin, J.-J. Daudin, H. Richard, M.-F. Sagot and S. Schbath, Occurrence probability of structured motifs in random sequences. J. Comp. Biol., 9:761-773, 2003.

• C. S. Iliopoulos, J. McHugh, P. Peterlongo, N. Pisanti, W. Rytter and M.-F. Sagot, A first approach to finding common motifs with gaps. International Journal of Foundations of Computer Science, 6:1145-1154, 2005.

• J. Allali and M.-F. Sagot, A new distance for high level RNA secondary structure comparison. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2(1): 3-14, 2005.

• N. Pisanti, M, Crochemore, R. Grossi and M.-F. Sagot, Bases of motifs for generating repeated patterns with don't cares. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2(1): 40-50, 2005.

• A. Carvalho, A. T. Freitas, A. L. Oliveira and M.-F. Sagot, An Efficient Algorithm for the Identification of Structured Motifs in DNA Promoter Sequences, accepted with minor revisions at IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2005.

• V. Lacroix, C. G. Fernandes and M.-F. Sagot. Motif Search in Graphs: Application to Metabolic Networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3:360-368, 2006.

• M. Crochemore, C. S. Iliopoulos, M. Mohamed, M.-F. Sagot. Longest repeats with a block of k don't cares. Theoretical Computer Science, 363:248-254, 2006.

• E. Cambouropoulos, M. Crochemore, C. S. Iliopoulos, M. Mohamed, M.-F. Sagot. All maximal-pairs in step-leap representation of melodic sequence. Inf. Sci., 177(9):1954-1962, 2007.

• E. M. Rodrigues, M.-F. Sagot, and Y. Wakabayashi. The Maximum Agreement Forest Problem: approximation algorithms and computational experiments. Theoretical Computer Science, 374:91-110, 2007.

• Y. Diekmann, E. Tannier, M.-F. Sagot. Evolution under reversals: parsimony and conservation of common intervals. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(2):301-309, 2007.

• E. Tannier, A. Bergeron and M.-F. Sagot. Advances on sorting by reversals. Discrete Applied Mathematics, 155(6-7): 881-888, 2007.

• R. Bourqui, L. Cottret, V. Lacroix, D. Auber, P. Mary, M.-F. Sagot and F. Jourdan. Metabolic network visualization eliminating node redundance and preserving metabolic pathways. BMC Syst. Biol., 1:29, 2007.

• J. Allali and M.-F. Sagot, A multiple layer model to compare RNA secondary structures. Software Practice and Experience, 38(8):775-792, 2008.

• P. Peterlongo, J. Allali, and M.-F. Sagot. Indexing Gapped-Factors using a Tree, International Journal of Foundations of Computer Science, 19:71-87, 2008.

• P. Peterlongo, N. Pisanti, F. Boyer, A. P. do Lago, and M.-F. Sagot. Lossless filter for multiple repetitions with Hamming distance. Journal of Discrete Algorithms, 6(2), 2008.

• C. Lemaitre and M.-F. Sagot. A Small Trip in the Untranquil World of Genomes. Theor. Comp. Sci., 295:171-192, 2008.

• M. D. V. Braga, M.-F. Sagot, C. Scornavacca and E. Tannier. Exploring the solution space of sorting by reversals, with experiments and an application to evolution. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(3):348-356, 2008.

• P. G. S. Fonseca, C. Gautier, K. Guimarães, and M.-F. Sagot. Efficient representation and p-value computation for high order Markov motifs.accepted at ECCB'08, Bioinformatics, 24:i160-i167, 2008.

• C. Lemaitre, E. Tannier, C. Gautier, and M.-F. Sagot. Precise detection of rearrangement breakpoints in mammalian chromosomes. BMC Bioinformatics, 9:286, 2008.

• V. Lacroix, L. Cottret, P. Thébault and M.-F. Sagot. An introduction to metabolic networks and their structural analysis. IEEE-ACM Transactions in Computational Biology and Bioinformatics, 5(4):1-24, 2008.

• V. Acuña, F. Chierichetti, V. Lacroix, A. Marchetti-Spaccamela, M.-F. Sagot, and L. Stougie. Modes and cuts in metabolic networks: Complexity and algorithms. BioSystems, 95(1):51-50, 2008.

• P. Peterlongo, G. A. T. Sacomoto, A. P. do Lago, N. Pisanti, M.-F. Sagot. Lossless filter for multiple repeats with bounded edit distance. Algorithms for Molecular Biology, 4:3, 2009.

• M. Deloger, F. M. G. Cavalli, E. Lerat, C. Biémont, M.-F. Sagot, C. Vieira. Identification of expressed transposable element insertions in the sequenced genome of Drosophila melanogaster. Gene, 439:55-62, 2009.

• C. Lemaitre, L. Zaghloul, M.-F. Sagot, C. Gautier, A. Arnéodo, E. Tannier, B. Audit. Analysis of fine-scale mammalian evolutionary breakpoints provides new insight into their relation to genome organisation. BMC Genomics, 10:335, 2009.

• N. Mendes, A. T. Freitas, M.-F. Sagot. Current tools for the identification of miRNA genes and their targets. Nucleic Acids Research, 37)8):2419-2433, 2009.

• C. Lemaitre, M. D. V. Braga, C. Gautier, M.-F. Sagot, E. Tannier, G. Marais. Footprints of inversions at present and past pseudoautosomal boundaries in human sex chromosomes. Genome Biology and Evolution, 1(1):56-66, 2009.

• S. Schbath, V. Lacroix, M.-F. Sagot. Assessing the exceptionality of coloured motifs in networks. accepted in EURASIP Journal on Bioinformatics and Systems Biology, 2009.

• V. Acuña, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie. A note on the complexity of finding and enumerating elementary modes. Biosystems, 99(3):210-214, 2010.

• S. S. Adi, M. D. V. Braga, C. G. Fernandes, C. E. Ferreira, F. V. Martinez, M.-F. Sagot, M. A. Stefanes, C. Tjandraatmadja, Y. Wakabayashi.Repetition-free longest common subsequence. Discrete Applied Mathematics, 158:1315-1324, 2010.

• C. Baudet, C. Lemaitre, D. Zanoni, C. Gautier, E. Tannier, M.-F. Sagot. Cassis: precise detection of rearrangement breakpoints , Bioinformatics, 26(15):1897-1898, 2010.

• L. Cottret, P.V. Milreu, V. Acuña, A. Marchetti-Spaccamela, L. Stougie, H. Charles, M.-F. Sagot. Graph based analysis of the metabolic exchanges between two co-resident intracellular symbionts, Baumannia cicadellinicola and Sulcia muelleri, with their insect host, Homalodisca coagulata, PLoS Computational Biology, 6(9):307-316, 2010.

• N. Mendes, A.T. Freitas, A.T. Vasconcelos, M.-F. Sagot. Combination of measures distinguishes pre-miRNAs from other stem-loops in the genome of the newly sequenced Anopheles darlingi, BMC Genomics, 11:529, 2010.

• Y.-P. Deniélou, M.-F. Sagot, F. Boyer, A. Viari. Bacterial syntenies: An exact approach with gene quorum, BMC Bioinformatics, 12:193, 2011.

• P. Simões, G. Mialdea, D. Reiss, M.-F. Sagot, S. Charlat. Wolbachia detection: An assessment of standard PCR Protocols. Molecular Ecology Resources, 11:567-572, 2011.

• A.F. Vellozo, A. Véron, P. Baa-Puyoulet, J. Huerta-Cepas, L. Cottret, G. Febvay, F. Calevro, Y. Rahbé, A.E. Douglas, T. Gabaldon, M.-F. Sagot, H. Charles, S. Colella. CycADS: An annotation database system to ease the development and update of BioCyc databases, Database, in press, 2011.

• G. A. T. Sacomoto, J. Kielbassa, R. Chikhi, R. Uricaru, P. Antoniou, M.-F. Sagot, P. Peterlongo, V. Lacroix. KISSPLICE: de-novo calling alternative splicing events from RNA-seq data. BMC Bioinformatics, 13(Suppl 6):S5, 2012.

• V. Acuña, P. V. Milreu, L. Cottret, A. Marchetti-Spaccamela, L. Stougie, M.-F. Sagot. Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. Bioinformatics, 28(19):2474-2483, 2012.

• I. Nor, D. Hermelin, S. Charlat, J. Engelstadter, M. Reuter, O. Duron, M.-F. Sagot. Mod/Resc Parsimony Inference: Theory and application. Inf. Comput., 213: 23-32, 2012.

• V. Acuña, E. Birmelé, L. Cottret, P. Crescenzi, F. Jourdan, V. Lacroix, A. Marchetti-Spaccamela, A. Marino, P.V. Milreu, M.-F. Sagot, L. Stougie. Telling Stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets. Theor. Comput. Sci., 457:1-9, 2012.

• C.C. Klein, L. Cottret, J. Kielbassa, H. Charles, C. Gautier, A.T.R. Vasconcelos, V. Lacroix, M.-F. Sagot. Exploration of the core metabolism of symbiotic bacteria. BMC Genomics, 13(1):438, 2012.

• C. Baudet, Z. Dias, and M.-F. Sagot. Sampling solution traces for the problem of sorting permutations by signed reversals. Algorithms for Molecular Biology, 7(1):18, 2012.

• M. Brilli, P. Lio, V. Lacroix, and M.-F. Sagot. Short and long-term genome stability analysis of prokaryotic genomes. BMC Genomics, 14:309, 2013.

• N. D. Mendes, S. Heyne, A. T. Freitas, M.-F. Sagot, and R. Backofen. Navigating the unexplored seascape of pre-miRNA candidates in single-genome approaches. Bioinformatics, 28(23):3034–3041, 2012.

• I. Nor, D. Hermelin, S. Charlat, J. Engelstadter, M. Reuter, O. Duron, and M.-F. Sagot. Mod/Resc Parsimony Inference: Theory and application. Information and Computation, 213:23–32, 2012.

• J. Allali, C. Saule, C. Chauve, Y. D’Aubenton-Carafa, A. Denise, C. Drevet, P. Ferraro, D. Gautheret, C. Herrbach, F. Leclerc, A. De Monte, A. Ouangraoua, M.-F. Sagot, M. Termier, C. Thermes, H. Touzet. BRASERO: A resource for benchmarking RNA secondary structure comparison algorithms. Advances in Bioinformatics, 5:10.1155/2012, 2012

• C. C. Klein, A. Marino, M.-F. Sagot, P. Vieira Milreu, M.Brilli. Structural and dynamical analysis of biological networks. Briefings in Functional Genomics and Proteomics, 14:309, 2012

• J. M. P. Alves, C. C. Klein, F. Maia da Silva, A. G. Costa-Martins, M. G. Serrano, G. A. Buck, A. T. R. Vasconcelos, M.-F. Sagot, M. M. G. Teixeira, M. C. M. Motta and E. P. Camargo. Endosymbiosis in trypanosomatids: the genomic cooperation between bacterium and host in the synthesis of essential amino acids is heavily influenced by multiple horizontal gene transfers. BMC Evol Biol, 13:190, 2013.

• C. C. Klein, J. M. Alves, M. G. Serrano, G. A. Buck, A. T. Vasconcelos, M.-F. Sagot, M. M. Teixeira, E. P. Camargo, M. C. Motta. Biosynthesis of vitamins and cofactors in bacterium-harbouring trypanosomatids depends on the symbiotic association as revealed by genomic analyses. PLoS One, 8(11):e79786, 2013.

• M. Brilli, P. Liò, V. Lacroix, M.-F. Sagot. Short and long-term genome stability analysis of prokaryotic genomes. BMC Genomics, 14(1):309, 2013.

• I. Nor, J. Engelstadter, O. Duron, M. Reuter, M.-F. Sagot, and S. Charlat. On the genetic architecture of cytoplasmic incompatibility: inference from phenotypic data. American Naturalist, 182(1):15–24, 2013.

• M. C. Machado Motta, A. C. de A. Martins, [...], M.-F. Sagot, [...], W. De Souza, S. Schenkman, A. T. R. de Vasconcelos. Predicting the proteins of Angomonas deanei, Strigomonas culicis and their respective endosymbionts reveals new aspects of the trypanosomatidae family. PLoS ONE, 8(4):e60209, 2013.

• C. Baudet, B. Donati, B. Sinaimeri, P. Crescenzi, C. Gautier, C. Matias, M.-F. Sagot. Cophylogeny Reconstruction via an Approximate Bayesian Computation. Systematic Biology, (Advance access), 2014.

• M. Federico, P. Peterlongo, N. Pisanti, and M.-F. Sagot. Rime: Repeat identification. Discrete Applied Mathematics, 163(3):275-286, 2014.

• P. V. Milreu, C. C. Klein, L. Cottret, V. Acuña, E. Birmelé, M. Borassi, C. Junot, A. Marchetti-Spaccamela, A. Marino, L. Stougie, F. Jourdan, P. Crescenzi, V. Lacroix, M.-F. Sagot. Telling metabolic stories to explore metabolomics data: a case study on the yeast response to cadmium exposure. Bioinformatics, 30(1):61-70, 2014.

• A. C. Azevedo-Martins, A. C. L. Machado, C. C. Klein, L. Ciapina, L. Gonzaga, A. T. R. Vasconcelos, M. F. Sagot, W. De Souza, M. Einicker-Lamas, A. Galina, M. C. M. Motta. Mitochondrial respiration and genomic analysis provide insight into the influence of the symbiotic bacterium on host trypanosomatid oxygen consumption. Parasitology, 142(2):352-362, 2014.

• B. Donati, C. Baudet, B. Sinaimeri, P. Crescenzi, M.-F. Sagot. EUCALYPT: efficient tree reconciliation enumerator. Algorithms for Molecular Biology, 10(1):11, 2015.

• E. Bosi, B. Donati, M. Galardini, S. Brunetti, M.-F. Sagot, P. Liò, P. Crescenzi, R. Fani, M. Fondi. MeDuSa: a multi-draft based scaffolder. Bioinformatics, pii:btv171, 2015.

• G. Sacomoto, V. Lacroix, M.‑F. Sagot. A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs. Algorithms for Molecular Biology,10, 2015.

• S. Higashi, C. Fournier, C. Gautier, C. Gaspin, M.-F. Sagot. Mirinho: An efficient and general plant and animal pre-miRNA predictor for genomic and deep sequencing data. BMC Bioinformatics, 16(1):179, 2015.

• C. Baudet, B. Donati, B. Sinaimeri, P. Crescenzi, C. Gautier, C. Matias, M.-F. Sagot. Cophylogeny Reconstruction via an Approximate Bayesian Computation. Systematic Biology, 64(3):416-431, 2015.

• P.-A. Rollat-Farnier, D. Santos-Garcia, Q. Rao, M.-F. Sagot, F. J Silva, H. Henri, E. Zchori-Fein, A. Latorre, A. Moya, V. Barbe, S.-S. Liu, X.-W. Wang, F. Vavre, L. Mouton. Two Host Clades, Two Bacterial Arsenals: Evolution through Gene Losses in Facultative Endosymbionts. Genome Biology and Evolution, 7(3):839-855, 2015.

• Q. Rao, P.-A. Rollat-Farnier, D.-T. Zhu, D. Santos-Garcia, F. J Silva, A. Moya, A. Latorre, C. C. Klein, F. Vavre, M.-F. Sagot, S.-S. Liu, L. Mouton, X.-W. Wang. Genome reduction and potential metabolic complementation of the dual endosymbionts in the whitefly Bemisia tabaci. BMC Genomics, 16:226, 2015. P.-A. Rollat-Farnier, D. Santos-Garcia, Q. Rao, M.-F. Sagot, F. J Silva, H. Henri, E. Zchori-Fein, A. Latorre, A. Moya, V. Barbe, S.-S. Liu, X.-W. Wang, F. Vavre, L. Mouton. Two Host Clades, Two Bacterial Arsenals: Evolution through Gene Losses in Facultative Endosymbionts. Genome Biology and Evolution, 7(3):839-855, 2015.

• M. G. Ferrarini, F. M. Siqueira, S. G. Mucha, T. L. Palama, E. Jobard, B. Elena- Herrmann, A. T. R. Vasconcelos, F. Tardy, I. S. Schrank, A. Zaha, M.-F. Sagot. Insights on the virulence of swine respiratory tract mycoplasmas through genomescale metabolic modeling. BMC Genomics, 17(1):353, 2016.

• A. Julien-Laferrière, L. Bulteau, D. Parrot, A. Marchetti-Spaccamela, L. Stougie, S. Vinga, A. Mary, M.-F. Sagot. A Combinatorial Algorithm for Microbial Consortia Synthetic Design. Scientific Reports-Nature, in press, 2016.

Book chapters (invited papers)

• C. Mathé, T. Schiex, P. Rouzé, P. Blayo and M.-F. Sagot, Gene finding in eukaryotes, in Q. Lu and M. Weiner (eds.), Cloning and expression technologies, Eaton Publishing, pages 27-43, 2002.

• M.-F. Sagot and Y. Wakabayashi, Pattern inference under many guises, in B. Reed and C. L. Sales (eds.), Recent advances in algorithms and combinatorics, Springer Verlag, 2003.

• M. Crochemore and M.-F. Sagot, Motifs in sequences: localization and extraction, in A. Konopka and al. (eds.), Handbook of Computational Chemistry, Marcel Dekker Inc., pages 47-97, 2004.

• N. Pisanti and M.-F. Sagot, Network expression inference, in Lothaire 3, Applied Combinatorics on Words, Cambridge University Press, pages 227-250, 2005.

• N. Pisanti, M. Crochemore, R. Grossi and M.-F. Sagot, A comparative study of bases for motif inference, in King's College Publications, pages 195-226, 2005.

International conferences with program committee

• M.-F. Sagot, A. Viari, J. Pothier and H. Soldano, Finding flexible patterns in a text - An application to 3D matching (only the extended version exists), in A. Califano, I. Rigoutsos and H. Wolfson (eds.), First International IEEE Workshop on Shape and Pattern Matching in Computational Biology, Seattle, Washington, USA, pages 117-145, IEEE Press, 1994.

• M.-F. Sagot, V. Escalier, A. Viari and H. Soldano, Searching for repeated words in a text allowing for mismatches and gaps, in R. Baeza-Yates and U. Manber (eds.), Second South American Workshop on String Processing, Viñas del Mar, Chile, Proceedings, pages 87-100, University of Chile, 1995.

• M.-F. Sagot, A. Viari and H. Soldano, A distance-based block searching algorithm, in C. Rawlings, D. Clark, R. Altman, L. Hunter, T. Lengauer and S. Wodak (eds.), Third International Symposium on Intelligent Systems for Molecular Biology, Cambridge, United Kingdom, pages 322-331, AAAI Press, 1995.

• M.-F. Sagot, A. Viari and H. Soldano, Multiple comparison - A peptide matching approach. (only the extended version exists), in Z. Galil and E. Ukkonen (eds.), Combinatorial Pattern Matching 1995, Helsinki, Finlande, Lecture Notes in Computer Science, vol. 937, pages 366-385, Springer Verlag, 1995.

• M.-F. Sagot and A. Viari, A double combinatorial approach to discovering patterns in biological sequences, in D. Hischberg and G. Myers (eds.), Combinatorial Pattern Matching 1996, Laguna Beach, California, USA, Lecture Notes in Computer Science, vol. 1075 , pages 186-208, Springer Verlag, 1996.

• M.-F. Sagot and A. Viari, Flexible identification of structural objects in nucleic acid sequences: palindromes, mirror repeats, pseudoknots and triple helices, in A. Apostolico and J. Hein (eds.), Combinatorial Pattern Matching 97, Lecture Notes in Computer Science, vol. 1264, pages 224-246, Springer Verlag, 1997.

• M.-F. Sagot, Spelling approximate repeated or common motifs using a suffix tree, in C. L. Lucchesi and A. V. Moura (eds.), Latin 1998, Lecture Notes in Computer Science, vol. 1380, pages 111-127, Springer Verlag, 1998.

• M.-F. Sagot and E. W. Myers, Identifying satellites in nucleic acid sequences, in S. Istrail, P. Pevzner and M. Waterman, eds.), RECOMB 1998, New York, USA, Proceedings of the Second Annual International Conference on Computational Molecular Biology, pages 234-242, ACM Press, 1998.

• L. Marsan and M.-F. Sagot, Extracting structured motifs using a suffix tree - Algorithms and application to promoter consensus identification, in S. Minoru and R. Shamir (eds.), RECOMB 2000, Tokyo, Japon, Proceedings of the Fourth Annual International Conference on Computational Molecular Biology, pages 210-219, ACM Press, 2000.

• E. M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, Some approximation results for the maximum agreement forest problem, in M. Goemans, K. Jansen, J. D. P. Rolim and L. Trevisan (eds.), Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX and RANDOM 2001), Berkeley, California, USA, Lecture Notes in Computer Science, vol. 2129, pages 159-169, Springer Verlag, 2001.

ATTENTION: The algorithm introduced in this paper is for the maximum agreement forest (MAF) problem (see how this problem is formally defined in the paper). WE DO NOT CLAIM that the algorithm is for the problem of calculating the rSPR or TBR distance between two trees. The relation between the MAF problem and these other problems were addressed by others. At least two different sets of authors have recently stated that our algorithm was proposed for the TBR or rSPR distance and that it has some flaws in the sense that it is not a 3-approximation for these problems. However, all we say in the paper is that we present a 3-approximation for the MAF problem (as defined in the paper). A full version containing the results of this paper and other new results, implementations, comparisons, etc may be found in a paper with the same authors that appeared in Theor. Comput. Sci. (see the journal list above).

• N. Pisanti, M. Crochemore, R. Grossi and M.-F. Sagot, A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum, in B. Rovan, B.and P. Vojtas (eds.), 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Bratislava, Slovakia, Lecture Notes in Computer Science, vol. 2747, pages 622-632, Springer Verlag, 2003.

• A. Carvalho, A. T. Freitas, A. L. Oliveira and M.-F. Sagot, A parallel algorithm for the extraction of structured motifs, in Proceedings of 19th ACM Symposium on Applied Computing (SAC 2004), Nicosia, Cyprus, pages 147-153, 2004.

• M. Crochemore, C. S. Iliopoulos, M. Mohamed, M.-F. Sagot. Longest repeated motifs with k don't cares. in LATIN'04, Lecture Notes in Computer Science, vol. 2976, pages 271-278, 2004.

• E. Tannier and M.-F. Sagot, Sorting by reversals in subquadratic time. in Combinatorial Pattern Matching 2004. Lecture Notes in Computer Science, vol. 3109, pages 1-13, 2004.

• J. Allali and M.-F. Sagot, Novel tree edit operations for RNA secondary structure comparison. in WABI 2004. Lecture Notes in BioInformatics, vol. 3240, pages 412-425, 2004.

• M. Crochemore, R. Giancarlo and M.-F. Sagot, Longest motifs with a functionally equivalent block. in Proceedings of the 11th Conference on String Processing and Information Retrieval (SPIRE 2004). Lecture Notes in Computer Science, vol. 3246, pages 298-309, 2004.

• A. Carvalho, A. T. Freitas, A. L. Oliveira and M.-F. Sagot. Efficient Extraction of Structured Motifs Using Box-links. in Proceedings of the 11th Conference on String Processing and Information Retrieval (SPIRE 2004), Lecture Notes in Computer Science, vol. 3246, pages 267-268, 2004.

• E. Cambouropoulos, M. Crochemore, C. S. Iliopoulos, M. Mohamed, M.-F. Sagot. A Pattern Extraction Algorithm for Abstract Melodic Representations that Allow Partial Overlapping of Intervallic Categories. in Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR'05), pages 167-174, 2005.

• A. Carvalho, A. T. Freitas, A. L. Oliveira and M.-F. Sagot. A highly scalable algorithm for the extraction of cis-regulatory regions. Proceedings of The 3rd Asia-Pacific Bioinformatics Conference (APBC 2005) published as a volume in the Advances in Bioinformatics and Computational Biology series, Imperial College Press, pages 273-282, 2005.

• M.-F. Sagot and E. Tannier, Perfect sorting by reversals. Proceedings of 11th Computing and Combinatorics (COCOON'05) Annual International Conference, Lecture Notes in Computer Science, vol. 3595, pages 42-51, 2005.

• V. Lacroix, C. G. Fernandes and M.-F. Sagot, Reaction motifs in metabolic networks. Proceedings of 5th Workshop on Algorithms for BioInformatics (WABI'05) , Lecture Notes in BioInformatics, subseries Lecture Notes in Computer Science, vol. 3692, pages 178-191, 2005.

• J. Allali and M.-F. Sagot, A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison, Proceedings of 12th String Processing and Information Retrieval (SPIRE'05) International Conference, Lecture Notes in Computer Science, vol. 3772, pages 348-359, 2005.

• P. Peterlongo, N. Pisanti, F. Boyer and M.-F. Sagot, Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-Factor Array, Proceedings of 12th String Processing and Information Retrieval (SPIRE'05) International Conference, Lecture Notes in Computer Science, vol. 3772, pages 179-190, 2005.

• P. Peterlongo, J. Allali, and M.-F. Sagot. The gapped factor-tree, Prague Stringology Conference, 2006.

• N. Pisanti, A. Carvalho, L. Marsan and M.-F. Sagot, RISOTTO: Fast extraction of motifs with mismatches, in LATIN'06, vol. 3887, pages 757-768, 2006.

• M. D. V. Braga, M.-F. Sagot, C. Scornavacca and E. Tannier. The solution space of sorting by reversals. International Symposium on Bioinformatics Research and Applications (ISBRA'07), Lecture Notes in BioInformatics vol. 4463, pages 293-304, 2007.

• S. S. Adi, M. D. V. Braga, C. Fernandes, C. Ferreira, F. Martinez, M.-F. Sagot, M. A. Stefanes, C. Tjandraatmadja and Y. Wakabayashi. Repetition-free LCS with few reversals. in IV Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'07), Electronic Notes in Discrete Mathematics, Volume 30, pages 243-248, 2008.

• L. Cottret, P. V. Milreu, V. Acuña, A. Marchetti-Spaccamela, F. V. Martinez, M.-F. Sagot and L. Stougie. Enumerating precusor sets of metabolites in a metabolic network. WABI'08, Lecture Notes in Computer Science/Lecture Notes in BioInformatics volume 5251, pages 233-244, 2008.

• Y.-P. Deniélou, F. Boyer, M.-F. Sagot, A. Viari. Multiple alignment of biological networks: A flexible approach. CPM'09, Lecture Notes in Computer Science volume 5542, pages 173-185, 2009.

• I. Nor, D. Hermelin, S. Charlat, J. Engelstadter, M. Reuter, O. Duron, M.-F. Sagot. Mod/Resc Parsimony Inference. CPM'10, Lecture Notes in Computer Science, vol. 6129, pages 202-213, 2010.

• P. Milreu, V. Acuña, E. Birmelé, P. Crescenzi, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie and V. Lacroix. Enumerating chemical organisations in consistent metabolic networks: Complexity and algorithms. WABI'2010, LNBI/LNCS, vol. 6293, pages 226-237, 2010.

• P. Peterlongo, N. Schnel, N. Pisanti, M.-F. Sagot, V. Lacroix. Identifying SNPs without a reference genome by comparing raw reads, SPIRE'2011, Lecture Notes in Computer Science, vol. 6393, pp.147-158, 2011.

• A. Freire, V. Acuña, P. Crescenzi, C. Ferreira, V. Lacroix, P.V. Milreu, E. Moreno, M.-F. Sagot. Minimum ratio cover of matrix columns by extreme rays of its induced cone. accepted at ISCO'12, Lecture Notes in Computer Science, vol. 7422, pages 165-177, 2012.

• E. Birmelé, P. Crescenzi, R. Ferreira, R. Grossi, V. Lacroix, A. Marino, N. Pisanti, G. Sacomoto, M.-F. Sagot. Efficient bubble enumeration in directed graphs, SPIRE'2012, Lecture Notes in Computer Science, volume 7608, pp.118-129, 2012.

• G. A. T. Sacomoto, V. Lacroix, and M.-F. Sagot. A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs and its application to the detection of alternative splicing in RNA-seq data. In 13th Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science, volume 8126, pages 99-111, 2013.

• M. Borassi, P. Crescenzi, V. Lacroix, A. Marino, M.-F. Sagot, P. Vieira Milreu. Telling Stories Fast. in 12th International Symposium Experimental Algorithms (SEA), Lecture Notes in Computer Science, volume 7933, pp.200-211, 2013.

• G. A. T. Sacomoto, B. Sinaimeri, C. Marchet, V. Miele, M.-F. Sagot, V. Lacroix, Navigating in a Sea of Repeats in RNA-seq without Drowning. In 14th Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science, volume 8701, pages 82-96, 2014.

• R. Ferreira, R. Grossi, R. Rizzi, G. A. T. Sacomoto, M.-F. Sagot. Amortized Õ(|V|)-Delay. Algorithm for Listing Chordless Cycles in Undirected Graphs. in 22th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, volume 8737, pp 418-429, 2014.

• R. Rizzi, G. A. T. Sacomoto, M.-F. Sagot. Efficiently listing bounded length st-paths. in Twenty-Fifth International Workshop on Combinatorial Algorithms (IWOCA 2014), Lecture Notes in Computer Science, in press, 2014.

• R. Andrade, E. Birmelé, A. Mary, T. Picchetti, M.-F. Sagot. Incremental complexity of a bi-objective hypergraph transversal problem. Fundamentals of Computation Theory (FCT2015), Lecture Notes in Computer Science, vol. 9210, pp. 202-213, 2015.

Vulgarisation journals

• M.-F. Sagot, Combinatorial algorithms in computational biology, Ercim News, number 43, pages 27-28.

PhD Manuscript (in french)

• Titre
• Dedicace
• Citation
• Remerciements
• Tables des matières
• Chapitre 1 - Introduction
• Chapitre 2
• Chapitre 3
• Chapitre 4
• Chapitre 5
• Chapitre 6
• Chapitre 7
• Chapitre 8 - Conclusion
• Bibliographie
• Résumé

Habilitation manuscript (in english)

• Complete manuscript

Slides from recent talks

• Un lac, deux villes et trois rivières. Sous-titre : Algorithmes combinatoires et biologie moléculaire. General talk (in english, only the title is in french) given when arriving in the Rhône-Alpes region
  • Biological version
  • Slightly more computer oriented version

• On the syntenic distance between genomes (A few results and conjectures). Talk given at the Special Session on Combinatorics, 23rd Brazilian Colloquium on Mathematics, IMPA, Rio de Janeiro, Brazil, July 23, 2001

• Some approximation results for the Maximum Agreement Forest (MAF) problem. Talk given last at the Laboratoire de Probabilité, Combinatoire et Statistiques (LACS) of the University of Lyon I in February 7, 2002

• Network expression inference. Talk given at Dagstuhl Seminar on Computational Biology in November 2002

• Tiny steps towards addressing one part of the DNA rearrangement puzzle. Talk given at the Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Computing 2003 in May 2003

• Motifs and Regulation. Talk given at Tel Aviv University in May 2003

• A few combinatorial problems and algorithms for molecular biology. Talk given at the Laboratoire Leibniz, IMAG, University Joseph Fourier at Grenoble and King's College, London in May 2003 (the slide version corresponds to the talk given in London)

• Biological motif inference. Talk given at the Linnaeus Center for Bioinformatics, Uppsala University, Sweden, in November 2003

• On bases of motifs. Talk given at the Journées Montoises, University of Liège, Belgium, in September 2004

• Some questions around genome rearrangements. Talk given at Linnaeus Center for Bioinformatics, Uppsala University, Sweden, in July 2004 and at WABI/ALGO 2004, Bergen, Norway, in September 2004 (the slide version corresponds to the talk given at Bergen)

More recent talks may be found here.