Locating Restriction Sites (Rosalind)

  

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

Overview 

Di problem ini kita akan disajikan sebuah string dengan format FASTA, sebut saja string s. Tugas kita ialah mencari posisi dan panjang dari substring s yang merupakan reverse palindrom. Substring reverse palindrom sendiri ialah substring yang jika dibalik, maka menghasilkan substring komplemen dari substring awal. Contoh, substring "GATC" ialah reverse palindrom karena jika dibaca dari kanan ke kiri, maka jadinya "CTAG" yang merupakan komplemen dari substring awal ("GATC"). Kita juga pernah belajar tentang komplemen di problem sebelumnya, yakni "Complementing a Strand of DNA". 

Kode Pengerjaan

Berikut kode pengerjaannya dalam bahasa java :

1. static void solve() {
2. HashMap<Character, Character> thisPair = new HashMap<>();
3. thisPair.put('G', 'C');
4. thisPair.put('C', 'G');
5. thisPair.put('A', 'T');
6. thisPair.put('T', 'A');
7. Scanner sc = new Scanner(System.in);
8. sc.next();
9. String s = "";
10. while (sc.hasNext()) {
11. s += sc.next();
12. }
13. for (int i = 1; i < s.length(); i++) {
14. if (thisPair.get(s.charAt(i - 1)) == s.charAt(i)) {
15. int panjang = 2;
16. int l = i - 1;
17. int r = i;
18. while (--l >= 0 && ++r < s.length() && panjang < 12) {
19. if (thisPair.get(s.charAt(l)) != s.charAt(r)) break;
20. panjang += 2;
21. if (panjang >= 4){
22. out.println((l + 1) + " " + panjang);
23. }
24. }
25. }
26. }
27. }    
    

Penjelasan Kode

Mungkin sudah cukup jelas, disini kita tinggal mencari reverse palindrom secara manual. Untuk mempermudah pencarian, kita bisa mencari 2 karakter yang bersebelahan untuk memulai pencarian (baris 14). 

Baru, jika 2 karakter tersebut saling komplemen (dengan kata lain, reverse palindrom), maka kita tinggal mengurutkan karakter-karakter di sebelahnya (kanan dan kiri) untuk mencari panjang substring reverse palindrom tersebut (baris 18-24). 

Tentu, setiap menemukan 1 reverse palindrom, kita men-print lokasi dan panjangnya, seperti yang diinginkan problem. 

Input dan Output

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 22). 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/