Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

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 the 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|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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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