The world of sequence mining — four lenses on the same stream of events.

An event log — classroom turns, clinical actions, MOOC clicks, gameplay moves — is a stream of categorical events ordered in time. Researchers want very different things from the same stream:

• "How likely is each next move given the current one?" → TNA
• "Does B follow A more than chance would predict?" → LSA
• "Which long sub-sequences recur across many sessions?" → SPM
• "Are observed moves driven by a few hidden cognitive states?" → HMM

Each method makes different assumptions and produces a different artefact. Treating them as competitors is a category error — they answer different questions. The next chapter maps method to question.

Visual decision tree

Many standard statistical procedures quietly assume that observations are independent and identically distributed (IID), or at least close enough that large-sample approximations behave well. Sequence data usually break that intuition. In an event stream, what happens at time t is often constrained by what happened at t-1, t-2, or by the broader local state of the interaction.

So does the central limit theorem fail?

Not exactly. The central limit theorem is not simply "false" for all dependent data, but you do not get to assume the simple IID version by default. Some dependent processes still admit asymptotic normality under additional mixing or stationarity conditions, but most applied behavioral datasets do not justify that leap automatically. Classroom talk, gameplay actions, clinical routines, and clickstreams are often path-dependent, bursty, and heterogeneous across sessions.

That is why sequence analysis often leans on resampling, permutation, simulation, or model-based likelihood logic instead of casually treating every event as if it were an independent draw from one big population.

Why permutation shows up so often

Permutation logic is attractive in sequence work because it can compare the observed structure to a rearranged world where the target effect is absent, while preserving parts of the data you still believe. For example, you may want to preserve session boundaries, overall code frequencies, or group labels, but break the specific alignment that would make one transition pattern look stronger than another.

That is also why permutation is not one single thing. A good permutation scheme must respect the unit of analysis. Sometimes you permute group labels across sessions. Sometimes you shuffle within session under constraints. Sometimes you simulate from a fitted null process instead of permuting raw events. The right choice depends on which dependence structure you are trying to keep and which structure you are testing against.

How this maps onto the four methods here

• TNA: often uses bootstrap or permutation-style comparisons because edge weights and centralities come from dependent event transitions, not IID rows.
• LSA: explicitly asks whether an observed lagged transition is above a chance model, so the null model is built into the logic of the z statistic.
• SPM: is descriptive first; the statistical challenge is usually choosing support thresholds and filtering trivial patterns, not pretending the discovered motifs came from IID events.
• HMM: handles dependence by modeling it directly through latent states and transition probabilities rather than pretending successive events are independent.

Every figure in this guide comes from one synthetic CSV bundled at example_data/fake_dialogue_long.csv. It is not real data — transition matrices were hand-tuned so each method has something interesting to find.

First ten rows

Each row is one turn. The five code columns are 0/1; exactly one is on per turn (in this synthetic data).

user_id, cond,      turn_idx, speaker, ASK, EXPLAIN, EXAMPLE, AGREE, ELABORATE
P001,    treatment, 1,        A,        0,   1,       0,       0,     0
P001,    treatment, 2,        B,        0,   0,       0,       0,     1
P001,    treatment, 3,        A,        0,   0,       0,       0,     1
P001,    treatment, 4,        A,        0,   0,       1,       0,     0
P001,    treatment, 5,        B,        0,   0,       0,       0,     1
P001,    treatment, 6,        A,        0,   0,       0,       0,     1
P001,    treatment, 7,        B,        0,   1,       0,       0,     0
P001,    treatment, 8,        A,        0,   0,       0,       0,     1
P001,    treatment, 9,        B,        0,   0,       0,       0,     1
P001,    treatment, 10,       B,        0,   0,       0,       1,     0

Sample-size cheat sheet

Per-method, this CSV is reshaped exactly once into the structure that method needs:

Open R. Paste the block. You should see a TNA network of the synthetic data within a minute.

# 1) Install once (skips already-installed)
pkgs <- c("tna", "TraMineR", "arulesSequences", "seqHMM", "ggplot2")
new <- setdiff(pkgs, rownames(installed.packages()))
if (length(new)) install.packages(new,
       repos = "https://cloud.r-project.org")

# 2) Load + grab the bundled fake CSV from GitHub
library(tna); library(TraMineR)
url <- "https://educatian.github.io/sequence-mining/example_data/fake_dialogue_long.csv"
long <- read.csv(url, stringsAsFactors = FALSE)

# 3) Reshape one-hot to a single ‘code’ column, then to wide matrix
CODES <- c("ASK","EXPLAIN","EXAMPLE","AGREE","ELABORATE")
long$code <- CODES[apply(long[, CODES], 1, which.max)]
ids <- unique(long$user_id)
Lmax <- max(table(long$user_id))
W <- matrix(NA_character_, length(ids), Lmax,
            dimnames = list(ids, paste0("t", 1:Lmax)))
