Change detection using an iterative algorithm with guarantees

Systems with abruptly changing parameters and states are common in multiple domains. Such systems often generate signals corrupted by noise and sensor dynamics. As such, many studies involving such systems normally involve detecting and analyzing signals with abrupt steps. While studying biological systems and processes at the molecular scale is fundamental for understanding the underlying failure mechanism of many human diseases, it is important to note that these systems are mostly driven by discontinuous processes at the nanoscale level. For example, molecular motor proteins responsible for cargo transport within cells take discrete steps. Defects in such molecular motors are linked with many afflictions including the Alzheimer’s disease.

Recent research in single molecule biophysics has focused on answering questions such as: How do mutations affect the step sizes and velocities of molecular motors? How does the cellular environment affect the ability of motors to carry a cargo? How do multiple motors share the work in transporting a load? Providing answers to such questions requires robust algorithms for detecting steps with high temporal and spatial resolution. Existing linear filtering techniques are ineffective when applied to step signals because of an overlap in the frequency domain content of noise and the step signals. Therefore, step detection in noisy signals has become an important research problem. Unfortunately, the complexity in filtering such step signals is further compounded by the availability of little or no prior information on the underlying generative processes like the distributions of the magnitudes and times of the steps.

Although there are several non-linear filtering techniques with different efficiencies and efficacies, only a handful offer theoretical guarantees. The recent research and development of heuristic, iterative and non-linear filtering technique based on dynamic programming has emerged as an effective game changer in filtering step signals. This technique has proved effective for estimating stepping probability under low signal to noise ratios. It has been found to be effective over a wide range of applications, like fluorophore event detection in nanodot array studies.

Inspired by this technique, PhD candidate Sivaraman Rajaganapathy, Dr. James Melbourne and Professor Murti Salapaka from the University of Minnesota developed an iterative step detection algorithm (SDA) for change detection. In their approach, each iteration involved two stages. The first stage involved determining the location and magnitude of the steps to estimate the true signal. The second stage consisted of computing the distribution of the event magnitude from the output of the first stage. Their work is currently published in the journal, Automatica.

The research team showed that each algorithm iteration improved the posterior probability of the obtained estimates. To this end, the iteration resulted in a converging sequence of the posterior probability. Comparative tests revealed that the presented algorithm provided significant performance improvement, particularly for applications where sensor dynamics must be considered. Furthermore, a python-based implementation was provided and compared with the existing methods.

In summary, the theoretical foundation and applicability of the newly proposed SDA was reported. The operational steps of this algorithm were analyzed using a non-restrictive probabilistic framework. The algorithm generally outperformed many existing algorithms, suggesting its potential applicability in a wide range of fields. In a statement to Advances in Engineering, Professor Murti Salapaka explained that their findings would contribute to the accurate detection of steps in noisy or corrupted signals commonly encountered in many fields.