Calculate the Hamming difference between two DNA strands

Question

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.

Answer 1

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.

Answer 2

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());
    }
}

Answer 3

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 ;-)