for (uid in ids) {
  s <- long[long$user_id == uid, ]
  W[uid, 1:nrow(s)] <- s$code[order(s$turn_idx)]
}

# 4) Fit + plot
seq_obj <- seqdef(W, alphabet = CODES)
m <- build_model(seq_obj)
plot(m)              # your first TNA figure
centralities(m)      # in/out degree etc.

TNA models your stream as a first-order Markov chain (next state depends only on current state) and renders the resulting transition matrix as a directed weighted graph — with centrality, bootstrap edge stability, community detection, and permutation-based group comparison built in.

Minimal code

library(tna); library(TraMineR)
seq_obj <- seqdef(wide_matrix, alphabet = CODES)
m <- build_model(seq_obj)            # fit first-order TNA
plot(m)                                # transition graph
centralities(m)                        # in/out degree, betweenness, closeness, ...
boot <- bootstrap(m)                 # edge stability
gm <- group_model(seq_obj, group = cond)  # per-group
permutation_test(gm)                   # test group difference

TNA · full cohortEdge labels = first-order transition probability. Self-loops show how often a state stays put. The strong ASK→EXPLAIN→EXAMPLE→ELABORATE backbone reflects the synthetic transition matrix.

TNA · per-groupTreatment vs Control side-by-side. Each panel uses the same node positions; visual differences reflect transition-probability differences.

LSA is the classic confirmatory test: given antecedent A, is consequent B significantly more likely at lag k than chance? It produces a z-score per (A, B, lag) cell. Popularised by Bakeman & Gottman; Allison & Liker (1982) corrected the variance for the dependence between row and column counts.

Minimal code (no external package)

# Reshape long-format CSV into a list of code-vectors (one per session)
sessions <- split(long$code, long$user_id)
CODES <- c("ASK","EXPLAIN","EXAMPLE","AGREE","ELABORATE")
trans <- matrix(0, length(CODES), length(CODES),
                dimnames = list(CODES, CODES))
# Build lag-1 transition counts
for (s in sessions) {
  for (i in 1:(length(s) - 1))
    trans[s[i], s[i+1]] <- trans[s[i], s[i+1]] + 1
}
# Allison-Liker z
N <- sum(trans); rsum <- rowSums(trans); csum <- colSums(trans)
pA <- rsum / N; pB <- csum / N
expected <- outer(rsum, pB)
var_AL  <- outer(rsum, pB * (1 - pB)) * outer(1 - pA, rep(1, length(pB)))
z <- (trans - expected) / sqrt(var_AL)

LSA · AL z-scoresRead row to column. The +20.6 cell (ASK→EXPLAIN) confirms the synthetic backbone. Negative z (teal) means the consequent occurs less than chance after that antecedent.

Lag k > 1

To test "does B follow A two turns later," replace s[i+1] with s[i+k] in the inner loop and adjust the loop bound to length(s) - k. The Allison–Liker formula stays the same. In practice researchers report lag 1 and lag 2; longer lags require much more data.

SPM looks for variable-length sub-sequences that occur in at least minSupport fraction of your sessions — without imposing any Markov assumption. The cSPADE algorithm (Zaki 2001) implemented in arulesSequences is the standard R route; SPMF (Java) and PrefixSpan (Python) cover the rest.

Minimal code

library(arulesSequences)
# Step 1 — write a basket file (one row per event):
#   sequenceID  eventID  size  item
# Example first 4 lines of "baskets.txt":
#   P001 1 1 ASK
#   P001 2 1 EXPLAIN
#   P001 3 1 EXAMPLE
#   P001 4 1 ELABORATE
# Step 2 — read it back as a transactions object:
trans <- read_baskets("baskets.txt",
                       info = c("sequenceID","eventID","SIZE"),
                       sep = " ")
patterns <- cspade(trans,
                   parameter = list(support = 0.3,
                                    maxsize = 1, maxlen = 4))
df <- as(patterns, "data.frame")
df$n_items <- stringr::str_count(df$sequence, ",") + 1
df_focus <- subset(df, n_items >= 2 & support < 0.98)
df_focus[order(-df_focus$support, -df_focus$n_items), ]   # more interpretable top patterns

HMM lets the state be latent. Observed codes are noisy emissions from a smaller set of unobserved cognitive/behavioural states. The model learns (1) emission probabilities P(code | state), (2) transition probabilities P(state_t+1 | state_t), and (3) the most-likely state sequence per observation (Viterbi).

Minimal code

library(seqHMM); library(TraMineR)
seq_obj <- seqdef(wide_matrix, alphabet = CODES)
hmm0 <- build_hmm(observations = seq_obj, n_states = 3)
fit  <- fit_model(hmm0,
                  control_em = list(restart = list(times = 5)))
fit$model$transition_probs        # K x K state-transition matrix
fit$model$emission_probs          # K x V code-emission matrix
plot(fit$model)                   # observed + hidden state plot

