Analysis of temporal patterns

Question

I am analysing data on events that I have categorized into groups.

So, for instance, say I have 3000 events categorized into 5 groups, which we call A to E.

I will have something like

    Event  | Group | Time
   --------+-------+-------
       1   |   A   |   0
       2   |   A   |   5
       3   |   C   |   7
       4   |   D   |   16
      ...  |       |
     3000  |   B   |   6000

Now, I would like to see whether there is some sort of n-event long temporal sequence appearing repeatedly (higher than chance).

So for instance one 4-event long pattern may be:
A - 3 seconds - A - 2 seconds - D - 5 seconds - C

I found this paper which proposes some interesting method (I am not actually working on spike trains, but the issue is similar enough), but before implementing that I would like to see whether anyone knew of other methods/statistics that can be applied to this kind of problems.

Answer 1

A runs test seems appropriate, and the cited literature at the end develops the test statistic for multiple categories. Unfortunately the paper is paywalled but here is a quick run-down of the test statistic (screen shot of relevant page here).

For each individual group, we can count;

• $n_s = \text{Number of successes}$
• $r_s = \text{Number of success runs}$
• $s_{s}^{2} = \text{Sample variance of success run lengths}$
• $c_s = (r^2-1)(r+2)(r+3)/[2r(n-r-1)(n+1)]$
• $v_s = cn(n - r)/[r(r + 1)]$

Then you calculate this for each separate group, and the test statistic is the sum of the each $c_s \cdot s_{s}^{2}$ and is distributed as $\chi^{2}$ with $\sum{v_i}$ degrees of freedom.

So, lets say we have a table of run lengths for three different groups as follows;

Data: 221331333121112112212112122

Length Group1  Group2  Group3
-----------------------------
     1   5       4       0 
     2   2       3       1
     3   1       0       1
-----------------------------
    n_s 12      10       5
    r_s  8       7       2
    s_s  0.6     0.3     0.5
    c_s 11.1    14.0     1.3
    v_s  7.4     7.5     3.1 
-----------------------------
x^2 = (0.6*11.1) + (0.3*14) + (0.5*1.3) = 11
DF  = 7.4 + 7.5 + 3.1 = 18

Evaluating the area to the right of the test statistic is .9, so in this circumstance we would either fail to reject the null hypothesis that the distribution of the runs are randomly distributed. It is fairly close to the other tail though, so it is borderline evidence the data is more dispersed than you would expect by chance (as this is one of those circumstances it makes sense to evaluate the left tail of the Chi-Square distribution).

---

O'Brien, Peter C. & Peter J. Dyck. 1985. A runs test based on run lengths. Biometrics 41(1):237-244.

I've posted a code snippet on estimating this in SPSS at this dropbox link. It includes the made up example here, as well as a code example replicating the tables and statistics in the O'Brien & Dyck paper (on a made up set of data that looks like theirs).

Answer 2

If I understand, you are looking for k-mers which are patterns of size k found in sequences.

There is an R package for analyzing sequence data called TraMineR which includes functions for plotting the sequences, finding the variance of state durations, compute within sequence entropy, extract frequent event subsequences, etc.

You could also compare two sequences to see how they align in time by using Dynamic Time Warping