Perfect Matchings and RNA Secondary Structures (Rosalind)

   

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

Overview 

Kanan : satu contoh dari perfect matching RNA.

Di problem ini kita akan disajikan sebuah string dengan format FASTA, sebut saja string s. Tugas kita ialah menentukan total jumlah kemungkinan perfect matching. Perfect matching sendiri ialah suatu keadaan jika setiap karakter di string tersebut mempunyai pasangan RNA-nya: 'A' dengan 'U', 'C' dengan 'G'. Contoh, "ACGU" ialah perfect matching karena 'A' bisa berpasangan dengan 'U' dan 'C' berpasangan dengan 'G'. "ACGUUU" bukan perfect matching karena ada 2 karakter 'U' yang tidak mempunyai pasangan. 

Kode Pengerjaan

Berikut kode pengerjaannya dalam bahasa java :

1. static BigInteger permut (int num) {
2. BigInteger res = BigInteger.valueOf(1);
3. for (int i = 1; i <= num; i++) res = res.multiply(BigInteger.valueOf(i));
4. return res;
5. }
6. static void solve() {
7. Scanner sc = new Scanner(System.in);
8. sc.next();
9. String s = "";
10. while (sc.hasNext()) {
11. s += sc.next();
12. }
13. int numA = 0;
14. int numC = 0;
15. for (char x : s.toCharArray()) {
16. if (x == 'A') numA++;
17. if (x == 'C') numC++;
18. }
19. out.println(permut(numA).multiply(permut(numC)));
20. }   
    

Penjelasan Kode

Idenya disini kita mencari jumlah total kemungkinan perfect matching menggunakan kombinatorika. 

Pertama kita cari dahulu jumlah kemungkinan 'A' bertemu dengan 'U' dan 'C' bertemu dengan 'G' menggunakan permutasi. Oleh karena jumlah karakter 'A' sama dengan jumlah karakter 'U', begitu pula 'C' dengan 'G'; maka kita ambil saja jumlah 'A' dan 'C' (baris 15-18). Jumlah 'A' dan 'C' masing-masing kita cari permutasinya, kemudian kita kalikan untuk mencari jumlah totalnya, rumusnya ialah P(x, x) * P(y, y) untuk x = jumlah 'A' dan y = jumlah 'C' (baris 19). 

Disini saya memakai BigInteger karena untuk berjaga-jaga seandainya angkanya tidak bisa di-handle oleh tipe data long (baris 2). 

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

Sumber gambar 2 :https://dodona.ugent.be/nl/activities/1690462122/