Analyzing brain signals by combinatorial optimization

We present a new method to determine the similarity (or synchrony) of a collection of multi-dimensional signals. The signals are first converted into point processes, where each event of a point process corresponds to a burst of activity of the corresponding signal in an appropriate feature space. The similarity of signals is then computed by adaptively aligning the events from the different point processes. If the point processes are similar, clusters containing one point from each time series will naturally appear. Synchrony is then measured as a function of the size of the clusters and the distance between points within one cluster. The alignment of events is defined in a natural statistical model; the optimal clustering is obtained through maximum a posteriori inference and can be cast as a combinatorial optimization problem. As the dimension and the number of signals increase, so does the complexity of the inference task. In particular, the inference task corresponds to: a) a dynamic program when comparing two 1-dimensional signals; b) A maximum weighted matching on a bipartite graph when comparing two d-dimensional signals; c) A NP-hard integer program that can be reduced to N-dimensional matching when comparing N ges 2 signals We show the applicability of the method by predicting the onset of mild cognitive impairment (MCI) from EEG signals.