Laurent Marsan, Marie-france Sagot
promoter consensus identification
Lemaitre, Claire, Zaghloul, Lamia, Sagot, Marie-France, Gautier, Christian, Arneodo, Alain, Tannier, Eric, ...
Abstract Background The Intergenic Breakage Model, which is the current model of structural genome evolution, considers that evolutionary rearrangement breakages happen with a uniform propensity...
Benchmarking RNA secondary structure comparison algorithms ⋆ (2009)
Julien Allali, Cédric Chauve, Alain Denise, Christine Drevet, Pascal Ferraro, Daniel Gautheret, ...
Abstract: Since the last ten years several tools have been proposed for RNA secondary structure pairwise comparison. These tools use different models (ordered tree or forest, arc annotated sequence,...
Lossless filter for multiple repeats with bounded edit distance (2009)
Peterlongo, Pierre, Sacomoto, Gustavo, Do Lago, Alair, Pisanti, Nadia, Sagot, Marie-France
Abstract Background Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological...
Assessing the Exceptionality of Coloured Motifs in Networks (2009)
Sophie Schbath, Vincent Lacroix, Marie-France Sagot
Various methods have been recently employed to characterise the structure of biological networks. In particular, the concept of network motif and the related one of coloured motif have proven useful...
ISMB/ECCB 2009 Stockholm (2009)
Sagot, Marie-France, McKay, B.J. Morrison, Myers, Gene
The International Society for Computational Biology (ISCB; http://www.iscb.org) presents the Seventeenth Annual International Conference on Intelligent Systems for Molecular Biology (ISMB), organized...
Assessing the Exceptionality of Coloured Motifs in Networks (2009)
Sophie Schbath, Vincent Lacroix, Marie-France Sagot
Various methods have been recently employed to characterise the structure of biological networks. In particular, the concept of network motif and the related one of coloured motif have proven useful...
Lossless filter for multiple repeats with bounded edit distance. (2009)
Peterlongo, Pierre, Sacomoto, Gustavo Akio Tominaga, Do Lago, Alair Pereira, Pisanti, Nadia, Sagot, Marie-France
BACKGROUND: Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and...
Lossless filter for multiple repeats with bounded edit distance. (2009)
Peterlongo, Pierre, Sacomoto, Gustavo Akio Tominaga, Do Lago, Alair Pereira, Pisanti, Nadia, Sagot, Marie-France
BACKGROUND: Identifying local similarity between two or more sequences, or identifying repeats occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and...
A new distance for high level RNA secondary structure comparison (2008)
Allali, Julien, Sagot, Marie-France
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Abstract Background Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are...
Novel tree edit operations for RNA secondary structure comparison (2008)
Julien Allali, Marie-france Sagot
Abstract. We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree...
Pierre Peterlongo, Julien Allali, Marie-france Sagot
Communicated by Editor’s name We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is...
The solution space of sorting by reversals (2008)
Marie-france Sagot, Celine Scornavacca
Abstract. In comparative genomics, algorithms that sort permutations by reversals are often used to propose evolutionary scenarios of large scale genomic mutations between species. One of the main...
The solution space of sorting by reversals (2008)
Marie-france Sagot, Celine Scornavacca, Eric Tannier
comparing the contents of two different genomes, try to identify the mutation events (reversals, insertions, deletions, transpositions...) that have transformed one genome into the other. Identify...
Pierre Peterlongo, Julien Allali, Marie-france Sagot
Communicated by Editor’s name We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is...
MPEG Sofwarc Simulation Group ftp://ftp .netcom. com/pub/cf/cf ogg/mpeg2 (2008)
Catherine Matheâ, Marie-france Sagot, Thomas Schiex, Pierre Rouzeâ
While the genomes of many organisms have been sequenced over the last few years, transforming such raw sequence data into knowledge remains a hard task. A great number of prediction programs have...
Modes and Cuts in Metabolic Networks: Complexity and Algorithms ∗ (2008)
Flavio Chierichetti, Vincent Lacroix, Alberto Marchetti-spaccamela, Marie-france Sagot, Leen Stougie
Constraint-based approaches recently brought new insight into our understanding of metabolism. By making very simple assumptions such as that the system is at steady-state and some reactions are...
An Efficient Algorithm for the Identification of Structured Motifs in DNA Promoter Sequences (2008)
Ra M. Carvalho, Ana T. Freitas, Arlindo L. Oliveira, Marie-france Sagot
We propose a new algorithm for identifying cis-regulatory modules in genomic sequences. The proposed algorithm, named RISO, uses a new data structure, called boxlink, to store the information about...
Efficient learning of Bayesian network classifiers: An (2008)
Ra M. Carvalho, Arlindo L. Oliveira, Marie-france Sagot
We introduce a Bayesian network classifier less restrictive than Naive Bayes (NB) and Tree Augmented Naive Bayes (TAN) classifiers. Considering that learning an unrestricted network is unfeasible the...
A Multiple Graph Layers Model with (2008)
Application To Rna, Julien Allali, Marie-france Sagot
We introduce a new data structure, called MiGaL for "Multiple Graph Layers", that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is...
Novel tree edit operations for RNA secondary structure (2008)
Comparison Julien Allali, Julien Allali, Marie-france Sagot
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree edit...
Marie-France Sagot, Alain Viari
. This paper presents algorithms for flexibly identifying structural objects in nucleic acid sequences. These objects are palindromes, mirror repeats, pseudoknots and triple helices. We further...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are...
Precise detection of rearrangement breakpoints in mammalian chromosomes (2008)
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Genomes undergo large structural changes that alter their organisation. The chromosomal regions affected by these rearrangements are called breakpoints, while those which have not been rearranged are...
A multiple layer model to compare RNA secondary structures (2008)
Allali, Julien, Sagot, Marie-France
We formally introduce a new data structure, called MiGaL for ``Multiple Graph Layers'', that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is...
A multiple layer model to compare RNA secondary structures (2008)
Allali, Julien, Sagot, Marie-France
We formally introduce a new data structure, called MiGaL for ``Multiple Graph Layers'', that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is...
Marie-france Sagot, Eugene Myers, Service D'informatique Scientifique
We present in this paper an algorithm for identifying satellites in DNA sequences. Satellites (simple, micro, or mini) are repeats in number between 30 and as many as 1,000,000 whose lengths vary...
Nadia Pisanti, Nadia Pisanti, Maxime Crochemore, Maxime Crochemore, Roberto Grossi, Roberto Grossi, ...
We investigate the problem of determining the basis of repeated motifs with don't cares in an input string. We give new upper and lower bounds on the problem, introducing a notion of basis that...
On motifs in biological sequences (2007)
Conserved patterns of any kind are of great interest in biology as they are likely to represent objects upon which strong constraints are potentially acting and may therefore perform a biological...
This is page 1 Printer: Opaque this 1 Pattern Inference under many Guises (2007)
Marie-france Sagot, Yoshiko Wakabayashi
This paper surveys some of the main combinatorial methods for inferring patterns from a string, or a set of strings. The types of problems that will be addressed are repeat identication and common...
y IST/INESC-ID Inria Rh^one-Alpes (2007)
Alexandra M. Carvalho, Ana T. Freitas, Arlindo L. Oliveira, Marie-france Sagot
In this work we propose a parallel algorithm for the ecient extraction of bindingsite consensus from genomic sequences. This algorithm, based on an existing approach, extracts structured motifs, that...
Further thoughts on the syntenic distance between genomes (2007)
Nadia Pisanti, Marie-france Sagot
The syntenic distance between two multi-chromosomal genomes is the minimum number of fusion (union), ssion (split) and translocation (exchange) operations necessary to transform a genome into...
Lossless filter for multiple repetitions with Hamming distance (2007)
Peterlongo, Pierre, Pisanti, Nadia, Boyer, Frédéric, Pereira Do Lago, Alair, Sagot, Marie-France
Similarity search in texts, notably in biological sequences, has received substantial attention in the last few years. Numerous filtration and indexing techniques have been created in order to...
Lossless filter for multiple repetitions with Hamming distance (2007)
Peterlongo, Pierre, Pisanti, Nadia, Boyer, Frédéric, Pereira Do Lago, Alair, Sagot, Marie-France
Similarity search in texts, notably in biological sequences, has received substantial attention in the last few years. Numerous filtration and indexing techniques have been created in order to...
Indexing gapped-factors using a tree (2007)
Peterlongo, Pierre, Allali, Julien, Sagot, Marie-France
We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the...
Indexing gapped-factors using a tree (2007)
Peterlongo, Pierre, Allali, Julien, Sagot, Marie-France
We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the...
BMC Systems Biology BioMed Central (2007)
Romain Bourqui, Ludovic Cottret, Vincent Lacroix, David Auber, Patrick Mary, Marie-france Sagot, ...
Software Metabolic network visualization eliminating node redundance and preserving metabolic pathways
Sérgio Lifschtiz, Marie-france Sagot, Inria France, Sérgio Ii. Sagot
The Brazilian Symposium on Bioinformatics (BSB 2007) was held in Angra dos
Peterlongo, Pierre, Allali, Julien, Sagot, Marie-France
We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The...
Peterlongo, Pierre, Allali, Julien, Sagot, Marie-France
We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The...
RISOTTO: Fast extraction of motifs with mismatches (2006)
Nadia Pisanti, Alexandra M. Carvalho, Ra M. Carvalho, Marie-France Sagot, Laurent Marsan
We present in this paper an exact algorithm for motif extraction. E#ciency is achieved by means of an improvement in the algorithm and data structures that applies to the whole class of motif...
Reaction Motifs in Metabolic Networks (2005)
Lacroix, Vincent, Gomes Fernandes, Cristina, Sagot, Marie-France
The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network...
Perfect Sorting by Reversals (2005)
Sagot, Marie-France, Tannier, Eric
In computational biology, gene order data is often modelled as signed permutations. A classical problem in genome comparison is to detect conserved segments in a permutation, that is, genes that are...
Reaction Motifs in Metabolic Networks (2005)
Lacroix, Vincent, Gomes Fernandes, Cristina, Sagot, Marie-France
The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network...
Perfect Sorting by Reversals (2005)
Sagot, Marie-France, Tannier, Eric
In computational biology, gene order data is often modelled as signed permutations. A classical problem in genome comparison is to detect conserved segments in a permutation, that is, genes that are...
Reaction Motifs in Metabolic Networks (2005)
Lacroix, Vincent, Gomes Fernandes, Cristina, Sagot, Marie-France
The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network...
Perfect Sorting by Reversals (2005)
Sagot, Marie-France, Tannier, Eric
In computational biology, gene order data is often modelled as signed permutations. A classical problem in genome comparison is to detect conserved segments in a permutation, that is, genes that are...
A new distance for high level RNA secondary structure comparison (2005)
Allali, Julien, Sagot, Marie-France
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations...
A new distance for high level RNA secondary structure comparison (2005)
Allali, Julien, Sagot, Marie-France
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations...
A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison (2005)
Allali, Julien, Sagot, Marie-France
We introduce a new data structure, called MiGaL for ``Multiple Graph Layers'', that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is useful...
A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison (2005)
Allali, Julien, Sagot, Marie-France
We introduce a new data structure, called MiGaL for ``Multiple Graph Layers'', that is composed of various graphs linked together by relations of abstraction/refinement. The new structure is useful...
Reaction motifs in metabolic networks (2005)
Vincent Lacroix, Cristina G. Fern, Marie-france Sagot
Abstract. The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the...
Emilios Cambouropoulos, Maxime Crochemore, Costas Iliopoulos, Manal Mohamed, Marie-france Sagot
This paper proposes an efficient pattern extraction algorithm that can be applied on melodic sequences that are represented as strings of abstract intervallic symbols; the melodic representation...
A New Distance for High Level RNA (2005)
Secondary Structure Comparison, Julien Allali, Marie-france Sagot
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations...
Emilios Cambouropoulos, Maxime Crochemore, Costas Iliopoulos, Manal Mohamed, Marie-france Sagot
This paper proposes an efficient pattern extraction algorithm that can be applied on melodic sequences that are represented as strings of abstract intervallic symbols; the melodic representation...
Sorting by reversals in subquadratic time (2004)
Tannier, Eric, Sagot, Marie-France
The problem of sorting by signed reversals is inspired by a genome rearrangement problem in computational molecular biology. Given two genomes represented as signed permutations of the same elements...
Sorting by reversals in subquadratic time (2004)
Tannier, Eric, Sagot, Marie-France
The problem of sorting by signed reversals is inspired by a genome rearrangement problem in computational molecular biology. Given two genomes represented as signed permutations of the same elements...
Sorting by reversals in subquadratic time (2004)
Tannier, Eric, Sagot, Marie-France
The problem of sorting by signed reversals is inspired by a genome rearrangement problem in computational molecular biology. Given two genomes represented as signed permutations of the same elements...
Novel tree edit operations for RNA secondary structure comparison (2004)
Allali, Julien, Sagot, Marie-France
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree edit...
Novel tree edit operations for RNA secondary structure comparison (2004)
Allali, Julien, Sagot, Marie-France
We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two novel operations, called node fusion and edge fusion, besides the tree edit...
A comparative study of bases for motif inference (2004)
Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-france Sagot
Motif inference is at the heart of several time-demanding computational tasks, such as in molecular biology, data mining and identification of structured motifs in sequences, and in data compression,...
A Parallel Algorithm for the Extraction of Structured Motifs (2004)
Alexandra M. Carvalho, Ana T. Freitas, Arlindo L. Oliveira, Marie-France Sagot
In this work we propose a parallel algorithm for the e#cient extraction of bindingsite consensus from genomic sequences. This algorithm, based on an existing approach, extracts structured motifs,...
A Parallel Algorithm for the Extraction of Structured Motifs (2004)
Alexandra M. Carvalho, Arlindo L. Oliveira, Ana T. Freitas, Marie-France Sagot
In this work we propose a parallel algorithm for the efficient extraction of binding-site consensus from genomic sequences. This algorithm, based on an existing approach, extracts structured motifs,...
The at Most k-Deep Factor Tree (2004)
Julien Allali, Marie-France Sagot
We present a new data structure to index strings that is very similar to a su#x tree.
Bases of motifs for generating repeated patterns with wild cards (2003)
Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-france Sagot
Motif inference represents one of the most important areas of research in computational biology, and one of its oldest ones. Despite this, the problem remains very much open in the sense that no...
Knowledge Representation Model (2003)
For Prokaryote Transcription, Sbastien J. Provencher, Marie-france Sagot
Introduction In the last decades, particularly due to the proliferation of powerful molecular biological tools and the automation of some processes, we assisted to an explosion of biological data....
A Basis for Repeated Motifs in Pattern Discovery and Text Mining Nadia Pisanti (2002)
Nadia Pisanti, Maxime Crochemore Roberto, Roberto Grossi, Marie-france Sagot
We present a new notion of basis that is able to generate the repeated motifs (possibly exponential in number) that appear at least twice with don't care symbols in a string of length n over an...
Current methods of gene prediction, their strengths and weaknesses (2002)
Mathé, Catherine, Sagot, Marie-France, Schiex, Thomas, Rouzé, Pierre
While the genomes of many organisms have been sequenced over the last few years, transforming such raw sequence data into knowledge remains a hard task. A great number of prediction programs have...
Anne Vanet, Laurent Marsan, Agneás Labigne, Marie-france Sagot, Uniteâ De Pathogeânie, ...
binding site. E-mail address of the corresponding author:
Laurent Marsan, Marie-france Sagot
promoter consensus identification
Laurent Marsan, Marie-France Sagot
This paper introduces two exact algorithms for extracting conserved structured motifs from a set of DNA sequences. Structured motifs may be described as an ordered collection of p # 1...
Laurent Marsan, Marie-France Sagot
This paper introduces two exact algorithms for extracting conserved structured motifs from a set of DNA sequences. Structured motifs are composed of p # 2 parts separated by constrained spacers....
Identifying Satellites and Periodic Repetitions in Biological Sequences (1998)
Marie-France Sagot, Eugene W. Myers, Service D'informatique Scientifique
We present in this paper an algorithm for identifying satellites in DNA sequences. Satellites (simple, micro, or mini) are repeats in number between 30 and as many as 1,000,000 whose lengths vary...
Spelling Approximate Repeated Or Common Motifs Using a Suffix Tree (1998)
Marie-France Sagot, Marie-france Sagot
. We present in this paper two algorithms. The first one extracts repeated motifs from a sequence defined over an alphabet \Sigma . For instance, \Sigma may be equal to fA, C, G, Tg and the sequence...
Identifying Satellites in Nucleic Acid Sequences (1998)
Marie-France Sagot, Eugene W. Myers, Service D'informatique Scientifique
We present in this paper an algorithm for identifying satellites in DNA sequences. Satellites (simple, micro, or mini) are repeats in number between 30 and as many as 1,000,000 whose lengths vary...
Identifying Satellites and Periodic Repetitions in Biological Sequences (1998)
Marie-France Sagot, Eugene W. Myers, Service D'informatique Scientifique
We present in this paper an algorithm for identifying satellites in DNA sequences. Satellites (simple, micro, or mini) are repeats in number between 30 and as many as 1,000,000 whose lengths vary...
Searching for Repeated Words in a Text Allowing for Mismatches and Gaps (1995)
Marie-France Sagot, Vincent Escalier, Alain Viari, Henri Soldano, Atelier De Bioinformatique
We present in this paper an algorithm that locates similar words common to a set of strings defined over an alphabet \Sigma, where the similarity is stated in terms of a Levenshtein edit distance....
Multiple Sequence Comparison - A Peptide Matching Approach (1995)
Marie-France Sagot, Alain Viari, Henri Soldano, Atelier De Bioinformatique, Avenue J. B
We present in this paper a peptide matching approach to the multiple comparison of a set of protein sequences. This approach consists in looking for all the words that are common to q of these...
Finding flexible patterns in a text: an application to three-dimensional molecular matching (1995)
Sagot, Marie-France, Viari, Alain, Pothier, Joël, Soldano, Henri
Finding certain regularities in a text is an important problem in many areas, e.g. in the analysis of biological molecules such as nucleic acids or proteins. In the latter case, the text may be...
Finding Flexible Patterns In A Text - An Application To 3d Molecular Matching (1994)
Marie-France Sagot, Alain Viari, Joël Pothier, Henri Soldano, Atelier De Bioinformatique
: Finding certain regularities in a text is an important problem in many areas, for instance in the analysis of biological molecules such as nucleic acids or proteins. In the latter case, the text...
SURVEY AND SUMMARY: Current methods of gene prediction, their strengths and weaknesses
Mathé, Catherine, Sagot, Marie-France, Schiex, Thomas, Rouzé, Pierre
While the genomes of many organisms have been sequenced over the last few years, transforming such raw sequence data into knowledge remains a hard task. A great number of prediction programs have...
SURVEY AND SUMMARY: Current methods of gene prediction, their strengths and weaknesses
Mathé, Catherine, Sagot, Marie-France, Schiex, Thomas, Rouzé, Pierre
While the genomes of many organisms have been sequenced over the last few years, transforming such raw sequence data into knowledge remains a hard task. A great number of prediction programs have...
Metabolic network visualization eliminating node redundance and preserving metabolic pathways
Bourqui, Romain, Cottret, Ludovic, Lacroix, Vincent, Auber, David, Mary, Patrick, Sagot, Marie-France, ...
Precise detection of rearrangement breakpoints in mammalian chromosomes
Lemaitre, Claire, Tannier, Eric, Gautier, Christian, Sagot, Marie-France
Assessing the Exceptionality of Coloured Motifs in Networks
Schbath, Sophie, Lacroix, Vincent, Sagot, Marie-France
Various methods have been recently employed to characterise the structure of biological networks. In particular, the concept of network motif and the related one of coloured motif have proven useful...
Lossless filter for multiple repeats with bounded edit distance
Peterlongo, Pierre, Sacomoto, Gustavo Akio Tominaga, Do Lago, Alair Pereira, Pisanti, Nadia, Sagot, Marie-France
Sagot, Marie-France, McKay, B.J. Morrison, Myers, Gene
The International Society for Computational Biology (ISCB; http://www.iscb.org) presents the Seventeenth Annual International Conference on Intelligent Systems for Molecular Biology (ISMB), organized...