We present a new algorithm to discovering natural partitions of a set of samples based on their gene expression patterns found with microarray experiments. The algorithm uses a bi-criteria combinatorial optimization search to simultaneously identify an interesting set of genes and a partition of the array samples. Each gene in the gene set should respect the sample partition in the sense that if the gene’s values are colored according to the partition class they come from, then the values, when sorted, should have a minimal number of color changes. We refer to this as the full color criterion. It measures how well a particular gene sorts the various partition classes. The other is the black and white criterion that measures how well a gene distinguishes one sample class from the remaining samples. Using a branch-and-bound algorithm we are able to find both the optimal gene set and the sample partitioning that minimizes the total color change. Additionally we can calculate a “p-value” to interpret the significance of the results. 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.