Publications and talks
This page contains online papers when these are already available but
also slides from the more recent seminar presentations. Slides from
previous talks were hand-written and are not available.
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. accepted in Discrete Applied Mathematics, 2009.
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, 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 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.
- 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.
- 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.
- 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.
Vulgarisation journals
PhD Manuscript (in french)
Habilitation manuscript (in english)
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
- 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.