0
$\begingroup$

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.

$\endgroup$
  • 4
    $\begingroup$ Why is this tagged with "genetic-algorithms"? $\endgroup$ – Raphael Sep 26 '11 at 10:17
  • 3
    $\begingroup$ There seems to be some confusion: the title mentions "substrings" but the body of the question mentions "subsequences". Either way, I do not quite understand what is the goal (what should be the output): the set of all common substrings or subsequences can very large; you cannot expect a linear-time algorithm. $\endgroup$ – Jukka Suomela Sep 26 '11 at 11:36
  • 3
    $\begingroup$ @mcorley, could you clarify if the answer I gave below is what you were looking for and if not, what exactly you would like the output to be, please. $\endgroup$ – Raphael Sep 26 '11 at 12:45
  • 1
    $\begingroup$ @mcorley: I think you have a misunderstanding here; genetic algorithms are not the same thing as algorithms for analysing DNA sequences. $\endgroup$ – Jukka Suomela Sep 26 '11 at 16:02
  • 1
    $\begingroup$ Unfortunately, the clarification does not yet help much. Consider, for example, the case of strings CDEFACFH and ACDEFH. Now what are the common substrings? (CDEF,H)? (CDE,FH)? (AC,FH)? Something else? $\endgroup$ – Jukka Suomela Sep 26 '11 at 18:23
4
$\begingroup$

Depending on your application (and assuming I have correctly understood your general aim), a standard practical method will be to find all maximal repeated substrings between the two strings, number those substrings and then compute the longest increasing subsequence. This is exactly what the bioinformatics tool Reputer does. See http://bibiserv.techfak.uni-bielefeld.de/reputer/ and http://bioinformatics.oxfordjournals.org/content/15/5/426 for an original reference.

This is is slightly super-linear time overall as you have to compute the longest increasing subsquence (see e.g. http://en.wikipedia.org/wiki/Longest_increasing_subsequence ).

$\endgroup$
  • $\begingroup$ I apologize, this is actually a great paper and I am looking further into this. $\endgroup$ – mcorley Sep 26 '11 at 19:46

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.