With the development of bright fluorescent probes, stable microscopes and sensitive cameras, live cell imaging has become a standard technique to study sub-cellular dynamics. The resulting images often consist of punctate features, representing small molecular assemblies or even single molecules1–3
. To gain insight into the molecular mechanisms that drive the observed dynamics, such experiments must be combined with single particle tracking (SPT) that captures the full spatio-temporal complexity of sub-cellular particle behavior.
SPT faces several challenges that in practice hinder such studies. Importantly, SPT goes beyond the detection and localization of particles; its key step is the establishment of correspondence between particle images in a sequence of frames. Establishing correspondence is complicated by various factors, most notably high particle density, particle motion heterogeneity, temporary particle disappearance (e.g. due to out-of-focus motion and detection failure), particle merging (i.e. two particles approaching each other within distances below the resolution limit), and particle splitting (i.e. two unresolved particles diverging to resolvable distances)4, 5
. Historically, many of these challenges have been overcome by diluting the fluorescent probes, resulting in a low particle density with almost unambiguous particle correspondence6, 7
. Under such conditions, particle tracking is indeed reduced to a simple particle detection and localization problem8
. However, while low particle densities reveal motion characteristics1–3, 9, 10
, they do not allow probing of the interactions between particles11
. Also, the amount of data collected per experiment is low, limiting the observation of spatially and temporally heterogeneous particle behavior and hindering the capture of infrequent events. Furthermore, even with low particle density, low signal-to-noise ratio (SNR) and probe flicker complicate the search for particle correspondence. Therefore, for most cell biological studies, there is a great need for robust SPT methods that address the challenges mentioned above.
The most accurate solution to SPT is provided by the method of multiple-hypothesis tracking (MHT)12
. In MHT, given particle positions in every frame, all particle paths within the bounds of expected particle behavior are constructed throughout the whole movie. The largest non-conflicting ensemble of paths is then chosen as the solution, where non-conflicting means that no two paths share in any frame the image of the same particle. This solution is globally optimal in both space and time, i.e. it is the best solution that can be found by simultaneously accounting for all particle positions at all time points. Clearly, MHT is computationally prohibitive even for problems with a few tens of particles tracked over a few tens of frames. Therefore, heuristic algorithms with higher computational efficiency have been proposed to approximate the MHT solution. Most of these algorithms are greedy
, i.e. they seek to approach the globally optimal solution by taking a series of locally optimal solutions. Usually, this means that particle correspondence is determined step-by-step between consecutive frames13
, reducing computational complexity at the expense of temporal globality. Many tracking algorithms then solve the frame-to-frame correspondence problem in a spatially global manner14–20
, and seek to recover tracks after temporary particle disappearance14–18, 21
. Some algorithms treat merging and splitting as a temporary disappearance of one of the particles14–16
, while others treat them as separate events20, 22
. Racine et al.23
are unique in their approach to SPT in that they use kymograms to maximally benefit from temporal information and thus avoid many of the problems of greedy algorithms. However, their method cannot track Brownian motion and is thus not generally applicable. While the many existing algorithms address one or the other of the issues in SPT, none of them tackles all the issues simultaneously. Consequently, investigators must sacrifice some tracking aspects for the sake of others, based on their specific application.
Here we present a tracking algorithm that uses one mathematical framework, the linear assignment problem (LAP)24, 25
, to provide an accurate solution to all the SPT challenges listed above. Given a set of detected particles throughout a time-lapse image sequence, the algorithm first links the detected particles between consecutive frames, and then links the track segments generated in the first step to simultaneously close gaps and capture particle merge and split events. Thus, while the initial particle assignment is temporally greedy, the subsequent track assignment is accomplished via temporally global optimization, overcoming the shortcomings of algorithms relying solely on greedy assignment strategies. Both steps employ global optimization in space. Overall, this approach defines an accurate, yet computationally feasible, approximation to MHT, allowing the robust tracking of particles under high density conditions.
We demonstrate our approach based on two applications that critically depend on tracking robustness and globality: (1) Accurate, comprehensive lifetime analysis of endocytic clathrin-coated pits (CCPs), and (2) single molecule tracking of the macrophage trans-membrane receptor CD36, revealing receptor aggregation and dissociation events.