2
$\begingroup$

What would be a good / efficient algorithm or approach to find all the largest sequences within a list of chains with varying lengths?

For instance these chains:

0: [4,5,2,1,3,6,8,9]
1: [2,1,3,4,5,6,7,8,10,11]
2: [15,12]

The longest common subsequence would be [2,1,3,6,8] but there is another important subsequence [4,5,6,8] that we would be needed to find.

All other sequences with 2 or more elements would be inside those two chains. For instance [1,3,6] or [5,6,8] or [2,1] are all inside the two resulting chains.

Note: the example uses integers for more clarity but the real data will use floats, and they will be taken as a "match" when both are separate within a given threshold.

Improve this question
$\endgroup$
2
  • $\begingroup$ Some progress on this question is reported at stats.stackexchange.com/questions/32531/…. $\endgroup$
    – whuber ♦
    Jun 5, 2014 at 19:12
  • $\begingroup$ NB: Although I pointed to a similar-looking question, there is a basic difference: in this one, a "subsequence" need not be contiguous. This becomes apparent in the examples: e.g., 4568 is not a contiguous subsequence of 4521368, but the digits 4568 do appear within the latter in that order (separated in the middle by the string 213). I do find it a little strange that subsequences would be referred to as "patterns," though. I guess I tend to think of a "pattern" as being some kind of coherent local feature. This (nonlocal) sense of pattern might not be amenable to statistical methods. $\endgroup$
    – whuber ♦
    Jun 5, 2014 at 20:36

1 Answer 1

Reset to default
1
$\begingroup$

This looks like the longest common subsequence problem, solvable with dynamic clustering. It is applied pairwise, to two sequences at a time. If you are interested in generalising this to more than two sequences you will likely need the two-sequence computation as an intermediate step.

See http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

On further reflection, it sounds as if the problem you want to solve is finding all maximal common subsequences between two sequences (i.e. all those that cannot be further extended). The page referenced above says this:

Indeed the LCS problem is often defined to be finding all common subsequences of a maximum length. This problem inherently has higher complexity, as the number of such subsequences is exponential in the worst case,[3] even for only two input strings.

It further lists this paper in the references: "A linear space algorithm for computing maximal common subsequences". Communications of the ACM 18 (6): 341–343. doi:10.1145/360825.360861.

I think that the approach that I sketched in the comments will work, and the depth-first search agrees with the possibility of an exponential number of sequences. More importantly, this problem has already been studied and solutions exist. Perhaps use this as the start of a web/literature search.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Already tried with the LCS although with LCS the result is only [2,1,3,6,8] while another important result is [4,5,6,8]. This second sequence is not detected by LCS. $\endgroup$
    – Davinish
    Jun 6, 2014 at 14:58
  • $\begingroup$ Ah yes, I wanted to comment on that but forgot. I think that by inspecting the alignment matrix (i.e. extending the regular backtracking algorithm) you should be able to find those other sequences as well. They show up as cells where the jump (cell value difference) is 2 or more rather than 1, and they should appear on the same row or column as the optimal jump (with difference 1), assuming you indicate a match by incrementing the cell value by 1. I may have missed something - it could be tricky if these suboptimal values are very close to the optimal values. $\endgroup$
    – micans
    Jun 6, 2014 at 15:54
  • $\begingroup$ Could you give an example of this approach? $\endgroup$
    – Davinish
    Jun 6, 2014 at 15:59
  • $\begingroup$ Highlight all cells that indicate equal values in both sequences. Any common subsequence is started from its rightmost element (a high-valued cell). At any point in a common subsequence, you only consider the matrix to the left and the top relative to the current cell. In this matrix you need to look for high-valued equality cells, not necessarily just the one that leads to the best scoring subsequence. In your example you would find e.g. 2 and 3 cell values where the 2 lies outside the matrix top-left to 3 and the 3 lies outside the matrix top-left to the 2. $\endgroup$
    – micans
    Jun 6, 2014 at 16:21
  • $\begingroup$ I think I get what you mean (correct me if I'm wrong). starting at sequence "0:", from right to left, we get: 8,6,3,1,2 (inverted [2,1,3,6,8]) and starting at sequence "1:" from right to left, we get: 8,6,5,4 (inverted [4,5,6,8]). $\endgroup$
    – Davinish
    Jun 6, 2014 at 17:29

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.