Publications

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, extended version of a paper presented at the 1st International IEEE Workshop on Shape and Pattern Matching in Computational Biology.

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.

N. 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. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(2):126-140, 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. presented 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. EURASIP Journal on Bioinformatics and Systems Biology, 2009(1): 616234, 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, Z. Dias, 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, 2011:bar008, 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. Information and Computation, 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.

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, […], C.C. KLein, […], 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, 64(3):416–431, 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. Veríssimo, A. L. Oliveira, M.-F. Sagot, S. Vinga. DegreeCox – A network-based regularization method for survival analysis. BMC Bioinformatics, 17:449, 2016.

F. Siqueira, G. L. de Morais, S. Higashi, L. S. Beier, G. M. Breyer, C. P. de Sá Godinho, M.-F. Sagot, I. S. Schrank, A. Zaha, A. T. R. de Vasconcelos. Mycoplasma non-coding RNA: identification of small RNAs and targets. BMC Genomics, 23:1289-1326, 2016.

H. Lopez-Maestre, L. Brinza, C. Marchet, J. Kielbassa, S. Bastien, M. Boutigny, D. Monnin, A. El Filali, C. M. Carareto, C. Vieira, F. Picard, N. Kremer, F. Vavre, M.-F. Sagot, V. Lacroix. SNP calling from RNA-seq data without a reference genome: identification, quantification, differential analysis and impact on the protein sequence. Nucleic Acids Research, 44(19):e148, 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, 6:29182, 2016.

R. Andrade, M. Wannagat, C. C. Klein, V. Acuña, A. Marchetti-Spaccamela, P. V. Milreu, L. Stougie, M.-F. Sagot. Enumeration of minimal stoichiometric precursor sets in metabolic networks. Algorithms for Molecular Biology, 11:25, 2016.

L. Lima, B. Sinaimeri, G. Sacomoto, H. Lopez-Maestre, C. Marchet, V. Miele, M.-F. Sagot, V. Lacroix. Playing hide and seek with repeats in local and global de novo transcriptome assembly of short RNA-seq reads. Algorithms for Molecular Biology, 12:1-19, 2017.

M. Bailly-Bechet, P. Martins-Simões, G. J. Szöllösi, G. Mialdea, M.-F. Sagot, S. Charlat. How Long Does Wolbachia Remain on Board? Molecular biology and evolution, 34:1183-1193, 2017.

A. Dudnik, F. Almeida, R. Andrade, B. Avila, P. Bañados, B. Diane, J.-E. Bassard, M. Benkoulouche, M. Bott, A. Braga, D. Breitel, R. Brennan, L. Bulteau, C. Chanforan, I. Costa, R. S. Costa, M. Doostmohammadi, N. Faria, C. Feng, R. Ferro, A. Fernandes, P. Ferreira, A. Foito, S. Freitag, C. Jardim, G. Garcia, P. Gaspar, J. Godinho-Pereira, B. Hamberger, A. Hartmann, H. Heider, S. Li, A. Julien-Laferrière, N. Kallscheuer, W. Kerbe, O. Kuipers, N. Love, A. Marchetti-Spaccamela, J. Marienhagen, C. Martin, A. Mary, V. Mazurek, C. Meinhart, D. M. Sevillano, R. Menezes, M. Naesby, M. Nørholm, F. Okkels, J. Oliveira, M. Ottens, D. Parrot, L. Pei, I. Rocha, R. Rosado-Ramos, C. Rousseau, M.-F. Sagot, C. N. dos Santos, M. Schmidt, T. Shelenga, L. Shepherd, A. R. Silva, M. H. da Silva, O. Simon, S. G. Stahlhut, A. Solopova, A. Sorokin, D. Stewart, L. Stougie, M. Trick, S.g Su, V. Thole, O. Tikhonova, P. Vain, A. Veríssimo, A. Vila-Santa, S. Vinga, M. Vogt, L. Wang, L. Wang, W. Wei, S. Youssef, A. R. Neves, J. Förster. BacHBerry: BACterial Hosts for production of Bioactive phenolics from bERRY fruits. Phytochemistry Reviews, 1-36, 2017.

