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:
- Noise and Background: Random localizations unrelated to biological structures.
- Blinking Artifacts: Single molecules appearing as multiple points due to stochastic switching.
- Scale: Datasets often exceed millions of points.
- 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