K Mer Counting Assignment
Background
The term k-mer refers to a substring of length k and k-mer counting refers to the process of finding the number of occurrences of a k-mer in a given string. This computational problem has many real-world applications, the most notable being in the field of computational genomics. In this assignment, you will design a program that will ultimately take in a human X-chromosome and count the number of k-mers in the string of DNA. You will be making use of everything you have learned thus far, including atomic variables. It is useful to know that given a string of length n, the amount of possible k-mers is equal to n - k + 1.
Breakdown
This assignment is broken into in-class studios, demos, and a take-home assignment. For this assignment, you will create a k-mer counting program using several different data structures. Links to the documentation for all of the java.util.concurrent data types can be found below.
ConcurrentHashMap and AtomicIntegerArray.
Warmups
The warm-ups associated with this assignment can be found under the kmer.warmup packages.
String HashMap Implementation
In this completely sequential implementation, you will have to write the parse method. The method takes in a list of arrays of bytes and a k-mer length. It should return a StringMapKmerCount (which takes in a map), a class provided to you which does exactly what its name suggests. In order to implement this method, we recommend taking a look at the KMerUtils class and more specifically the toString method, which converts a given byte array into a String in order to make it compatible with the String HashMap.
parse should go through the amount of possible k-mers for every byte array in the list of sequences. As it goes through the bytes in the array, use the KMerUtils.toString() method to create a string to use for the HashMap. The map should take in a String as the key and an Integer as the value. We recommend using the map.compute() method and reviewing how to use lambdas.
String ConcurrentHashMap Implementation
This implementation will make your sequential String HashMap implementation into a parallel one. To do so, you will be making use of Java’s atomic version of a HashMap: a ConcurrentHashMap. Like before, you will be need to complete the parse method. You can choose to finish this method with a forall loop or a finish/async approach, which is completely up to you.
ByteArrayOffset Implementation
This parallel implementation will overlap greatly with your previous two implementations, but it will use ByteArrayOffsetKMer instead of Strings. Refer to the ByteArrayOffsetKMer class in order to get a better idea of how to implement this method and instantiate an instance of the class. The class closely resembles the Slice class you worked on earlier in the semester.
Assignment
The assignment itself can be found under the kmer.assignment packages.
ThresholdSlices
This class is designed to take in a list of bytes and convert it into a list of slices. The slice class should be familiar to you from earlier in the semester, but feel free to refer back to the documentation on Slices for a quick recap. You should perform this task recursively and there are two methods you will need to implement. The createSlicesBelowThreshold method should call the addToCollectionKernel once, but the kernel should take over the recursion from there.
In the createSlicesBelowThreshold method, you should call the recursive kernel for each sequence in the list of sequences. When defining the min and max values, keep the information mentioned in the "Background" section in mind. As for the kernel, it should add a new slice to the collection of slices once the length of the slice dips below the provided threshold, but it should otherwise split itself into two smaller slices using recursion.
Hint: when defining the new slice, the sliceIndexId does not matter in this case.
Long ConcurrentHashMap Implementation
This parallel implementation will also overlap greatly with everything you have done previously, but instead of using Strings or SequenceSlice, we will be using Longs to represent DNA data. In order to do this, refer to the KMerUtils class, more specifically the toPackedLong method which will convert a sequence of bytes into a Long for our purposes. As the data that this implementation can take is much larger than the previous implementations, consider how to instantiate the ConcurrentHashMap in order to avoid dynamically resizing the map. KMerUtils has a method which will calculate this number for you, but think about which one to use, why you would use it, and how that would differ from simply calculating n - k + 1 yourself.
Hint: calculatePossibleKmers and calculateSumOfAllKmers are distinct and take different input parameters. calculateSumOfAllKmers performs the n - k + 1 calculation on a list of arrays of sequences and sums the total. calculatePossibleKmers only takes the length of the k-mer (k) as the input parameter, meaning it will calculate possibilities independent of the size of the sequence. Thus, the n - k + 1 calculation would yield a value ranging from 0 (inclusive) to the result of calculatePossibleKmers (exclusive).
Int Array Implementation
Like the String HashMap implementation, this implementation should be completed sequentially. However, unlike the previous implementations, we will be using an array instead of a map. This means that you must keep in mind what size to make the array in order to instantiate it. KMerUtils has a method which will calculate this number for you, but think about which one to use, why you would use it, and how that would differ from simply calculating n - k + 1 yourself. Think of using the int array as similar to using the map, but with ints as the key/value pairs. Use KMerUtils.toPackedInt() in order to convert the sequence into an int for our purposes.
Hint: calculatePossibleKmers and calculateSumOfAllKmers are distinct and take different input parameters. calculateSumOfAllKmers performs the n - k + 1 calculation on a list of arrays of sequences and sums the total. calculatePossibleKmers only takes the length of the k-mer (k) as the input parameter, meaning it will calculate possibilities independent of the size of the sequence. Thus, the n - k + 1 calculation would yield a value ranging from 0 (inclusive) to the result of calculatePossibleKmers (exclusive).
AtomicIntegerArray Implementation
This implementation is simply the parallel equivalent of the int array implementation. To do so, you will be making use of Java’s atomic version of an array: an AtomicIntegerArray. Like before, you will be need to complete the parse method. You can choose to finish this method with a forall loop or a finish/async approach, which is completely up to you.
IsolatedBucketDictionary Implementation
This parallel implementation will go a step beyond the previous implementations and divide entries into 1024 buckets. Although a different number of buckets can be used, we will simply stick to 1024. Every time an entry is added to the bucket dictionary, it will create a hash based on the entry's key and place the entry into one of the 1024 buckets. Because we would only need to search one bucket for an entry based on a key's hash, this mainly serves the purpose of cutting down on search time. The compute method of the IsolatedBucketDictionary should automatically compute the correct bucket for the entry, so this implementation should closely resemble the previous ConcurrentHashMap implementations. When instantiating the IsolatedBucketDictionary, we recommend making the key/value pairs a String and an Integer.
Open-ended K-mer Counter (AtomicReferenceArrayDictionary Implementation)
This implementation is extra credit and (as the name suggests) completely open-ended. Approach it however you wish!
Rubric
Total points: 100
- Correct ThresholdSlices (10)
- Correct Long ConcurrentHashMap (15)
- Correct Int Array (15)
- Correct AtomicIntegerArray (15)
- Correct BucketDictionaryCounter (15)
- Correct BucketDictionary implementation (20)
- Clarity and efficiency (10)
Research
paper: A fast, lock-free approach for efficient parallel counting of occurrences of k-mers (Jellyfish)
paper: Multiple comparative metagenomics using multiset k-mer counting
