7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The book, Discrete Multivariate Analysis, by Bishop, Holland, and others, has some techniques for finding patterns in sequences. $\endgroup$ – user31676 Oct 18 '13 at 21:06
  • $\begingroup$ I'm wondering if you had any updates on how you analzyed these data. I would be very interested in solutions as to finding sequences that occurred higher than chance $\endgroup$ – jalapic May 25 '15 at 2:17
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ That is interesting Andy, thank you. I guess it would need some tweaking to be generalized to multiple groups, but I will see if I can come up with something. By the way, if you register a JSTOR account you can read the paper online for free. $\endgroup$ – nico Oct 19 '13 at 7:28
  • $\begingroup$ @nico - I'm not sure what you mean by generalizing to multiple groups. I gave an example for runs in three groups, but the logic applies to more. (The typical runs test in most software I've seen only allows two, but the cited papers establishes the test statistic for multiple groups. That is why I elaborated with an example with 3 groups.) $\endgroup$ – Andy W Oct 20 '13 at 13:29
  • $\begingroup$ Sorry, what I meant is that the test analyses runs of binary events (success/failure), while I have more than two levels in my group variable. $\endgroup$ – nico Oct 20 '13 at 13:40
  • $\begingroup$ This is a great approach. Note though that above cs is defined slightly wrong -- you missed the last division. It should be: $c_s = (r^2-1)(r+2)(r+3)/([2r(n-r-1)(n+1)]$ $\endgroup$ – fsociety Jun 3 '14 at 9:15
  • $\begingroup$ Something else: Can you elaborate how you calculate the sample variance of success run lengths? $\endgroup$ – fsociety Jun 3 '14 at 9:22
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you Enrique, TraMineR seems very interesting I will try it on Monday! $\endgroup$ – nico Oct 19 '13 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.