RT Journal
A1 Herwig, Ralf
A1 Poustka, Albert J.
A1 Müller, Christine
A1 Bull, Christof
A1 Lehrach, Hans
A1 O'Brien, John
T1 Large-Scale Clustering of cDNA-Fingerprinting Data
JF Genome Research 
JO Genome Research 
YR 1999 
FD November 01 
VO 9 
IS 11 
SP 1093 
OP 1105 
DO 10.1101/gr.9.11.1093 
UL http://genome.cshlp.org/content/9/11/1093.abstract 
AB Clustering is one of the main mathematical challenges in large-scale gene expression analysis. We describe a clustering procedure based on a sequential k-means algorithm with additional refinements that is able to handle high-throughput data in the order of hundreds of thousands of data items measured on hundreds of variables. The practical motivation for our algorithm is oligonucleotide fingerprinting—a method for simultaneous determination of expression level for every active gene of a specific tissue—although the algorithm can be applied as well to other large-scale projects like EST clustering and qualitative clustering of DNA-chip data. As a pairwise similarity measure between two p-dimensional data points,x and y, we introduce mutual information that can be interpreted as the amount of information about x iny, and vice versa. We show that for our purposes this measure is superior to commonly used metric distances, for example, Euclidean distance. We also introduce a modified version of mutual information as a novel method for validating clustering results when the true clustering is known. The performance of our algorithm with respect to experimental noise is shown by extensive simulation studies. The algorithm is tested on a subset of 2029 cDNA clones coming from 15 different genes from a cDNA library derived from human dendritic cells. Furthermore, the clustering of these 2029 cDNA clones is demonstrated when the entire set of 76,032 cDNA clones is processed.