I have a series of 15bp DNA sequences from single-cell barcodes and I would like to encode them into a shorter than 15 digits number so that each unique 15bp DNA sequence will create a unique numeric value. What's the best way of achieving this?
1 Answer
What you are asking is called a "hash" (wiki).
In python, get your oligo as a string and use the standard library method hash(oligo)
, this is a number that gets used for a lot of operations. It is however always a 18+1 digit number in decimal, so a different solution is needed.
There are four nucleobases, so binary conversion from scratch is easy and best option and each solution will be unique and small. Each base takes up 2 bits and you concatenate these and convert them to hex or decimal —the length should be 10 decimal digits. One issue is when you have a oligo of a different length which start with adenosine or not.
One issue with this is the order. I am not sure where it comes from but the bases are nearly often expressed in the order ATGC. So...
mapping = {'A': '00', 'T': '01', 'G': '10', 'C': '11'}
It is satisfying how the first digit is the W/S, while the second is R/Y.
Now simply covert and add them compressed = functools.reduce(lambda acc,base : acc+mapping[base], oligo, '')
and covert the string to decimal like so int(compressed, 2)
.
-
$\begingroup$ The problem is hash collisions, there is no guarantee that the compression is unique $\endgroup$ Jun 19, 2020 at 14:41
-
$\begingroup$ Hash collision with the fake-hash would happen with two oligos that are the same but one has one or more extra adenosines. The oligo was said to be 15bp, so this does not apply. A workaround is to add a 1 at the start... $\endgroup$ Jun 19, 2020 at 15:00