Re^3: Hamming Distance Between 2 Strings

There are several problem with that.

Unless you were comparing each sequence against many others, the cost of encoding the sequences is going to exact a high price.
Packing 4 chars per byte is a nice way of doing 1/4 of the work at the xor stage, if you can amortise the conversion. But DNA sequences often contain other characters, N and X for example, and I'm sure I've seen others. I'm not sure what they mean, but I've seen them.
Once you are down to packing two, 3-bit or 4-bit values per byte, the cost of the encoding gets harder to claw back.
And when you've done the xor, you have to count the results. With the string version, where the null byte means the characters were the same, and anything else, different, the "count the stars" mode of tr/// is an efficient way of achieving this.
With the bit-encode sequences, you would have to count the zero and non-zero-ness of pairs, or triples or quads of bits. For 2 and 4 bits, this could be done using vec, but not very efficiently. Doing it for triples would be very laborious.

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.

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

Replies are listed 'Best First'.
Re^4: Hamming Distance Between 2 Strings - Fast(est) Way? by b_hall (Scribe) on Oct 14, 2005 at 22:18 UTC
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.	[reply]
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]


Welcome to the Monastery
	PerlMonks

Re^3: Hamming Distance Between 2 Strings - Fast(est) Way?