Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

A DNA molecule can be represented as a string of symbols $A, C, G$ and $T$, such as $GGATAATTCTAG\ldots GACCGTACCC$.

For the purposes of this question, we will assume that all DNA molecules contain the same (large!) number $N$ of symbols. Thus, a DNA molecule is an $N$-tuple $x = (x_1,\ldots , x_N)$ where $x_i\in\{A,C,G,T\}$ for each $i$.

Define the distance between two DNA molecules $x, y$ as the number of elements $i$ in ${1, \ldots ,N}$ such that $x_i\neq y_i$.

Prove that this defines a metric on the set of DNA molecules.

Tutor defined a set $S(x,y)=\{1,3,6\}$. Why is this? The rest of the working after that is fine.

share|cite|improve this question

marked as duplicate by Martin Sleziak, Silvia Ghinassi, Ross Millikan geometry Jan 21 at 17:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

When editing the question the linebreaks implied that this is somehow copy-pasted from somewhere else. This feels more so as $S(x,y)$ is not defined in the question given here. – Asaf Karagila Oct 28 '11 at 13:04
See Hamming distance. – Did Oct 28 '11 at 13:18

Hint: for a problem like this, where you are asked to show that some object (this measure of distance) belongs to some class (metrics) you are asked to verify the definition of the class. I found them very useful to check my understanding of a definition. So just go down the requirements for a metric and see if it works. Clearly the distance between two strings is $\ge 0$, is only $0$ when the strings are identical, and is symmetric. The only one that takes a bit of work is the triangle inequality.

share|cite|improve this answer
thank you for your reply, my main problem is that I can't define the metric in the first place. Do you have any suggestions? – LM_ Nov 1 '11 at 19:05
@LM_: The metric is the number of positions where two strings disagree. That is your third paragraph. A metric is a way of thinking about the distance between two points in a space. That is where the requirements come from: distances are positive, greater than zero if you have to move at all, and going from a to b directly should be no longer than going via c. – Ross Millikan Nov 1 '11 at 19:40
okay, but why is S(x,y)={1,3,6} ? – LM_ Nov 4 '11 at 16:44
Presumably that was the list of positions where they disagree. Then the distance would be the size of $S$, which is $3$. Does that work? – Ross Millikan Nov 4 '11 at 16:46

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