R/BHC: fast Bayesian hierarchical clustering for microarray data

Richard S. Savage, Katherine A. Heller, Yang Xu, Zoubin Ghahramani, William M. Truman, Murray Grant, Katherine J. Denby, David L. WildBMC Bioinformatics 2009 · DOI

TL;DR

This paper introduces R/BHC, a novel Bayesian hierarchical clustering algorithm for gene expression data that addresses the common issue of uncertainty in clustering results. By employing a Dirichlet Process mixture model and Bayesian hypothesis testing, R/BHC automatically determines the optimal number of clusters and avoids arbitrary choices of distance metrics, leading to more biologically plausible and interpretable results.

What Problem Does This Paper Address?

Gene expression data analysis often relies on clustering to group genes with similar expression patterns, hinting at shared biological functions or regulatory mechanisms. However, traditional hierarchical clustering methods have several drawbacks: they often require pre-specifying the number of clusters, rely on subjective distance metrics, and fail to quantify the uncertainty associated with the resulting clusters. This makes it difficult to assess the reliability of the findings and compare different clustering outcomes. While Bayesian approaches offer a principled way to handle uncertainty, existing methods often suffer from computational limitations, especially with large datasets. This paper aims to bridge this gap by providing a fast, Bayesian hierarchical clustering method that addresses these limitations.

Methods

The core of the R/BHC algorithm is a Bayesian agglomerative hierarchical clustering approach. It starts by treating each data point as its own cluster and iteratively merges pairs of clusters. Unlike traditional methods that use distance metrics, R/BHC employs a statistical hypothesis test to decide which clusters to merge. Specifically, it compares two hypotheses: that the data within a potential merged cluster comes from a single probabilistic model versus that it contains multiple clusters. This comparison is based on the marginal likelihoods of a Dirichlet Process (DP) mixture model. The DP is a powerful tool for clustering as it allows for an infinite number of clusters, with the probability of a new data point forming a new cluster being controlled by a hyperparameter. The algorithm uses Bayesian model selection to determine the optimal tree depth, effectively finding the best number and size of clusters. The implementation is an R/Bioconductor port, with efficient C++ routines for speed.

Datasets

The primary dataset used for evaluation is a published gene expression dataset of Arabidopsis thaliana subjected to various biotic and abiotic stresses, originally from the AtGenExpress consortium and used by Torres-Zabala et al. [26]. This dataset consists of 880 genes and 31 experimental conditions. The authors also mention using synthetic and real non-biological datasets for validation, though these are not detailed in the main text.

Key Insights and Ideas

  • Principled Uncertainty Handling: The Bayesian framework inherently quantifies uncertainty, allowing for a more robust assessment of clustering results compared to traditional methods.
  • Automatic Cluster Number Determination: The Dirichlet Process mixture model and Bayesian hypothesis testing eliminate the need to pre-specify the number of clusters, a common challenge in clustering.
  • Model-Based Merging: Replacing ad-hoc distance metrics with a model-based criterion for merging clusters leads to more biologically meaningful groupings.
  • Improved Biological Interpretability: The R/BHC algorithm produced results that were more intuitively aligned with biological knowledge, as evidenced by the analysis of Gene Ontology (GO) annotations.

Key Results

The R/BHC algorithm was applied to the Arabidopsis thaliana dataset and demonstrated biologically plausible results.

  • Higher DendrogramPurity: R/BHC achieved a DendrogramPurity of 0.968, significantly outperforming traditional agglomerative hierarchical clustering (0.473).
  • More Intuitive Condition Clustering: The clustering of experimental conditions was found to be more intuitive, particularly for treatments like abscisic acid (ABA), where R/BHC's grouping aligned better with biological expectations than previous methods.
  • Finer Granularity Gene Clustering: For gene clustering, R/BHC identified finer granularity clusters, revealing biologically relevant groupings of genes involved in specific pathways (e.g., ion homeostasis, secondary metabolism).
  • Strong Performance on Yeast Data: When applied to a yeast dataset (Ideker et al.), R/BHC achieved an adjusted Rand index of 0.955, outperforming standard hierarchical clustering (0.866) and other methods.
  • Computational Efficiency: The R/BHC algorithm has a computational complexity of O(N^2) for N data points and runs efficiently, with a dataset of 880 genes and 31 features taking about 8 minutes on a Macbook Pro.

Limitations and Future Work

  • Computational Complexity: While faster than many Bayesian methods, the O(N^2) complexity might still be a limitation for extremely large datasets.
  • Extension to Other Distributions: The authors note that the algorithm's framework can be extended to other distributions in the exponential family, such as Gaussians, which could be beneficial for data where such distributions are well-justified.
  • Further Experimental Validation: The paper suggests that experiments are underway to address hypotheses generated by the BHC clustering, particularly regarding co-regulated genes involved in secondary metabolism.

Summary updated

BibTeX
@article{savage2009r,
  author = {Richard S. Savage and Katherine A. Heller and Yang Xu and Zoubin Ghahramani and William M. Truman and Murray Grant and Katherine J. Denby and David L. Wild},
  title = {{R/BHC: fast Bayesian hierarchical clustering for microarray data}},
  journal = {BMC Bioinformatics},
  year = {2009},
  doi = {10.1186/1471-2105-10-242},
}
Figure