# similarity measure between two different ordered sequences

I know we can quantify the similarity between two sequences with the same length and same elements by rank order correlation. But how to measure similarity between two sequences of different length, and only having some elements in common?

For example, if I have three rank ordered numeric sequences like this:

sequence A: 1,2,3,4,5,6,7,8,9;

sequence B: 2,3,4,5,6,7,8,9,10,11,12,13

sequence C: 4,2,9,7,11,13,14,16,18

Intuitively, I guess sequence A and B are more similar, since they have more numbers in common and the common numbers have same order in both sequences. Sequence A and C are less similar since they have less number in common and the common numbers have difference orders in each sequence. Is there any quantitative measurement to capture both the order similarity in common elements and the percentage of common elements in two sequences?

• Approaches and measures of similarity are so plenty. First of all, you should decide whether you want to compare these as sequences or as texts (documents). First means that not only co-occurences but also co-positions of the identical elements bother you. Search internet for document similarity measures, text similarity measures, sequences similarity measires, edit distance, DNA comparisons, alignment distances and so on. Aug 26, 2015 at 19:16
• I was just going to suggest edit distance but I see @ttnphns already mentioned it. Aug 26, 2015 at 19:35
• To get meaningful answers to this question you will need to disclose more information about what "similarity" is intended to mean. What is the underlying statistical problem you are trying to solve?
– whuber
Aug 26, 2015 at 20:41

As mentioned in @ttnphns' comment, there exist plenty of dissimilarity measures. Have a look at the review by Studer & Ritschard (2015) who examine the sensitivity of the measures to ordering, position (timing) and duration (how many times a state is repeated). The measures addressed in that paper are all provided by the seqdist function of the TraMineR R package.

If you are primarily interested in the uncommon part between your two sequences, an edit distance such as optimal matching may be the solution. Optimal matching measures the minimal cost of transforming one sequence into the other by means of indels (insert or delete) and substitutions and can account for indel and substitution costs. If the difference say between rank 1 and 3 is twice the difference between rank 1 and 2 you could set the substitution costs as the rank differences for example. Such a measure works for sequences of different length. It would just account for the cost of the indels necessary to make the sequences of equal length.

If you prefer to give more focus on the similarity in the ordering of the elements in the sequences, some other measures such as optimal matching of transitions for instance could be a better choice.

Hope this helps.

It sounds to me that you are seeking something like a sub-sequence similarity, am I right? If so: Imagine both sequences A and B as strings, then you could apply:

The length of the resulting string could be then divided by the maximum length regarding A and B. Would this be an option for you?

• Not exactly, I also want to take into account the uncommon part between two sequence. The more uncommon part, the more different two sequences. But thanks anyway.
– sgyf
Aug 27, 2015 at 13:44