Pencocokan Dna Menggunakan Longest Common Subsequences (LCS) [PDF]

Citation preview

PENCOCOKAN DNA MENGGUNAKAN LONGEST COMMON SUBSEQUENCES (LCS) DISUSUN UNTUK MEMENUHI TUGAS AKHIR MATA KULIAH DESAIN ANALISIS DAN ALGORITMA



OLEH : KELOMPOK 9 Nur Adli A. D. Muhja Mufidah A. A.



135150207111119 135150207111120



UNIVERSITAS BRAWIJAYA MALANG 2015



ABSTRAK Mencari rangkaian bersama terpanjang atau longest common subsequence (LCS) dari beberapa buah rangkaian adalah sebuah masalah klasik dalam ilmu komputer. Masalah ini adalah masalah dengan penyelesaian sederhana, yaitu berupa sebuah fungsi rekursif dengan melakukan penghitungan yang sama secara berulang. Algoritma LCS ini telah dipelajari untuk waktu yang lama dan sekarang telah menjadi bagian penting dari ilmu komputer. Aplikasinya dipakai secara luas, tidak hanya terbatas pada lingkup ilmu komputer seperti pengenalan pola, namun juga di bidang biologi seperti untuk pencocokan DNA. Dalam pengaplikasian di bidang biologi sering diperlukan pembandingan atau pencocokan DNA dari dua (atau lebih) organisme yang berbeda. Seuntai DNA terdiri dari serangkaian molekul yang disebut basis. Basis yang mungkin adalah adenin, guanin, citosin, dan timin. Keempat basis DNA ini dapat dituliskan dengan notasi huruf {A, C, G, T}. Untuk mengukur kemiripan untaian DNA satu dan DNA kedua adalah dengan menemukan untaian DNA ketiga sebagai untaian terpanjang dari kedua untaian, dimana basis pada untaian ketiga muncul di setiap untaian pertama dan kedua. Semakin panjang untaian ketiga yang ditemukan, maka DNA satu dan DNA kedua semakin mirip. Kata kunci : LCS, longest common subsequences, subrangkaian terpanjang, DNA, pencocokan DNA



BAB I PENDAHULUAN 1.1. Latar Belakang Mencari rangkaian bersama terpanjang atau longest common subsequence (LCS) dari beberapa buah rangkaian adalah sebuah masalah klasik dalam ilmu komputer. Masalah ini adalah masalah dengan penyelesaian sederhana, yaitu berupa sebuah fungsi rekursif dengan melakukan penghitungan yang sama secara berulang. Algoritma LCS ini telah dipelajari untuk waktu yang lama dan sekarang telah menjadi bagian penting dari ilmu komputer. Algoritma ini akan mencari sub rangkaian terpanjang dari dua buah rangkaian yang memiliki pola atau string yang cocok. Aplikasinya dipakai secara luas, tidak hanya terbatas pada lingkup ilmu komputer seperti pengenalan pola, namun juga di bidang biologi seperti untuk pencocokan DNA. Permasalahan pencocokan string tersebut akan coba diterapkan pada sequence DNA (rangkaian DNA). Dalam pengaplikasian di bidang biologi ini, sering diperlukan pembandingan atau pencocokan DNA dari dua (atau lebih) organisme yang berbeda. DNA merupakan sejenis asam nukleat yang tergolong biomolekul utama penyusun berat kering setiap organisme dan merupakan sebuah polimer yang terdiri dari 3 komponen utama, yaitu gugus fosfat, gula deoksiribosa, dan basa nitrogen. Seuntai DNA terdiri dari serangkaian molekul yang disebut basis. Basis yang mungkin adalah adenin (A), guanin (G), citosin (C), dan timin (T). Rangkaian DNA mengandung informasi setiap organisme dan dapat dianggap sebagai rangkaian string yang merupakan kombinasi dari 4 karakter yaitu A,T,G,C. Untuk mengukur kemiripan untaian DNA satu dan DNA kedua adalah dengan menemukan untaian DNA ketiga sebagai untaian terpanjang dari kedua untaian, dimana basis pada untaian ketiga muncul di setiap untaian pertama dan kedua. Semakin panjang untaian ketiga yang ditemukan, maka DNA satu dan DNA kedua semakin mirip. Berbagai algoritma pencocokan string dapat digunakan untuk mengukur kemiripan antara dua untaian DNA, namun algoritma yang paling cocok adalah dengan menggunakan LCS seperti yang telah dijelaskan diatas. Oleh karenanya, kami membuat sebuah program berbasis Java dengan menggunakan algoritma LCS sebagai program pencocokan string DNA.



