Team:NEFU China/Coding book

Code Book

Code Book

In English text, each letter has a certain frequency. We constructed a list of letter frequencies for each letter. Also, in living organisms, each codon is used with a certain frequency. Based on this relationship between English letters and codons, we find out the correspondence between letters and codons by using DFS (Depth First Search) algorithm and optimization arithmetic.



Create a letter-frequency table and a codon-frequency table

According to the literature, we obtain the information of the frequency of letters and codons.
letter frequency table:

codon frequency table:




Find out the correspondence between letters and codons by using DFS Algorithm

We build up a tree structure where the codons and the frequency of the codons are stored on each node. Then we use the depth-first search algorithm to traverse down from the root node successively, and match condon-frequence with the letter- frequency to obtain the correspondence between letters and codons.
The tree structure is shown as bellow.




Get the optimal solution by using optional algorithm.

In step 2, we get the correspondence between letters and codons. But some letters have multiple corresponding relationships. For example, in figure 1, the letters E and T correspond to codons GAU, GCU, GAA, E and T also correspond to codons GAU, GCU, AUG. What’s more, the letter T can also correspond to codons GAU, GCU, GCA. Therefore, we use the optimal algorithm to determine one of the multiple correspondence.

For example (letter T):




RESULTS

Print the correspondence between letters and codons: