3
\$\begingroup\$

Write a program that can calculate the Hamming difference between two DNA strands.

GAGCCTACTAACGGGAT CATCGTAATGACGGCCT ^ ^ ^ ^ ^ ^^

The Hamming distance between these two DNA strands is 7.


import java.util.Optional;


public class Hamming {
  public static int compute(String s1, String s2) {
    validateInputs(s1, s2);

    int hammingDistance = 0;
    int stringLength = s1.length();

    for (int i = 0; i < stringLength; i++) {
      if (s1.charAt(i) != s2.charAt(i)) {
        hammingDistance++;
      }
    }
    return hammingDistance;
  }

  private static void validateInputs(String s1, String s2) {
    if (s1.length() != s2.length()) {
      throw new IllegalArgumentException();
    }
  }
}

Test suite:

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.Test;

public class HammingTest {

    @Test
    public void testNoDifferenceBetweenIdenticalStrands() {
        assertThat(Hamming.compute("A", "A"), is(0));
    }

    @Test
    public void testCompleteHammingDistanceOfForSingleNucleotideStrand() {
        assertThat(Hamming.compute("A", "G"), is(1));
    }

    @Test
    public void testCompleteHammingDistanceForSmallStrand() {
        assertThat(Hamming.compute("AG", "CT"), is(2)); 
    }

    @Test
    public void testSmallHammingDistance() {
        assertThat(Hamming.compute("AT", "CT"), is(1));
    }

    @Test
    public void testSmallHammingDistanceInLongerStrand() {
        assertThat(Hamming.compute("GGACG", "GGTCG"), is(1));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testValidatesFirstStrandNotLonger() {
        Hamming.compute("AAAG", "AAA");
    }

    @Test(expected = IllegalArgumentException.class)
    public void testValidatesOtherStrandNotLonger() {
        Hamming.compute("AAA", "AAAG");
    }

    @Test
    public void testLargeHammingDistance() {
        assertThat(Hamming.compute("GATACA", "GCATAA"), is(4));
    }

    @Test
    public void testHammingDistanceInVeryLongStrand() {
        assertThat(Hamming.compute("GGACGGATTCTG", "AGGACGGATTCT"), is(9));
    }

}

Questions:

  1. Am I using the correct data structures?
  2. Can I improve performance? Right now it seems to be \$Θ(n)\$ since it has to check all the characters in the string.
\$\endgroup\$
  • \$\begingroup\$ Can you link to some information in regards to hammering DNA difference? \$\endgroup\$ – THE AMAZING May 2 '16 at 15:41
  • 1
    \$\begingroup\$ @Richard_Grant, naming is something that can be addressed in your review of the code. do not edit the code to change the code. \$\endgroup\$ – Malachi May 2 '16 at 16:18
3
\$\begingroup\$

Your code is really all that there is to it. It is clear and concise: one method to validate the input (validateInputs) and the rest of the method to calculate the Hamming distance with a simple loop.

A couple of comments:

  • In case of inputs of different length, you are (rightfully) throwing a IllegalArgumentException like this:

    if (s1.length() != s2.length()) {
      throw new IllegalArgumentException();
    }
    

    This is a generic IllegalArgumentException with no message. You might want to add a message so that it is clearer to the caller what went wrong; it would also help the debugging (imagine a bigger application).

  • To resemble what is done by the existing Objects class, you could rename your validating method to requireSameLength and make it return the length:

    private static int requireSameLength(String s1, String s2) {
        if (s1.length() != s2.length()) {
            throw new IllegalArgumentException();
        }
        return s1.length();
    }
    

    This has the advantage that the method name is now self-documenting and it is returning the correct value, which means we can chain the result (just like requireNonNull which returns the non-null value or throws an exception).

  • import java.util.Optional; is not needed, you aren't using it.

