RNA Splicing (Rosalind)

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "RNA Splicing". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini). 

String utama terdiri dari intron dan ekson.

Di problem ini kita akan disajikan beberapa string dalam bentuk FASTA format yang berisikan urutan DNA. String tersebut terdiri dari satu string utama dan beberapa string intron (jumlah tidak diketahui). String intron sendiri merupakan substring dari string utama. 

Tugas kita ialah men-translate string ekson (dari string utama) menjadi protein. Seperti yang kita ketahui, string utama ialah string yang terdiri dari intron dan ekson. Untuk mencari eksonnya maka otomatis kita harus menghilangkan intron dari string utama (seperti pada gambar diatas). 

Berikut kode pengerjaannya dalam bahasa java :

1. static int tot = 0;
2. static void makeItDot (int awal, int akhir, char[] pat) {
3. for (int i = awal; i <= akhir; i++) {
4. pat[i] = '.';
5. }
6. }
7. static int[] makeRev (char[] sample) {
8. int[] rev = new int[sample.length]; rev[0] = 0; rev[1] = 0;
9. int pvt = 0;
10. for (int i = 2; i < sample.length; i++) {
11. if (sample[i] != sample[pvt + 1]) {
12. if (sample[i] == sample[1]) pvt = 1;
13. else pvt = 0;
14. }
15. else {
16. pvt++;
17. }
18. rev[i] = pvt;
19. }
20. return rev;
21. }
22. static void match (char[] pat, char[] sample) {
23. int[] rev = makeRev(sample);
24. int pvt = 0;
25. for (int i = 1; i < pat.length; i++) {
26. while (pat[i] != sample[pvt + 1] && pvt != 0) {
27. pvt = rev[pvt];
28. }
29. if (pat[i] == sample[pvt + 1]) pvt++;
30. if (pvt == sample.length - 1) {
31. makeItDot(i - (sample.length - 1) + 1, i, pat);
32. tot += sample.length - 1;
33. break;
34. }
35. }
36. }
37.     static void solve() {
38. HashMap<String, String> codonTable = new HashMap<>();
39. codonTable.put("UUU", "F");      
40. codonTable.put("UUC", "F");      
41. codonTable.put("UUA", "L");      
42. codonTable.put("UUG", "L");      
43. codonTable.put("UCU", "S");      
44. codonTable.put("UCC", "S");      
45. codonTable.put("UCA", "S");      
46. codonTable.put("UCG", "S");      
47. codonTable.put("UAU", "Y");      
48. codonTable.put("UAC", "Y");      
49. codonTable.put("UAA", "Stop");   
50. codonTable.put("UAG", "Stop");   
51. codonTable.put("UGU", "C");      
52. codonTable.put("UGC", "C");      
53. codonTable.put("UGA", "Stop");   
54. codonTable.put("UGG", "W");      
55. codonTable.put("CUU", "L");      
56. codonTable.put("CUC", "L");      
57. codonTable.put("CUA", "L");      
58. codonTable.put("CUG", "L");      
59. codonTable.put("CCU", "P");      
60. codonTable.put("CCC", "P");      
61. codonTable.put("CCA", "P");      
62. codonTable.put("CCG", "P");      
63. codonTable.put("CAU", "H");      
64. codonTable.put("CAC", "H");      
65. codonTable.put("CAA", "Q");      
66. codonTable.put("CAG", "Q");      
67. codonTable.put("CGU", "R");      
68. codonTable.put("CGC", "R");      
69. codonTable.put("CGA", "R");      
70. codonTable.put("CGG", "R");      
71. codonTable.put("AUU", "I");      
72. codonTable.put("AUC", "I");      
73. codonTable.put("AUA", "I");      
74. codonTable.put("AUG", "M");      
75. codonTable.put("ACU", "T");      
76. codonTable.put("ACC", "T");      
77. codonTable.put("ACA", "T");      
78. codonTable.put("ACG", "T");      
79. codonTable.put("AAU", "N");      
80. codonTable.put("AAC", "N");      
81. codonTable.put("AAA", "K");      
82. codonTable.put("AAG", "K");      
83. codonTable.put("AGU", "S");      
84. codonTable.put("AGC", "S");      
85. codonTable.put("AGA", "R");      
86. codonTable.put("AGG", "R");      
87. codonTable.put("GUU", "V");
88. codonTable.put("GUC", "V");
89. codonTable.put("GUA", "V");
90. codonTable.put("GUG", "V");
91. codonTable.put("GCU", "A");
92. codonTable.put("GCC", "A");
93. codonTable.put("GCA", "A");
94. codonTable.put("GCG", "A");
95. codonTable.put("GAU", "D");
96. codonTable.put("GAC", "D");
97. codonTable.put("GAA", "E");
98. codonTable.put("GAG", "E");
99. codonTable.put("GGU", "G");
100. codonTable.put("GGC", "G");
101. codonTable.put("GGA", "G");
102. codonTable.put("GGG", "G"); 
104. Scanner sc = new Scanner(System.in);
105. Vector<String> dnas = new Vector<>();
106. while (sc.hasNext()) {
107. String s = "";
108. while (sc.hasNext()) {
109. String masuk = sc.next();
110. if (masuk.charAt(0) == '>') break;
111. s += masuk;
112. }
113. if (s != "") dnas.add(s); 
114. }
115. Collections.sort(dnas, new Comparator<String>(){
116. public int compare (String a, String b) {
117. return b.length() - a.length();
118. }
119. });
120. char[] pat = ("." + dnas.remove(0)).toCharArray();
121. while (!dnas.isEmpty()) {
122. char[] sample = ("." + dnas.remove(0)).toCharArray();
123. match(pat, sample);
124. }
125. String s = "";
126. for (char ch : pat) {
127. if (ch != '.') s += ch;
128. }
129. for (int i = 0; i < s.length(); i+= 3) {
130. String prot = codonTable.get(s.substring(i, i + 3).replace('T', 'U'));
131. if (prot != "Stop") out.print(prot);
132. }
133.     }
     

