[gambit-list] Re: Re: Regarding garbage collection

Stéphane Le Cornec coleste at videotron.ca
Sat Sep 12 21:50:17 EDT 2009

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  

Moreover, you could pre-calculate a NxN edit distance. A 1 meg table  
would handle 4x4, 5x5 needs 16 megs.

More information about the Gambit-list mailing list