1.2. Rumusan Masalah Berdasarkan latar belakang yang telah diulas, maka permasalahan yang dibahas adalah sebagai berikut : 1. Apa itu algoritma longest common subsequence (LCS) ? 2. Bagaimana untaian DNA dikatakan mirip dengan untaian DNA yang lain ? 3. Bagaimana cara mengimplementasikan algoritma longest common subsequence (LCS) sebagai algoritma pencocokan DNA sebagai program berbahasa Java? 4. Bagaimana kompleksitas yang terbentuk dari algoritma yang digunakan?



1.3. Tujuan Penulisan Dari rumusan masalah yang terbentuk, maka tujuan dari penulisan makalah ini adalah : 1. Mengetahui ulasan dari algoritma longest common subsequence (LCS) 2. Mengetahui cara pencocokan dua untaian DNA sehingga diketahui tingkatan kemiripannya 3. Mengetahui pengimplementasian algoritma longest common subsequence (LCS) sebagai algoritma pencocokan DNA dalam program berbahasa Java 4. Mengetahui kompleksitas dari algoritma longest common subsequence (LCS)



BAB II PEMBAHASAN 2.1. Longest Common Subsequences (LCS) Longest Common Subsequences adalah masalah mencari subrangkaian bersama (common subsequence) terpanjang dari beberapa (biasanya hanya 2) buah rangkaian. Subrangkaian (subsequence) dari sebuah string S adalah sekumpulan karakter yang ada pada S yang mempunyai urutan kemunculan sama. Dalam definisi formalnya, rangkaian Z adalah subrangkaian dari X , jika terdapat urutan menaik yang merupakan indeks X untuk semua j=1,2,..,k, yang memenuhi xi=zj . Misal pada S = GAATACA, beberapa subrangkaian yang mungkin adalah : GAT, TCA, dan GC. Subrangkaian bersama (common subsequence) dari 2 rangkaian adalah subrangkaian yang terdapat pada kedua rangkaian tersebut. Misal S1 = GATTTAC dan S2 = AAGATC, maka GAT, GATC, maupun GAC adalah subrangkaian bersama dari S1 dan S2. Subrangkaian bersama terpanjang (longest common subsequences) adalah subrangkaian bersama dari 2 rangkaian yang paling panjang



2.1.1. Algoritma Penyelesaian LCS Algoritma untuk permasalahan LCS adalah berdasarkan teorema di bawah : Misal X = < x1, x2, .. , xm > dan Y = < y1, y2, .. , yn > adalah rangkaian dan Z = < z1, z2, .. , zk> adalah suatu LCS dari X dan Y. 1. Jika xm = yn, maka zk = xm = yn dan Zk-1 adalah suatu LCS dari Xm-1 dan Yn-1. 2. Jika xm ≠ yn maka zk ≠xm mengimplikasikan bahwa Z adalah suatu LCS dari Xm-1 dan Y 3. Jika xm ≠ yn maka zk ≠ yn mengimplikasikan bahwa Z adalah suatu LCS dari X dan Yn-1



2.1.2. Mendapatkan Panjang LCS Misal m adalah panjang S1, n adalah panjang S2, dan tab adalah matriks berukuran m x n, dan tab[i, j] adalah panjang LCS dari subrangkaian pertama yang terdiri dari i karakter pertama S1 dengan subrangkaian kedua yang terdiri dari j karakter



pertama S2, maka untuk 1 ≤ i ≤ m dan 1 ≤ j ≤ n, sesuai dengan fungsi rekursif di atas, maka :  tab[i -1, j-1]+1, S1[i]=S2[j] tab[i, j] =   max (tab[i -1, j], tab[i, j-1]) Misal, untuk S1 = AGCGA dan S2 = CAGATAGAG, tabel yang terbentuk adalah tabel berukuran 5 x 9 yang isinya sebagai berikut :



