Finding a Shared Motif (Rosalind)

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

Di problem ini kita akan disajikan beberapa string dalam bentuk FASTA format yang berisikan urutan DNA. Tugas kita ialah mencari longest common substring atau substring terpanjang yang terdapat pada semua string diatas. 

Berikut kode pengerjaannya dalam bahasa java :

1. static void solve() {
2. Scanner sc = new Scanner(System.in);
3. sc.next();
4. int flow = 0;
5. TreeMap<String, Integer> subString = new TreeMap<>();
6. while (sc.hasNext()) {
7. flow++;
8. HashMap<String, Boolean> substringYgUdah = new HashMap<>();
9. String s = "";
10. while (sc.hasNext()) {
11. String masuk = sc.next();
12. if (masuk.charAt(0) == '>') break;
13. s += masuk;
14. }
15. if (flow == 1) {  
16. for (int i = 0; i < s.length(); i++) {
17. String walk = "";
18. for (int j = i; j >= 0; j--) {
19. walk = s.charAt(j) + walk;
20. subString.put(walk, 1);
21. }
22. }
23. }
24. {
25. for (int i = 0; i < s.length(); i++) {
26. String walk = "";
27. for (int j = i; j >= 0; j--) {
28. walk = s.charAt(j) + walk;
29. if (!substringYgUdah.containsKey(walk)) {
30. if (subString.containsKey(walk)) subString.put(walk, subString.get(walk) + 1);
31. substringYgUdah.put(walk, true);
32. }
33. }
34. }
35. }
36. }
37. String res = "";
38. while (!subString.isEmpty()) {
39. String s = subString.firstKey();
40. if (subString.get(s) == flow) {
41. if (s.length() > res.length()) {
42. res = s;
43. }
44. }
45. subString.pollFirstEntry();
46. }
47. out.println(res);
48. }
     

Karena yang dicari disini ialah longest common substring, maka hal yang pertama kita lakukan ialah mencari semua substring yang bisa menjadi kandidat jawaban. Untuk lebih mudahnya kita ambil substring dari sampel string teratas saja, sebut saja string 1. Disini kita catat semua substring yang ada di string 1 (baris 15-23). 

Langkah kedua, setelah kita mencatat semua substring dari string 1, maka kita tinggal memastikan apakah substring-substring tersebut ada di string-string yang lain (baris 25-34). 

Langkah terakhir ialah mencari substring yang memenuhi syarat (substring yang ada di semua string) dan cari yang paling panjang (baris 37-47). 

Seperti yang teman-teman lihat; disini, saya memakai fungsi next() (baris 11) untuk meng-input data string. Sebelumnya saya juga menggunakan hasNext() (baris 10) 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.println() (baris 47). Fungsi tersebut juga adalah modifikasi dari fungsi System.out.println() 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/