Gene Expression Time Course Clustering with Countably Infinite Hidden Markov Models

Matthew J. Beal, Praveen KrishnamurthyUAI 2006

TL;DR

This paper introduces the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) for clustering gene expression time-course data. By employing a "countably infinite" model, it overcomes limitations of traditional methods that struggle with model complexity and temporal information, demonstrating superior performance on real-world biological datasets.

What Problem Does This Paper Address?

Understanding gene expression over time is crucial for deciphering biological processes and gene regulation. However, clustering this time-series data presents two major challenges:

  1. Model Complexity: When using model-based clustering, it's difficult to determine the optimal complexity (e.g., the number of hidden states in a model) beforehand. Traditional methods often require manual selection or heuristic criteria, which can be suboptimal.
  2. Temporal Information: Many existing clustering methods treat each time point as an independent dimension, effectively ignoring the crucial temporal correlations between adjacent time points. This means they are insensitive to the order of events, which is biologically significant.

While Hidden Markov Models (HMMs) can capture temporal dependencies, they still face the model complexity issue. Infinite mixture models, like Dirichlet Process Mixture Models, have successfully addressed this for independent data, but their direct application to time-series data is problematic without resorting to the aforementioned temporal information disregard.

Methods

The core innovation of this paper is the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM). This model is a temporal extension of the Hierarchical Dirichlet Process (HDP) mixture model.

Here's a breakdown of the key methodological aspects:

  • Countably Infinite States: Unlike traditional HMMs that require pre-specifying a fixed number of hidden states, the HDP-HMM allows for a countably infinite number of states. This is achieved by leveraging the properties of Dirichlet Processes, which provide a nonparametric prior over the number of components in a mixture model.
  • Hierarchical Dirichlet Process (HDP): The HDP framework is used to link multiple groups of data (in this case, different genes) and share mixture components across them. This is crucial for learning a common structure from multiple gene expression profiles.
  • Stick-Breaking Construction: The paper utilizes the stick-breaking interpretation of the HDP. This provides a way to construct the mixing proportions for the infinite number of states in a structured manner.
  • Auxiliary Variable Gibbs Sampling: To perform inference (learning the model parameters) in this complex infinite model, the authors employ an auxiliary variable Gibbs sampling scheme. This method, adapted from existing HDP inference techniques, allows for efficient sampling of the model's parameters.
  • Sequence Similarity Measure: A novel dissimilarity measure is proposed for comparing gene time courses. It's based on the probability that two genes traverse similar hidden state trajectories, calculated from the posterior samples of the HDP-HMM. This measure explicitly accounts for the temporal dependencies captured by the model.

Datasets

The authors evaluated their HDP-HMM on two publicly available gene expression time-course datasets:

  1. Iyer et al. (1999): This dataset consists of 517 genes measured across 12 time points. The genes are pre-labeled into 10 clusters plus an outlier cluster.
  2. Cho et al. (1998): This dataset includes 386 genes measured over 17 time points, with hand-labeled genes into 5 clusters.

These datasets are standard benchmarks in gene expression analysis, and the provided labels serve as "ground truth" for evaluating clustering performance.

Key Insights and Ideas

  • Infinite Models Conquer Complexity: The HDP-HMM elegantly sidesteps the problem of choosing the "right" number of hidden states by allowing an infinite number. This prevents overfitting and allows the model to discover complex temporal patterns without explicit model selection.
  • Temporal Information is Key: The HDP-HMM significantly outperforms simpler methods that ignore time (like Eisen's correlation-based approach) and even finite HMMs, highlighting the importance of modeling temporal dependencies.
  • Richer Architectures Emerge Naturally: The infinite model, without explicit constraints, learns more complex and sparser transition matrices compared to finite HMMs. This suggests that biological systems might indeed utilize intricate, yet structured, temporal regulatory mechanisms.
  • Robustness to Hyperparameters: The performance of the HDP-HMM was found to be remarkably stable across different settings of its higher-level hyperparameters, indicating a robust learning process.

Key Results

The HDP-HMM demonstrated superior performance across various external and internal clustering indices on both the Iyer and Cho datasets.

  • Outperforms Existing Methods: The HDP-HMM consistently achieved better results than standard Eisen correlation analysis and finite HMMs, even when the finite HMMs were tuned with model selection criteria.
  • Avoids Overfitting: Unlike finite HMMs, which showed signs of overfitting (particularly with more states), the HDP-HMM did not suffer from this issue, as it integrates over an infinite set of models.
  • Learns Complex Dynamics: Analysis of the learned transition matrices revealed that the HDP-HMM learns significantly sparser connectivity patterns compared to finite HMMs, suggesting a more efficient and potentially biologically relevant representation of gene state transitions.

Limitations and Future Work

  • Computational Cost: While the auxiliary variable Gibbs sampler is feasible, sampling for inference in the HDP-HMM can be computationally intensive, especially for very long time series. This makes tasks like leave-one-out cross-validation for density estimation challenging.
  • Further Exploration of Architectures: The authors are actively investigating the learned architectures more closely, aiming to uncover biological insights into regulatory networks.
  • Extensions: Future work includes exploring nested group models for capturing ontological information and developing countably infinite switching state-space models, as well as variants based on Pitman-Yor processes for time-series modeling.

Summary updated

BibTeX
@inproceedings{beal2006gene,
  author = {Matthew J. Beal and Praveen Krishnamurthy},
  title = {{Gene Expression Time Course Clustering with Countably Infinite Hidden Markov Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2006},
}
Figure