9
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – ttnphns
    Commented Aug 26, 2015 at 19:16
  • $\begingroup$ I was just going to suggest edit distance but I see @ttnphns already mentioned it. $\endgroup$
    – Enrique
    Commented Aug 26, 2015 at 19:35
  • $\begingroup$ 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? $\endgroup$
    – whuber ♦
    Commented Aug 26, 2015 at 20:41

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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:

  1. Longest common substring
  2. Longest common subsequence

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – sgyf
    Commented Aug 27, 2015 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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