# How to compute the longest non-contiguous common sequence?

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.

• 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. – Leonid Shifrin Jan 22 '15 at 14:52
• 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. – Wouter Jan 25 '15 at 13:24
• Combinatorica can no longer be used – M.R. Jan 25 '15 at 19:36
• Without breaking all Graph functionality and a few other things... – M.R. Jan 27 '15 at 1:54