LongestCommonSequence[] works well, but what about finding the longest common sub-sequence (not necessarily contiguous)? Is this function built in to the genome package? And it would really help me to know the big-o complexity for this function.

  • $\begingroup$ There is LongestCommonSubsequence. AFAIK, the complexity is O(n^2) in general. Perhaps, in some cases, when certain additional information about sequences is available, there exist faster algorithms. $\endgroup$ – Leonid Shifrin Jan 22 '15 at 14:52
  • $\begingroup$ The function LongestIncreasingSubsequence (in Combinatorica) is defined for a permutation as argument. But since you inquire about the genome package, this function will not be applicable. $\endgroup$ – Wouter Jan 25 '15 at 13:24
  • $\begingroup$ Combinatorica can no longer be used $\endgroup$ – M.R. Jan 25 '15 at 19:36
  • $\begingroup$ Without breaking all Graph functionality and a few other things... $\endgroup$ – M.R. Jan 27 '15 at 1:54

Your Answer

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

Browse other questions tagged or ask your own question.