Open Reading Frames (Rosalind | English)

Hi everyone, how are you? This time, I want to discuss about one problem (which is bioinformatics problem) that exist in rosalind.info's web. The title is "Open Reading Frames". For the reference, you can first check out the problem that will be discussed (here). 

Overview

In this problem, we will given a DNA string based on FASTA format; let's call it s string. 

Before stepping further, first we must know about what the Open Reading Frame is. 

In short, the Open Reading Frame (ORF) is a method for reading DNA string. ORF itself divided by 4 steps. 

First, we transcribe a DNA string into a RNA string. For example, 

"ATGGCCATGGCGTGA" becomes "AUGGCCAUGGCGUGA". 

Second, we devide that DNA string by 3 for each. Continuing the string above: 

"AUGGCCAUGGCGUGA" be modified into

AUG-GCC-AUG-GCG-UGA,

UGG-CCA-UGG-CGU,

and GGC-CAU-GGC-GUG. 

Third, we make a reverse complement from the "3-letter string" above. Let's continue;

the reverse complement from AUG-GCC-AUG-GCG-UGA is UAC-CGG-UAC-CGC-ACU,

the reverse complement from UGG-CCA-UGG-CGU is ACC-GGU-ACC-GCA, and

the reverse complement from GGC-CAU-GGC-GUG isCGG-GUA-CCG-CAC

Forth, we translate all of the "3-letter string"s above (6 total) into protein strings. In the past, we've translated a RNA string into a protein string using RNA codon table. This step is something like that. Like in the RNA-translate rule, here we will translating a RNA starting from start-codon (AUG) and stopping at stop-codon (UAA, UGA, UAG). For example, 

the translation of AUG-GCC-AUG-GCG-UGA is MAMA.

For the further understanding of Open Reading Frame, let's see a reference here on youtube

This is how to read a protein strain.

The Code 

This is the code for solving this problem (with java language): 