Tabel hasil kalkulasi LCS dari AGCGA dan CAGATAGAG C



A



G



A



T



A



G



A



G



1



2



3



4



5



6



7



8



9



A



1



0



1



1



1



1



1



1



1



1



G



2



0



1



2



2



2



2



2



2



2



C



3



1



1



2



2



2



2



2



2



2



G



4



1



1



2



2



2



2



3



3



3



A



5



1



2



2



3



3



3



3



4



4



Dan sesuai dengan arti notasi dari setiap tab[i, j] bahwa LCS dari S1 dan S2 adalah tab[m, n] atau dalam kasus ini adalah 4.



2.1.3. Mendapatkan LCS Sedangkan untuk mendapatkan LCS yang dimaksud, kita bisa merunut balik tabel dimulai dari tab[m, n]. Dalam runut balik ini, yang kita lakukan sebenarnya hanyalah merunut balik pilihan yang dilakukan pada saat kalkulasi tab[i, j]. Untuk setiap 1 ≤ i ≤ m dan 1 ≤ j ≤ n, jika S1[i] sama dengan S2[j], maka maka karakter itu pasti terdapat pada LCS. Selain itu, cek, darimana dia mendapatkan LCS saat itu, lakukan pemilihan yang sama. Lakukan hal tersebut dimulai dari i = m dan j = n. Setelah hal itu dilakukan maka akan terbentuk tabel seperti di bawah ini. Di mana cell yang berwarna kuning menandakan karakter yang masuk ke dalam LCS.



Tabel hasil perunutan balik dari AGCGA dan CAGATAGAG C



A



G



A



T



A



G



A



G



1



2



3



4



5



6



7



8



9



A



1



0



1



1



1



1



1



1



1



1



G



2



0



1



2



2



2



2



2



2



2



C



3



1



1



2



2



2



2



2



2



2



G



4



1



1



2



2



2



2



3



3



3



A



5



1



2



2



3



3



3



3



4



4



Berdasarkan tabel di atas, terlihat bahwa LCSnya adalah AGGA.



2.2. Pencocokan DNA Sebagian besar subjek dari biologi molekuler adalah yang berhubungan dengan analisis dan perbandingan dari materi genetik (DNA, RNA, protein, kromosom, gen, dan sebagainya) dari organisme yang berbeda-beda. Untuk melakukan hal ini diperlukan pengumpulan, pemerosesan dan penyimpanan informasi dalam jumlah yang besar. Untungnya, banyak jenis dari data biomolekular memiliki struktur data yang mirip, contohnya struktur primer dari protein adalah rantai satu dimensi dari residu asam amino dan untaiannya dapat dituliskan sebagai string dengan panjang tertentu. Struktur yang sama ditemukan juga pada rangkaian dalam DNA, yang biasa disebut rangkaian genetik. Rangkaian genetik merupakan sebuah string yang dibentuk dari empat buah alfabet {A,G,T,C}. Keempat alfabet ini mewakili struktur penyusun DNA yang terdiri dari purin (Adenin an Guanin) dan pirimidin (Timin dan Sitosin). Gen merupakan rangkaian genetik yang berisi informasi-informasi yang dibutuhkan untuk menyusun sebuah protein. Untuk mengukur kemiripan untaian DNA satu dan DNA kedua adalah dengan menemukan untaian DNA ketiga sebagai untaian terpanjang dari kedua untaian, dimana basis pada untaian ketiga muncul di setiap untaian pertama dan kedua. Semakin panjang untaian ketiga yang ditemukan, maka DNA satu dan DNA kedua semakin mirip.



2.3. Implementasi pada Program Implementasi dilakukan menggunakan bahasa Java. Source di bawah ini merupakan implementasi langsung dari algoritma LCS untuk pengimplementasian DNA. Source code-nya dalam bahasa Java adalah sebagai berikut :



