Independent Alleles (Rosalind)

            

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

Di problem ini kita akan disajikan 2 buah bilangan bulat (integer) yang mewakili "generasi ke berapa" dan "jumlah keturunan minimal", sebut saja k dan N. Dan tugas kita ialah mencari probabilitas dari munculnya keturunan AaBb, minimal N buah di generasi ke-k. 

Idenya ialah dengan mencari total jumlah kemungkinan AaBb yang berjumlah minimal N buah; lalu dibagi dengan total semua kemungkinan. 

Berikut kode pengerjaannya (dalam bahasa java) :

1. public double comb (int n, int k) {
2. double atas = 1.0;
3. for (int i = 1; i <= n; i++) {
4. atas *= i;
5. }
6. for (int i = 1; i <= k; i++) {
7. atas /= i;
8. }
9. for (int i = 1; i <= n - k; i++) {
10. atas /= i;
11. }
12. return atas;
13. }
14. public void solve() {
15. int k = in.readInt();
16.         int n = in.readInt();
17. int base = 1;
18. for (int i = 0; i < k; i++) base *= 2;
19.         double res = 0.0;
20. for (int i = base; i >= n; i--) {
21. res += comb(base, i) * Math.pow(1, i) * Math.pow(3, base - i) / Math.pow(4, base);
22. }
23. out.printf("%.3f\n", res);
24. }

Pertama, kita bisa mencari total semua kemungkinan dahulu (2^k); disini saya memakai variabel base untuk menghitungnya (baris 17-18). 

Kemudian untuk mengkalkulasi, kita bisa memakai binomial distribution (baris 20-22). Inti dari binomial distribution sendiri ialah menghitung semua kemungkinan kombinasi sembari menghitung probabilitas di setiap kombinasi tersebut. Disini kita mencari kemungkinan kombinasi AaBb yang memiliki jumlah N buah sampai 2^k buah serta menghitung probabilitas di setiap kombinasi tersebut 

Diatas, saya memakai fungsi in.readInt() untuk meng-input data integer. Fungsi tersebut adalah modifikasi dari salah satu sistem input yang ada di java (BufferedReader). Sedangkan untuk output-nya saya memakai fungsi out.printf() . Fungsi tersebut juga adalah modifikasi dari fungsi System.out.printf()  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 :http://rosalind.info/problems/lia/