# [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
strings.

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

```