Discovering coherent biclusters from gene expression data using zero-suppressed binary decision diagrams.
The biclustering method can be a very useful analysis tool when some genes have multiple functions and experimental conditions are diverse in gene expression measurement. This is because the biclustering approach, in contrast to the conventional clustering techniques, focuses on finding a subset of the genes and a subset of the experimental conditions that together exhibit coherent behavior. However, the biclustering problem is inherently intractable, and it is often computationally costly to find biclusters with high levels of coherence. In this work, we propose a novel biclustering algorithm that exploits the zero-suppressedbinary decision diagrams (ZBDDs) data structure to cope with the computational challenges. Our method can find all biclusters that satisfy specific input conditions, and it is scalable to practical gene expression data. We also present experimental results confirming the effectiveness of our approach.
Yoon
Sungroh
S
Computer Systems Laboratory, Stanford University, Room 334, William Gates Computer Science Hall, Stanford, CA 94305, USA. sryoon@stanford.edu
Nardini
Christine
C
Benini
Luca
L
De Micheli
Giovanni
G
D000465:Algorithms; D002453:Cell Cycle / Q000235:genetics; D016000:Cluster Analysis; D030541:Databases, Genetic; D020869:Gene Expression Profiling; D005786:Gene Expression Regulation; D023281:Genomics; D016247:Information Storage and Retrieval; D020411:Oligonucleotide Array Sequence Analysis; D012372:ROC Curve; D012441:Saccharomyces cerevisiae / Q000235:genetics; D012984:Software