- Article -
| In Silico Biology 7, 0031 (2007); ©2007, Bioinformation Systems e.V. |
Clustering gene expression data using graph separators
Bangaly Kaba1, Nicolas Pinet1, Gaëlle Lelandais2, Alain Sigayret1 and Anne Berry1*
1 LIMOS, UMR CNRS 6158, Ensemble des Cézeaux, 63173 Aubière cedex, France. Mail: {kaba; pinet; sigayret; berry} @isima.fr
2 Equipe de Bioinformatique Génomique et Moléculaire, INSERM U726, Université Paris 7, case 7113, 2 Place Jussieu, 75251 Paris cedex 05, France. Mail: lelandais @ebgm.jussieu.fr
* Corresponding author
Email: berry@isima.fr
Edited by E. Wingender; received February 12, 2007; revised May 09, 2007; accepted June 07, 2007; published August 27, 2007
Abstract
Recent work has used graphs to modelize expression data from microarray experiments, in view of partitioning the genes into clusters. In this paper, we introduce the use of a decomposition by clique separators. Our aim is to improve the classical clustering methods in two ways: first we want to allow an overlap between clusters, as this seems biologically sound, and second we want to be guided by the structure of the graph to define the number of clusters. We test this approach with a well-known yeast database (Saccharomyces cerevisiae). Our results are good, as the expression profiles of the clusters we find are very coherent. Moreover, we are able to organize into another graph the clusters we find, and order them in a fashion which turns out to respect the chronological order defined by the the sporulation process.
Keywords: clustering method, microarray, graph decomposition, threshold family of graphs, expression profile