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:

  1. Normalize the expression data (if needed).
  2. From the (normalized) expression data, choose a distance function to compute a distance matrix.
  3. From the distance matrix, choose a threshold to compute the adjacency matrix of an undirected graph.
  4. Compute a minimal triangulation of the graph.
  5. Compute a clique tree of the minimal triangulation
  6. Compute an atom tree from the clique tree by merging nodes separated by a non-clique 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 :

Second year Master research internships:

Other projects:

Link to software

References:

Papers with my students:

  1. Clustering gene expression data using graph separators.
    B. Kaba, N. Pinet, G. Lelandais, A. Sigayret, A. Berry.
    In Silico Biol. 2007;7(4-5):433-52.

  2. An introduction to Clique Minimal Separator Decomposition.
    A. Berry, R. Pogorelcnik and G. Simonet.
    Algorithms 3(2): 197-215 (2010).
    http://www.mdpi.com/1999-4893/3/2/197/

  3. 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): 508-511 (2011).

  4. 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): 508-511 (2011).

  5. 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.

  6. MosaicFinder: Identification of fused gene families in sequence similarity networks.
    P.-A Jachiet, R. Pogorelcnik, A. Berry, P. Lopez, E. Bapteste.
    Bioinformatics: 29(7):837-44 (2013).

  7. 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:

  1.  J.R.S. Blair and B.W. Peyton.
    An introduction to chordal graphs and clique trees.
    Graph Theory and Sparse Matrix Computation, 84(1-3): 1-29, 1993.

  2. R.E. Tarjan.
    Decomposition by clique separators.
    Discrete Math., 55:221-232, 1985.

  3. H.-G. Leimer.
    Optimal decomposition by clique separators.
    Discrete Math., 113:99-123, 1993.