HNCcorr: combinatorial optimization for neuron identification

We present a combinatorial algorithm for cell detection in two-photon calcium imaging. Calcium imaging is a modern technique used by neuroscientists for recording movies of in-vivo neuronal activity at cellular resolution. The proposed algorithm, named HNCcorr, builds on the combinatorial clustering problem Hochbaum’s Normalized Cut (HNC). HNC is a model that trades off two goals: One goal is that the cluster has low similarity to the remaining objects. The second goal is that the cluster is highly similar to itself. The HNC model is closely related to the Normalized Cut problem of Shi and Malik, a well-known problem in image segmentation. However, whereas Normalized Cut is an NP-hard problem, HNC is solvable in polynomial time. The neuronal cell detection in calcium imaging movies is viewed here as a clustering problem. HNCcorr utilizes HNC to detect cells in these movies as coherent clusters of pixels that are highly distinct from the remaining pixels. HNCcorr guarantees, unlike existing methodologies for cell identification, a globally optimal solution to the underlying optimization problem. Of independent interest is a novel method, named similarity-squared, that is devised here for measuring similarity. In an experimental study on data from the Neurofinder cell identification benchmark, HNCcorr is a top performer. In particular, it achieves a higher average score than two frequently used matrix factorization algorithms. The Python and Matlab implementations of HNCcorr used here are publicly available. The use of HNCcorr demonstrates that combinatorial optimization is a valuable tool for neuroscience and other biomedical disciplines.