HNCcorr: combinatorial optimization for neuron identification

Roberto Asín Achá (), Dorit S. Hochbaum () and Quico Spaen ()
Additional contact information
Roberto Asín Achá: Universidad de Concepción
Dorit S. Hochbaum: University of California
Quico Spaen: University of California

Annals of Operations Research, 2020, vol. 289, issue 1, No 2, 5-32

Abstract: Abstract 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.

Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03464-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:289:y:2020:i:1:d:10.1007_s10479-019-03464-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03464-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().