Overlap Graphs (Rosalind)

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "Overlap Graphs". 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-urutan DNA (jumlah tidak diketahui). Tugas kita ialah menentukan pasangan dari string-string tersebut. Dua string bisa disebut berpasangan jika 3 huruf terakhir (suffix) dari string pertama sama dengan 3 huruf awal (prefix) dari string kedua. Sebagai contoh, string "CGAAC" dapat dipasangkan dengan string "AACTT" dengan "AAC" sebagai 3 huruf yang sama; "CGAAC" adalah string pertama, "AACTT" adalah string kedua. 

Cara pengerjaannya sendiri cukup sederhana: kita hanya perlu memasangkan string-string tersebut dengan prinsip prefix-suffix seperti yang sudah dijelaskan diatas. 

Berikut kode pengerjaannya dalam bahasa java :

1. static class Data {
2. String name = "";
3. String strand = "";
4. Data (String name, String strand) {
5. this.name = name;
6. this.strand = strand;
7. }
8. }
9. static void tambahCekEkor (String strand, String name, HashMap<String, Vector<String>> cekEkor, Vector<Data> peserta) {
10. String suffix = strand.substring(strand.length() - 3);
11. if (cekEkor.get(suffix) == null) {
12. cekEkor.put(suffix, new Vector<>());
13. }
14. cekEkor.get(suffix).add(name);
15. peserta.add(new Data(name, strand));
16. }
17. static void solve() {
18. Scanner sc = new Scanner(System.in);
19. HashMap<String, Vector<String>> cekEkor = new HashMap<>();
20. Vector<Data> peserta = new Vector<>();
21. String name = sc.next().substring(1);
22. while (sc.hasNext()) {
23. boolean last = true;
24. String strand = "";
25. while (sc.hasNext()) {
26. String masuk = sc.next();
27. if (masuk.charAt(0) == '>') {
28. tambahCekEkor(strand, name, cekEkor, peserta);
29. name = masuk.substring(1);
30. last = false;
31. break;
32. }
33. strand += masuk;
34. }
35. if (last) {
36. tambahCekEkor(strand, name, cekEkor, peserta);
37. }
38. }
39. for (Data x : peserta) {
40. String preffix = x.strand.substring(0, 3);
41. if (cekEkor.get(preffix) != null) {
42. for (String s : cekEkor.get(preffix)) {
43. if (s != x.name) out.println(s + " " + x.name);
44. }
45. }
46. }
47. }
  

Pertama, kita bisa membuat HashMap<String, Vector<String>> untuk menyimpan suffix dari masing-masing string terlebih dahulu (baris 19). Setelah mengisi HashMap tersebut (baris 22-38), kita pun bisa langsung mencari preffix-nya sekaligus mem-print jawabannya sesuai dengan ketentuan dari problem (baris 39-46). 

Seperti yang teman-teman lihat; disini, saya memakai fungsi next() (baris 21) untuk meng-input data string. Sebelumnya saya juga menggunakan hasNext() (baris 22) 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 43). 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/