|Home | About | Journals | Submit | Contact Us | Français|
Large gene expression studies, such as those conducted using DNA arrays, often provide millions of different pieces of data. To address the problem of analyzing such data, we describe a statistical method, which we have called 'gene shaving'. The method identifies subsets of genes with coherent expression patterns and large variation across conditions. Gene shaving differs from hierarchical clustering and other widely used methods for analyzing gene expression studies in that genes may belong to more than one cluster, and the clustering may be supervised by an outcome measure. The technique can be 'unsupervised', that is, the genes and samples are treated as unlabeled, or partially or fully supervised by using known properties of the genes or samples to assist in finding meaningful groupings.
We illustrate the use of the gene shaving method to analyze gene expression measurements made on samples from patients with diffuse large B-cell lymphoma. The method identifies a small cluster of genes whose expression is highly predictive of survival.
The gene shaving method is a potentially useful tool for exploration of gene expression data and identification of interesting clusters of genes worth further investigation.
Through the use of recently developed DNA arrays, it is now possible to obtain accurate, quantitative (relative) measurements of a large proportion of the mRNA species present in a biological sample. DNA arrays have been used to monitor changes in gene expression during important biological processes (for example, cellular replication and the response to changes in the environment), and to study variation in gene expression across collections of related samples (such as tumor samples from patients with cancer). A major challenge in interpreting these results is to understand the structure of the data produced by such studies, which often consist of millions of measurements. A variety of clustering techniques have been applied to such data, and have proved useful for identifying biologically relevant groupings of genes and samples [1,2,3,4,5,6,7,8,9,10,11,12,13]. Although the underlying principles and computational details of these methods differ, they share the goal of organizing the elements under consideration (such as genes) into groups (clusters) with coherent behavior across relevant measurements (such as samples). Generally absent is any consideration of the nature of the coherent variation. For example, one might want to identify groups of genes that have coherent patterns of expression with large variance across samples, or groups of genes that optimally separate samples into predefined classes (such as different clinical response groups in tumor samples). Here, we introduce a new statistical method, which we call gene shaving, that attempts to identify groups of elements (genes) that have coherent expression and are optimal for various properties of the variation in their expression.
Figure Figure11 shows the dataset used in our study, which consisted of 4673 gene expression measurements on 48 patients with diffuse large B-cell lymphoma (DLCL). These data have been described in detail previously . The column labels refer to different patients, and the rows correspond to genes. The order of rows and columns is arbitrary.
Some authors have recently explored the use of clustering methods to arrange the genes in some systematic way, with similar genes placed close together (see  for developments and  for an overview). In Figure Figure2,2, we have applied hierarchical clustering to the genes and samples separately. Each clustering produces a (non-unique) ordering, one that ensures that the branches of the corresponding dendrogram do not cross. Figure Figure22 displays the original data, with rows and columns ordered accordingly.
Some structure is evident in Figure Figure2,2, and this method can be used to recognize relationships among the genes and samples.With any method that reduces the dimension of the data, however, finer structure can be lost. For example, suppose the expression of some subset of genes divides the samples in an informative way, correlating with the rate of proliferation of tumor cells, for example, whereas another subset of genes divides the samples a different way, representing the immune response, for example. Then methods such as two-way hierarchical clustering, which seek a single reordering of the samples for all genes, cannot find such structure.
The method of gene shaving we describe here is designed to extract coherent and typically small clusters of genes that vary as much as possible across the samples. Figure Figure33 shows three gene clusters for the DLCL data, found using shaving. Some of the genes within each cluster lie close to each other in the hierarchical clustering of Figure Figure2,2, but others, and the clusters themselves, are quite far apart.
In Figure Figure33 the samples have been ordered by values of the average gene expression. This average gene is a good representative of the cluster, as all the members are so similar. The variance measures at the top of each cluster are discussed in more detail later. The clusters are all of different sizes. We use an automatic method for determining the size of the clusters, based on a randomization procedure that protects us from looking too hard in the large sea of genes and finding spurious structure. The three cluster-average genes, one from each cluster, are reasonably uncorrelated (see below and Figure Figure6).6). This is another aspect of the shaving process - it seeks different clusters, where difference is measured by correlation of the cluster mean. Figure Figure44 shows the results of a hierarchical clustering applied to the three column-average genes. Whereas hierarchical clustering suggests two main gene groupings, the shaving process may suggest more useful groupings.
This article is organized as follows. In the section 'Gene shaving' we describe the method itself. The section entitled 'The gap estimate of cluster size' outlines the gap test for choosing the cluster size. In the section 'Predicting patient survival' we try to predict patient survival from gene cluster averages. 'Supervised shaving' is discussed in the following section. Finally, in the 'Conclusions' we propose some further generalizations. A more statistical treatment of gene shaving is given in .
In this section we describe in detail our technique for finding clusters like the example in Figure Figure3.3. A gene expression matrix is an N × p matrix of real-valued measurements X = xij. The rows are genes, the columns are samples, and xij is the measured (log) expression, relative to a baseline. Typically there are missing entries in X. We use a technique described in , an iterative algorithm based on the singular value decomposition, for imputing missing expression values;our analysis here assumes that X has no missing values.
Let Sk be the indices of a cluster of k genes, and
be the collection of p column averages of the expression values for this cluster. Then for each cluster size k, gene shaving seeks a cluster Sk having the highest variance of the column averages:
The important question of how to choose the cluster size k is addressed in the next section.
Our procedure generates a sequence of nested clusters Sk, in a top-down manner, starting with k = N, the total number of genes, and decreasing down to k = 1 gene. At each stage the largest principal component of the current cluster of genes is computed. This eigen gene is the normalized linear combination of genes with largest variance across the samples. We then compute the inner product (essentially the correlation) of each gene with the eigen gene, and discard ('shave off') a fraction of the genes having lowest (absolute) inner product. The process is repeated on the reduced cluster of genes. The shaving algorithm is depicted in Figure Figure55 and given in detail in Box Box11.
There are a number of duplicate genes in the dataset. In some cases the sequence for a given gene appears on the microarray more than once, either by design or by accident. In other cases, more than one different EST (expressed sequence tag) is present for the same gene. Gene shaving can be affected by duplicate genes, since they are highly correlated with each other. We therefore averaged expression profiles for the duplicate genes, leaving 3624 unique gene profiles.
The sequence of operations 1-5 in Box Box11 gives the first cluster of rows - the first ribbon in Figure Figure3.3. Step 6 orthogonalizes the data to encourage discovery of a different (uncorrelated) second cluster. Note that although we work with the orthogonalized matrix in the shaving process for the second and subsequent clusters, the derived clusters and their averages involve the original genes.
The shaving process requires repeated computation of the largest principal component of a large set of variables. If naively implemented, this requires the construction of a N × N sample covariance matrix ∑ of the genes, and the computation of its largest eigenvector. We can avoid the computational burden by working in the dual space, where the matrices have dimension p × p. Furthermore, as we require only the largest eigenvector, the computations can be reduced even further by using the power method, using the eigenvector of the previous cluster as a starting value.
The three resulting clusters are shown in Figure Figure33 and again in Figure Figure4.4. Figure Figure66 shows the pairwise scatterplots of each of the three column averages ('super genes') from the clusters. The absolute correlations range from 0.27 to 0.68. The full gene names for the members of the first three clusters are given in Table Table11.
It is useful to evaluate how much of the dimensionality of the gene expression variation is captured by the clusters derived from gene shaving. We can approximate the expression profile for each gene in the complete dataset as a linear combination of the three super genes from each cluster (which are simple averages of the genes in each cluster). The percent variance explained by the first j = 1,2, ... 10 super genes is shown in Figure Figure77.
Thus the three gene clusters, involving a total of 33 genes, explain about 20% of the variation. The percent variance explained by the first j principal components (broken curve) exceeds that from gene shaving. Each principal component gives a non-zero weight to all 3624 genes, however.
Each shaving sequence produces a nested set of gene clusters Sk, starting with the entire expression matrix and then proceeding down to some minimum cluster size (typically 1). If we applied this procedure to null data, in which the rows and columns were independent of each other, we could still find some interesting-looking patterns in the resulting blocks. Hence, we need to calibrate this process so that we can differentiate real patterns from spurious ones. Even in the case of real structure, it is unlikely that a distinct set of genes is correct for a cluster, and the rest not. More likely there is a graduation of membership eligibility, and we have to decide where to draw the line. Here we describe a procedure based on randomization that helps us select a reasonable cluster size.
Our method requires a quality measure for a cluster. We favor both high-variance clusters, and high coherence between members of the cluster. As the generation of the cluster sequence was driven strongly by the former, we focus on the latter in selecting a good cluster. By analogy with the analysis of variance for grouped data, we define the following measures of variance for a cluster Sk:
The between variance is the variance of the (signed) mean gene. The within variance measures the variability of each gene about the cluster average, also averaged over samples. As this can be small if the overall variance is small, a more pertinent measure is the between-to-within variance ratio VB/VW, or alternatively, the percent variance explained
A large value of R2 implies a tight cluster of coherent genes. This is the quality measure we use to select a cluster from the shaving sequence Sk.
Let Sk index the clusters of a given shaving sequence (with k being the number of genes). Let Dk be the R2 measure for the kth member of sequence. We wish to know whether Dk is larger than we would expect by chance, if the rows and columns of the data were independent.
Let X*b be a permuted data matrix, obtained by permuting the elements within each row of X. We form B such matrices, indexed by b = 1,2,... B. Let Dk*b be the R2 measure for cluster Sk*b. Denote by k* the average of Dk*b over b. The Gap function is defined by
We then select as the optimal number of genes that value of k producing the largest gap:
The idea is that at the value the observed variance is the most ahead of expected. Multiple clusters are produced for the randomized data just like for the original data, and the gap test is used repeatedly to select the cluster size at each stage.
For the DLCL data, the maximum for the first cluster occurs at eight genes. Figure Figure88 shows the percent-variance curves, Dk, for both the original and randomized tumor data as a function of size, and the gap curves used to select the specific cluster sizes in Figure Figure33.
One important motivation for developing gene shaving was the wish to identify distinct sets of genes whose variation in expression could be related to a biological property of the samples. In the present example, finding genes whose expression correlates with patient survival is an obvious challenge. Group factors g1, g2, g3 were created by splitting each gene cluster in Figure Figure33 into two groups of 24 patients. We used each of these groupings as a factor in Cox's proportional hazards model for predicting overall survival . Of the group factors only g2 was significant, at the 0.05 level (p = 0.04).
In , a cluster of 380 genes was chosen on the basis of their large variation over samples, and their 'germinal center B-like' or 'activated B-like' expression profiles. Using these 380 genes, a hierarchical clustering produced two groups of patients which were (just) statistically different in survival. Close inspection shows that 18 of the 23 genes in the second cluster above also fall into this cluster of 380 genes. Hence, gene shaving can find clinically and biologically relevant subdivisions in gene expression data in an unsupervised fashion.
It may be fortuitous that one of these groupings correlates with survival, as the clusters were not chosen with survival in mind. We next describe a modification of gene shaving that explicitly looks for clusters that are related to patient survival.
The methods discussed so far have not used information about the columns to 'supervise' the shaving of rows. Here we generalize gene shaving to incorporate full or partial supervision.
As in Equation (1), we consider a cluster of genes Sk having column average vector . Let y = (y1, y2, ... yp) be a set of auxiliary measurements available for the samples. For example each yj, might be a survival time for the patient corresponding to sample j or a class label for each sample, such as a diagnosis category. Supervised shaving maximizes a weighted combination of column variance and an information measure J(, y):
for fixed 0 ≤ α ≤ 1. The value α = 1 gives full supervision; values between o and 1 provide partial supervision.
Choice of the measure J(, y) depends on the nature of the auxiliary information y. If the y codes class labels, J(, y) can be taken as the sum of squared differences between the category averages . For censored survival times y, think of as a covariate in a Cox (proportional hazards) model. If the score vector from this model is g, we set J(, y) = ggT, a p × p matrix. Computationally we first scale the genes so that the within-risk set variance is 1.
When fully supervised, the shaving procedure reduces to simply ranking the genes from largest to smallest Cox model score test. Thus there is no role for principal components or top-down shaving in this case. However, to encourage coherence within the gene clusters, it can be better to use a partially supervised criterion, which does use principal components and top-down shaving. This is demonstrated in the example below. One can also include other prognostic factors in the model, and direct shaving to find a gene cluster whose column average is a strong predictor in the model. This can be done with other models, for example a linear regression model for a quantitative measurement. Operationally, all of these choices for J are quadratic functions of the column averages , and gene shaving can be carried out via principal components of a suitably modified variance matrix.
We applied supervised shaving to the set of 3624 genes from the DLCL samples. Figure Figure99 examines the effect of different values of the supervision weight α, showing the average (absolute) gene correlation and Cox model p value for each choice. From this plot we chose the value α = 0.10, which gives a good mix of high gene correlation and low p value. Partially supervised gene shaving produced a cluster with 234 genes, shown in Figure Figure1010 and in Table Table22.
Some of the genes are close together in the hierarchical clustering order (indicated by the first number in Table Table2),2), many are not. Some genes have a negative sign, and others have no sign. We will call these 'negative' and 'positive' genes respectively. The negative genes have their expression values flipped before being averaged with other gene expression profiles. Figure 11a shows the gap curve, suggesting a cluster size of 35. However, further analysis below suggests the better cluster size of 234.
The cluster of 234 genes contains many of the strongest individual genes for predicting survival. For example, 130 of the strongest 200 genes are in the cluster. Some weaker genes are, however, also in the cluster, the weakest being the 1332nd strongest gene among the full list of 3624. Figure 11b shows the survival curves stratified by the low and high expression of this gene cluster, using the median of the cutoff point. The two resulting groups are shown in Figure Figure1212.
Using this grouping as a predictor in the Cox model for survival gave a highly significant p value (0.00042). However, this p value must be scrutinized. Figure 13a,,bb shows the Cox model p value as a function of the cluster size, for both partially and fully supervised shaving. We will call these the 'training set p values'. As the gene shaving process was supervised by the survival times, the training set p values will be biased downward, and it is important to adjust them appropriately. We permuted the survival times, re-ran the shaving process and computed the corresponding p values. This was repeated 100 times, and for each cluster size we computed the proportion of times the permutation p values were less than or equal to the training set p values. These proportions are shown in Figure 13c,,d,d, and are unbiased estimates of the true p values. Fully supervised shaving is too aggressive, and the upward adjustment of the p values is large. As a result the p value is around 0.05 for the full set of genes, but none of the smaller clusters is significant at the 0.05 level. For partially supervised shaving, many of the p values are below 0.05, and from this we chose the cluster size of 234 near the minimum.
Using the full set of genes, flipping each to have positive correlation with survival, averaging their expression values and finally cutting at the median, gave a grouping nearly the same as Groups 1 and 2 in Figure Figure12.12. The only change was a swap between DLCL-oo14 and DLCL-oo18, and these two samples are right at the median cutpoint between the two groups in Figure Figure1010.
The international prognostic index (IPI) A score was also available for these patients. Components of the IPI include age, level of the enzyme lactate dehydrogenase (LDH) and the number of extranodal sites. As in , we dichotomized IPI scores into low (0, 1 or 2) and high (3, 4 or 5). The resulting grouping seems to be about as predictive as the IPI index, and is quite independent from it, as Table Table33 indicates.
When added to a Cox model containing IPI, this grouping had a training set p value of 0.0006. Figure Figure1414 shows the Kaplan-Meier survival curves for each group, stratified by low and high IPI.
In , two patient groups were defined from a hierarchical clustering tree grown from a 38o-gene cluster. As a predictor, the grouping was just significant in the low IPI group only, at the 0.05 level. Table Table44 gives a cross-tabulation of that grouping with the one used in this paper in Figure Figure1010.
Thus 25/36 = 69% of the patients are classified the same way by both groupings. The patient grouping of Alizadeh et al.  was based on a cluster of 380 genes, chosen for their large variation over the samples. Our cluster of 234 genes has 38 genes in common with this cluster of 380, and they are indicated by an asterisk in Table Table2.2. Five of the 234 genes also appear in the unsupervised clusters found earlier, in the second of the three clusters.
We have proposed a set of 'shaving' methods for isolating interesting clusters of genes from a set of DNA microarray experiments. The methods may be unsupervised, or may be supervised - that is, use information available about the samples such as a class label or survival time. The proposed shaving methods search for clusters of genes showing both high variation across the samples, and coherence (correlation) across the genes. Both of these aspects are important and cannot be captured by simple clustering of the genes, or thresholding of individual genes based on the variation over samples.
With our model-based approach for supervised shaving, one can incorporate other prognostic factors in the search for interesting gene clusters. If an outcome such as survival time is available for each sample, the method searches for a gene cluster whose column average gene has a significant effect, possibly the presence of other prognostic factors, for predicting the outcome.
The microarray data xij we have considered are real-valued expression levels. However, other kinds of arrays produce different kinds of data. In particular, some arrays detect the presence or absence of single-nucleotide polymorphisms (SNPs), so that the xij values take on one of k ≥ 2 unordered values. The shaving methods described can be easily modified to handle this kind of data. In detail, we construct k data matrices X1, X2 ... Xk, each of size n × m. The ijth element of Xj is 1 if xij falls in class j, and zero otherwise. Letting ∑jj = 1, 2, ... k be the n × n covariance matrices of the genes in each Xj, we simply apply principal component shaving, using ∑j, as the variance matrix for the penalty. This can be done unsupervised, or a supervision term can also be added.
We thank Mark Segal for helpful discussions, and Nick Fisher and Jerome Friedman for their work on 'bump-hunting' which inspired some of the ideas in this paper. The first two authors were supported by grants from The National Science Foundation and the National Institutes of Health. W.C.C. was supported by NIH grant UOI-CA 84967. R.L and collaborators were supported by LPPG grant CA 34233.