Kevin - Jellyfish Notes
Basic Kmer Counting
- Naïve python way (See Figure 1)
○ Okay if you're in a microbial genome
○ Runs out of memory
§ ~60 bytes per entry
§ Every error creates a unique kmer and therefore a unique entry
- How to go faster
○ Want a faster language
○ Memory-mapped I/O
§ Move data as a disk block to memory
○ Process Kmers one character at a time to avoid building big strings
§ Look at sequences a kmer at a time
○ How to compress results (See Figure 2)
§ Strings are inefficient way to store kmers
§ Want to compress keys and values
□ We have lots of 1s and a few large numbers
§ We want a special purpose hash table
□ Make a numeric code for a Kmer
® w/ 4 letters you can encode it with 2 bits. But we have wildcards and N. You need 4 bits. What do we care about?
® Jellyfish only encodes for AGTC with 2 bits. We are ignoring then ambiguous or unknown sequences.
® Can restart sequences at N to avoid ambiguity problems
□ Shifts to minimize machine commands
□ We want spread out hash values
® Jellyfish limits array size to a power of 2
□ Invertible mapping - Can unscramble our scrambled and spread out key
® Allows you to discard part of the scrambled key since when you know where you are in the array you know where you are vis a vis M.
◊ In a 64 bit system. We can store the key in 33 bits. We have 32 bits left for other things.
□ We won't have perfect hashes (no collisions) since it is computationally expensive.
® Can use a new hash function when you have one
® Can increment by one to change hash -Linear probing
® Jellyfish uses quadratic probing 2, 8, etc
◊ Uses first open cell
◊ 90% = too full
} Can make a bigger table (not used here)
} Jellyfish dumps the table to disk and uses a new table. Means you need to eventually needs to merge the tables.
} We need to know the # of reprobes to figure out where it was in memory. To get the scrambled key and to reverse the process. Max # reprobes dictates how much space you need for this info. Max reprobes reached = dump to disk.
□ What do we do when the value exceeds our left over space?
® We can indicate in a field that there is over flow with 1111 -> 0000
◊ We look at key for value 1. If there is indicated over flow we keep looking till we find the end
○ We need to sync multi core CPUs to avoid collisions in data structure.
§ Lock structure would cause serialization bottleneck.
□ Wait in line model
§ Want something with no costs during no-collisions while handling collisions that happen
§ CPUs have CAS - Compare and Save
□ Address, old value, new value (a, x, y)
□ Look at address. If value at mem address is old value write new value. Returns old value.
® If x = y OK
® If x does not equal y Some sort of collision.
◊ If it’s a memory collision reprobe for mem
◊ If it’s a hash collision re hash
□ Only one can succeed. Supported by hardware.
§ Almost linear speed increase.
§ Need to sync input side too. Not sure how they do that.
□ Can interleave - straight through most efficient for I/O
□ Can start in widely spaced pages
○ Small kmers it uses direct addressing to speed things up