EXCAVATOR: a computer program for ef®ciently mining gene expression data

Massive amounts of gene expression data are generated using microarrays for functional studies of genes and gene expression data clustering is a useful tool for studying the functional relationship among genes in a biological process. We have developed a computer package EXCAVATOR for clustering gene expression pro®les based on our new framework for representing gene expression data as a minimum spanning tree. EXCAVATOR uses a number of rigorous and ef®cient clustering algorithms. This program has a number of unique features, including capabilities for: (i) data-constrained clustering; (ii) identi®cation of genes with similar expression pro®les to pre-speci®ed seed genes; (iii) cluster identi®cation from a noisy background; (iv) computational comparison between different clustering results of the same data set. EXCAVATOR can be run from a Unix/Linux/ DOS shell, from a Java interface or from a Web server. The clustering results can be visualized as colored ®gures and 2-dimensional plots. Moreover, EXCAVATOR provides a wide range of options for data formats, distance measures, objective func-tions, clustering algorithms, methods to choose number of clusters, etc. The effectiveness of EXCAVATOR has been demonstrated on several experimental data sets. Its performance compares favorably against the popular K-means clustering method in terms of clustering quality and comput-ing time