What is the burst search algorithm?¶
To give some context, in the analysis of freely-diffusing single-molecule fluorescence experiments,
the burst search algorithm is the central step that allows identifying
bursts of photons emitted by single molecules during their diffusion
through a small excitation volume.
Here we use a simplified burst search that saves only start and stop times
of each burst. A complete real-world implementation can be found in
FRETBursts, a burst analysis
software (relevant code here and here).
Briefly, a burst search algorithm tries to identifies bursts in a long stream
of events. In single-molecule fluorescence experiments, this stream is
represented by photon arrival times (timestamps) with a resolution of a few nanoseconds.
A common algorithm, introduced by the Seidel group
(Fries 1998), consists in using a
sliding windows of duration $T$ and identifying bursts when at least $m$ photons
lie in this window.
The final step of selecting bursts by size (counts, or number of photons)
is computationally inexpensive and it will be ignored in this post.
Numerically, we need to “slide” the window in discrete steps, and since
photon arrival times are stochastic, it makes sense to place
the windows start in correspondence with each timestamp $t_i$ and check
if there are at least $m$ photons between $t_i$ and $t_i + T$.
But how can we “check if there are $\le m$ photons between
$t_i$ and $t_i + T$”? We can take a window $T$ and test if it
contains at least $m$ photon, or, we can take $m$ consecutive photons ($m$ fixed)
and test if they lie in a time window $\le T$.
The latter approach is much easier to implement and more
efficient, as it requires looping through the timestamps only once.
In this post we’ll follow this latter method.
For the sake of this post, we assume that each burst is characterized
by only a start and stop time. Finally, since the number of bursts
is not known in advance, we’ll use a list to collect the bursts
found during the search.