  • Consider making the class final since it looks like a utility class (only public static methods).

If you're using Java 8, you could write this a bit shorter using the Stream API:

public static int compute(String s1, String s2) {
    int length = requireSameLength(s1, s2);
    return IntStream.range(0, length).map(i -> s1.charAt(i) == s2.charAt(i) ? 0 : 1).sum();
}

private static int requireSameLength(String s1, String s2) {
    if (s1.length() != s2.length()) {
        throw new IllegalArgumentException();
    }
    return s1.length();
}

It maps each index to 0 or 1 based on whether the two input Strings have equal characters at that index, and sums the result.

\$\endgroup\$
  • \$\begingroup\$ Adding message to the exception is the good idea, but I am not in favor of having a method with side effects, requireSameLength does two things and its not good, for now validateInputs is simple and short and does one thing very well. \$\endgroup\$ – CodeYogi May 3 '16 at 3:45
  • \$\begingroup\$ @CodeYogi Yes, you could see it that way. (This was more of an idea based on some existing classes, as FYI; your initial code is already very good :) ). \$\endgroup\$ – Tunaki May 3 '16 at 7:29
1
\$\begingroup\$

By the structural design of your code i believe you should return a short integer from your void methods in the hammingtest Object.

Also, you can speed up your application by not using int, which is a 32 bit signed long. If this was written in a C language i would suggest using an unsigned short integer; however, Java does not have unsigned short integers so short int would need to suffice.

if you are really concerned about speed consider changing this block of code:

int stringLength = s1.length();

    for (int i = 0; i < stringLength; i++) {
      if (s1.charAt(i) != s2.charAt(i)) {
        hammingDistance++;
      }
    }
    return hammingDistance;
  }

Whats wrong with this code is that you are assigning an unnecessary value in memory that is practically used as a constant to avoid for loop condition from evaluating s1.length() on each increment.

you should change this to: (untested, but you get the idea)

for (short int i = s1.length() - 1; i >= 0; i--) {
    if (s1.charAt(i) != s2.charAt(i)) {
        hammingDistance++;
    }
}
return s1.length() - hammingDistance;

I would re-write your hamming as:

import java.util.Optional;


public class Hamming {
    public static int compute(String s1, String s2) {
        if(validateInputs(s1, s2)){
            int hammingDistance = 0;
            int stringLength = s1.length();

            for (short int i = s1.length() - 1; i >= 0; i--) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    hammingDistance++;
                }
            }
            return s1.length() - hammingDistance;
        }
        return -1;//assume hamming can not be negative
    }

    private static boolean validateInputs(String s1, String s2) {
        return (s1.length() == s2.length());
    }
}
\$\endgroup\$
-1
\$\begingroup\$

As a good practice, I would suggest to work with interface and object instead of static class (then, any refactoring must not break this interface). Here something like :

public interface HammingDifference {
    int compute();
    boolean validate();
}

Then your implementation will be restricted to this contract. And you can have a constructor based on the implementation specifics, eg:

StringHammerDifference(String a, String b)
ArrayHammerDifference(character[] a, character[] b)
// or even custom objects
DnaSequenceHammerDifference(DnaSequence a, DnaSequence b)

If you are really concerned about speed - and when you talk about speed, I hope you mean long DNA sequence comparision (??) - I would strongly suggest to work on the DnaSequence representation. For example:

  • An array of small chunks with a corresponding checksum (then you compare only when checksums are different)
  • A tree (I don't know if there are Hamming focused trees, but my guess is there are)

I think that tweaking from big to short integers may not be sufficient enough.


My final thought will be: there are, I guess, a lot of documentation and even libraries out there, so looking at them may be a good thing ;-)

\$\endgroup\$
  • \$\begingroup\$ there is a tremendous difference between short integers and long integers, especially on the assembly side. changing the data types to the correctly intended datatype could substantially improve the compiled code. \$\endgroup\$ – THE AMAZING May 2 '16 at 16:32
  • 1
    \$\begingroup\$ a checksum for partial chunks of a dna structure is not reliable nor a fast approach. I strongly suggest removing this approach. You need to look at how check sums actually work. \$\endgroup\$ – THE AMAZING May 2 '16 at 16:36
  • \$\begingroup\$ I'm not saying this is the way to do it, I just meant to say that speed might be increased by data structure (and imagining data structures for such cases... but only imagining). If you want to increase space used by your data, why not use booleans? A DNA Sequence with 2 letters is 16 possibilities, which is actually only 4 booleans or an hexadecimal number. \$\endgroup\$ – GournaySylvain May 3 '16 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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