GraphClust
A software to implement clique minimal separator decomposition
from a table of expression data

The GraphClust software implements clique minimal separator
decomposition of an undirected graph, starting from expression data
(such as microarray data).
The decomposition is obtained in 6 steps from a file containing the expression data:
 Normalize the expression data (if needed).
 From the (normalized) expression data, choose a distance function to compute a distance matrix.
 From the distance matrix, choose a threshold to compute the adjacency matrix of an undirected graph.
 Compute a minimal triangulation of the graph.
 Compute a clique tree of the minimal triangulation
 Compute an atom tree from the clique tree by merging nodes separated by a nonclique minimal separator.
Projected improvements:
Start with a distance matrix or with the matrix of a graph as input.
This project was implemented by students during 4 years of work:
PhD student :
 Romain Pogorelcnik, 20092012.
Second year Master research internships:
 Marie DefayFavre 2011: Impact of the distance function, ANR TODO.
 Bilel Yahiaoui 2012: In collaboration with BIOGEMMA, study of the clusters obtained by GraphClust on wheat disease data.
 Ghazi Kaoutar 2013: Implementation and tests, analysis of wheat data, ANR TODO.
Other projects:
 Karima Ennaoui 20122013: ISIMA Internship with Ghazi Kaoutar to implement new algorithms for GraphClust.
 Julien Combe: First year Master project: Implementing and testing
GraphClust, and 'Leimer', which does not compute the clique tree of a
minimal triangulation as preprocessing, ANR TODO.
 Jérémy
Renaud: First year Master project: Implementing 'OCF', a technique that
does not use minimal triangulation as preprocessing, ANR TODO.
 Raphaël CazenaveLévêque: 20132014: UE libre découverte du
milieu de la recherche: Discovering GraphClust and giving suggestions
on the interface.
Link to software
References:
Papers with my students:
 Clustering gene expression data using graph separators.
B. Kaba, N. Pinet, G. Lelandais, A. Sigayret, A. Berry.
In Silico Biol. 2007;7(45):43352.
 An introduction to Clique Minimal Separator Decomposition.
A. Berry, R. Pogorelcnik and G. Simonet.
Algorithms 3(2): 197215 (2010).
http://www.mdpi.com/19994893/3/2/197/
 A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph.
A. Berry, R. Pogorelcnik.
Information Processing Letters: 111(11): 508511 (2011).
 A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph.
A. Berry, R. Pogorelcnik.
Information Processing Letters: 111(11): 508511 (2011).
 Impact of the distance choice on clustering gene expression data using graph decompositions
Marie Defay, Romain Pogorelcnik, Annegret Wagler, Anne Berry.
Archive ouvertes HAL, 15.03.2012.
 MosaicFinder: Identification of fused gene families in sequence similarity networks.
P.A Jachiet, R. Pogorelcnik, A. Berry, P. Lopez, E. Bapteste.
Bioinformatics: 29(7):83744 (2013).
 Organizing the atoms of the clique separator decomposition into an atom tree.
A. Berry, G. Simonet and R. Pogorelcnik.
Submitted to Discrete Applied Mathematics.
pdf
Other references:
 J.R.S. Blair and B.W. Peyton.
An introduction to chordal graphs and clique trees.
Graph Theory and Sparse Matrix Computation, 84(13): 129, 1993.
 R.E. Tarjan.
Decomposition by clique separators.
Discrete Math., 55:221232, 1985.
 H.G. Leimer.
Optimal decomposition by clique separators.
Discrete Math., 113:99123, 1993.