2
$\begingroup$

If I represent DNA as binary values, what is the best way of computing distance between them.

So : A = 00, T = 11, G = 01 and C = 10

Hamming Distance between ATGC and TAAC is 3, however their binary representations give a different answer:

Hamming Distance of 00110110 and 11000010 = 5.

Whats the best way of distance computation if the DNA bases are represented in this way?

$\endgroup$

closed as off-topic by Remi.b, AliceD, rg255, kmm, March Ho Apr 4 '16 at 3:07

  • This question does not appear to be about biology within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ It is a question of theoretical computer science, not biology. I am voting to close. You should give it a try on cstheory.SE. $\endgroup$ – Remi.b Mar 31 '16 at 18:57
  • 3
    $\begingroup$ Agree with @Remi.b. But before you leave us, "Why would you want to do that?" as IT Support used to say. $\endgroup$ – David Mar 31 '16 at 22:47
  • $\begingroup$ Ask this question on StackOverflow not cstheory $\endgroup$ – Maljam Apr 1 '16 at 0:23
  • $\begingroup$ I found a solution, I'll answer it when you ask it again on StackOverflow $\endgroup$ – Maljam Apr 1 '16 at 0:34
  • $\begingroup$ This is a relevant question for biology.se, I think. "what is the best way of computing ..." phrase in the question is misleading, however. The question is not about how to perform a computation, but rather how to represent some biological entity formally, in a biologically meaningful way. This is a question about theoretical biology, not about cs. $\endgroup$ – Macond Apr 1 '16 at 7:16
2
$\begingroup$

The best way is to choose a distance that represents what you want it to rather than necessarily relying on the Hamming distance.

If you simply want base-by-base difference then calculate that (this may help) but you may also want a difference that depends on the likelyhood of mutating between different bases in which case you want to define a function that translates the mutation into a score for each transfer, i.e. you might want to score a deamination from 5-methylcytosine to thymine as the most likely occurrence. Expressing the relative likelyhoods of different mutations is not an easy problem but there are a number of widely used options.

The important thing is to ensure you represent the underlying biology not ensure that you have the fastest implementation. Decide on this first, then on the algorithm that gives you the best speed (also, deciding on that algorithm is on-topic for Stack Overflow not this Stack Exchange).

$\endgroup$
0
$\begingroup$

This encoding doesn't make sense as nucleotides are not in the Hamming space. Hamming distance between every two nucleotides is constantly 1, but in binary encoding, it varies from 1 to 2.

$\endgroup$
0
$\begingroup$

I am reluctant to answer with code, but it seems that the community decided that was an appropriate question for Biology.SE. So here is my solution.

The idea is to "compress" the two bit that represent each nucleotide, such that each nucleotide will contribute 0 or 1 (not more) to the distance.

You could use binary operations to do something like this (in Java, but you can apply the logic in any language):

int seq1 = 54, seq2 = 194;//ATGC and TAAC
int evenBit = 0xAAAAAAAA, oddBit = 0x55555555;

int pseudoDist = seq1 ^ seq2; //Integer.bitCount(pseudoDist) is 5
int dist = ( (pseudoDist&evenBit)>>1 ) | (pseudoDist&oddBit);
int finalDist = Integer.bitCount(dist);//output 3 not five

The idea is to get the total number of bits that are different with:

seq1 ^ seq2

But you can't just count the bits yet, because you will get the hamming distance instead, so you have to compress all the bits that correspond to the same nucleotide to the same bit using: (pseudoDist&0xAAAAAAAA>>1) and pseudoDist&0x55555555. The first one keeps the bits on even positions and the second the ones on odd positions.

Now you use evenBits | oddBits, and you can count the bits.

$\endgroup$
  • $\begingroup$ The original question conflates mathematical operations with the edit distance between two strings. A hamming distance is a measure of the number of changes you have to make to convert one string into another string. Converting the the alphabet into binary digits and then adding or subtracting the numbers is not going to tell you how many edits were required. $\endgroup$ – mdperry Apr 5 '16 at 1:09
  • $\begingroup$ @mdperry The fact that you don't understand it, does not invalidate it... You say it's impossible, but have you looked at my answer, have you tested it? Look it says that the hamming distance between ATGC and TAAC is 3, which is the right answer. $\endgroup$ – Maljam Apr 5 '16 at 1:50
  • $\begingroup$ If your approach and solution is correct then it should be straightforward to apply your code to the examples on this page: en.m.wikipedia.org/wiki/Hamming_distance. $\endgroup$ – mdperry Apr 5 '16 at 2:09
  • $\begingroup$ @mdperry this is not meant for any string, the fact that there are only four states possible allows you simplify it into 3 lines of code, that works for this particular problem $\endgroup$ – Maljam Apr 5 '16 at 2:11
  • $\begingroup$ Actually, I now agree with you: my comment is incorrect, my apologies. $\endgroup$ – mdperry Apr 5 '16 at 2:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.