A. Hartmann, A. Vila-Santa, N. Kallscheuer, M. Vogt, A. Julien-Laferrière, M.-F. Sagot, J. Marienhagen, S. Vinga. OptPipe – a pipeline for optimizing metabolic engineering targets. BMC Systems Biology, 11:1-9, 2017.

K. Böhmová, L. Häfliger, M. Mihalák, T. Pröger, G. Sacomoto, M.-F. Sagot. Computing and Listing st-Paths in Public Transportation Networks. Theory of Computing Systems, 62(3):600-621, 2018.

M. G. Ferrarini, S. G. Mucha, D. Parrot, G. Meiffrein, J. F. Ruggiero Bachega, G. Comte, A. Zaha, M.‐F. Sagot. Hydrogen peroxide production and myo‐inositol metabolism as important traits for virulence of Mycoplasma hyopneumoniae. Molecular Microbiology, 108)6):683-696, 2018.

I. Kyrkou, H. T. Pusa, L. Ellegaard-Jensen, M.-F. Sagot, L. H. Hansen. Pierce’s Disease of Grapevines: A Review of Control Strategies and an Outline of an Epidemiological Model. Frontiers in microbiology, 9, 2018.

A. Di Genova, G. A. Ruz, M.-F. Sagot, A. Maass. Fast-SG: An alignment-free algorithm for hybrid assembly. GigaScience, 7(5), 2018.

K. T Huber, V. Moulton, M.-F. Sagot, B. Sinaimeri. Geometric medians in reconciliation spaces of phylogenetic trees. Information Processing Letters, 136:96-101, 2018.

P. I. P. Ramos, D. F. Do Porto, E. Lanzarotti, E. J. Sosa, G. Burguener, A. M. Pardo, C. C. Klein, M.-F. Sagot, A. T. R. de Vasconcelos, A. C. Gales, M. Marti, A. G. Turjanski, M. F. Nicolás. An integrative, multi-omics approach towards the prioritization of Klebsiella pneumoniae drug targets. Scientific Reports-Nature, 8(1): 10755, 2018.

K. T Huber, V. Moulton, M.-F. Sagot, B. Sinaimeri. Exploring and Visualizing Spaces of Tree Reconciliations. Systematic Biology, 68(4):607-618, 2018.

L. Urbini, B. Sinaimeri, C. Matias, M.-F. Sagot. Exploring the robustness of the parsimonious reconciliation method in host-symbiont cophylogeny. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16(3):738-748, 2019.

H. T. Pusa, M. Wannagat, M.-F. Sagot. Metabolic games. Frontiers in Applied Mathematics and Statistics, 5:18, 2019.

V. Acuña, R. Grossi, G. Italiano, L. Lima, R. Rizzi, G. Sacomoto, M.-F. Sagot, B. Sinaimeri. On Bubble Generators in Directed Graphs. Algorithmica, 82:898-914, 2020.

H. T. Pusa, M. G. Ferrarini, R. Andrade, A. Mary, A. Marchetti-Spaccamela, L. Stougie, M.-F. Sagot.MOOMIN – Mathematical explOration of ’Omics data on a Metabolic Network. Bioinformatics, 36(2):514-523, 2020.

R. Andrade, M. Doostmohammadi, J. Santos, M.-F. Sagot, N. Mira, S. Vinga. MOMO – multi-objective metabolic mixed integer optimization: application to yeast strain engineering. BMC Bioinformatics, 21(1):1-13, 2020.

Y. Wang, A. Mary, M.-F. Sagot, B. Sinaimeri. CAPYBARA: equivalence ClAss enumeration of coPhylogenY event-BAsed ReconciliAtions. Bioinformatics, 36(14):4197-4199, 2020.

T. Calamoneri, M. Gastaldello, A. Mary, M.-F. Sagot, B. Sinaimeri. Algorithms for the quantitative Lock/Key model of cytoplasmic incompatibility. Algorithms for Molecular Biology, 15(1):1-16, 2020.

S. Mucha, M. Ferrarini, C. Moraga, A. Genova, L. Guyon, F. Tardy, S. Rome, M.-F. Sagot, A. Zaha. Mycoplasma hyopneumoniae J elicits an antioxidant response and decreases the expression of ciliary genes in infected swine epithelial cells. Scientific Reports-Nature, 10:13707, 2020.

