On 2009-9-9, at 22:42 , peter lo wrote:
As the code is very long and spans a number of files, maybe I only post a fragment of it. I will explain just a bit what I am doing. Basically given a number of input DNA sequences, I would like to find "similar" (in terms of edit distance) subsequences and rank them using a scoring scheme. The length of subsequences range from 5 to 20. Previously, for each subsequence length, I go through all the subsequences, find their similar occurrences, and rank them. But this is too slow, so I use a heuristic, which is to record the similar occurrences of each subsequence of length L, then using them to refine the search for subsequences of length L+1. This is the part that is causing trouble. As the total length of input sequences increase and L increase, the number of unique subsequences increase very rapidly, and since each of them keeps a list of occurrences, the amount of live objects when going from length L to length L+1 can get very large.
If your string lengths do not exceed 20 and your alphabet has 4 characters, you could mangle every chain into a single integer in the range 0...2^40 or so. These values fit easily in a 64 bit integer, and distance can be calculated by xoring 2 numbers (well, only if the weights are the same).
For instance assuming letters {0 1 2 3}, the sequence "01320" maps to {10 13 20} = 0x478 if you use a stop bit as Marc remarked. Or it could be {00 13 20 05} = 0x785 if you use a length byte a la Pascal strings.
Moreover, you could pre-calculate a NxN edit distance. A 1 meg table would handle 4x4, 5x5 needs 16 megs.