WikiSysop at 09:33, 17 June 2024

2024-06-17T09:33:15Z

← Older revision		Revision as of 11:33, 17 June 2024
Line 1:		Line 1:
	{\| width=500 style="float:right; margin-left: 10px; margin-top: -56px;"		{\| width=500 style="float:right; margin-left: 10px; margin-top: -56px;"
	\|Previous: [[~~MapReduce and~~ Binary representation]]		\|Previous: [[Binary representation]]
	\|Next: [[Exercises and Organization]]		\|Next: [[Exercises and Organization]]
	\|}		\|}
Line 8:		Line 8:
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=df2d4e4c-5e16-4671-bba0-af170070db98 Count-min Sketch, a probabilistic counter]<br>		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=df2d4e4c-5e16-4671-bba0-af170070db98 Count-min Sketch, a probabilistic counter]<br>
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=dac4011c-dec5-4c3f-8b8c-af170070b46d MinHash, a probabilistic set similarity score]<br>		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=dac4011c-dec5-4c3f-8b8c-af170070b46d MinHash, a probabilistic set similarity score]<br>
	Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/~~HPCLife09~~-Hashes.ppt The use of hash]<br>		Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/22112_12-Hashes.ppt The use of hash]<br>
	Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=e6c44ada-9074-4821-bb91-af1700708f13 Exercises]		Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=e6c44ada-9074-4821-bb91-af1700708f13 Exercises]

WikiSysop: Created page with "{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;" |Previous: MapReduce and Binary representation |Next: Exercises and Organization |} == Material for the lesson == Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f253830c-9a70-4aaa-b61e-af170071451a Hashes, properties and use]
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=52b59412-1df9-4e2b-b8de-af1700710cab Bloom filter, a probabilistic set]
Video: [https:/..."

2024-03-06T10:57:50Z

Created page with "{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;" |Previous: MapReduce and Binary representation |Next: Exercises and Organization |} == Material for the lesson == Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f253830c-9a70-4aaa-b61e-af170071451a Hashes, properties and use] Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=52b59412-1df9-4e2b-b8de-af1700710cab Bloom filter, a probabilistic set] Video: [https:/..."

New page

{| width=500 style="float:right; margin-left: 10px; margin-top: -56px;"
|Previous: [[MapReduce and Binary representation]]
|Next: [[Exercises and Organization]]
|}
== Material for the lesson ==
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=f253830c-9a70-4aaa-b61e-af170071451a Hashes, properties and use] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=52b59412-1df9-4e2b-b8de-af1700710cab Bloom filter, a probabilistic set] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=df2d4e4c-5e16-4671-bba0-af170070db98 Count-min Sketch, a probabilistic counter] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=dac4011c-dec5-4c3f-8b8c-af170070b46d MinHash, a probabilistic set similarity score] 
Powerpoint: [https://teaching.healthtech.dtu.dk/material/22112/HPCLife09-Hashes.ppt The use of hash] 
Video: [https://panopto.dtu.dk/Panopto/Pages/Viewer.aspx?id=e6c44ada-9074-4821-bb91-af1700708f13 Exercises]

== Exercises ==
'''Determine if unknown DNA is human or not''' 
The way to go about this is to create a Bloom filter containing all 30-mers from the human.fsa file and then query that with the unknown DNA in the mixeddna.fsa file. A 30-mer is chosen, as it is very likely unique.
Make two programs; one that creates the Bloom filter from the human DNA and saves it to a file, and one program that reads in the filter from file, and queries it based on an input fasta file.

'''1)''' Computing the Bloom filter parameters 
The false positive rate, '''p''' must be 1% or lower. Figure out the size of the input, i.e. approximately how many elements will be put in the filter, '''n'''. Compute the size of the filter, '''m''', and the number of hash functions, '''k''' necessary. Adjust values so they fit your purpose, and make a final calculation of '''p'''. Pick hash function(s) and explain your choice.

'''2)''' Making the Bloom filter 
You can use previous functions and ideas. The Bloom filter must be a bytearray and it can be written directly to a binary file.
Since Bloom filters can be added together then you can parallelize the filter construction per chromosome. This is not required. Realize that using joblib creates several filters and they are sizable, i.e. running out of memory is possible.

To help out a bit I have created 3 functions: one that takes a k-mer (as a bytes object) and gives back an integer representing a 32 byte (256 bit) integer number -
the hash-number. One that finds the next position of the bit to set, given a hash-number, and one that sets a bit in a bytearray given positions. These functions are here to increase your understanding, not the programs performance. Using them as they are will not give you the performance boost you need.
I used 7 hours mainly in calculating the Bloom filter in a not-parallel program.
<pre>
import sys, hashlib

# Computes a hash based on a kmer
def hashit(kmer):
myhashobj = hashlib.sha256()
myhashobj.update(kmer)
return int.from_bytes(myhashobj.digest(), byteorder=sys.byteorder)

# The size of the bit field (the slice of bits taken from the hash, how many bits you need)
bitfieldsize = xxxx # your number that correlates with m.

# "eats" a slice from the hash and returns the position in the bloom filter that slice corresponds to.
# Also returns the "leftover" hash, so it can be used again for a new position.
def nextposition(hashnumber):
position = hashnumber & (2**bitfieldsize - 1)
byteposition = position >> 3
bitposition = position & 7
hashnumber >>= bitfieldsize # discarding the used hash slice
return(hashnumber, byteposition, bitposition)

# Sets the bit in the bloom filter
def setbit(bloomfilter, byteposition, bitposition):
bloomfilter[byteposition] |= 1 << bitposition
</pre>

'''3)''' Querying the Bloom filter.
The Bloom filter can/should be loaded with one read. When querying for sequence, also try the reverse complement. Query all 30-mers in the input fasta file, mixeddna.fsa,
and output the no_of_hits/no_of_kmers ratio in percent per sequence. If near 100%, it is human DNA, else not.

<pre>
# This function return True if a bit is set on the position given.
def isbitset(bloomfilter, byteposition, bitposition):
return (bloomfilter[byteposition] & (1 << bitposition)) != 0
</pre>

Hash usage - Revision history

WikiSysop at 09:33, 17 June 2024