Process segmentation and modelling applied to time series featuring the response of biological materials to toxic agents

Graduation date: 2005The detection of biological and chemical toxins has become one of the main concerns\ud in environmental and military fields. In this framework, the department of Microbiology\ud and Biochemistry at Oregon State University has discovered that fish living cells\ud are promising indicators of the presence of a wide range of toxins. Thus, an interdisciplinary\ud project called ”SOS Cytosensor” was launched to create an autonomous and\ud mobile device to detect such toxins using these living cells.\ud After exposing a cell culture to a specific biological or chemical agent, a sequence\ud of cell images is recorded. The extraction of features from the experimental sequences\ud of images results in time series that have to be modelled and classified in order to prove\ud useful in toxin detection. The chosen models should give a representation of time series\ud that supports accurate classification and clustering and that would also make storage\ud and transmission more efficient. There are many techniques for dimensionality reduction\ud of time series data in the literature, such as Fourier transforms, but segmentation is\ud the most popular technique for extracting structures from time series. Segmentation\ud algorithms can be classified as batch or online. The main idea is that given a time\ud series Y, segmentation produces the best representation using an undefined number K\ud of segments, such that the combined error of all segments is less than a user-specified threshold and that the maximum error for any segment doesn’t exceed a user-specified\ud local threshold. First, we modelled each time series data using a single ARX model\ud with regularly spaced breakpoints. Then, we considered improving the result by placing\ud the breakpoints dynamically. As a pre-analysis of the curves, we performed a piecewise\ud linear segmentation, thus tracking changes in the behaviour of the time series and placing\ud breakpoints at those locations. Piecewise linear regression refers to the approximation of\ud a time series Y, of length N, with K straight lines. Because K is typically much smaller\ud than N, this representation makes the storage, transmission and computation of data\ud more efficient. The piecewise linear regression is usually used for change point detection,\ud which is our goal in this study.\ud As the segmentation into several simple adequate AR models proved not to be\ud satisfying in terms of fitting, we combined this concept with the piecewise linear segmentation\ud discussed above. Instead of modelling the time series by a single ARX model\ud using breakpoints determined by the segmentation algorithm or by several AR models,\ud we model each segment with a different ARX model. We use sum of square errors or the\ud residual error as a measure of the cost of merging segments. Computation speed has been\ud increased by presegmenting the time series with a fine piecewise linear approximation.\ud It also enables the user to predefine the number of final segments for classification and\ud clustering purposes. The final state can be detected by extracting the last segment from\ud the segmentation process.\ud Finally, classification and clustering are essential steps in the analysis of the experimental\ud time series. Cytosensor project required a numerical and non-numerical representation\ud of the experimental data. The approach adopted in this study is a soft\ud classification approach, which allows a better understanding and eases decision making,\ud thus complementing numerical features. Using calibration runs and the resulting model\ud parameters, we build a database of tight clusters representing scenarios. Then, we calculate\ud the probabilistic distances between an operational cluster and each of the calibration\ud clusters, leading to the identification of an operational run to a specific scenario