Difference between revisions of "K-MerCounting Assignment"

From CSE231 Wiki
Jump to: navigation, search
(KMerUtils)
(KMerUtils)
Line 30: Line 30:
 
long possibleKMers = 1L << bitsPerKMer;
 
long possibleKMers = 1L << bitsPerKMer;
 
return possibleKMers;
 
return possibleKMers;
 +
}</nowiki>
 +
 +
==int calculateSumOfAllKMers(List<byte[]> sequences, int kMerLength)==
 +
<nowiki>public static int calculateSumOfAllKMers(List<byte[]> sequences, int kMerLength) {
 +
int sum = 0;
 +
for (byte[] sequence : sequences) {
 +
int i = (sequence.length - kMerLength + 1);
 +
if( i > 0 ) {
 +
sum += i;
 +
}
 +
}
 +
return sum;
 
}</nowiki>
 
}</nowiki>
  

Revision as of 00:38, 3 December 2017

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.

KMerUtils

The following methods should be useful as you build the assignment.

Check out the Javadocs either on the web, or in the comments in KMerUtils.java for further details on how they work.

String toString(byte[] sequence, int offset, int kMerLength)

public static String toString(byte[] sequence, int offset, int kMerLength) {
	return new String(sequence, offset, kMerLength, StandardCharsets.UTF_8);
}

String toString(byte[] kMer)

public static String toString(byte[] kMer) {
	return new String(kMer, StandardCharsets.UTF_8);
}

long calculatePossibleKMers(int kMerLength)

public static long calculatePossibleKMers(int kMerLength) {
	int bitsPerBase = 2;
	int bitsPerKMer = kMerLength * bitsPerBase;
	long possibleKMers = 1L << bitsPerKMer;
	return possibleKMers;
}

int calculateSumOfAllKMers(List<byte[]> sequences, int kMerLength)

public static int calculateSumOfAllKMers(List<byte[]> sequences, int kMerLength) {
	int sum = 0;
	for (byte[] sequence : sequences) {
		int i = (sequence.length - kMerLength + 1);
		if( i > 0 ) {
			sum += i;
		}
	}
	return sum;
}

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.

Circle-information.svg Tip: Get ThresholdSlices working and then use it to balance all of your parallel KMerCounter implementations.

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.

Attention niels epting.svg Warning: be sure to slice the offset (a.k.a. startingIndex) space

for N=10 and K=3, you should be slicing like this:

ThresholdSlices.svg

LongConcurrentHashMapKMerCounter

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

IntArrayKMerCounter

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

AtomicIntegerArrayKMerCounter

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.

IsolatedBucketDictionaryKMerCounter

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.

IsolatedBucketDictionary

Attention niels epting.svg Warning: Do NOT call get() from compute(). It will result in a nonintuitive error. getEntry(bucket, key) gives you everything you need.
Circle-information.svg Tip: Be sure to make your IsolatedBucketDictionary thread-safe. If any code is going to access shared mutable data, it needs to do so in a thread-safe manner.

A simple example of how to use the many incantations of isolated:

@ThreadSafe
public class IsolatedInteger {
    private int value;

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

    public int getValue() {
        return isolatedWithReturn(objectBased(readMode(this)), () -> {
            return value;
        });
    }

    public void increment() {
        isolated(objectBased(this), () -> {
            value++;
        });
    }
}

Extra Credit

Open-ended K-mer Counter

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

wikipedia article on k-mers

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

Collection of approaches to k-mer counting

Burrows–Wheeler transform

Significance of k-mer Counting