1
$\begingroup$

I'm looking for pointers to algorithms which will find long connected similar subsequences which two given sequences have in common. For example, in case of two strings:

abcaabbaabUVWXYZ
UVWXeYZababababab

I'm interested in:

**********UVWXYZ
UVWXYeZ**********

Not in:

ab*aabba*b*****
******aba*ab*bab

(which would be one possible longest common subsequence for the given strings).

For the example above, e represents a (small) difference in the otherwise identical strings UVWXYZ and UVWXeYZ. This is where the similarity comes in. e is not necessarily an addition of a single character. It may be a change as well. When thinking on longer strings, multiple characters (even in direct succession) may be different.

The algorithm should probably be driven by a rating function for the length and the similarity of subsequences.

I'm aware that this problem is rather vague, so any pointers to possibly related problem domains and corresponding algorithms are appreciated as well.

Update: Removed exclusion criterion "LCS", because it actually seems to be what I'm looking for.

$\endgroup$
  • 1
    $\begingroup$ Are you looking for the longest common substring? en.wikipedia.org/wiki/Longest_common_substring_problem $\endgroup$ – D.W. Sep 20 '16 at 23:39
  • $\begingroup$ @D.W. thanks for this pointer. I'm pretty sure "longest common substrings with k mismatches" is what I'm looking for. Though my k won't be constant but somehow be related to the substring length. $\endgroup$ – mstrap Sep 21 '16 at 8:32
  • $\begingroup$ @Evil I meant similarity in a more abstract way. It's pretty much the similarity which e.g. a human would see between two similar sentences. I'm not yet clear on how to formalize this. $\endgroup$ – mstrap Sep 21 '16 at 8:41
  • 3
    $\begingroup$ You're looking at a special case of sequence alignment: local and with high cost for gaps. $\endgroup$ – Raphael Sep 21 '16 at 9:38
  • 3
    $\begingroup$ Note that your example is not very descriptive. For instance, since you allow insertions, deletions and mismatches, you can express the match you don't want in these terms as well. You need to specify more precisely what you want "connected" to mean. (I think you have an intuitive notion of a cost function for sequence alignments, but you'll have to solidify that.) $\endgroup$ – Raphael Sep 21 '16 at 9:41
1
$\begingroup$

You might be interested in linear-time LCS variant with $k$ mismatches taking gaps with some penalty. Even though the core algorithm is with fixed gaps it is easily converted to your problem by just running algorithm with several gap lengths (naive approach). Better one would be to change the function calculating distance with function over penalties.

Another approach would be to take suffix tree modified to ignore gaps of length at most $k$ and then calculating penalties on the results (starting from longest one and then prunning results based on calculated best so far match including gap penalties). Optimized tree or DAG will decrease the memory footprint.

If you are interested in circular match simply concanate one string with itself.

$\endgroup$
  • $\begingroup$ Thanks for this idea. From my understanding, the approach of the cited paper is $O(n^2)$. From what I have read until now, there is probably no more efficient solution. Especially, suffix trees won't improve this? From a practical perspective, I'm dealing with sequences with 100 - 1000 tokens on average. Implementation will be in Java. Given that, would you recommend to follow the approach suggested in the paper or would you use suffix trees? $\endgroup$ – mstrap Sep 21 '16 at 22:13
  • $\begingroup$ @mstrap It depends on gaps (count and length). Suffix trees are good to pursue, it will decrease the average cost. Please check also fast k-mismatch. $\endgroup$ – Evil Sep 22 '16 at 2:23
  • $\begingroup$ LCS Variant Link is dead. Could you locate the new one or remove it all together. $\endgroup$ – Cyclotron3x3 Sep 12 '18 at 12:27
  • $\begingroup$ @Cyclotron3x3 researchgate.net/publication/…, I will look into it later to find not walled version. $\endgroup$ – Evil Sep 12 '18 at 17:06
1
$\begingroup$

Let's call this problem LCCS, which is different with LCS. One straightforward way is to use a brute force algorithm with time complexity $O(nm(n+m))$.

 1. Input: A[1..n], B[1..m] 
 2. Output: Length of the longest common connected subsequence
 3. max = 0
 4. for i from 1 to n
 5.    for j from 1 to m
 6.        if (lowercase(A[i]) = lowercase(B[j]))
 7.           i' = i
 8.           j' = j
 9.           len = 1
 10.          while (i' <= n and j' <= m)
 11.             i'++
 12.             j'++
 13.             if (lowercase(A[i']) != lowercase(B[j'])) break;
 14.             else len++;
 15.          if (len > max) max = len
 16. return max
$\endgroup$
  • 2
    $\begingroup$ Or use a suffix tree and get $\Theta (n + m)$. There is one problem, how your code detects "Y" -> "y"? It breaks so it returns "UVWX" only as count 4 not 6. $\endgroup$ – Evil Sep 21 '16 at 4:47
  • 2
    $\begingroup$ @Evil can we just take the lowercase? $\endgroup$ – orezvani Sep 21 '16 at 5:22
  • 1
    $\begingroup$ Unfortunately, this approach does not account to the similarity. I've updated my question -- sorry for not being precise here. $\endgroup$ – mstrap Sep 21 '16 at 8:45

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.