J. Cardinali-Rezende, A. Di Genova, R.A.T.P.S. Nahat, A. Steinbüchel, M.-F. Sagot, R.S. Costa, H.C. Oliveira, M.K. Taciro, L.F. Silva, J.G.C. Gomez. The relevance of enzyme specificity for coenzymes and the presence of 6-phosphogluconate dehydrogenase for polyhydroxyalkanoates production in the metabolism of Pseudomonas sp. LFM046, Int J Biol Macromol, 163:240-250, 2020.

A. di Genova, E. Buena-Atienza, S. Ossowski, M.-F. Sagot. Efficient and high-quality hybrid de novo assembly of human genomes with WENGAN (Edited title of the publication initially called “WENGAN: Efficient and high-quality hybrid de novo assembly of human genomes”). Accepted in Nature Biotechnology, 39:422-430, 2021.

M. Ferrarini, L. Nisimura, R. Girard, M. Alencar, M. Fragoso, C. Araújo-Silva, A. Veiga, A. Abud, S. Nardelli, R. Vommaro, A. Silber, M.-F. Sagot, A. R. Ávila. Dichloroacetate and Pyruvate Metabolism: Pyruvate Dehydrogenase Kinases as Targets Worth Investigating for Effective Therapy of Toxoplasmosis. MSphere, 6(1), 2021.

M. Borderes, C. Gasc, E. Prestat, M. Ferrarini, S. Vinga, L. Boucinha, M.-F. Sagot. A comprehensive evaluation of binning methods to recover human gut microbial species from a non-redundant reference gene catalog. NAR Genomics and Bioinformatics, 3(1), 2021.

V. Acuña, L. S. de Lima, G. Italiano, L. Sciarria, M.-F. Sagot, B. Sinaimeri. A family of tree-based generators for bubbles in directed graphs. Journal of Graph Algorithms and Applications, 25(1): 549-562, 2021.

N. Parisot, C. Vargas-Chávez, C. Goubert, P. Baa-Puyoulet, S. Balmand, L. Beranger, C. Blanc, A. Bonnamour, M. Boulesteix, N. Burlet, F. Calevro, P. Callaerts, T. Chancy, H. Charles, S. Colella, A. da Silva Barbosa, E. Dell’aglio, A. di Genova, G. Febvay, T. Gabaldón, M. G. Ferrarini, A. Gerber, B. Gillet, Robert Hubley, S. Hughes, E. Jacquin-Joly, J. Maire, M. Marcet-Houben, F. Masson, C. Meslin, N. Montagné, A. Moya, A. T. R. de Vasconcelos, G. Richard, J. Rosen, M.-F. Sagot, A. Smit, J. Storer, C. Vincent-Monegat, A. Vallier, A. Vigneron, A. Zaidman-Rémy, W. Zamoum, C. Vieira, R. Rebollo, A. Latorre, A. Heddi. The transposable element-rich genome of the cereal pest Sitophilus oryzae. BMC Biology, 19(1):1-29, 2021.

M. G. Ferrarini, I. Ziska, R. Andrade, A. Julien-Laferrière, L. Duchemin, R. Marcondes César, A. Mary, S. Vinga, M.-F. Sagot. Totoro: Identifying Active Reactions During the Transient State for Metabolic Perturbations. Frontiers in Genetics, 13:1-12, 2022.

Y. Wang, A. Mary, M.-F. Sagot, B. Sinaimeri. Efficiently sparse listing of classes of optimal cophylogeny reconciliations. Algorithms for Molecular Biology, 17(1):1-16, 2022.

Y. Wang, A. Mary, M.-F. Sagot, B. Sinaimeri. A general framework for enumerating equivalence classes of solutions. Algorithmica, 2023.

N. Homberg, M. Galvão Ferrarini, C. Gaspin, M.-F. Sagot. MicroRNA Target Identification: Revisiting Accessibility and Seed Anchoring. Genes, 14(3):664, 2023.

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). 1st International IEEE Workshop on Shape and Pattern Matching in Computational Biology, IEEE Press, pages 117-145, 1994.

