Nucleic Acids Research Advance Access published online on June 9, 2009
Nucleic Acids Research, doi:10.1093/nar/gkp491
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Methods Online |
QUBIC: a qualitative biclustering algorithm for analyses of gene expression data
1Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, and Institute of Bioinformatics, University of Georgia, Athens, GA 30602, USA, 2School of Mathematics, Shandong University, Jinan 250100, China, 3Department of Plant Biology, University of Georgia, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China
*To whom correspondence should be addressed. Tel.: 706 542 9779, 706 542 7783; Fax: 706-542-9751/7782; Email: xyn{at}csbl.bmb.uga.edu
Received March 18, 2009. Revised May 19, 2009. Accepted May 20, 2009.
Biclustering 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. 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 general biclustering problem. We report a QUalitative BIClustering algorithm (QUBIC) that can solve the biclustering problem in a more general form, compared to existing algorithms, through employing a combination of qualitative (or semi-quantitative) measures of gene expression data and a combinatorial optimization technique. One key unique feature of the QUBIC algorithm is that it can identify all statistically significant biclusters including biclusters with the so-called ‘scaling patterns’, a problem considered to be rather challenging; another key unique feature is that the algorithm solves such general biclustering problems very efficiently, capable of solving biclustering problems with tens of thousands of genes under up to thousands of conditions in a few minutes of the CPU time on a desktop computer. We have demonstrated a considerably improved biclustering performance by our algorithm compared to the existing algorithms on various benchmark sets and data sets of our own. QUBIC was written in ANSI C and tested using GCC (version 4.1.2) on Linux. Its source code is available at: http://csbl.bmb.uga.edu/
maqin/bicluster. A server version of QUBIC is also available upon request.