Aligning and clustering sequences of events

Question

I have some data describing sequences of events. There are a number of different events (over 30), and the data records which event occurred in what order. There are no fixed number of events that occur in each sequence, and the same event may occur multiple times in the same sequence. Timing and length of events is irrelevant. This is "Distinct-State-Sequence" data in the language of TraMineR.

So for example, using letters to code for the events, some datapoints may be:

1: ABCDEFG
2: ACDGH
3: BDEFEGI
4: AH
5: DEGHI

My aim is to uncover consistent patterns in the order of events, e.g. trying to find a minimal set of different representative sequences (clustering). However, my hunch is that because the sequences are uneven in length and inconsistent in starting point, that these should be aligned first to be able to be fairly compared, such that the data looks something like this:

1: ABCDEF-G--
2: A-CD---GH-
3: -B-DEFE--I
4: A-------H
5: ---DE--GHI

I've come across the TraMineR package which may well do what I want in general, but it has limited options for alignment (left align, right align, align on a single character).

I'm familiar with DNA/RNA/AA sequence alignment, but even if I can get an alignment algorithm to work with 34-state data, this probably isn't appropriate for non-biological data.

I've also come across alignment methods for text corpora, but since this isn't natural language data this probably isn't appropriate either.

I'm familiar with R in general but more for standard tabular data. I'd appreciate any pointers towards algorithms that I can use to align these sequences - from there on I think I can probably figure out how to do things like distance calculations and clustering.

Answer 1

TraMineR does not propose any aligning algorithm. It offers plenty of dissimilarity measures that can be used to compute pairwise distances between sequences as well as distances from each sequence to a reference sequence. The proposed methods include "aligning methods" that set the distance between two sequences as the cost of transforming one sequence into the other. This latter transformation can be seen as an aligning operation.

You do not explain how you would identify the representative patterns or clusters from your aligned sequences. Probably you will first compute dissimilarities between aligned sequences, and then input the pairwise dissimilarities into a cluster algorithm. Since computing the dissimilarities does not require to first align all sequences, you could do the same with dissimilarities computed by means of TraMineR.

I illustrate below with you small example data set and using the LCS distance based on the length of the longest common subsequence between the two considered sequences.

First we define the sequence object and compute the matrix diss of pairwise dissimilarities.

library(TraMineR)
dat <- c("ABCDEFG",
         "ACDGH",
         "BDEFEGI",
         "AH",
         "DEGHI")
ddat <- seqdecomp(dat, sep="")
seq <- seqdef(ddat)
seq

##     Sequence     
## [1] A-B-C-D-E-F-G
## [2] A-C-D-G-H    
## [3] B-D-E-F-E-G-I
## [4] A-H          
## [5] D-E-G-H-I 

diss <- seqdist(seq, method="LCS")
diss

##      [,1] [,2] [,3] [,4] [,5]
## [1,]    0    4    4    7    6
## [2,]    4    0    8    3    4
## [3,]    4    8    0    9    4
## [4,]    7    3    9    0    5
## [5,]    6    4    4    5    0

We observe that the greatest distance is between sequences 3 and 4 that differ by the greatest number (9) of elements (events). The closest sequences are 2 and 4 that differ by 3 elements only.

Now, we can use the dissimilarity matrix to identify the smallest set of representative sequences (here the smallest set that covers 60 % of all sequences with a neighborhood radius equal to 40 % of the maximal distance)

seqrep(seq, diss=diss, coverage=.6, pradius=.4)

##  [>] number of objects (sum of weights): 5
##  [>] max. distance: 9
##  [>] neighborhood radius: 3.6
##  [>] 2 representative(s) selected, coverage=60% (threshold=60%)
##  [>] 5 distinct sequence(s) 

##  [>] criterion: density 
##  [>] 5 sequence(s) in the original data set
##  [>] 2 representative sequence(s)
##  [>] overall quality: -1.85 
##
##     Sequence     
## [1] A-C-D-G-H    
## [2] A-B-C-D-E-F-G

The representative sequences are respectively the second and first sequences.

We can also input the diss matrix into a clustering algorithm (here hclust):

clust <- hclust(as.dist(diss))
plot(clust)