HDCluster: High-Degree Graph Clustering for Robust Analysis of Single Molecule Localization Microscopy

Ismail M. Khater, Ivan R. Nabi, Ghassan HamarnehbioRxiv 2025 · DOI

Abstract

Clustering is a fundamental task in data analysis, particularly in super-resolution single molecule localization microscopy (SMLM). We introduce HDCluster, a novel high-degree graph-based clustering algorithm designed to handle the massive, noisy point clouds generated by SMLM. HDCluster efficiently manages datasets with millions of localizations and variable cluster counts using a single primary parameter. Our results demonstrate that HDCluster significantly outperforms state-of-the-art methods like DBSCAN in both time efficiency—achieving speedups of over 55x—and clustering accuracy (ARI and AMI), especially in the presence of molecular blinking and high noise.

Introduction

Single Molecule Localization Microscopy (SMLM) techniques, such as STORM and PALM, have revolutionized biology by enabling nanometer-scale visualization beyond the diffraction limit of light. However, the output of these techniques is not a direct image but a "point cloud" consisting of millions of individual coordinates. Analyzing this data is computationally demanding due to several factors:

  1. Noise and Background: Random localizations unrelated to biological structures.
  2. Blinking Artifacts: Single molecules appearing as multiple points due to stochastic switching.
  3. Scale: Datasets often exceed millions of points.
  4. Parameter Sensitivity: Traditional algorithms often require complex tuning or prior knowledge of cluster counts.

HDCluster addresses these challenges through an unsupervised, iterative similarity graph-based approach that prioritizes high-degree nodes to ensure robust cluster identification.

Methodology

HDCluster operates on a "high-degree-first" merging strategy. The algorithm follows a four-step iterative process:

  • Graph Construction: A similarity graph is built where points (nodes) are connected if their distance is within a user-defined merging threshold ($mTh$).
  • Iterative Merging: The algorithm identifies nodes with the highest degree (most connections) and merges them with their neighbors. A new "mean" coordinate is calculated for each merged group.
  • Convergence: This process repeats, treating the new mean coordinates as nodes in a subsequent graph, until no edges remain between nodes, indicating that clusters are fully resolved.
  • Denoising: An optional parameter, $\beta$, allows the algorithm to discard low-degree nodes, effectively filtering out background noise.

This "mean of means" approach naturally gravitates toward the true center of biological structures, effectively mitigating the scatter caused by molecular blinking and measurement uncertainty.

Experimental Evaluation

The performance of HDCluster was validated across several benchmarks:

  • Shape Benchmarking: Standard 2D datasets (e.g., Aggregation, Flame) were used to test the algorithm's ability to handle non-spherical clusters.
  • Simulated SMLM Data: 500 synthetic datasets were generated to mimic realistic blinking and localization errors.
  • Real-World Biological Data: A dataset of Caveolin-1 labeled HeLa cells containing over 1.5 million localizations was used to test scalability.
  • DNA Origami Nanostructures: Gatta-PAINT "nanorulers" with known binding site spacings (20nm to 80nm) were used to verify reconstruction precision.

Key Results

HDCluster demonstrates significant advantages over industry standards like DBSCAN and Border Peeling (BP):

  • Computational Efficiency: On a 1.5-million-point dataset, HDCluster was over 55 times faster than optimized DBSCAN, completing the task in approximately one minute compared to nearly an hour.
  • Clustering Accuracy: In scenarios involving multiple molecular blinks, HDCluster showed a 10-12% relative improvement in Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI) over DBSCAN.
  • Robustness to Noise: HDCluster maintained high performance even when 50% of the points were random background noise, a scenario where other methods often fail.
  • Precision: The algorithm successfully recovered 20nm spacings in DNA origami grids, where other methods tended to merge distinct sites.

Conclusion and Future Work

HDCluster provides a fast, robust, and scalable solution for SMLM data analysis. By reducing the complexity to a single physical parameter ($mTh$), it simplifies the workflow for researchers. While currently optimized for 2D projections, future work will focus on expanding its application to 3D datasets and further automating parameter selection through heuristics like Ripley’s H-function.

Summary updated

Abstract

Clustering is a fundamental task in data analysis: grouping similar objects together into distinguishable subsets. Here, we introduce HDCluster, a novel high-degree graph-based clustering algorithm designed to effectively and rapidly handle various real-world clustering applications, particularly in the context of super-resolution single molecule localization microscopy (SMLM). HDCluster efficiently handles datasets with large and variable numbers of clusters, without requiring prior knowledge of the cluster count, relying on only one parameter. The high speed and efficiency of HDCluster allow it to handle large SMLM datasets with millions of localizations. A comprehensive quantitative comparison against state-of-the-art clustering methods using simulated, public, and real-world datasets demonstrates that HDCluster outperforms other clustering algorithms in terms of time efficiency and clustering performance measures, such as ARI and AMI. HDCluster is particularly robust to noise, making it a promising and effective tool for various clustering tasks in big-data settings, such as SMLM.
BibTeX
@misc{khater2025hdcluster,
  author = {Ismail M. Khater and Ivan R. Nabi and Ghassan Hamarneh},
  title = {{HDCluster: High-Degree Graph Clustering for Robust Analysis of Single Molecule Localization Microscopy}},
  year = {2025},
  doi = {10.1101/2025.10.23.684134},
  howpublished = {bioRxiv},
}
Figure