# How to calculate extent of Sequence similarity [closed]

I had a problem that I was wondering if it could be solved by one of the techniques/algorithms used in bioinformatics to give the extent of similarity.

I have a Problem Statement: we have a sensor (its like a magnetic compass and has a dial with twelve equal zones- 30 degrees each) that every second outputs where its pointing. The typical random output of the sensor may look like (for example):

30 30 30 30 30 30 120 120 120 120 120 120 60 60 60 60 60 60 330 330 330 330 30 30 30 30 210 210 210 210 210 60 60 60 60 60 60 60 60 60 60 60 60 60 ……… etc.

We wanted to see if we can calculate a measure of similarity of two 4-minute sequence samples taken at different times during the day. (It would be great if we could state something like - the sequences are similar and there is a 1 in million (say) chance that we may be wrong.)

## closed as primarily opinion-based by WYSIWYG, Chris♦, Cornelius, Armatus, Devashish DasJul 31 '14 at 13:05

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

• very interesting ... the standard methods all work on linear values, and not angles. Is the pattern "30 60 90" similar to "120 150 180"? (I.e. do you only care about relative movement, or also about the actual direction?) – Michael Kuhn Sep 5 '13 at 6:11
• It seems OP asked the question and never returned... – Memming Oct 6 '13 at 18:34

## 4 Answers

Well. You perhaps need not use the bioinformatic algorithms of string matching. These algorithms were primarily developed because of the extensive search space.

In your problem you just need to compare two recording experiments and you should use mathematical metrics for it. You have a 60x4 i.e 240 dimensional random variable. Moreover this variable is not discrete, it is continuous. For similarity measurements you have to use statistical tests or otherwise define a cutoff either on each element of the vector or the total magnitude defined by any norm.

I tend to agree that bioinformatics has no special general help for matching sequences of numbers. Most of the specialized algorithms in bioinformatics are string oriented.

If distance metrics, Fourier or wavelet decomposition don't work, you might want to look for motifs in your sequence, then you might try a motif dictionary similar to an alignment algorithm. They are like NGram algorithms, but then they extend out.

1. Build dictionary of all sequences of numbers from your reference sequence: say of 5 or 7 length.
2. Identify identical or better yet linear combinations of those dictionary entries and then expand the comparison by one index in either direction to get the maximal length of comparable identity/similarity.
3. List all your 'hits' by a score - a length and distance based metric.

is this the sort of thing you were looking for?

The first thing that comes on my mind is to use cross-correlation (CCF). Essentially you compare one trace with variously shifted version of the other to see if there is a correlation between them.

For example (I am using R but you should be able to adapt this to your software of choice, I have added comments), say A and B are very similar, but shifted of a certain amount in the x axis (10 units in the example) and C is extremely different

# Set the random seed to get a reproducible example
set.seed(12345)
# Number of points per trace
n <- 1000
# All of the possible sensor values
values <- seq(0, 330, 30)
# Sample with replacement to get 100 random values
A <- sample(values, n, replace=TRUE)
# Let B = A shifted by 10 positions and then change one value every 5
B <- c(A[-1:-10], A[1:10])
B[seq(0, n, 5)] <- sample(values, n/5, replace=TRUE)
# C is a completely different trace
C <- sample(values, n, replace=TRUE)
# Plot the traces (I'm offsetting B and C just for visual clarity)
plot(A, t="l", col="red", lwd=2, ylim=c(0, 1200))
points(B + 360, t="l", col="green", lwd=2)
points(C + 720, t="l", col="blue", lwd=2)

# Now calculate the CCF
c.AB <- ccf(A,B, 100)
c.BC <- ccf(B,C, 100)
c.AC <- ccf(A,C, 100)

# Superimpose the CCF plots
plot(c.AB$lag, c.AB$acf, t="o", col="green", ylim=c(-0.5,1), ylab="CCF", xlab="Lag")
points(c.BC$lag, c.BC$acf, t="o", col="red")
points(c.AC$lag, c.AC$acf, t="o", col="blue")
abline(v=10, col="grey", lty=3)
legend("topleft", c("A-B", "B-C", "A-C"), col=c("green", "red", "blue"), lty=1, lwd=2, pch=20)


The CCF graphs look like this: This graphs means that there is a strong positive correlation (max correlation = 1, here you have 0.8) between A and B and that they are shifted of 10 units. You can see this because the peak is at lag=10, corresponding to the gray dashed line, so the maximum correlation is when you shift trace B by 10 units.

B and C and A and C are instead uncorrelated.

You can try dynamic time warping, or string kernel as a measure of similarity. However, similarity is highly context-dependent, and you may have to invent your own notion of similarity. First you need to ask yourself what do you consider similar. This is a hard problem, and borrowing arbitrary solutions from different fields may not be the best idea.