Research

A biclustering algorithm based on a Bicluster Enumeration Tree: application to DNA microarray data

Wassim Ayadi^1,2 , Mourad Elloumi¹ and Jin-Kao Hao²

¹  UTIC, Higher School of Sciences and Technologies of Tunis, 1008 Tunis, Tunisia

²  LERIA, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers, France

author email corresponding author email

BioData Mining 2009, 2:9doi:10.1186/1756-0381-2-9

Published:	16 December 2009

Abstract

Background

In a number of domains, like in DNA microarray data analysis, we need to cluster simultaneously rows (genes) and columns (conditions) of a data matrix to identify groups of rows coherent with groups of columns. This kind of clustering is called biclustering. Biclustering algorithms are extensively used in DNA microarray data analysis. More effective biclustering algorithms are highly desirable and needed.

Methods

We introduce BiMine, a new enumeration algorithm for biclustering of DNA microarray data. The proposed algorithm is based on three original features. First, BiMine relies on a new evaluation function called Average Spearman's rho (ASR). Second, BiMine uses a new tree structure, called Bicluster Enumeration Tree (BET), to represent the different biclusters discovered during the enumeration process. Third, to avoid the combinatorial explosion of the search tree, BiMine introduces a parametric rule that allows the enumeration process to cut tree branches that cannot lead to good biclusters.

Results

The performance of the proposed algorithm is assessed using both synthetic and real DNA microarray data. The experimental results show that BiMine competes well with several other biclustering methods. Moreover, we test the biological significance using a gene annotation web-tool to show that our proposed method is able to produce biologically relevant biclusters. The software is available upon request from the authors to academic users.