Discovering classes in microarray data using island counts

We present a new biclustering algorithm to simultaneously discover tissue classes and identify a set of genes that well-characterize these classes from DNA microarray data sets. We employ a combinatorial optimization approach where the object is to simultaneously identify an interesting set of genes and a partition of the array samples that optimizes a certain score based on a novel color island statistic. While this optimization problem is NP-complete in general, we are effectively able to solve problems of interest to optimality using a branch-and-bound algorithm. We have tested the algorithm on a 30 sample Cutaneous T-cell Lymphoma data set; it was able to almost perfectly discriminate short-term survivors from long-term survivors and normal controls. Another useful feature of our method is that can easily handle missing expression data.