Finding Occurrences of Protein Complexes in Protein-Protein Interaction Graphs (2009)
Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the protein-protein interaction...
Maximum Motif Problem in Vertex-Colored Graphs (2009)
Dondi, Riccardo, Fertin, Guillaume, Vialette, Stéphane
Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In this context, dierent graph motif problems have been considered [12, 6, 4]. Pursuing a line of...
On the Approximability of Comparing Genomes with Duplicates (2009)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thévenin, Annelyse, Vialette, Stéphane
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such measures has...
Comparing Bacterial Genomes by Searching their Common Intervals (2009)
Angibaud, Sébastien, Eveillard, Damien, Fertin, Guillaume, Rusu, Irena
Comparing bacterial genomes implies the use of a dedicated measure. It relies on comparing circular genomes based on a set of conserved genes. Following this assumption, the common interval appears...
Pseudo-Boolean Programming for Partially Ordered Genomes (2009)
Angibaud, Sébastien, Fertin, Guillaume, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species is a crucial problem in comparative genomics. Different measures have been proposed to compare two genomes: number of common intervals, number of adjacencies,...
The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated (2009)
Blin, Guillaume, Fertin, Guillaume, Sikora, Florian, Vialette, Stéphane
A promising and active field of comparative genomics con- sists in comparing two genomes by establishing a one-to-one correspon- dence (i.e., a matching) between their genes. This correspondence is...
Comparison of Spectra in Unsequenced Species (2009)
Cliquet, Freddy, Fertin, Guillaume, Rusu, Irena, Tessier, Dominique
We introduce a new algorithm for the mass spectromet- ric identication of proteins. Experimental spectra obtained by tandem MS/MS are directly compared to theoretical spectra generated from pro-...
On the S-labeling Problem (2009)
Fertin, Guillaume, Vialette, Stéphane
Let G be a graph of order n and size m. A labeling of G is a bijective mapping theta : V(G) --> 1, 2...n, and we call Theta(G) the set of all labelings of G. For any graph G and any labeling theta in...
On Finding Small 2-Generating Sets (2009)
Fagnot, Isabelle, Fertin, Guillaume, Vialette, Stéphane
Given a set of positive integers S, we consider the problem of finding a minimum cardinality set of positive integers X (called a minimum 2-generating set of S) s.t. every element of S is an element...
Finding Occurrences of Protein Complexes in Protein-Protein Interaction Graphs (2009)
Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the protein-protein interaction...
Maximum Motif Problem in Vertex-Colored Graphs (2009)
Dondi, Riccardo, Fertin, Guillaume, Vialette, Stéphane
Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In this context, different graph motif problems have been considered [12, 6, 4]. Pursuing a line of...
On the Approximability of Comparing Genomes with Duplicates (2009)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thévenin, Annelyse, Vialette, Stéphane
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such measures has...
Comparing Bacterial Genomes by Searching their Common Intervals (2009)
Angibaud, Sébastien, Eveillard, Damien, Fertin, Guillaume, Rusu, Irena
Comparing bacterial genomes implies the use of a dedicated measure. It relies on comparing circular genomes based on a set of conserved genes. Following this assumption, the common interval appears...
Pseudo-Boolean Programming for Partially Ordered Genomes (2009)
Angibaud, Sébastien, Fertin, Guillaume, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species is a crucial problem in comparative genomics. Different measures have been proposed to compare two genomes: number of common intervals, number of adjacencies,...
The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated (2009)
Blin, Guillaume, Fertin, Guillaume, Sikora, Florian, Vialette, Stéphane
A promising and active field of comparative genomics con- sists in comparing two genomes by establishing a one-to-one correspon- dence (i.e., a matching) between their genes. This correspondence is...
Comparison of Spectra in Unsequenced Species (2009)
Cliquet, Freddy, Fertin, Guillaume, Rusu, Irena, Tessier, Dominique
We introduce a new algorithm for the mass spectromet- ric identication of proteins. Experimental spectra obtained by tandem MS/MS are directly compared to theoretical spectra generated from pro-...
On the S-labeling Problem (2009)
Fertin, Guillaume, Vialette, Stéphane
Let G be a graph of order n and size m. A labeling of G is a bijective mapping theta : V(G) --> 1, 2...n, and we call Theta(G) the set of all labelings of G. For any graph G and any labeling theta in...
On Finding Small 2-Generating Sets (2009)
Fagnot, Isabelle, Fertin, Guillaume, Vialette, Stéphane
Given a set of positive integers S, we consider the problem of finding a minimum cardinality set of positive integers X (called a minimum 2-generating set of S) s.t. every element of S is an element...
Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms (2009)
Bulteau, Laurent, Fertin, Guillaume, Rusu, Irena
Given two comparative maps, that is two sequences of markers each representing a genome, the Maximal Strip Recovery problem (MSR) asks to extract a largest sequence of markers from each map such that...
Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms (2009)
Bulteau, Laurent, Fertin, Guillaume, Rusu, Irena
Given two comparative maps, that is two sequences of markers each representing a genome, the Maximal Strip Recovery problem (MSR) asks to extract a largest sequence of markers from each map such that...
Cedric Chauve Lacim, Guillaume Blin, Cedric Chauve, Guillaume Fertin
The breakpoint distance for signed sequences (extended abstract) Guillaume Blin, Guillaume Fertin LINA FRE CNRS 2729, Universit'e de Nantes
On the Approximability of Comparing Genomes with Duplicates (2008)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogeny. All the existing measures are defined on...
Manuscript Extracting Constrained 2-Interval Subsets in 2-Interval Sets ⋆ Abstract (2008)
Guillaume Blin, Guillaume Fertin, Stéphane Vialette
2-interval sets were used in [28,29] for establishing a general representation for macroscopic describers of RNA secondary structures.In this context, we have a 2-interval for each legal local fold...
Common Structured Patterns in Linear Graphs: Approximations and Combinatorics ⋆ (2008)
Guillaume Fertin, Danny Hermelin, Romeo Rizzi, Stéphane Vialette
Abstract. A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting (⊏) or crossing (≬). Given a...
Tiziana Calamoneri, Saverio Caminiti, Guillaume Fertin, Tiziana Calamoneri, Saverio Caminiti, Guillaume Fertin, ...
New Bounds for the L(h, k) Number of Regular Grids 18 p. Les rapports de recherche du Laboratoire d’Informatique de Nantes-Atlantique sont disponibles aux formats PostScript ® et PDF ® à l’URL:
similarity search under mRNA (2008)
Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette
Fixed-parameter algorithms for protein
On the Approximability of Comparing Genomes with Duplicates (2008)
Sébastien Angibaud, Guillaume Fertin, Irena Rusu
Abstract. A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such...
2 LINA- FRE CNRS 2729- Universit'e de Nantes (2008)
Guillaume Blin, Guillaume Fertin
1 Introduction In computational biology, the understanding of biological mechanisms is fre-quently induced by sequences comparison. However, in the context of RiboNucleic Acid molecules (RNA), one...
The breakpoint distance for signed sequences (extended abstract) (2008)
Guillaume Blin, Cedric Chauve, Guillaume Fertin
Abstract. We consider the problem of estimating the rearrangement distance in terms of reversals, insertion and deletion between two genomes, G and H with possibly multiple genes from the same gene...
Common Structured Patterns in Linear Graphs: Approximation and Combinatorics (2008)
Guillaume Fertin, Danny Hermelin, Romeo Rizzi
Abstract. A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting (⊏) or crossing (≬). Given a...
No-Hole L p ¡ 0 ¢ Labelings † (2008)
Guillaume Fertin, André Raspaud
We address here a particular case of the general problem of λ labelings, motivated by frequency assignment for telecommunication networks. In this model, stations lying within a given radius r must...
Recognizing Recursive Circulant Graphs Abstract (Extended Abstract) (2008)
Recursive circulant graphs G(N�d) have been introduced in 1994 by Park and Chwa [PC94] as a new topology for interconnection networks. Recursive circulant graphs G(N�d) are circulant graphs with...
Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Annelyse Thévenin, Stéphane Vialette
A Pseudo-Boolean programming approach for
Guillaume Blin, Guillaume Fertin, Gaël Herry, Stéphane Vialette
Abstract. In the recent past, RNA structure comparison has appeared as an important field of bioinformatics. In this paper, we introduce a new and general intermediate model for comparing RNA...
Genomes containing Duplicates are Hard to compare (Extended Abstract) ⋆ (2008)
Cedric Chauve, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Abstract. In this paper, we are interested in the algorithmic complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes. In that case, there are usually...
Recognizing Recursive Circulant Graphs Abstract (Extended Abstract) (2008)
Recursive circulant graphs G(N � d) have been introduced in 1994 by Park and Chwa [PC94] as a new topology for interconnection networks. Recursive circulant graphs G(N � d) are circulant graphs...
High dimensional Apollonian networks (2008)
Zhongzhi Zhang, Francesc Comellas, Guillaume Fertin, Lili Rong
Abstract. We propose a simple algorithm which produces high dimensional Apollonian networks with both small-world and scale-free characteristics. We derive analytical expressions for the degree...
Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Abstract. Comparing genomic properties of multiple species at varying evolutionary distances is a powerful approach for studying biological and evolutionary principles. In the context of comparative...
Conversion de Longueur d’Onde dans les (2008)
Guillaume Fertin, Emmanuel Godard, André Raspaud
godard,raspaud£
Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough (2008)
Guillaume Fertin, André Raspaud
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
No-Hole L p�0 Labelings † (2008)
Guillaume Fertin, André Raspaud
We address here a particular case of the general problem of λ labelings, motivated by frequency assignment for telecommunication networks. In this model, stations lying within a given radius r must...
Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Abstract. Comparing genomic properties of multiple species at varying evolutionary distances is a powerful approach for studying biological and evolutionary principles. In the context of comparative...
Acyclic Coloring of Graphs of Maximum Degree ∆ (2008)
Guillaume Fertin, André Raspaud
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough (2008)
Guillaume Fertin, André Raspaud
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
Weak pattern matching in colored graphs: Minimizing the number of connected components (2008)
Riccardo Dondi, Guillaume Fertin, Stéphane Vialette
In the context of metabolic network analysis, Lacroix et al. 11 introduced the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors and an...
similarity search under mRNA (2008)
Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette
Fixed-parameter algorithms for protein
Acyclic Coloring of Graphs of Maximum Degree ∆ (2008)
Guillaume Fertin, André Raspaud
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
Fertin: New bounds for the L(h, k) number of regular grids (2008)
Tiziana Calamoneri, Saverio Caminiti, Guillaume Fertin
Abstract: For any non negative real values h and k, an L(h, k)-labeling of a graph G = (V, E) is a function L: V → R such that |L(u) − L(v) | ≥ h if (u, v) ∈ E and |L(u) − L(v) | ≥ k if...
Guillaume Blin, Guillaume Fertin, Romeo Rizzi
Universit'e de Nantes, 2 rue de la Houssini`ere
A general framework for computing rearrangement distances between genomes with duplicates (2008)
Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Stéphane Vialette
Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance
Guillaume Fertin, Irin Upres-ea
Abstract Kn"odel graphs of even order n and degree 1 ^ \Delta ^ blog2(n)c, W\Delta;n, are graphs which have been introduced some 25 years ago as the topology underlying a time optimal...
On the Approximability of Comparing Genomes with Duplicates (2008)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogeny. All the existing measures are defined on...
On the Approximability of Comparing Genomes with Duplicates (2008)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogeny. All the existing measures are defined on...
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species is a fundamental problem in comparative genomics. Recent research has resulted in the introduction of different measures between pairs of genomes: reversal...
Fixed-Parameter Algorithms For Protein Similarity Search Under mRNA Structure Constraints (2008)
Blin, Guillaume, Fertin, Guillaume, Hermelin, Danny, Vialette, Stéphane
In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally...
On the Approximability of Comparing Genomes with Duplicates (2008)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena
A central problem in comparative genomics consists in computing a (dis-)simi- larity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such measures has...
Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough (2008)
Fertin, Guillaume, Raspaud, André
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
Vertex labeling and routing in expanded Apollonian networks (2008)
Zhang, Zhongzhi, Comellas, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species is a fundamental problem in comparative genomics. Recent research has resulted in the introduction of different measures between pairs of genomes: reversal...
Fixed-Parameter Algorithms For Protein Similarity Search Under mRNA Structure Constraints (2008)
Blin, Guillaume, Fertin, Guillaume, Hermelin, Danny, Vialette, Stéphane
In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally...
On the Approximability of Comparing Genomes with Duplicates (2008)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena
A central problem in comparative genomics consists in computing a (dis-)simi- larity measure between two genomes, e.g. in order to construct a phylogenetic tree. A large number of such measures has...
Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough (2008)
Fertin, Guillaume, Raspaud, André
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic...
Vertex labeling and routing in expanded Apollonian networks (2008)
Zhang, Zhongzhi, Comellas, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
Diameter of Knödel Graph (2007)
Guillaume Fertin, André Raspaud, Heiko Schröder, Ondrej Sykora, Imrich Vrto
We show that the diameter of 2 k nodes Knödel graph of degree k is d(k +2)=2e:
A Survey on Knödel Graphs (2007)
Guillaume Fertin, André Raspaud, F Talence Cedex
Knodel graphs of even order n and degree 1 \Delta blog 2 (n)c, W \Delta;n , are graphs which have been introduced some 25 years ago as the topology underlying a time optimal algorithm for gossiping...
Recognizing Recursive Circulant Graphs G(cd m ,d) (2007)
Guillaume Fertin, André Raspaud, F Talence Cedex
Recursive circulant graphs G(N, d) have been introduced in 1994 by Park and Chwa [PC94] as a new topology for interconnection networks. Recursive circulant graphs G(N, d) are circulant graphs with N...
Trade-Offs for Odd Gossiping (Extended abstract) (2007)
Guillaume Fertin, F Talence Cedex
In the gossiping problem, each node of a network starts with a unique piece of information and must acquire the information of all the other nodes. This is done using two-way communications between...
Minimum Gossip Digraphs (2007)
Guillaume Fertin, F Talence Cedex
Gossiping is a problem of information dissemination described in a group of individuals connected by a communication network, where every individual in the network knows a unique item of information...
On the Structure of Minimum Broadcast (2007)
Guillaume Fertin, F Talence Cedex
Broadcasting is a problem of information dissemination described in a group of individuals connected by a communication network, where one individual has an item of information and needs to...
Succursale Centre-ville, Cedric Chauve, Cedric Chauve, Cedric Chauve, ...
On maximal instances for the original syntenic distance
Guillaume Fertin, Bruce Reed, Irin Upres-ea
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
Routing Permutations and 2-1 Routing Requests in the Hypercube 1 (2007)
Olivier Baudon, Guillaume Fertin, F Talence Cedex, Ivan Havel
Let H n be the directed symmetric n-dimensional hypercube. Using the computer, we show that for any permutation of the vertices of H 4, there exists a system of pairwise arc-disjoint directed paths...
Vertex labeling and routing in expanded Apollonian networks (2007)
Zhang, Zhongzhi, Comellas Padró, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
Vertex labeling and routing in expanded Apollonian networks (2007)
Zhang, Zhongzhi, Comellas Padró, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
Vertex labeling and routing in expanded Apollonian networks (2007)
Zhang, Zhongzhi, Comellas Padró, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
On the Approximability of Comparing Genomes with Duplicates (2007)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes. A large number of such measures has been proposed in the recent past: breakpoints,...
On the Approximability of Comparing Genomes with Duplicates (2007)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena
A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes. A large number of such measures has been proposed in the recent past: breakpoints,...
Extending the Hardness of RNA Secondary Structure Comparison (2007)
Blin, Guillaume, Fertin, Guillaume, Rusu, Irena, Sinoquet, Christine
...
Extending the Hardness of RNA Secondary Structure Comparison (2007)
Blin, Guillaume, Fertin, Guillaume, Rusu, Irena, Sinoquet, Christine
...
TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2 (2007)
Guillaume Blin, Cedric Chauve, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
In this paper, we are interested in the computational complexity of computing (dis)simila-rity measures between two genomes when they contain duplicated genes or genomic markers, a problem that...
Extending the hardness of RNA secondary structure comparison (2007)
Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet
Abstract. In molecular biology, RNA structure comparison is of great interest to help solving problems as different as phylogeny reconstruction, prediction of molecule folding and identification of a...
TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2 (2007)
Guillaume Blin, Cedric Chauve, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
In this paper, we are interested in the computational complexity of computing (dis)simila-rity measures between two genomes when they contain duplicated genes or genomic markers, a problem that...
Sharp tractability borderlines for finding connected motifs in vertex-colored graphs (2007)
Michael R. Fellows, Guillaume Fertin, Danny Hermelin, Stéphane Vialette
Abstract. We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices with a...
Sharp tractability borderlines for finding connected motifs in vertex-colored graphs (2007)
Michael R. Fellows, Guillaume Fertin, Danny Hermelin
Abstract. We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices with a...
Extending the hardness of RNA secondary structure comparison (2007)
Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet
Abstract. In molecular biology, RNA structure comparison is of great interest to help solving problems as different as phylogeny reconstruction, prediction of molecule folding and identification of a...
Sharp tractability borderlines for finding connected motifs in vertex-colored graphs (2007)
Michael R. Fellows, Guillaume Fertin, Danny Hermelin, Stéphane Vialette
Abstract. We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices with a...
L(p,q) labeling of d-Dimensional Grids (2007)
Fertin, Guillaume, Raspaud, André
In this paper, we address the problem of lambda labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r...
L(p,q) labeling of d-Dimensional Grids (2007)
Fertin, Guillaume, Raspaud, André
In this paper, we address the problem of lambda labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r...
Exemplar Longest Common Subsequence (2007)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo, Fertin, Guillaume, Rizzi, Rafaella, Vialette, Stéphane
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common...
Comparing Genomes with Duplications: a Computational Complexity Point of View (2007)
Blin, Guillaume, Chauve, Cedric, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In this paper, we are interested in the computational complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes or genomic markers, a problem that...
Extracting Constrained 2-Interval Subsets in 2-Interval Sets (2007)
Blin, Guillaume, Fertin, Guillaume, Vialette, Stéphane
2-interval sets were used in [S. Vialette, Pattern matching over 2-intervals sets, in: Proc. 13th Annual Symposium Combinatorial Pattern Matching, CPM 2002, in: Lecture Notes in Computer Science,...
Exemplar Longest Common Subsequence (2007)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo, Fertin, Guillaume, Rizzi, Rafaella, Vialette, Stéphane
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common...
Comparing Genomes with Duplications: a Computational Complexity Point of View (2007)
Blin, Guillaume, Chauve, Cedric, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In this paper, we are interested in the computational complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes or genomic markers, a problem that...
Extracting Constrained 2-Interval Subsets in 2-Interval Sets (2007)
Blin, Guillaume, Fertin, Guillaume, Vialette, Stéphane
2-interval sets were used in [S. Vialette, Pattern matching over 2-intervals sets, in: Proc. 13th Annual Symposium Combinatorial Pattern Matching, CPM 2002, in: Lecture Notes in Computer Science,...
A General Framework for Computing Rearrangement Distances between Genomes with Duplicates (2007)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Vialette, Stéphane
Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions: number of breakpoints,...
A General Framework for Computing Rearrangement Distances between Genomes with Duplicates (2007)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Vialette, Stéphane
Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions: number of breakpoints,...
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs (2007)
Fellows, Michael R., Fertin, Guillaume, Hermelin, Danny, Vialette, Stéphane
We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices with a bijection...
Weak pattern matching in colored graphs: Minimizing the number of connected components (2007)
Dondi, Riccardo, Fertin, Guillaume, Vialette, Stéphane
In the context of metabolic network analysis, Lacroix et al.11 introduced the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors and an...
Blin, Guillaume, Fertin, Guillaume, Herry, Gaël, Vialette, Stéphane
In the recent past, RNA structure comparison has appeared as an important field of bioinformatics. In this paper, we introduce a new and general intermediate model for comparing RNA structures: the...
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species has become a crucial problem in comparative genomics. Recent research have resulted in different genomic distance definitions: number of breakpoints, number of...
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs (2007)
Fellows, Michael R., Fertin, Guillaume, Hermelin, Danny, Vialette, Stéphane
We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices with a bijection...
Extending the Hardness of RNA Secondary Structure Comparison (2007)
Blin, Guillaume, Fertin, Guillaume, Rusu, Irena, Sinoquet, Christine
In molecular biology, RNA structure comparison is of great interest to help solving problems as different as phylogeny reconstruction, prediction of molecule folding and identification of a function...
Common Structured Patterns in Linear Graphs: Approximations and Combinatorics (2007)
Fertin, Guillaume, Hermelin, Danny, Rizzi, Romeo, Vialette, Stéphane
A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (
Weak pattern matching in colored graphs: Minimizing the number of connected components (2007)
Dondi, Riccardo, Fertin, Guillaume, Vialette, Stéphane
In the context of metabolic network analysis, Lacroix et al.11 introduced the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors and an...
Blin, Guillaume, Fertin, Guillaume, Herry, Gaël, Vialette, Stéphane
In the recent past, RNA structure comparison has appeared as an important field of bioinformatics. In this paper, we introduce a new and general intermediate model for comparing RNA structures: the...
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Thevenin, Annelyse, Vialette, Stéphane
Comparing genomes of different species has become a crucial problem in comparative genomics. Recent research have resulted in different genomic distance definitions: number of breakpoints, number of...
Extending the Hardness of RNA Secondary Structure Comparison (2007)
Blin, Guillaume, Fertin, Guillaume, Rusu, Irena, Sinoquet, Christine
In molecular biology, RNA structure comparison is of great interest to help solving problems as different as phylogeny reconstruction, prediction of molecule folding and identification of a function...
Common Structured Patterns in Linear Graphs: Approximations and Combinatorics (2007)
Fertin, Guillaume, Hermelin, Danny, Rizzi, Romeo, Vialette, Stéphane
A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (
Vertex labeling and routing in expanded Apollonian networks (2006)
Zhang, Zhongzhi, Comellas, Francesc, Fertin, Guillaume, Raspaud, André, Rong, Lili, Zhou, Shuigeng
We present a family of networks, expanded deterministic Apollonian networks, which are a generalization of the Apollonian networks and are simultaneously scale-free, small-world, and highly...
New Bounds for the L(h, k) Number of Regular Grids (2006)
Calamoneri, Tiziana, Caminiti, Saverio, Fertin, Guillaume
For any non negative real values h and k, an L(h; k)-labeling of a graph G = (V;E) is a function L : V ! R such that jL(u) L(v)j h if (u; v) 2 E and jL(u) L(v)j k if there...
New Bounds for the L(h, k) Number of Regular Grids (2006)
Calamoneri, Tiziana, Caminiti, Saverio, Fertin, Guillaume
For any non negative real values h and k, an L(h; k)-labeling of a graph G = (V;E) is a function L : V ! R such that jL(u) L(v)j h if (u; v) 2 E and jL(u) L(v)j k if there...
New Bounds for the L(h, k) Number of Regular Grids (2006)
Calamoneri, Tiziana, Caminiti, Saverio, Fertin, Guillaume
For any non negative real values h and k, an L(h; k)-labeling of a graph G = (V;E) is a function L : V ! R such that jL(u) L(v)j h if (u; v) 2 E and jL(u) L(v)j k if there...
New Bounds for the L(h, k) Number of Regular Grids (2006)
Calamoneri, Tiziana, Caminiti, Saverio, Fertin, Guillaume
For any non negative real values h and k, an L(h; k)-labeling of a graph G = (V;E) is a function L : V ! R such that jL(u) L(v)j h if (u; v) 2 E and jL(u) L(v)j k if there...
How pseudo-boolean programming can help genome rearrangement distance computation (2006)
Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Stéphane Vialette
Abstract. Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions: number of...
Exemplar longest common subsequence (2006)
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, Stéphane Vialette
Abstract. In the paper we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest...
Exemplar longest common subsequence (2006)
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, Stéphane Vialette
Abstract. In the paper we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest...
Genomes containing Duplicates are Hard to compare (2006)
Chauve, Cedric, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In this paper, we are interested in the algorithmic complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes. In that case, there are usually two main...
How Pseudo-Boolean Programming can help Genome Rearrangement Distance Computation (2006)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Vialette, Stéphane
Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions: number of breakpoints,...
Genomes containing Duplicates are Hard to compare (2006)
Chauve, Cedric, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In this paper, we are interested in the algorithmic complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes. In that case, there are usually two main...
How Pseudo-Boolean Programming can help Genome Rearrangement Distance Computation (2006)
Angibaud, Sébastien, Fertin, Guillaume, Rusu, Irena, Vialette, Stéphane
Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions: number of breakpoints,...
High Dimensional Apollonian Networks (2005)
Zhang, Zhongzhi, Comellas, Francesc, Fertin, Guillaume, Rong, Lili
We propose a simple algorithm which produces high dimensional Apollonian networks with both small-world and scale-free characteristics. We derive analytical expressions for the degree distribution,...
What makes the arc-preserving subsequence problem hard (2005)
Guillaume Blin, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Abstract. In molecular biology, RNA structure comparison and motif search are of great interest for solving major problems such as phylogeny reconstruction, prediction of molecule folding and...
Genes order and phylogenetic reconstruction: Application to γ-proteobacteria (2005)
Guillaume Blin, Cedric Chauve, Guillaume Fertin
Abstract. We study the problem of phylogenetic reconstruction based on gene order for whole genomes. We define three genomic distances between whole genomes represented by signed sequences, based on...
What makes the arc-preserving subsequence problem hard (2005)
Guillaume Blin, Guillaume Fertin, Romeo Rizzi
1 Introduction At a molecular state, the understanding of biological mechanisms is subordinated to RNA functionsdiscovery and study. Indeed, it is established that the conformation of a...
What makes the arc-preserving subsequence problem hard (2005)
Guillaume Blin, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Abstract. Given two arc-annotated sequences (S, P) and (T, Q) representing RNA structures, the Arc-Preserving Subsequence (APS) problem asks whether (T, Q) can be obtained from (S, P) by deleting...
What makes the Arc-Preserving Subsequence problem hard ? (2005)
Blin, Guillaume, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In molecular biology, RNA structure comparison and motif search are of great interest for solving major problems such as phylogeny reconstruction, prediction of molecule folding and identification of...
What makes the Arc-Preserving Subsequence problem hard ? (2005)
Blin, Guillaume, Fertin, Guillaume, Rizzi, Romeo, Vialette, Stéphane
In molecular biology, RNA structure comparison and motif search are of great interest for solving major problems such as phylogeny reconstruction, prediction of molecule folding and identification of...
Recursive graphs with small-world scale-free properties (2004)
Comellas, Francesc, Fertin, Guillaume, Raspaud, André
We discuss a category of graphs, recursive clique trees, which have small-world and scale-free properties and allow a fine tuning of the clustering and the power-law exponent of their discrete degree...
Star Coloring of Graphs (2004)
Fertin, Guillaume, Raspaud, André, Reed, Bruce
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
A Survey of Knödel Graphs (2004)
Fertin, Guillaume, Raspaud, André
Knödel graphs of even order n and degree 1\leq Delta \leq \lfloor log2(n)\rfloor, W(Delta,n), are graphs which have been introduced some 25 years ago as the topology underlying a time optimal...
No-Hole L(p,0)-Labelling of Cycles, Grids and Hypercubes (2004)
Fertin, Guillaume, Raspaud, André, Sykora, Ondrej
In this paper, we address a particular case of the general problem of $\lambda$ labellings, concerning frequency assignment for telecommunication networks. In this model, stations within a given...
Star Coloring of Graphs (2004)
Fertin, Guillaume, Raspaud, André, Reed, Bruce
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
A Survey of Knödel Graphs (2004)
Fertin, Guillaume, Raspaud, André
Knödel graphs of even order n and degree 1\leq Delta \leq \lfloor log2(n)\rfloor, W(Delta,n), are graphs which have been introduced some 25 years ago as the topology underlying a time optimal...
No-Hole L(p,0)-Labelling of Cycles, Grids and Hypercubes (2004)
Fertin, Guillaume, Raspaud, André, Sykora, Ondrej
In this paper, we address a particular case of the general problem of $\lambda$ labellings, concerning frequency assignment for telecommunication networks. In this model, stations within a given...
On Maximal Instances for the Original Syntenic Distance (2004)
Chauve, Cedric, Fertin, Guillaume
The syntenic distance between two genomes has been introduced by Ferretti, Nadeau and Sankoff as an approximation of the evolutionary distance between genomes for which the gene order is not known....
On Maximal Instances for the Original Syntenic Distance (2004)
Chauve, Cedric, Fertin, Guillaume
The syntenic distance between two genomes has been introduced by Ferretti, Nadeau and Sankoff as an approximation of the evolutionary distance between genomes for which the gene order is not known....
On maximal instances for the original syntenic distance (2003)
Cedric Chauve, Guillaume Fertin
The syntenic distance was introduced by Ferretti Nadeau and Sankoff as a mesure of evolutionary distance between multichromosomal genomes in terms of rearrangements at the genes level. In this work,...
Tiziana Calamoneri, Saverio Caminiti, Guillaume Fertin
For any non negative real values h and k, an L(h, k)-labeling of a graph G = (V, E) is a function L: V → IR such that |L(u) − L(v) | ≥ h if (u, v) ∈ E and |L(u) − L(v) | ≥ k if there...
On maximal instances for the original syntenic (2003)
Cedric Chauve, Guillaume Fertin, Cedric Chauve, Guillaume Fertin, Cedric Chauve, ...
distance
On maximal instances for theoriginal syntenic distance (2003)
Recherche En, Informatique De Nantes, Cedric Chauve, Guillaume Fertin
IRIN, Universit'e de Nantes2, rue de la Houssini`ere B.P. 92208-- F-44322 NANTES CEDEX 3 Cedric Chauve and Guillaume FertinOn maximal instances for the original syntenic distance 22 p. Les...
L(p, q) Labeling of d-Dimensional Grids (2003)
Guillaume Fertin, André Raspaud
In this paper, we address the problem of λ labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r must...
RNA Sequences and the EDIT(Nested, Nested) Problem (2003)
Guillaume Blin, Guillaume Blin, Guillaume Fertin, Guillaume Fertin, Irena Rusu, Irena Rusu, ...
In this paper, we prove that the so-called Edit(Nested,Nested) problem -- corresponding to the edit distance computation between two RNA secondary structures -- is NP-Complete. General Terms:...
L(p, q) Labeling of d-Dimensional Grids (2003)
Guillaume Fertin, André Raspaud
In this paper, we address the problem of λ labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r must...
On maximal instances for the original syntenic (2003)
Cedric Chauve, Guillaume Fertin, Cedric Chauve, Guillaume Fertin, Cedric Chauve, ...
distance
On the oriented chromatic number of grids (2003)
Fertin, Guillaume, Raspaud, André, Roychowdhury, Arup
In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph $G$ without symmetric arcs such that (i) no two neighbors in $G$ are...
On the oriented chromatic number of grids (2003)
Fertin, Guillaume, Raspaud, André, Roychowdhury, Arup
In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph $G$ without symmetric arcs such that (i) no two neighbors in $G$ are...
Minimum feedback vertex set and acyclic coloring (2002)
Fertin, Guillaume, Godard, Emmanuel, Raspaud, André
In the feedback vertex set problem, the aim is to minimize, in a connected graph G =(V,E), the cardinality of the set overline(V) (G) \subseteq V , whose removal induces an acyclic subgraph. In this...
Minimum feedback vertex set and acyclic coloring (2002)
Fertin, Guillaume, Godard, Emmanuel, Raspaud, André
In the feedback vertex set problem, the aim is to minimize, in a connected graph G =(V,E), the cardinality of the set overline(V) (G) \subseteq V , whose removal induces an acyclic subgraph. In this...
k-neighborhood broadcasting (2001)
Broadcasting refers to the task whereby a node in a network, knowing piece of information, must transmit it to all the other nodes. In this pap we consider a generalized form of broadcasting, that we...
On star coloring of graphs (2001)
Guillaume Fertin, André Raspaud, Bruce Reed
In this paper, we deal with the notion of star coloring of graphs. A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such...
On star coloring of graphs (2001)
Guillaume Fertin, André Raspaud, Bruce Reed
In this paper, we deal with the notion of star coloring of graphs. A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such...
Compounding of Gossip Graphs (1999)
Guillaume Fertin, Roger Labahn
Gossiping refers to the problem of information dissemination described in a group of individuals connected by a communication network, whereby every node has a piece of information and needs to...
Compounding of gossip graphs (1999)
Guillaume Fertin, Roger Labahn
Gossiping refers to the following task: In a group of individuals connected by a communication network, every node has a piece of information and needs to transmit it to all the nodes in the network....
Guillaume Fertin, Joseph G. Peters
In the gossiping problem, each node in a network starts with a unique piece of information and must acquire the information of all other nodes using two-way communications between pairs of nodes. In...
A study of minimum gossip graphs (1997)
Guillaume Fertin, F Talence Cedex
Gossiping and broadcasting are two problems of information dissemination described in a group of individuals connected by a communication network. In broadcasting, one individual has an item of...