Chubek/README.md

So, for the past several hours I have began a bioinformatics project that I suspect may end sooner than I expected, and that project is, a DNA to Protein translator and reverse-translator aptly titled TransGatacca. The main crux of the program is in x86-64 and Aarch64 Assembly languages. However it is desined to be callable from C and will also have bindings in Rust using global_asm! macro. There will also be Python bindings.

The aim of this software is speed, and speed alone, so I am trying to do as many micro-optimizations as possibly there can be. One of these venues is of course, the genetics table --- and later, codon frequency table. One needs to encode these tables in such way that they can be represented all inside one 64-bit register or memory address with zero overflow, and that the remain unique across all the possible permutations of the nucleotide triplets, and finally, they can be represented a contiguous series of memory blocks which end at an even memory address.

I devised the following ways to encode:

1- Nucleotide Triplet - Peptide Mapping for translation
2- Peptide - Nucleotide Triplet Mapping for reverse-translation
3- Codon Frequency Table for reverse-translation

... in such way to be easy for a 64bit CPU or memory address to handle. I technically have access to 128-bit-wide addresses in both archs, but I will hesitate to use them as I want my code to be easily modified to be runnable on 32-bit machines which do have 64-bit addresses.

First, we do the following mapping of:

A (65) -> 0
C (67) -> 1
G (71) -> 3
T (84) -> 2

Using 3 & (nuc >> 1). It is possible to switch 2 with 3 and make them in order using two additional operations, that is 3 & ((nuc >> 1) ^ (nuc >> 2)) but that is only useful in case of complements. For now this shall suffice.

After that:

1- To encode triplets, we pack all 3 2-bit integers into a 6-bit intger (order of bits is not important, but the deocder must use the same order) and thus we will have a maximum of 64 different integers. We can create an array of 64, with each 6-bit index representing a peptide corresponding to that nucleotide triplet. We now have an array where arr[i] = byte value of peptide.

2- To encode peptides, we take all the possible triplets that we encoded before, which non-empty numbers can range from 1 to 10, and pack all those 6-bit integers that we got into an n * 6 bit integer, with n being the number of possible degenerate triplets for that peptide. We then shift the length of the possible triplets by 60. Finally, for example, for peptide F in table 33 we get:

We will then lay them an array of size 26, after we subtract 64 from peptide ('A' - 1). We now have an array where arr[n] = packed values.

3 - To encode codon frequency: By subtracting 64 from peptide, we are left with a 5-bit integer. We apply the following to the encoded triplet:

(nuc1 | (nuc3 << 1)) ^ nuc2

We now have a 3-bit integer which we can append to the end of pep - 64 by shifting the said value 3 to the left and OR'ing it with the 3-bit integer. We now can use this value to index the frequency. But how do we represent the frequency? Basically, we take the first two digits after the decimal point and atoi them (or just int(s.split(".")[-1][:2])). The maximum our index can be is 255 so we store everythng n an array of size 256, where arr[i] = freq.

The following files in this Gist are an implementation of this encoding. Files encoded_codons_freq.json, encoded_codons_table.json and encoded_reverse_codons_table.json are the resulting values. For frequeny, the most popular values have been chosen. The data is hard-coded into the Python files because it's simply superior to be able to portably transfer an entire file from hell and back hithereto eternity without having to transfer anything else alongside.

Please contact me on Discord at Chubak#7400 if you got any questions.