Take the 2-minute tour ×

I have a set of sequences (e.g. 10000 sequences), and generate a matrix (10000x10000) representing the pairwise similarity between every two sequences.

Now the goal is to retrieve a subset (for example 1000 sequences) from the large set and make sure the pairwise similarity between every two sequences in this subset is among a range (e.g. 50%~85%).

Is there any fast algorithm to do that?

share|improve this question
sounds like clustering to me –  Karoly Horvath Jul 19 '11 at 21:18
Why do you need to represent the data in a matrix? What kinds of operations are you using to extract the subset? Can you construct the subset and calculate the pairwise similarities in a single pass? –  Daniel Pryden Jul 19 '11 at 21:19
Do you want to do clustering? –  starblue Jul 19 '11 at 21:41
Can you calculate/assign values for each sequence, then view/envision/organize the sequences as a normal distribution/bell curve? If so, then all sequences within x standard deviations from the mean would be within a certain range y% of similarity. –  Jonathan M Jul 19 '11 at 22:07

4 Answers 4

up vote 2 down vote accepted

You can transform this to the graph theory problem:

  1. Each sequence is a node
  2. If similarity of two nodes is in given range than there is an edge between them
  3. Your goal is to find the larges connected component(if your similarity relation is transitive...) or the larges clique(...if not).
share|improve this answer
similarity is almost certainly not transitive, so you have to look for cliques. nice answer! –  Karoly Horvath Jul 19 '11 at 22:12
Isn't finding cliques in a graph NP-Hard? Some approximation algorithm would probably do the trick though. –  kyun Jul 19 '11 at 22:18

You could generate a sorted list of pairwise similarities (referring back to your matrix), take the subset of that sorted list, then assure that the intersection between that sublist and your subset is of the same size as your subset, thereby verifying that all the elements in your subset are in the specified range.

Requires a lot of setup to generate the matrix and a lot of space to create the ordered list, though. At the very least, your matrix setup is O(n^2).

share|improve this answer

This sounds like "clique finding" to me; the clique decision problem is NP-complete.

Depending on the statistics behind the similarities of your sequences, you may be satisfied with an approximation algorithm for the max clique problem. A randomized algorithm might even be good enough for you. But in general this is a very tough problem and it's unlikely you'll be able to do much even for N = 100.

share|improve this answer

A lot of similarities are equivalent to, or related to, a dot product in an n-dimensional space, even when the similarity is not explicitly calculated as such. In these cases, and possibly others, it is likely that high values of a.b and b.c imply high values of a.c, but the bound for this isn't very good - not as good as I thought it was at first.

With only three vectors involved - a, b, and c I think that you can draw a 3-dimensional diagram regardless of the dimensionality of the underlying space, and I think the worst case is where all three vectors are in a plane, with a above b and c below b. In that case, e.g. for all being unit vectors and a.b = b.c = 0.9, a is about 25 degrees above b and c is about 25 degrees below it, and a.c = 0.62. In fact for a.c = b.c = x in this case, a.c = 2x^2 - 1.

In these circumstances, if I absolutely had to solve this particular problem, I would try backtracking searches to enumerate sets of nodes very close to a particular node. You could, for instance, start off with the two most similar nodes, and then run a search that, at each level, added the node not yet tried that was closest to one of the original seed nodes. Or you could build a single link clustering and check out all of its subtrees of the required size.

share|improve this answer

Your Answer


