Publications and talks

International journals

  • 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.
  • 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, in press, 2015.

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.

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, 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.
  • 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).
  • 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.
  • 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.
  • 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.
  • 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. 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.

Vulgarisation journals

PhD Manuscript (in french)

Habilitation manuscript (in english)

Slides from recent talks

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