package latihan; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class LongestCommonSubsequence { /** Fungsi untuk LCS **/ public String lcs(String str1, String str2) { int l1 = str1.length(); int l2 = str2.length(); int[][] arr = new int[l1 + 1][l2 + 1]; for (int i = l1 - 1; i >= 0; i--) { for (int j = l2 - 1; j >= 0; j--) { if (str1.charAt(i) == str2.charAt(j)) { arr[i][j] = arr[i + 1][j + 1] + 1; } else { arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]); } } } int i = 0, j = 0; StringBuffer sb = new StringBuffer(); while (i < l1 && j < l2) { if (str1.charAt(i) == str2.charAt(j)) { sb.append(str1.charAt(i)); i++; j++; } else if (arr[i + 1][j] >= arr[i][j + 1]) { i++; } else { j++; } } return sb.toString(); }



public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("****DNA COMPARISON USING LCS ALGORITHM BY KELOMPOK 9***"); System.out.println("Masukkan kedua untaian DNA sesuai petunjuk di bawah"); System.out.println("Untaian DNA : Adenin (A), Guanin (G), Citosin (C), Timin (T)"); System.out.println("\nEnter DNA String 1 : "); String str1 = br.readLine(); System.out.println("\nEnter DNA String 2"); String str2 = br.readLine();



LongestCommonSubsequence obj = new LongestCommonSubsequence(); String result = obj.lcs(str1, str2); System.out.println("\nLongest Common Subsequence dari Kedua DNA adalah : "+ result); } } 2.4. Keluaran Program Permasalahan atau contoh kasus yang diambil untuk menguji program adalah seperti pada permasalahan di atas, dengan String DNA 1 yaitu AGCGA dan String DNA 2 yaitu CAGATAGAG. Output atau keluaran yang dihasilkan ketika program dijalankan adalah seperti screenshot berikut :



2.5. Kompleksitas Algoritma Berikut adalah algoritma LONGEST-COMMON-SUBSEQUENCE



Dari algoritma di atas, kompleksitas nya adalah O(mn). Algoritma di atas akan menentukan subsequence terpanjang dan kemudian menelusuri kembali dengan cara backtracking untuk mendapatkan urutan subsequence terpanjang nya.



2.6. Manualisasi Algoritma dengan Menggunakan Excell Berikut adalah 2 string urutan DNA yang di gunakan dalam mengimplementasikan algoritma LCS (Longest Commong Subsequence) : 



String DNA 1



= AGCGA







String DNA 2



= CAGATAGAG



Untuk mendapatkan hasil LCS dari kedua DNA tersebut digunakan rumus berikut : 0 𝑖𝑓 𝑥 = 0 𝑜𝑟 𝑗 = 0 [ ] 𝑐 𝑖 − 1, 𝑗 − 1 + 1 𝑖𝑓 𝑖, 𝑗 > 0 𝑎𝑛𝑑 𝑥𝑖 = 𝑦𝑗 𝑐[𝑖, 𝑗] = { max(𝑐 [𝑖, 𝑗 − 1], 𝑐 [𝑖 − 1, 𝑗] 𝑖𝑓 𝑖, 𝑗 > 0 𝑎𝑛𝑑 𝑥𝑖 ≠ 𝑦𝑗



Berikut adalah pengimplementasian rumus di atas dalam program excel :



Implementasikan fungsi tersebut kesemua cell untuk mendapatkan Longest Common Sequence dari kedua String DNA di atas. Setelah fungsi tersebut telah di implementasikan ke semua cell yang terkait, maka akan di dapatkan hasil LCS nya, yaitu AGGA.



BAB III PENUTUP Kesimpulan 1. Algoritma longest common subsequence (LCS) adalah algoritma untuk mencari subrangkaian bersama (common subsequence) terpanjang dari beberapa buah rangkaian. 2. Untuk mengukur kemiripan untaian DNA satu dan DNA kedua adalah dengan menemukan untaian DNA ketiga sebagai untaian terpanjang dari kedua untaian, dimana basis pada untaian ketiga muncul di setiap untaian pertama dan kedua. Semakin panjang untaian ketiga yang ditemukan, maka DNA satu dan DNA kedua semakin mirip. 3. Kompleksitas dari algoritma LCS adalah O(mn).