Finding a Motif in DNA (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 Motif in DNA". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini).

Di problem ini kita akan disajikan 2 buah string DNA, sebut saja s dan t. Tugas kita ialah menemukan posisi dari string t yang dapat ditemukan di string s (bisa lebih dari satu). Metode pengerjaannya cukup sederhana: kita hanya perlu mencocokan string t ke string s, lalu mencatat di posisi mana sajakah string t berada. 

Berikut kode untuk pengerjaannya (dalam bahasa java) :

static void solve() {

char[] ch1 = ("." + ns()).toCharArray();

char[] ch2 = ("." + ns()).toCharArray();

int[] rev = new int[ch2.length]; 

        rev[0] = 1; 

        rev[1] = 1;

int pvt = 1;

for (int i = 2; i < ch2.length; i++) {

if (ch2[i] != ch2[pvt]) {

if (ch2[i] == ch2[1]) pvt = 2;

else pvt = 1;

}

else {

pvt++;

}

rev[i] = pvt;

}

pvt = 1;

for (int i = 1; i < ch1.length; i++) {

if (ch1[i] != ch2[pvt]) {

pvt = rev[pvt - 1];

if (ch1[i] == ch2[pvt]) pvt++;

else if (ch1[i] == ch2[1]) pvt = 2;

else pvt = 1;

continue;

}

if (pvt == ch2.length - 1) {

out.print((i - (ch2.length - 1) + 1) + " ");

        pvt = rev[pvt]; 

                        continue;

        }

         pvt++;

        }

}    

Seperti yang teman-teman lihat, disini saya menggunakan algoritma KMP (Knuth-Morris-Pratt) untuk meng-efisiensi-kan waktu pencocokan string. Algoritma KMP ini sangat berguna terutama jika harus mengolah data yang sangat besar yang seringkali memakan waktu. Bagi teman-teman yang ingin mempelajari algoritma KMP saya punya video yang bagus disini.

Disini saya memakai fungsi ns() untuk meng-input data string. Fungsi tersebut adalah extend dari salah satu sistem input di java, yaitu BufferedReader. Sedangkan untuk output-nya saya memakai fungsi out.print() . Fungsi tersebut adalah modifikasi dari fungsi System.out.print()  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://en.wikipedia.org/wiki/Alu_element