M.-F. Sagot, V. Escalier, A. Viari and H. Soldano. Searching for repeated words in a text allowing for mismatches and gaps. 2nd South American Workshop on String Processing, pages 87-100, 1995.

M.-F. Sagot, A. Viari and H. Soldano. A distance-based block searching algorith. 3rd International Symposium on Intelligent Systems for Molecular Biology (ISMB 1995), AAAI Press, pages 322-331, 1995.

M.-F. Sagot, A. Viari and H. Soldano. Multiple comparison – A peptide matching approach. 6th Annual Symposium on Combinatorial Pattern Matching (CPM 1995), Lecture Notes in Computer Science, volume 937, pages 366-385, 1995.

M.-F. Sagot and A. Viari. A double combinatorial approach to discovering patterns in biological sequences. 7th Annual Symposium on Combinatorial Pattern Matching (CPM 1996), Lecture Notes in Computer Science, volume 1075, pages 186-208, 1996.

M.-F. Sagot and A. Viari. Flexible identification of structural objects in nucleic acid sequences: palindromes, mirror repeats, pseudoknots and triple helices. 8th Annual Symposium on Combinatorial Pattern Matching (CPM 1997), Lecture Notes in Computer Science, volume 1264, pages 224-246, 1997.

M.-F. Sagot. Spelling approximate repeated or common motifs using a suffix tree. 3rd Latin American Theoretical Informatics Symposium (LATIN 1998), Lecture Notes in Computer Science, volume 1380, pages 111-127, 1998.

M.-F. Sagot and E. W. Myers. Identifying satellites in nucleic acid sequences. 2nd Annual International Conference on Computational Molecular Biology (RECOMB 1998), ACM Press, pages 234-242, 1998.

L. Marsan and M.-F. Sagot. Extracting structured motifs using a suffix tree – Algorithms and application to promoter consensus identification. 4th Annual International Conference on Computational Molecular Biology (RECOMB 2000), ACM Press, pages 210-219, 2000.

E. M. Rodrigues, M.-F. Sagot and Y. Wakabayashi. Some approximation results for the maximum agreement forest problem.4th Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX and RANDOM 2001), Lecture Notes in Computer Science, volume 2129, pages 159-169, 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. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science, volume 2747, pages 622-632, 2003.

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

M. Crochemore, C. S. Iliopoulos, M. Mohamed, M.-F. Sagot. Longest repeated motifs with k don’t cares. 6th Latin American Theoretical Informatics Symposium (LATIN 2004), Lecture Notes in Computer Science, volume 2976, pages 271-278, 2004.

E. Tannier and M.-F. Sagot. Sorting by reversals in subquadratic time. 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004), Lecture Notes in Computer Science, volume 3109, pages 1-13, 2004.

J. Allali and M.-F. Sagot. Novel tree edit operations for RNA secondary structure comparison. 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Computer Science/Lecture Notes in BioInformatics, volume 3240, pages 412-425, 2004.

M. Crochemore, R. Giancarlo and M.-F. Sagot. Longest motifs with a functionally equivalent block. 11th Conference on String Processing and Information Retrieval (SPIRE 2004), Lecture Notes in Computer Science, volume 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. 11th Conference on String Processing and Information Retrieval (SPIRE 2004), Lecture Notes in Computer Science, volume 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. 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.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 Annual International Conference (COCOON 2005), Lecture Notes in Computer Science, volume 3595, pages 42-51, 2005.

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