1. static String reverseComplement (String s, HashMap<Character, Character> thisPair) {
2. char[] ch = s.toCharArray();
3. int n = ch.length;
4. for (int i = 0; i < n / 2; i++) {
5. char swap = ch[i];
6. ch[i] = ch[n - 1 - i];
7. ch[n - 1 - i] = swap;
8. }
9. s = "";
10. for (char x : ch) {
11. s += thisPair.get(x);
12. }
13. return s;
14. }
15. static void solve() {
16. HashMap<Character, Character> thisPair = new HashMap<>();
17. thisPair.put('A', 'T');
18. thisPair.put('T', 'A');
19. thisPair.put('G', 'C');
20. thisPair.put('C', 'G');
21. HashMap<String, String> codonTable = new HashMap<>();
22. codonTable.put("ATT", "I");
23. codonTable.put("ATC", "I");
24. codonTable.put("ATA", "I");
25. codonTable.put("ATG", "M");
26. codonTable.put("ACT", "T");
27. codonTable.put("ACC", "T");
28. codonTable.put("ACA", "T");
29. codonTable.put("ACG", "T");
30. codonTable.put("AAT", "N");
31. codonTable.put("AAC", "N");
32. codonTable.put("AAA", "K");
33. codonTable.put("AAG", "K");
34. codonTable.put("AGT", "S");
35. codonTable.put("AGC", "S");
36. codonTable.put("AGA", "R");
37. codonTable.put("AGG", "R");
38. codonTable.put("TTT", "F");                  
39. codonTable.put("TTC", "F");                  
40. codonTable.put("TTA", "L");                  
41. codonTable.put("TTG", "L");                  
42. codonTable.put("TCT", "S");                  
43. codonTable.put("TCC", "S");                  
44. codonTable.put("TCA", "S");                  
45. codonTable.put("TCG", "S");                  
46. codonTable.put("TAT", "Y");                  
47. codonTable.put("TAC", "Y");                  
48. codonTable.put("TAA", "Stop");               
49. codonTable.put("TAG", "Stop");               
50. codonTable.put("TGT", "C");                  
51. codonTable.put("TGC", "C");                  
52. codonTable.put("TGA", "Stop");
53. codonTable.put("TGG", "W");                  
54. codonTable.put("CTT", "L");
55. codonTable.put("CTC", "L");
56. codonTable.put("CTA", "L");
57. codonTable.put("CTG", "L");
58. codonTable.put("CCT", "P");
59. codonTable.put("CCC", "P");
60. codonTable.put("CCA", "P");
61. codonTable.put("CCG", "P");
62. codonTable.put("CAT", "H");
63. codonTable.put("CAC", "H");
64. codonTable.put("CAA", "Q");
65. codonTable.put("CAG", "Q");
66. codonTable.put("CGT", "R");
67. codonTable.put("CGC", "R");
68. codonTable.put("CGA", "R");
69. codonTable.put("CGG", "R");
70. codonTable.put("GTT", "V");
71. codonTable.put("GTC", "V");
72. codonTable.put("GTA", "V");
73. codonTable.put("GTG", "V");
74. codonTable.put("GCT", "A");
75. codonTable.put("GCC", "A");
76. codonTable.put("GCA", "A");
77. codonTable.put("GCG", "A");
78. codonTable.put("GAT", "D");
79. codonTable.put("GAC", "D");
80. codonTable.put("GAA", "E");
81. codonTable.put("GAG", "E");
82. codonTable.put("GGT", "G");
83. codonTable.put("GGC", "G");
84. codonTable.put("GGA", "G");
85. codonTable.put("GGG", "G"); 
86. 
    
87. Scanner sc = new Scanner(System.in);
88. sc.next();
89. String s = "";
90. while (sc.hasNext()) {
91. s += sc.next();
92. }
93. Vector<String> res = new Vector<>();
94. HashMap<String, Boolean> udah = new HashMap<>();
95. for (int j = 0; j < 3; j++) {
96. for (int i = 0; i + j <= s.length() - 3; i += 3) {
97. int ii = i + j;
98. String now = s.substring(ii, ii + 3);
99. if (now.equals("ATG")) {
100. res.add("");
101. }
102. else if (now.equals("TAA") || now.equals("TAG") || now.equals("TGA")) {
103. for (String ss : res) {
104. if (udah.get(ss) == null) out.println(ss);
105. udah.put(ss, true);
106. }
107. res = new Vector<>();
108. }
109. for (int k = 0; k < res.size(); k++) {
110. res.set(k, res.get(k) + codonTable.get(now));
111. }
112. }
113. res = new Vector<>();
114. }
115. s = reverseComplement(s, thisPair);
116. res = new Vector<>();
117. for (int j = 0; j < 3; j++) {
118. for (int i = 0; i + j <= s.length() - 3; i += 3) {
119. int ii = i + j;
120. String now = s.substring(ii, ii + 3);
121. if (now.equals("ATG")) {
122. res.add("");
123. }
124. else if (now.equals("TAA") || now.equals("TAG") || now.equals("TGA")) {
125. for (String ss : res) {
126. if (udah.get(ss) == null) out.println(ss);
127. udah.put(ss, true);
128. }
129. res = new Vector<>();
130. }
131. for (int k = 0; k < res.size(); k++) {
132. res.set(k, res.get(k) + codonTable.get(now));
133. }
134. }
135. res = new Vector<>();
136. }
137. }    
     
  

First, we make a RNA (or DNA) codon table in a HashMap variable. For efficiency, we could use a DNA codon table; thus, we can directly translate the DNA into the protein string (line 21-85). 

Then, we transform the s string into a "3-letter string" and translate it into protein after that (line 95-114).

Don't forget to make a reverse complement from s too (line 115). Make it and translate it like in the previous. 

Input and Output

In the code above, I used next() function for entering the string-form dataset (line 91). 

I also used another input function called hasNext() (line 90). That function is very useful especially if we need to process an unknown-amount of data, just like a FASTA format data. 

And for the output I used out.println() function (line 126). That function is a modification from System.out.println() function which is very familiar in java. You can see the additional code for that modification (input and output) in my complete code at github.

That's it. If you want to ask something, you can write it in the comment section below. I hope this article is useful and see you in the next article!

Reference :

Source of image 1 :https://www.facebook.com/ProjectRosalind/

Source of image 2 :https://www.pngdownload.id/png-e9lrt0/