HMM · K=3 hidden statesTop: observed code per turn per session. Bottom: most-likely hidden state assignment. Compact contiguous bands suggest the state model captures real structure rather than noise.

Choosing K with BIC

# Fit K = 2..6 and compare BIC
bic_table <- sapply(2:6, function(K) {
  set.seed(K)
  fit <- fit_model(build_hmm(seq_obj, n_states = K),
                    control_em = list(restart = list(times = 5)))
  BIC(fit$model)
})
best_K <- (2:6)[which.min(bic_table)]
cat("Best K by BIC:", best_K, "\n")

Pick the K with the lowest BIC, but also check that the gain from K to K+1 is meaningful. A drop of 2–6 BIC is "weak"; >10 is "strong" (Kass & Raftery 1995). For very long sequences BIC tends to over-penalise — cross-validated log-likelihood is more honest but takes longer to compute.

Hard state assignments (Viterbi)

paths <- hidden_paths(fit$model)   # most-likely state per turn per session
table(paths)                       # overall state usage

Run TNA on paths to get a transition graph in latent space — often more interpretable than the raw-code TNA.

To make the family relationship vivid: all four figures above were fit on exactly the same 4,136-turn synthetic CSV. They each tell a different story.

When to chain them

• TNA → HMM: Use TNA to confirm the data has structure; use HMM to ask whether that structure is driven by latent states.
• SPM → LSA: Use SPM exploratorily to surface frequent motifs; use LSA to test whether the surfaced motifs are statistically meaningful.
• LSA → TNA: Use LSA to identify which transitions are above chance; visualise only those edges in TNA for a cleaner figure.
• HMM → TNA: Run TNA on the inferred hidden-state sequence to get a transition graph in latent space.

Install issues (do this first)

Runtime issues

build_model(seq_obj)
group_model(seq_obj, group=g)
centralities(m)
bootstrap(m); plot(boot)
permutation_test(group_model)

trans <- count_lag1(sessions)
expected <- outer(rsum, csum/N)
var_AL   <- outer(rsum, p*(1-p)) *
            outer(1-pA, 1)
z <- (trans - expected) /
     sqrt(var_AL)

trans <- read_baskets(file)
patterns <- cspade(trans,
  parameter = list(
    support = 0.3,
    maxlen  = 4,
    maxsize = 1))
as(patterns, "data.frame")

hmm0 <- build_hmm(seq_obj,
                  n_states = K)
fit  <- fit_model(hmm0,
  control_em =
    list(restart =
         list(times = 5)))
hidden_paths(fit$model)

Inputs / outputs at a glance

TNA

• Tikka, S., López-Pernas, S., & Saqr, M. (2025). tna: An R Package for Transition Network Analysis. Applied Psychological Measurement. doi:10.1177/01466216251348840
• Saqr, M., López-Pernas, S., Törmänen, T., Kaliisa, R., Misiejuk, K., & Tikka, S. (2025). Transition Network Analysis: A Novel Framework. LAK '25 Proceedings. doi:10.1145/3706468.3706513
• Package site: sonsoles.me/tna/ · tutorials at lamethods.org/book2/ (chapters 15–17 cover TNA / FTNA / TNA-clusters).

Lag Sequential Analysis

• Bakeman, R., & Quera, V. (2011). Sequential Analysis and Observational Methods for the Behavioral Sciences. Cambridge University Press. Book page · Chapter 11 preview
• Allison, P. D., & Liker, J. K. (1982). Analyzing sequential categorical data on dyadic interaction. Psychological Bulletin, 91(3), 393–403. doi:10.1037/0033-2909.91.3.393 (The variance correction we use.)
• O'Connor, B. P. (1999). Simple and flexible SAS and SPSS programs for analyzing lag-sequential categorical data. Behavior Research Methods, Instruments, & Computers, 31, 718–726. doi:10.3758/BF03200753
• Draper, Z. A., & O'Connor, B. P. LagSequential [R package]. CRAN · reference manual · vignette / docs index.

Sequential Pattern Mining

• Zaki, M. J. (2001). SPADE: An efficient algorithm for mining frequent sequences. Machine Learning, 42, 31–60. Springer page (cSPADE adds constraints.)
• Buchta, C., & Hahsler, M. arulesSequences [R package]. CRAN · cSPADE function manual.
• Fournier-Viger, P. et al. SPMF — Java reference library with 55+ algorithms. official docs + examples
• Python: PrefixSpan-py.

HMM

• Helske, S., & Helske, J. (2019). Mixture Hidden Markov Models for Sequence Data: The seqHMM Package in R. Journal of Statistical Software, 88(3). doi:10.18637/jss.v088.i03
• seqHMM docs: package index · estimation vignette · algorithms vignette.
• Visser, I., & Speekenbrink, M. (2010). depmixS4: An R Package for Hidden Markov Models. Journal of Statistical Software, 36(7). JSS page.
• Python: hmmlearn · tutorial.