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

David Rush kumoyuki at gmail.com
Thu Sep 10 01:22:44 EDT 2009

2009/9/10 peter lo <peter19852001 at yahoo.com.hk>:
> 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.

Oh wow. I did something very much like this many years ago when I
first started using Scheme. I was working on a string-based nearest
neighbor search using a variety of tree structures where my similarity
metric was based on levenshtein edit distance (among others). The big
problem is simply that the algorithms just don't scale very nicely, in
either time or space - it's a great field for original research. I
ended up needing to break the problem into several parts, writing out
intermediate files with resulting data structures.

Do you have Dan Gusfield's _Algorithms on Strings, Trees and
Sequences_? As far as I'm concerned it's the  definitive work in the
field so far. Dan actually wrote most of it concerning the field of
DNA sequencing as well, so many of his examples may also be relevant.
Some of the key algorithms I needed to use tend to be a bit fiddly
about their implementation: e.g. when implementing a suffix tree, you
can blow the algorithm up from being linear to n^2 just by choosing a
bad data representation.

Sorry I am not being of more direct help, but you're right - if the
code you have is anything like mine was the amount you can post online
won't tell us very much. You are simply doing something that is hard.
Good luck with it :)

GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt

More information about the Gambit-list mailing list