Re^4: Hamming Distance Between 2 Strings

I don't think that this would be a suitable solution for every problem of this type, but I think how useful it is will depend on the precise problem being addressed. This is not my field, but here are some thoughts on your reply.

One situation where you would want to compare multiple long strings would be if you have a set of sequenced functional mutants which you needed to compare to the wildtype, and to one another to see if you can cluster them and obtain insight into function. If there were enough mutants, this may promote the vec method. If you are looking at non standard bases (perhaps from damage or being from an unusual archaea) this solution might not be suitable, but my understanding was that usually non standard bases replace the common ones, not add to the list so you would still keep the total to four (one example that comes to mind is in RNA U, uracil, replaces T, thymine). Unusual bases would also only appear in a fraction of problems, so it might well not be a problem here.

What I don't know is how large the problem set would have to be to offset the encoding time. If somebody knows how to find that, that would help determine if the solution is appropriate for a given problem. Unfortunately I don't.

Comment on Re^4: Hamming Distance Between 2 Strings - Fast(est) Way?

Replies are listed 'Best First'.
Re^5: Hamming Distance Between 2 Strings - Fast(est) Way? by BrowserUk (Patriarch) on Oct 14, 2005 at 22:58 UTC
This is not my field, but ... `\ \| / <<< <<< <<< <<< <<< -- O -- / \| \ """""\ """===(° "(O)" \ \u =¯ \| \__)` [download] That was your whole second paragraph going right over my head. T'ain't mine ivver! :) However, you're right that the bio guys do this sort of fuzzy comparison a lot--a lot a lot. And they frequently exhaustively cross compare huge volumes of very large strings. I was involved in a whole other thread here aimed at finding the fastest way to do exactly that in Perl. So, encoding 4 RAs per char and saving 75% memory and 75% of comparison time would be a huge saver--if you can get the encoding data/decoding results costs down. Maybe using C, but vec is just too slow, as you have to access every 2-(3-,4-)bit offset individually at the perl level. Maybe a XS/C/asm module that takes a list of numbers and a bit size and returns a fully encoded string. However, there is still another problem that I hadn't thought about before. This works ok for two equal length strings, but more often than not, the task is to compare relatively short fragments against huge sequences to try and locate (likely) positions at which the fragment matches. In that scenario, the shorter fragment has to be tried at all offsets against the longer. That means you would need to encode each fragment 4 times, and use them cyclically against the sequence in order to test all positions. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.	[reply] [d/l]

Replies are listed 'Best First'.

Re^5: Hamming Distance Between 2 Strings - Fast(est) Way?
by BrowserUk (Patriarch) on Oct 14, 2005 at 22:58 UTC

This is not my field, but ...

                                    \ | /
   <<<    <<<    <<<    <<<    <<< -- O --
                                    / | \
  """""\ 
 """===(° 
"(O)"    \
 \u     =¯
  |  \__)
[download]

That was your whole second paragraph going right over my head. T'ain't mine ivver! :)

However, you're right that the bio guys do this sort of fuzzy comparison a lot--a lot a lot. And they frequently exhaustively cross compare huge volumes of very large strings. I was involved in a whole other thread here aimed at finding the fastest way to do exactly that in Perl.

So, encoding 4 RAs per char and saving 75% memory and 75% of comparison time would be a huge saver--if you can get the encoding data/decoding results costs down.

Maybe using C, but vec is just too slow, as you have to access every 2-(3-,4-)bit offset individually at the perl level. Maybe a XS/C/asm module that takes a list of numbers and a bit size and returns a fully encoded string.

However, there is still another problem that I hadn't thought about before. This works ok for two equal length strings, but more often than not, the task is to compare relatively short fragments against huge sequences to try and locate (likely) positions at which the fragment matches. In that scenario, the shorter fragment has to be tried at all offsets against the longer. That means you would need to encode each fragment 4 times, and use them cyclically against the sequence in order to test all positions.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.

[reply]
[d/l]