Abstract
Motivated by high-throughput single-cell cytometry data with applications to vaccine development and immunological research, we consider statistical clustering in large-scale data that contain multiple rare clusters. We propose a new hierarchical mixture model, namely Hidden Markov Model on Variable Blocks (HMM-VB), and a new mode search algorithm called Modal Baum-Welch (MBW) for efficient clustering. Exploiting the widely accepted chain-like dependence among groups of variables in the cytometry data, we propose to treat the hierarchy of variable groups as a figurative time line and employ a HMM-type model, namely HMM-VB. We also propose to use mode-based clustering, aka modal clustering, and overcome the exponential computational complexity by MBW. In a series of experiments on simulated data HMM-VB and MBW have better performance than existing methods. We also apply our method to identify rare cell subsets in cytometry data and examine its strengths and limitations.
Introduction
In immunology and vaccine development, flow and mass cytometry (CyTOF) are used to analyze millions of individual cells across dozens of markers. A primary goal is identifying "rare subsets"—specific cell types that may constitute as little as 0.01% of a sample but are critical for understanding disease progression. Traditionally, this identification relies on "manual gating," where experts analyze 2D scatter plots to draw boundaries (Figure 1). This process is subjective, slow, and difficult to reproduce. While automated methods like Gaussian Mixture Models (GMMs) exist, they often struggle with high dimensionality, either merging rare clusters into background noise or becoming computationally intractable.
Methodology
To bridge the gap between manual expertise and automated computation, we introduce two major innovations:
HMM-VB: Hidden Markov Model on Variable Blocks
Biologists analyze markers in a sequence (e.g., Live Cells → Lymphocytes → CD4+ T-cells). HMM-VB mimics this by partitioning variables into "blocks" and treating the sequence as a timeline in a Hidden Markov Model. Each block is modeled as a mixture, and transitions between blocks capture hierarchical dependencies. This "hierarchy as time" approach allows the model to progressively "zoom in" on data, mirroring human expert logic. Furthermore, by using variable blocks, the model avoids the need for a full covariance matrix for all dimensions, providing a parsimonious representation that prevents over-fitting.
Modal Baum-Welch (MBW) Algorithm
Instead of assuming one Gaussian component equals one cell type, we utilize "modal clustering," which groups data points based on local maxima (modes) of the density function. This allows for identifying clusters with complex, non-elliptical shapes. To overcome the exponential complexity typically associated with finding modes in an HMM structure, we derived the MBW algorithm. By leveraging the block-diagonal structure of the model's covariance, MBW achieves linear complexity, making it practical for massive datasets.
Experimental Results
The model was evaluated using simulated data (8-13 dimensions with 0.01%–0.02% rare clusters) and a real-world CyTOF dataset from mouse lung samples (46,204 cells, 39 markers).
- Detection Accuracy: In simulations where standard GMMs failed to find the target subset, HMM-VB correctly identified nearly all target observations.
- Computational Efficiency: On the 39-dimensional CyTOF dataset, HMM-VB achieved a 25x speedup, completing fitting in 11.4 minutes compared to 284.2 minutes for a standard GMM.
- Resolution: The model identified 825 clusters in the CyTOF data, providing a finer resolution of cellular compositions than competing methods, which often merged distinct biological regions.
Conclusion and Future Work
HMM-VB and the MBW algorithm offer a powerful framework for identifying rare cell populations in high-throughput data. By mapping biological hierarchies to HMM structures, the method achieves both high sensitivity and computational efficiency. While the model's sensitivity can generate very small clusters requiring further biological validation, it represents a significant step toward objective, automated cytometry analysis. Future work will focus on metrics for cluster separability and automated optimization of variable ordering.
Summary updated