1
$\begingroup$

description of the algorithms behavior

I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the substring of s2, that has the biggest similarity to s1. The following alignments are possible:

[s2[:i] for i in range(len_s1)] + [s2[i:i+len_s1] for i in range(len_s2))]

e.g. for s1="ab" and s2="abcde" the following alignments should be considered:

['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

The similarity between s1 and the substring s2_substr of s2 is defined in terms of a normalized version of the InDel Distance. The InDel-Distance is a variation of the Levenshtein distance, that only allows the use of insertions and deletions (this can be e.g. achieved using a weight of 2 for substitutions). The distance is normalized in the following way: $1 - dist / (len\_s1 + len\_s2\_substr)$. I am using a bitparallel algorithm to calculate the InDel-Distance in $O([len_s1/w]len_s2)$ with the computer wordsize w (64 bit or higher when using SIMD). The algorithm is described in the paper New Bit-Parallel Indel-Distance Algorithm by Heikki Hyyrö.

Example

Here is a small example that shows how this algorithm works: For this example I am using the same example string shown above (s1="ab" and s2="abcde"). As shown above this generates the possible substrings of s2:

['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

These substrings have the following similarities to s1

s1 len_s1 s2_substr len_s2_substr distance similarity
'ab' 2 '' 0 2 DEL -> 2 1 - 2 / (2+0) = 0
'ab' 2 'a' 1 1 DEL -> 1 1 - 1 / (2+1) = 0.66
'ab' 2 'ab' 2 0 1 - 0 / (2+2) = 1
'ab' 2 'bc' 2 1 INS, 1 DEL -> 2 1 - 2 / (2+2) = 0.5
'ab' 2 'cd' 2 2 INS, 2 DEL -> 4 1 - 4 / (2+2) = 0
'ab' 2 'de' 2 2 INS, 2 DEL -> 4 1 - 4 / (2+2) = 0
'ab' 2 'e' 1 1 INS, 2 DEL -> 3 1 - 3 / (2+1) = 0

In this case the alignment 'ab' <-> 'ab' has the biggest similarity, so the function should return a similarity of 1.

Naive solution

A naive sliding window approach could calculate the distance in the following way:

max_similarity = 0
for s2_substr in variations:
    substr_similarity = similarity(s1, s2_substr)
    max_similarity = max(max_similarity, substr_similarity)

However this would have to test len_s1 + len_s2 possible alignments, so it has a complexity of O([len_s1+len_s2]*[len_s1/w]*len_s2. This becomes very slow for longer strings.

Different implementations of this algorithm

A relatively similar implementation is included e.g. in the Python library FuzzyWuzzy, which searches for the longest common substrings of s1 in s2. The starting points of those substrings are then used to calculate the best alignment. However it is not guaranteed, that the optimal alignment starts with one of the longest common substrings and therefore calculates a wrong similarity in many cases.

Question

Is there a faster algorithm to calculate this kind of similarity? The algorithm has the following requirements:

  1. defines similarity in Terms of the normalized InDel-Distance
  2. allows Gaps at start and end of s2
  3. when s2_substr is not placed at the start or end of s2 it requires the length len_s1

As suggested by D.W. the smallest distance with gaps at start and end can be found by making insertions to the smaller string free in the start (init first row of the distance matrix with 0 instead of insertion costs). The smallest value in the result row is the distance for the smallest alignment. However this approach has a couple of problems:

  1. it does not guarantee, that the length of the substring s2_substr is len_s1 for substrings that do not start at the start or end of s2. (Maybe this could be guaranteed with a modification, that I am just not aware of)
  2. it searches for the alignment with the smallest InDel Distance. However I am trying to optimize the normalized InDel Distance as described above. Since the normalization depends on the length of the substring s2_substr, which is not constant (at start/end of the string it can be smaller than len_s1), this does not always give the correct results.
$\endgroup$
0
$\begingroup$

I think you should be able to adapt the standard dynamic programming algorithm to this, with a minor modification: you simply treat deletions at the beginning and end of s2 as costing 0.

$\endgroup$
7
  • $\begingroup$ I have a couple of questions on this. 1) I know how to edit the distance to assign a cost of 0 to deletions in the beginning (init the matrix row to 0). How can I do this for the end of the string? 2) Is there a way to keep track of the length of the used substring for the normalization without searching for the path in the edit matrix? 3) How is substring length set to a size equal to s1 for substrings that are not at start/end? 4) This approach searches for the minimum edit distance. Does this necessarily mean a maximum similarity, since the substring might not always have a similar length $\endgroup$ Mar 12 at 21:16
  • $\begingroup$ @maxbachmann, the dynamic programming algorithm has two indices, one of them into s1. Adapt the distance function when the index into s1 is at the beginning or end of s1. No, search through the path after you've found a solution. You'll have to define what you mean by maximum similarity; please state all requirements in the question. $\endgroup$
    – D.W.
    Mar 12 at 21:24
  • $\begingroup$ The question states: defines similarity in Terms of the normalized InDel-Distance. The normalization is described in the section description of the algorithms behavior. Is there anything I should add to the question to make this more clear? $\endgroup$ Mar 12 at 21:29
  • $\begingroup$ Sorry, my fault, I missed that. I'm not sure what len_s2_sub represents. Apparently no substitutions are allowed so if that counts the number of substitutions it seems like without loss of generality it is zero, so you are just dividing by a fixed constant, which poses no problems. $\endgroup$
    – D.W.
    Mar 12 at 22:41
  • $\begingroup$ That was a bad naming convention. It represents the length of the substring, so I renamed it to s2_substr/len_s2_substr and added an example calculation of the algorithm $\endgroup$ Mar 12 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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