Finding the most common DNA patterns of some given length

Question

I'm working on an algorithm to search through 100,000+ lines of dna sequencing, with the fastest time possible. Here is my current code, I was wondering if there's any ways to make this run faster:

public static void mostCommonKmer(String s, int k) {
    // your code here
    HashMap<String, Integer> m = new HashMap<>();
    int l = 0, g;
    String n = "", ss;
    for (int i = 0; i < s.length() - k; i++) {
        ss = s.substring(i, i+k);
        g = m.getOrDefault(ss, 1);
        m.put(ss, g + 1);
        if (l < g) {
            l = g;
            n = ss;
        }
    }
    System.out.println("Most Frequent " + k + "-mer = " + n);
    System.out.println("frequency = " + l);
}

• s is the 100,000+ character string passed to the method and k is the length of pattern to look for

To be clear, it runs fast (0.08s for 100,000 chars), but I want to see how fast I can get it to go.

Answer 1

First, just for correctness..

a.- What if your input is s = "AGG" and k = 3?

Your program will not find any pattern.

b.- If your default value on getOrDefault is 1, then your logic should be consistent with this. (Now if you have one match, the result will be 1 [getOrDefault(ss, 1)] plus one [put(g+1)] ie, 2 and this is not correct.

Fixing that you will have:

public static void mostCommonKmer(String s, int k) {
    HashMap<String, Integer> m = new HashMap<>();
    int l = 0, g;
    String n = "", ss;

    for (int i = 0; i < s.length() - k + 1; i++) {
        ss = s.substring(i, i+k );
        g = m.getOrDefault(ss, 0);
        m.put(ss, g + 1);
        if (l < g + 1) {
            l = g + 1;
            n = ss;
        }
    }
    System.out.println("Most Frequent " + k + "-mer = " + n);
    System.out.println("frequency = " + l);
} 

---

Now, in order to make your code more readable you can try to use more meaningful names, like:

public static void mostCommonKmer(String dnaString, int kLength) {
    HashMap<String, Integer> frequencyMap = new HashMap<>();
    int maxFrequency = 0;
    String mostCommonPattern = "";

    int currentFrequency;
    String subDNAString;

    for (int i = 0; i < dnaString.length() - kLength + 1; i++) {
        subDNAString = dnaString.substring(i, i + kLength);
        currentFrequency = frequencyMap.getOrDefault(subDNAString, 0);
        frequencyMap.put(subDNAString, currentFrequency + 1);

        if (maxFrequency < currentFrequency + 1) {
            maxFrequency = currentFrequency + 1;
            mostCommonPattern = subDNAString;
        }
    }
    System.out.println("Most Frequent " + kLength + "-mer = " + mostCommonPattern);
    System.out.println("frequency = " + maxFrequency);
}

---

Now for make your program faster, this will be more a theorethical discussion than something that actually will improve the performance*. One approach is to think in less operations, (but this is not always true, if you replace 2 operations with one more 'expensive' for example).

Avoid HashMap resizing, even when it is an amortized operation can 'use some time', so in order to achieve that you can init your hashmap with a certain size.

Avoid boxing/unboxing; if you use int and Integer you should convert elements from one type to another, because you cannot use HashMaps with primitive values you can use Integer instead of int to avoid box/unboxing.

For cycle; remove any kind of dynamic evaluation (ie; length() )

Reduce any extra operation that you can (in the last code the + 1 operations)

So, you can have something like:

private static final int DNA_LETTERS = 4;

public static void mostCommonKmer(String dnaString, int kLength) {
    int possibleCombinations = (int)Math.pow(DNA_LETTERS, kLength);

    HashMap<String, Integer> frequencyMap = new HashMap<>(possibleCombinations);
    Integer maxFrequency = 0;
    String mostCommonPattern = "";

    Integer currentFrequency;
    String subDNAString;

    int searchLimit = dnaString.length() - kLength + 1;
    for (int i = 0; i < searchLimit ; i++) {
        subDNAString = dnaString.substring(i, i + kLength);
        currentFrequency = frequencyMap.getOrDefault(subDNAString, 0) + 1;
        frequencyMap.put(subDNAString, currentFrequency);

        if (maxFrequency < currentFrequency) {
            maxFrequency = currentFrequency;
            mostCommonPattern = subDNAString;
        }
    }
    System.out.println("Most Frequent " + kLength + "-mer = " + mostCommonPattern);
    System.out.println("frequency = " + maxFrequency);
}

I think that a good point was to declare the temporary variables (g and ss or currentFrequency and subDNAString) outside the for loop avoiding all those reallocations in memory (but I don't know if the compiler would make some optimizations about that).

*Now, why I say that this is more a theoretical discussion? If you test the last version of the code, you will see that takes more time that the original version of the code. And maybe someone else can give us some clues about that!

Answer 2

You can optimize a bit by pre-calculating s.length() - k

for (int i = 0, max = s.length() - k; i < max; i++) {
    ...
}

Furthermore, you can cut a bit of execution time by replacing the auto boxing and unboxing you do by using a mutable value class, something like this:

private static class MutableInt {
    public int value;

    public MutableInt(int value) {
        this.value = value;
    }
}

public static void mostCommonKmer3(String s, int k) {
    HashMap<String, MutableInt> m = new HashMap<>();
    int l = 0;
    MutableInt g;
    String n = "", ss;
    for (int i = 0, max = s.length() - k; i < max; i++) {
        ss = s.substring(i, i+k);

        // note: computeIfAbsent over getOrDefault in this case, so that
        // creation will only take place when necessary
        g = m.computeIfAbsent(ss, key -> new MutableInt(1));
        g.value++;
        if (l < g.value) {
            l = g.value;
            n = ss;
        }
    }
    //System.out.println("Most Frequent " + k + "-mer = " + n);
    //System.out.println("frequency = " + l);
}

Raw execution time for 1000 repetitions (with proper ramp-up) using 100000 chars and k = 150 went from 3308 ms for the original code to 3190 using both changes on my machine.

And as you are on codereview, one additional remark: longer variable names (longest, subsequence, n?) do not hurt execution time, but have the potential to make the code more readable.... ;-)