Pertama, kita buat katalog tabel kodon RNA/DNA terlebih dahulu (dua-duanya boleh). Untuk lebih cepatnya kita bisa langsung memakai tabel kodon DNA, jadi bisa langsung men-translate DNA menjadi protein. Disini saya memilih untuk memakai tabel kodon RNA (baris 38-102). 

(Untuk baris 115 sampai 119 saya memakai fungsi sort. Fungsi sort ini aslinya tidak diperlukan karena problem setter sudah menjamin tidak akan ada string intron yang berhubungan satu sama lain [supaya jawabannya hanya satu]. Saya memakai fungsi sort hanya untuk jaga-jaga.) 

Langkah selanjutnya, kita cocokan intron-intron-nya ke string utama (baris 120-124). Untuk mencocokannya saya memakai algoritma knuth-morris-pratt yang saya jabarkan di baris 2 sampai 36. Disini saya mencocokan string tersebut sekaligus merubah substring yang cocok (di string utama) menjadi karakter "." (titik). 

Karakter titik tersebut saya hapus di baris ke 125 sampai 128 (saya membuat string utama baru tanpa ".", pengganti string utama sebelumnya). 

Langkah terakhir ialah menerjemahkan string utama baru ke protein, seperti pada problem "Translating RNA into Protein". 

Seperti yang teman-teman lihat; disini, saya memakai fungsi next() (baris 109) untuk meng-input data string. Sebelumnya saya juga menggunakan hasNext() (baris 108) dikarenakan fungsi tersebut mampu meng-input data yang tidak diketahui jumlahnya. Fungsi tersebut sangat cocok jika dipakai untuk menangani input dengan format FASTA. 

Sedangkan untuk output-nya saya memakai fungsi out.print() (baris 131). Fungsi tersebut juga adalah modifikasi dari fungsi System.out.print() yang merupakan fungsi default di java. Untuk lebih jelasnya teman-teman bisa melihat kode tambahan untuk memodifikasi fungsi tersebut (input maupun output) di versi lengkap kode saya di github. 

Sekian dari saya. Jika teman-teman ingin menanyakan sesuatu, teman-teman bisa menulisnya di kolom komentar. Semoga bermanfaat dan sampai jumpa di artikel berikutnya!

Referensi :

Sumber gambar 1 :https://www.facebook.com/ProjectRosalind/

Sumber gambar 2 :https://commons.wikimedia.org/wiki/File:DNA_exons_introns.gif