Bioinformatics Advance Access originally published online on November 16, 2007
Bioinformatics 2008 24(5):719-720; doi:10.1093/bioinformatics/btm563
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Defining clusters from a hierarchical cluster tree: the Dynamic Tree Cut package for R
1Department of Human Genetics, University of California at Los Angeles, CA 90095-7088 and 2Rosetta Inpharmatics-Merck Research Laboratories, Seattle, WA, USA
*To whom correspondence should be addressed.
 |
ABSTRACT |
|---|
 TOP ABSTRACT 1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
Summary: Hierarchical clustering is a widely used method for detecting clusters in genomic data. Clusters are defined by cutting branches off the dendrogram. A common but inflexible method uses a constant height cutoff value; this method exhibits suboptimal performance on complicated dendrograms. We present the Dynamic Tree Cut R package that implements novel dynamic branch cutting methods for detecting clusters in a dendrogram depending on their shape. Compared to the constant height cutoff method, our techniques offer the following advantages: (1) they are capable of identifying nested clusters; (2) they are flexible—cluster shape parameters can be tuned to suit the application at hand; (3) they are suitable for automation; and (4) they can optionally combine the advantages of hierarchical clustering and partitioning around medoids, giving better detection of outliers. We illustrate the use of these methods by applying them to protein–protein interaction network data and to a simulated gene expression data set.
Availability: The Dynamic Tree Cut method is implemented in an R package available at http://www.genetics.ucla.edu/labs/horvath/CoexpressionNetwork/BranchCutting
Contact: stevitihit{at}yahoo.com
Supplementary information: Supplementary data are available at Bioinformatics online.
|
1 INTRODUCTION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
Detecting groups (clusters) of closely related objects is an important problem in bioinformatics and data mining in general. Many clustering methods exist in the literature (Hastic et al., 2001; Kaufman and Rousseeuw, 1990). We focus on hierarchical clustering, but our methods are useful for any clustering procedure that results in a dendrogram (cluster tree). Hierarchical clustering organizes objects into a dendrogram whose branches are the desired clusters. The process of cluster detection is referred to as tree cutting, branch cutting, or branch pruning. The most common tree cut method, which we refer to as the ‘static’ tree cut, defines each contiguous branch below a fixed height cutoff a separate cluster. The structure of cluster joining heights often poses a challenge to cluster definition. While distinct clusters may be recognizable by visual inspection, computational cluster definition by a static cut does not always identify clusters correctly. To address this challenge, we have developed a novel tree cut method based on analyzing the shape of the branches of a dendrogram. As a motivating example, consider Figure 1A that shows a dendrogram for cluster detection in a protein–protein interaction network in Drosophila. The Dynamic Tree Cut method succeeds at identifying branches that could not have been identified using the static cut method. The found clusters are highly significantly enriched with known gene ontologies (Dong and Horvath, 2007) which provides indirect evidence that the resulting clusters are biologically meaningful.
|
|
2 ALGORITHM AND IMPLEMENTATION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
We provide only a brief summary of the Dynamic Tree Cut method here; a detailed description is given in the Supplementary Material. To provide more flexibility, we present two variants of the method. The first variant, called the ‘Dynamic Tree’ cut, is a top-down algorithm that relies solely on the dendrogram. This variant has been used to identify biologically meaningful gene clusters in microarray data from several species such as yeast (Carlson et al., 2006; Dong and Horvath, 2007) and mouse (Ghazalpour et al., 2006), but has not previously been systematically described nor made publicly available. The algorithm implements an adaptive, iterative process of cluster decomposition and combination and stops when the number of clusters becomes stable. It starts by obtaining a few large clusters by the static tree cut. The joining heights of each cluster are analyzed for a characteristic pattern of fluctuations (see Supplementary Material for details) indicating a sub-cluster structure; clusters exhibiting this pattern are recursively split. To avoid over-splitting, very small clusters are joined to their neighboring major clusters.
The second variant, called the ‘Dynamic Hybrid’ cut, is a bottom-up algorithm that improves the detection of outlying members of each cluster. The detection proceeds in two steps. First, the method identifies preliminary clusters as branches that satisfy the following criteria: (1) they contain a certain minimum number of objects; (2) objects too far from a cluster are excluded from it even if they belong to the same branch of the dendrogram; (3) each cluster must be distinct from its surroundings and (4) the core of each cluster, defined as the tip of the branch, should be tightly connected. In the second step, all previously unassigned objects are tested for sufficient proximity to preliminary clusters; if the nearest cluster is close enough, the object is assigned to that cluster, see the Supplementary Material. Since Partitioning Around Medoids (PAM; kaufman and Rousseeuw, 1990) also involves assigning objects to their closest medoids, the Dynamic Hybrid variant can be considered a hybrid of hierarchical clustering and modified PAM.
|
3 DISCUSSION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
Many clustering procedures have been developed for the analysis of microarray data (Dembele and Kastner, 2003; Ghosh and Chinnaiyan, 2002; Thalamuthu et al., 2006; van der Laan and Pollard, 2003). Our method could be useful for any procedure that results in a dendrogram. In Figure 1B, we report a simulated gene expression data set (detailed description can be found in the Supplementary Material). We simulated 10 nested gene clusters labeled by different colors, shown in the first color band underneath the dendrogram. The results of the methods presented here are shown in correspondingly labeled color bands. Visual inspection shows the Dynamic Hybrid method outperforms the Static height cutoff method whose clusters either contain too few genes or are too coarse. PAM forces all genes into clusters and favors membership in large clusters at the expense of small ones. A quantitative analysis of this example is presented in the Supplementary Material.
The height and shape parameters of the Dynamic Tree Cut method provide improved flexibility for tree cutting. It remains an open research question how to choose optimal cutting parameters or how to estimate the number of clusters in the data set (Dudoit and Fridlyand, 2002). While our default parameter values have worked well in several applications, we recommend to carry out a cluster stability/robustness analysis in practice.
|
ACKNOWLEDGEMENTS |
|---|
|
TOPABSTRACT1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
We thank Ai Li, Jun Dong and Tova Fuller for discussions and suggestions. We acknowledge the grant support from 1U19AI063603-01 and NINDS/NIMH 1U24NS043562-01.
Conflict of Interest: none declared.
|
FOOTNOTES |
|---|
Associate Editor: Trey Ideker
The authors wish it to be known that, in their opinion, the first two authors should be regarded as joint First Authors. 
Received on September 12, 2007; revised on September 12, 2007; accepted on November 6, 2007
|
REFERENCES |
|---|
|
TOPABSTRACT1 INTRODUCTION2 ALGORITHM AND IMPLEMENTATION3 DISCUSSIONACKNOWLEDGEMENTSREFERENCES |
|---|
Carlson MR, et al. Gene connectivity, function, and sequence conservation: predictions from modularv yeast co-expression networks. BMC Genomics (2006) 7.
Dembele D, Kastner P. Fuzzy C-means method for clustering microarray data. Bioinformatics (2003) 19:973–980.
Dong J, Horvath S. Understanding network concepts in modules. BMC Syst. Biol (2007) 1:24.[CrossRef][Medline]
Dudoit S, Fridlyand J. A prediction-based resampling method for estimating the number of clusters in a dataset. In: Genome Biol. (2002) 3. research0036.1–research0036.21.
Ghazalpour A, et al. Integrating genetics and network analysis to characterize genes related to mouse weight. PLoS Genet (2006) 2:e130.[CrossRef][Medline]
Ghosh D, Chinnaiyan AM. Mixture modelling of gene expression data from microarray experiments. Bioinformatics (2002) 18:275–286.
Hastie T, et al. The Elements of Statistical Learning. (2001) New York: Springer.
Kaufman L, Rousseeuw P. Finding Groups in Data: An Introduction to Cluster Analysis. (1990) New York: John Wiley & Sons, Inc.
Thalamuthu A, et al. Evaluation and comparison of gene clustering methods in microarray analysis. Bioinformatics (2006) 22:2405–2412.
van der Laan MJ, Pollard KS. A new algorithm for hybrid hierarchical clustering with visualization and the bootstrap. J. Stat. Plan. Inference (2003) 117:275–303.[CrossRef]
Yip A, Horvath S. Gene network interconnectedness and the generalized topological overlap measure. BMC Bioinformatics (2007) 8:22.[CrossRef][Medline]
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Torkamani and N. J. Schork Identification of rare cancer driver mutations by network reconstruction Genome Res., September 1, 2009; 19(9): 1570 - 1578. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Bosco, K. L. McKenna, M. J. Firth, P. D. Sly, and P. G. Holt A Network Modeling Approach to Analysis of the Th2 Memory Responses Underlying Human Atopic Disease J. Immunol., May 15, 2009; 182(10): 6011 - 6021. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 B. Andreopoulos, A. An, X. Wang, and M. Schroeder A roadmap of clustering algorithms: finding a match for a biomedical application Brief Bioinform, May 1, 2009; 10(3): 297 - 314. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||