J. Allali and M.-F. Sagot. A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison. 12th String Processing and Information Retrieval International Conference (SPIRE 2005), Lecture Notes in Computer Science, volume 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. 12th String Processing and Information Retrieval International Conference (SPIRE 2005), Lecture Notes in Computer Science, volume 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, <>7th Latin American Theoretical Informatics Symposium (LATIN 2006), Lecture Notes in Computer Science, volume 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 2007), Lecture Notes in BioInformatics, volume 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. 4th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2007), 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 precursor sets of metabolites in a metabolic network. 8th Workshop on 8th Workshop on Algorithms in Bioinformatics (WABI 2008), 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. 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), 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. 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Lecture Notes in Computer Science, volume 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. 10th Workshop on Algorithms in Bioinformatics (WABI 2010), Lecture Notes in Computer Science/Lecture Notes in BioInformatics, volume 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, 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), Lecture Notes in Computer Science, volume 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. 2nd International Symposium on Combinatorial Optimization (ISCO 2012), Lecture Notes in Computer Science, volume 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. 19th International Symposium on String Processing and Information Retrieval (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. 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. 12th International Symposium Experimental Algorithms (SEA 2013), 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. 14th Workshop on Algorithms in Bioinformatics (WABI 2014), Lecture Notes in Computer Science/Lecture Notes in BioInformatics, 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. 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. 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), Lecture Notes in Computer Science, volume 8986, pp 318-329, 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 (FCT 2015), Lecture Notes in Computer Science, volume 9210, pp. 202-213, 2015.

K. Böhmová, M. Mihalák, T. Pröger, G. Sacomoto, M.-F. Sagot. Computing and Listing st-Paths in Subway Networks. International Computer Science Symposium in Russia, Lecture Notes in Computer Science, volume 9691, pp. 102-116, 2016.

T. Calamoneri, M. Gastaldello, A. Mary, M.-F. Sagot, B. Sinaimeri. On Maximal Chain Subgraphs and Covers of Bipartite Graphs. International Workshop on Combinatorial Algorithms (IWOCA 2016), Lecture Notes in Computer Science, volume 9843, pp.137-150, 2016.

L. Urbini, C. Matias, M.-F. Sagot, B. Sinaimeri. Robustness of the Parsimonious Reconciliation Method in Cophylogeny. Algorithms for Computational Biology (AlCoB 2016), Lecture Notes in Computer Science, volume 9702, pp. 119-130, 2016.

V. Acuña, R. Grossi, G. Italiano, L. Lima, R. Rizzi, G. Sacomoto, M.-F. Sagot, B. Sinaimeri. On Bubble Generators in Directed Graphs. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Lecture Notes in Computer Science, volume 10520, pp.18-31, 2017.

V. Acuña, L. Lima, G. Italiano, L.P. Sciarria, M.-F. Sagot, B. Sinaimeri. A Family of Tree-Based Generators for Bubbles in Directed Graphs. International Workshop on Combinatorial Algorithms (IWOCA 2020), Lecture Notes in Computer Science, volume 12126, pp.17-29, 2020.

Y. Wang, A. Mary, M.-F. Sagot, B. Sinaimeri. Making sense of a cophylogeny output: Efficient listing of representative reconciliations. accepted at 21st Workshop on Algorithms in Bioinformatics (WABI 2021), LIPICS, vol. 201, 3:1-3:18, 2021.

Y. Wang, A. Mary, M.-F. Sagot, B. Sinaimeri. A general framework for enumerating equivalence classes of solutions. accepted at 29th European Symposium on Algorithms (ESA 2021), LIPICS, vol. 204, 80:1-80:14, 2021.

Vulgarisation journals

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

DEA (equivalent Master) Manuscript (in french)

M.-F. Sagot. Analyse des structures primaire et tertiaire des protéines : localisation des mots répétés et recherche rapide sur banque. “Mémoire de DEA d’Informatique Fondamentale”, University of Paris 7, 1993.

PhD Manuscript (in french)

M.-F. Sagot. Ressemblance lexicale et structurale entre macromolécules – Formalisation et approches combinatoires. Defended July 9, 1996, Committee: Dominique Perrin, Didier Arquès, Antoine Danchin, Eugene W. Myers, David Sankoff, Maxime Crochemore, Alain Viari, at University of Marne-la-Vallée, given by University of Marne-la-Vallée, France.

Habilitation manuscript (in english)

M.-F. Sagot. Hope is the thing with feathers – Combinatorial algorithms and molecular biology. Defended October 11, 2000, Committee: Jean Berstel, Maxime Crochemore, Pierre Darlu, Christian Gautier, Dan Gusfield, Richard M. Karp, Eugene W. Myers, David Sankoff, Alain Viari, at Institut Pasteur, given by University of Marne-la-Vallée, France.