A close-to optimum bi-clustering algorithm for microarray gene expression data

Guojun Li*, Qin Ma, Bingqiang Liu, Haibao Tang, Andrew H. Paterson, Ying Xu

Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology and Institute of Bioinformatics, University of Georgia, Athens, GA 30605. USA. guojun@csbl.bmb.uga.edu

Proc LSS Comput Syst Bioinform Conf. August, 2009. Vol. 8, p. 139-149. Full-Text PDF

*To whom correspondence should be addressed.

Motivation: Bi-clustering extends the traditional clustering techniques by attempting to find (all) subgroups of genes with similar expression patterns under to-be-identified subsets of experimental conditions when applied to gene expression data. The bi-clustering strategy has been widely used for analyses of gene expression data and beyond since it was first proposed in 2000 since it provides much increased flexibility and analysis power in identifying co-expressed genes under some but not necessarily all conditions, compared to traditional clustering methods. Still the real power of this clustering strategy is yet to be fully realized due to the lack of effective and efficient algorithms for reliably solving the bi-clustering problem. Results: We present a novel method to solve a bi-clustering problem, using a (traditional) clustering algorithm combined with a combinatorial technique. The algorithm achieves the same asymptotic computational complexity of the underlying clustering algorithm. While it is a heuristic algorithm in nature, the algorithm achieves close-to optimum classification results across a large collection of benchmark sets.