IMPLEMENTASI PENSEJAJARAN GLOBAL SEKUENS DNA MENGGUNAKAN GSA TREE Nama Mahasiswa NRP Jurusan Pembimbing
: : : :
MOCHAMAD SAFI’I 1207100051 Matematika FMIPA-ITS Prof. DR. Mohammad Isa Irawan, MT.
Abstrak Pada Tugas Akhir ini diselidiki masalah pensejajaran global pasangan sekuens DNA. Metode ini terdiri dari 3 bagian: (1) algoritma pensejajaran sederhana, (2) algoritma ekstension untuk substring umum terpanjang, (3) Graphical Simple Alignment Tree (GSA tree) menggunakan penelusuran post-order traversal. Pendekatan pertama mendapatkan sebuah representasi grafis dari skor sekuens DNA dengan persamaan skor R0 ∗ R − S0 ∗ S − Σ(a + bk). Selanjutnya GSA tree akan dibangun untuk menyelesaikan masalah pensejajaran global pasangan sekuens DNA. Untuk Proses validasi digunakan tools EMBOSS pairwise alignment. Pengujian penggunaan parameter gap opening (a=10) dan gap extension (b=0.5) lebih baik dari pada penggunaan parameter gap opening (a=15) dan gap extension (b=1), dengan syarat parameter match R=9 dan mismatch S=1. Kata-kunci: Pairwise Alignment, Pensejajaran Global, Post-order traversal, Struktur Data Tree.
1. Pendahuluan Bioinformatika adalah ilmu yang mempelajari penerapan teknik komputasional untuk mengelola dan menganalisis informasi biologis dengan menerapkan beberapa cabang ilmu lain. Bidang ini mencakup penerapan metodemetode matematika, statistika, dan informatika. Informasi biologi tersebut adalah tentang sekuens DNA, RNA dan Protein. Salah satu cara untuk menganalisis informasi tersebut adalah melalui pensejajaran sekuens (sequence alignment). Sequence alignment juga penting dalam ilmu bioinformatika karena dapat digunakan untuk penelitian penyakit genetik dan epidemi. Misalnya, sequence alignment dapat digunakan untuk menentukan asal, variasi, perkembangan epidemi, untuk menemukan virus dan bakteri penyebab penyakit bahkan dapat digunakan sebagai metode penemuan obat [6]. Oleh karena itu, sequence alignment sangat penting di bidang bioinformatika karena berfungsi sebagai metode prediktif yang kuat. Metode alignment yang berbasis program dinamik pertama kali di usulkan oleh Needleman dan Wunsch yang dikenal dengan algoritma NW (Nedleman-Wunsch). Algoritma ini tidak praktis untuk perhitungan sekuens yang besar karena membutuhkan biaya komputasional yang mahal [1, 3]. Kemudian muncul algoritma heuristik yang lebih cepat dari metode berbasis program dinamik. Dalam penelitian ini akan digunakan pendekatan heuristik untuk mensejajarkan 2 sekuens DNA dengan metode struk-
tur data tree. Metode ini terdiri dari 3 bagian(1) algoritma improved simple alignment , (2) algoritma ekstension untuk substring umum terpanjang, (3) Graphical Simple Alignment Tree (GSA tree) menggunakan penelusuran post-order traversal. Implementasi pada penelitian ini dibuat dalam bahasa pemrograman java. Pemilihan bahasa pemrograman java untuk implementasi pensejajaran global sekuens DNA punya satu alasan yaitu pertimbangan hak cipta intelektual. Sebagaimana diketahui compiler java dengan Netbeans 6.9 merupakan free open source software (FOSS). Berdasarkan latar belakang yang ada, maka rumusan masalah dari tugas akhir ini adalah (1) Bagaimana mengimplementasikan metode struktur data tree pada pensejajaran global sekuens DNA, (2) Bagaimana hasil similaritas, gaps dan skor Pensejajaran Global struktur data tree bila dibandingkan dengan tools EMBOSS pairwise alignment. Batasan masalah dari tugas akhir ini adalah: (1) Data DNA diambil dari Gen Bank, (2) Bahasa pemrograman yang digunakan dalam implementasi penelitian adalah bahasa pemrograman java, (3) Ukuran sekuens maksimal tiga belas ribu base pair. Tujuan dari penelitian ini adalah untuk menghasilkan program yang dapat menentukan hasil pensejajaran global meliputi kesamaan, gaps, dan skor dari 2 sekuens DNA secara akurat menggunakan struktur data tree.
2. Dasar Teori 2.1. Pensejajaran Sekuens DNA adalah rantai double utama dari molekul sederhana yang disebut nukleotida diikat bersama sama dalam sebuah struktur helix yang dikenal sebagai double helix. DNA mempunyai peran sebagai materi genetik yang menyimpan cetak biru segala aktivitas sel. Nukleotidanukleotida dibedakan oleh basa nitrogen yang terdiri dari 4 macam yaitu: Adenosin, Sitosin, Guanin dan Timin. Base pairs adalah satuan umum untuk mengukur panjang DNA. DNA bisa ditentukan secara unix dengan mendaftar sekuens-sekuens nukleotida atau pasangan basa oleh karena itu untuk tujuan praktis DNA diabstraksikan sebagai teks panjang dengan 4 abjad masing-masing mewakili nukleotida yang berbeda A, C, T, dan G [1]. Pensejajaran antara dua sekuens adalah mencari pasangan kecocokan antar karakter pada setiap sekuens. Pensejajaran dari nukleotida atau sekuens asam amino sebenarnya sebagai salah satu penggambaran hubungan evolusi antara 2 atau lebih sekuens homologs (sekuens yang berasal dari nenek moyang yang sama) [2]. Tiga macam perubahan yang dapat terjadi di sebarang posisi dalam sekuens. (1) mutasi yang mengganti karakter dengan yang lain, (2) insersi yang menambah satu atau lebih posisi atau (3) delesi yang menghapus satu atau lebih posisi.
Gambar 1: Proses improved simple alignment (Panjang G1 adalah M. Panjang G2 adalah N dan M ≤ N )
tanpa spasi diantara sekuens. Gambar 1 menunjukkan proses improved simple alignment. Step (1) pada gambar 3 menunjukkan pensejajaran awal yang posisi base pertama G1 overlaps pada base pertama G2 . selanjutnya proses sliding selesai masing-masing sepanjang arah kiri dan kanan. Pertama, anggap proses sliding selesai sepanjang arah kanan yang ditunjukkan di step (2). setiap pensejajaran punya sebuah skor dengan persamaan P skoring R0 ∗ R − S0 ∗ S − (a + bk). kemudian skor Si menjadi skor pada step ke-i. Selanjutnya Smax adalah skor tertinggi dibandingkan dengan semua skor(contoh, Smax = max{S1 , S2 , ..., Si−1 }, i > 1). Untuk setiap step, 0 masih P mendefinisikan skor lain yakni Si = R0 ∗ R + S0 ∗ R− (a+bk). Dalam persamaan skoring di asumsikan semua basis yang cocok overlapped dengan yang lain, proses sliding berhenti ketika Smax ≥ Si0 . Langkah-langkah yang tersisa selanjutnya di sepanjang arah kanan tidak perlu karena semua langkah-langkah yang tersisa tidak memiliki kesempatan untuk mendapatkan skor yang lebih tinggi. Kemudian anggap proses sliding selesai sepanjang arah kiri. Skor tertinggi dengan semua skor dengan semua skor 0 adalah max{Smax , S1 , S2 , ..., Sj−1 Smax P}(J > 1). Persamaan skor Sj0 = R0 ∗ R + S0 ∗ S − (a + bk). Proses 0 sliding berhenti ketika Smax ≥ Sj0 .
2.2. Persamaan Penskoran berdasarkan matriks Penskoran Pensejajaran terbaik sangat bergantung pada persamaan penskoran dan parameter-parameter penskoran yang digunakan, yaitu bagaimana memberikan skor pada setiap kecocokan, ketidakcocokan dan gap. Matriks skoring dalam pensejajaran sekuens DNA ini relatif sederhana, yaitu setiap kecocokan ditandai dengan skor R positif (R > 0). Selanjutnya ketidakcocokan ditandai dengan skor S positif (S > 0). tetapi skor S harus dikurangi dari skor total pada sebuah pensejajaran. Untuk gaps dalam hal ini dibedakan menjadi dua yaitu gap open (a) dan gap ekstension (b). Biaya untuk gap open lebih besar daripada biaya untuk gap extension (a > b) [4]. Terdapat cara untuk menghitung biaya penalty untuk sebuah gaps pada n posisi adalah a + (n − 1) ∗ b, dimana a adalah gaps open penalty dan b adalah gaps extension penalty. Misalkan k = (n − 1), maka persamaan penskoran R0 ∗ R − S0 ∗ S − Σ(a + bk), dengan R adalah skor untuk setiap kecocokan, S skor untuk setiap ketidakcocokan dan (a + bk) adalah skor setiap gaps, parameter R0 dan S0 masing-masing menunjukkan menunjukkan jumlah total kecocokan dan jumlah total ketidakcocokan [3].
2.4. Algoritma Perluasan untuk Substring Umum Terpanjang. Dengan algoritma pensejajaran sederhana R yang baik dari G1 dan G2 ditentukan saat skor pensejajaran sederhana menghasilkan nilai yang maksimum. Misalkan C adalah substring umum terpanjang di R, dengan C = φ∪{C1 , C2 , C3 , . . . , Cm }. Jika C = φ, maka tidak terdapat substring terpanjang di R. Jika C = C1 , C2 , C3 , . . . , Cm , maka terdapat m substring terpanjang di R. Dengan C1 = C2 = . . . = Cm = k dan k menunjukkan banyaknya kecocokan pada substring terpanjang. Algoritma perluasan untuk substring umum terpanjang adalah sebagai
2.3. Algoritma Improved simple alignment Misalkan terdapat dua sekuens primer DNA: G1 (g1 g2 g3 . . . gM ) dan G2 (g1 g2 g3 . . . gN ), dimana M dan N masing-masing menunjukkan panjang dari G1 dan G2 . Algoritma ini membangun semua kemungkinan pensejajaran 2
berikut [3]:
umum terpanjang pada G1 dan G2 adalah “TCCCCCA”dengan panjang K adalah 7. Jelas, bahwa terdapat sedikitnya sebuah substring umum yang lebih panjang daripada “GCCT”atau “GCCC”. Untuk “GCCT”, dua subsekuens baru masing-masing “GCCTAGTTC”(S11 ) dan “GCCTCGCAT”(S12 ). karena tidak terdapat kenaikan tajam sunstring umum asli “GCCT”(C1 ) tidak berubah. Untuk “CCCC”, dua subsekuens baru masing-masing “AGTTCCCCCA”(S21 ) dan “CGCATCCCCCA”(S22 ) Karena terdapat kenaikan tajam, substring umum asli “CCCC”C2 diganti dengan substring umum yang terpanjang “TCCCCCA”. Untuk tambahan, algoritma extension untuk substring umum terpanjang melindungi substsring umum yang lebih panjang Ci Dari pemotongan oleh Ci . Sekarang diberikan U adalah substring yang dipisahkan oleh Ci , dimana U = φ{U1 , U2 , ..., Un }. Selanjutnya, String G1 dan G2 disejajarkan kedalam 2 tipe substring: (i) substring umum terpanjang C dengan kecocokan berlanjut : G1 [i] = G2 [i] (tentunya, kecocokan tunggal juga diizinkan) dan (ii)substring U dengan ketidakcocokan berlanjut G1 [i] = G2 [i] dan keduanya tanpa gap. Pensejajaran sederhana yang baik R pada G1 dan G2 ini secara bergantian di atur oleh C dan U (contoh R = C11 , U21 , C31 , U41 , dimana |C11 | = |C31 |. Disini superscript pada C atau U menunjukkan level sunpensejajaran. superscript “1”menunjukkan level pertama. Subscript menunjukkan indeks substring di subpensejajaran saat ini. pensejajaran R adalah hasil pada level pertama subpensejajaran). Untuk menjelaskan parameter diatas, diberikan contoh praktis. terdapat 2 sekuens acak:G1 (GCCTAGTTCCCCCA) dan G2 (GCCTCGCATCCCCCA). G1 [i] = G2 [i] masingmasing menunjukkan basis pada G1 dan G2 . menjadi kecocokan ketika G1 [i] = G2 [i]. dengan algoritma pensejajaran sederhana , pensejajaran sederhana R yang baik pada G1 dan G2 dapat ditentukan. Pensejajaran R adalah GCCTAGTTCCCCCA GCCTCGCATCCCCCA Algoritma extension substring umum yang terpanjang C pada R adalah “GCCT”dan “TCCCCCA”. selanjutnya G1 dan G2 diatur oleh C kedalam 3 substring: C11 adalah “GCCT”, U21 “AGT”dan “CGCA”, C31 adalah “TCCCCCA”.
1. Misalkan K adalah panjang dari substring umum terpanjang di G1 dan G2 . Nilainya didapatkan saat algoritma pensejajaran sederhana dilakukan pada sekuens G1 dan G2 2. Ketika k = K, tidak ada substring terpanjang Ci pada R yang dapat diperluas menjadi substring terpanjang. Substring terpanjang di R adalah C1 , C2 , . . . , Cm 3. Ketika k < K, terdapat paling sedikit sebuah substring yang lebih panjang dari Ci .Terdapat beberapa sub-step untuk mencari substring yang lebih panjang , yaitu : a. Misalkan Ll adalah banyaknya ketidakcocokan (mismatches) dari ujung kanan Ci−1 sampai ujung kiri Ci . Saat i = 1, Ll menunjukkan banyaknya mismatches dari ujung kiri G1 dan G2 sampai ujung kiri C1 . Demikian juga sebaliknya, Misalkan Lr adalah banyaknya mismatches dari ujung kanan Ci sampai ujung kiri Ci+1 . Saat i = 1, Lr menunjukkan banyaknya mismatches dari ujung kanan C1 sampai ujung kanan pada G1 dan G2 b. Ketika K < Ll , K yang mismatches diekstrak dari kiri pada Ci . Sebaliknya jika K ≥ Ll , Ll yang mismatches diekstrak dari kiri pada Ci . Sama ketika K < Lr , K yang mismatches diekstrak dari kanan pada Ci . Sebaliknya jika K ≥ Lr , Lr yang mismatches diekstrak dari kanan pada Ci . Kemudian sekuens diekstrak dari kiri pada Ci , Ci dan dari kanan Ci dihubungkan dua sub-sekuens Si1 dan Si2 . c. Selanjutnya, diterapkan algoritma pensejajaran sederhana untuk Si1 dan Si2 . Jika terdapat substring umum baru yang lebih panjang dalam Si1 dan Si2 daripada Ci , terdapat pilihan substring umum yang lebih panjang atau Ci . Jika ada kenaikan tajam(sore) saat substring lebih panjang yang baru menjadi ada, maka Ci asli akan diganti dengan substring baru yang juga disebut sebagai Ci . 4. Sehingga setiap Ci pada R, Ci asli digantikan oleh substring umum terpanjang baru, jika substring baru ada
2.5. Graphical Simple Alignment Tree (GSA tree) Diberikan sekuens G1 dan G2 , sebuah GSA tree dibangun dengan algoritma pensejajaran sederhana dan algoritma perluasan untuk substring umum terpanjang. Diberikan R sebagai pensejajaran sederhana yang baik dari G1 dan G2 . Misalkan Ci1 dan Uj1 substring umum terpanjang dari R. Dapat dilihat bahwa substring terpanjang Ci1 dari R menunjukkan skor maksimal untuk pensejajaran global. Tetapi, Uj1 dari R menyediakan sebuah kenaikan skor pada pensejajaran global jika diberikan gaps yang sesuai dengan Uj1 , walaupun skor Uj1 lebih rendah dalam level pertama sub-alignment. Berikut langkahlangkah dari algoritma GSA tree [3]:
Akan diberikan contoh praktis untuk menjelaskan step diatas. Terdapat 2 sekuens acak misalkan : G1 (GCCTAGTTCCCCCA) dan G2 (GCCTCGCATCCCCCA). Dengan algoritma pensejajaran sederhana, pensejajaran R yang baik di G1 dan G2 dapat ditentukan, dimana pensejajaran R adalah : GCCTAGTTCCCCCA GCCTCGCATCCCCCA Substring umum terpanjang C pada R adalah “GCCT”(C1 ) dan “CCCC”(C2 ). Namun, substring 3
1. Hitung skor dari semua pensejajaran sederhana dari Uj1 menggunakan algoritma pensejajaran sederhana. Sebuah pensejajaran sederhana yang baik Rj1 pada Uj1 dipilih ketika skor nya maksimal 2. Jika terdapat kenaikan skor karena gaps yang sesuai dalam Uj1 , Uj1 dibagi menjadi sub-alignment level kedua. Misalkan Ci2 sebagai substring terpanjang dari 2 2 2 2 Rj1 , dimana Ci2 = φ ∪ {Ci+1 , Ci+2 , Ci+3 , . . . , Ci+m }. Kemudian ada 2 sub tahap : 2 2 2 2 }, ter, . . . , Ci+m , Ci+3 , Ci+2 a. jika Ci2 = {Ci+1 dapat m substring umum terpanjang. Kemudian Uj1 dibagi menjadi sub-alignment level kedua dengan Ci2 . Diberikan Uj2 adalah substring yang terpisah oleh Ci2 , dimana Uj2 = 2 2 2 2 φ ∪ {Uj+1 , Uj+2 , Uj+3 , . . . , Uj+m }. Kemudian se2 tiap substring Ci+k (k = 1, 2, . . . , n) dari Ci2 menjadi node daun dalam GSA tree. Untuk se2 tiap substring Uj+k (k = 1, 2, . . . , n) dari Uj2 , arah operasi kembali ke tahap 1.
Gambar 2: Notasi untuk general trees. Node P adalah parent dari node V , S1 dan S2 . Selanjutnya V, S1 dan S2 adalah anak dari P . Node R dan P adalah ancestors dari V . V , S1 dan S2 disebut siblings .
2.6.1. Kunjungan pada general tree Jenis-jenis kunjungan pada general tree adalah postorder dan preorder. Kunjungan preorder pada general tree dilakukan dengan mengunjungi root pada tree kemudian mengunjungi subtree dari ujung kiri ke kanan. Kunjungan postorder merupakan kunjungan yang dilakukan mulai dari node-node turunan pada subtree kiri ke kanan, kemudian root. Kunjungan Inorder tidak mempunyai definisi murni pada general tree, karena tidak terdapat jumlah anak tertentu untuk sebuah node dalam. namun dari definisi sembarang yakni mengunjungi subtree paling kiri di inorder, root, kemudian mengunjungi subtree yang tersisa. Kunjungan preorder pada pohon di gambar
b. Jika Ci2 = φ, maka tidak ada substring terpanjang di Rj1 . Kemudian Uj1 tidak bisa dipecah lagi. Sebuah pensejajaran sederhana Rj1 yang baik dari Uj1 menjadi node daun di GSA tree. Dua sekuens dari Rj1 mungkin seluruhnya overlapping atau sebagian overlapping. Ketika dua sekuens dari Rj1 seluruhnya overlapping maka tidak terdapat gap dalam Rj1 . Sebaliknya ujung yang menggantung dari overlap menjadi gaps dari Rj1 . Posisi relatif dari gaps ini tidak ditentukan, dan menjadi gap-gap dalam pensejajaran global akhir Tahap-tahap diatas berulang sampai semua U dalam level terakhir sub-alignment tidak bisa dibentuk oleh algoritma pensejajaran sederhana dan algoritma perluasan untuk substring umum terpanjang.
Gambar 3: Contoh general tree
2.6. General tree Tree T adalah himpunan berhingga dari satu atau lebih node, misalkan sebuah node R, disebut root T jika himpunan (T − R) tidak kosong, node ini dipartisi menjadi T0 , T1 , T2 , . . . , Tn−1 subset terpisah. Setiap Tn adalah tree dengan root-root R1 , R2 , R3 , . . . , Rn yang masing masing adalah anak dari R. Subset Ti (0 ≤ i < n) disebut subtree dari T . Subtree ini tersusun dalam Ti sebelum Tj jika i < j. Dengan aturan, subtree yang disusun dari kiri ke kanan dengan subtree T0 disebut anak paling kiri dari R [5]. Setiap node dalam tree mempunyai tepat satu parent, kecuali node root yang tidak mempunyai parent. Dapat dikatakan bahwa tree dengan n node akan mempunyai (n − 1) edges. Karena setiap node, selain root mempunyai sebuah edge yang menghubungkan node ke parent nya [5]. Di gambar 2 menunjukkan contoh dari general tree
3 adalah RACDEBF . sedangkan kunjungan postorder adalah CDEAF BR. 2.6.2. Implementasi Dinamis Left-Child/Right-Sibling Impelementasi ”left-child/right-sibling” menyimpan jumlah pointer yang tetap untuk setiap nodenya. Ini dapat dengan mudah diadaptasi untuk implementasi dinamis. Pada dasarnya kita ganti sebuah binari tree untuk general tree. Anak kiri dari binari tree adalah anak kiri pertama dalam general tree, sedangkan anak kanan binari tree adalah sibling kanan pada general tree [5]. Implementasi pada gambar 4 hanya membutuhkan 2 pointer per node. Karena setiap node dari general tree berisi sejumlah pointer tetap dan karena masing-masing fungsi ADT pohon umum sekarang dapat diimplementasikan secara 4
FASTA dari GenBank (Sebuah repositori gratis yang menyediakan informasi DNA dari seluruh makhluk hidup). Informasi masukan adalah nukleotida (DNA). dalam kasus ini setelah informasi sekuens diberikan aplikasi akan otomatis dapat mengenali tipe DNA atau bukan. Dan sistem dapat meload data dalam bentuk FASTA, format FASTA dapat dilihat pada gambar 7. Format FASTA diawali dengan 1 baris deskripsi diikuti dengan baris data sekuens. Baris deskripsi dipisahkan dari data urutan dengan simbol (”>”). Kata setelah simbol ”>” adalah identifier dari sekuens, dan sisanya yang dipisahkan oleh spasi berupa keterangan. 2. Memproses sekuens. Aktor pengguna memproses dua sekuens pada aplikasi. User memilih nilai-nilai parameter kecocokan, ketidakcocokan, gap opening, dan gap extension. Kemudian user menekan tombol proses yang akan mengirim 2 sekuens untuk disejajarkan dengan algoritma GSA tree. 3. Lihat hasil pensejajaran. Aktor pengguna menginginkan melihat hasil dari pensejajaran dalam bentuk grafis yang berupa similaritas, gaps , dan skor serta letak gap dari kedua sekuens DNA.
Gambar 4: implementasi dinamis left-child/right-sibling
efisien. Implementasi dinamis ”leftchild-rightsibling” lebih disukai daripada implementasi general tree lainnya. 2.7. Pensejajaran global berdasarkan GSA tree
Gambar 5: contoh GSA tree
Dari contoh GSA tree pada gambar 5, dapat dilihat bahwa ada 2 tipe dari node yaitu node dalam (inner node) dan node daun (leaf node). Node dalam terdiri dari substring U yang bisa dipecah menjadi beberapa substring. Node daun termasuk substring C dan U . Dimana U tidak bisa lebih dipecah lagi dengan GSA tree. Untuk mendapatkan pensejajaran global dari string G1 dan G2 menggunakan post order traversal. Kemudian semua node-node dalam dihapus dari hasil post order traversal, selanjutnya akan dicapai pensejajaran global dari string G1 dan G2 . Contoh hasil post order traversal dari gambar 5 adalah C12 U13 C23 U22 C32 U11 C21 U42 C52 U31 C41 U62 C72 C33 U43 U82 U51 C61 . Kemudian dengan menghapus node dalam di dapat pensejajaran global G1 dan G2 C12 U13 C23 C32 C21 U42 C52 C41 U62 C72 C33 U43 C61 .
Gambar 6: Use case Diagram
3. Perancangan dan Implementasi Sistem Gambar 7: Sekuens dengan format FASTA
3.1. Use Case Diagram Dalam sub bab ini akan dijelasakan diagram use case untuk sistem pensejajaran sekuens DNA dengan GSA tree. Dari identifikasi permasalahan sebuah aktor ditentukan. Sistem hanya mempunyai satu aktor yaitu pengguna yang akan melakukan pensejajaran sekuens DNA. Dari gambar 6 terlihat 3 use case yaitu :
3.2. Class diagram Class diagram keseluruhan dari sistem ditunjukkan pada gambar 8. Terdapat 16 class yang masing-masing mempunyai fungsi tersendiri. Proses pensejajaran sekuens DNA pertama kali dilakukan pada kelas Frameutama kemudian di cek di kelas Controller kemudian jika data valid maka proses selanjutnya berada di kelas ModelGSAtree yang akan memproses 3 algoritma yaitu algoritma improved simple alignment, algoritma Extension, dan GSA
1. Input sekuens. Aktor pengguna memasukkan informasi berupa sekuens DNA ke dalam aplikasi. Input data dapat berupa sekuens DNA yang berbentuk teks atau juga dapat juga membaca format data berupa 5
tree. Setelah dari kelas ModelGSAtree kemudian di kembalikan lagi ke kelas FrameUtama melalui interface ListenerMUtama.
Gambar 9: Rancangan Antar Muka Form Pensejajaran
18
Gambar 8: Class diagram 19 20
3.3. Perancangan Antar Muka Sistem Desain antarmuka sistem melihat dari tools emboss dikarenakan tools emboss sudah sangat dikenal oleh khalayak ramai khususnya peneliti yang biasa mensejajarkan sekuens DNA, sehingga bila orang lain memakai tools GSA tree ini tidak terlalu kesulitan walaupun ada perbedaan dalam penentuan penskoran yang di emboss dan di GSA tree.
21
22 23 24 25 26 27 28 29
30
3.4. Implementasi Algoritma GSA tree 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17
p u b l i c v o i d g s a t r e e ( S t r i n g G1 , S t r i n g G2) { i n t i =0; l e v e l =0; runWaktu ( ) ; // c a t a t waktu mulai i f ( i ==0){ i n s e r t r o o t b a r u (G1 , G2) ; } do { tahap1GSA (G1 , G2) ; i f ( ! C . isEmpty ( ) ) { inserttree () ; tree . ubahposisiroot () ; // j i k a G1 dan G2 sama i f (G1 . e q u a l s ( t r e e . g e t C u r r ( ) . v a l u e ( ) . getG1 ( ) ) && G2 . e q u a l s ( t r e e . g e t C u r r ( ) . v a l u e ( ) . getG2 ( ) ) ) { break ; } G1=t r e e . g e t C u r r ( ) . v a l u e ( ) . getG1 ( ) ; G2= t r e e . g e t C u r r ( ) . v a l u e ( ) . getG2 ( ) ;
31
32 33 34 35 36 37 38 39 40
41
42 43 44 45 46 47 48
6
} e l s e { // C kosong ukuran U=1 , U t i d a k dapat dipecah // U1 l e b i h panjang d a r i U2 i f (U1 . g e t ( 0 ) . t r i m ( ) . l e n g t h ( )>U2 . g e t ( 0 ) . t r i m () . length () ){ i n t s e l i s i h =U1 . g e t ( 0 ) . t r i m ( ) . l e n g t h ( )−U2 . get (0) . trim ( ) . length ( ) ; S t r i n g lama=U2 . g e t ( 0 ) ; S t r i n g tambah=” ” ; f o r ( i n t j =0; j < s e l i s i h ; j ++){ tambah+=”−” ; // tambahkan gap } U2 . s e t ( 0 , lama+tambah ) ; } //U2 l e b i h panjang d a r i U1 i f (U2 . g e t ( 0 ) . t r i m ( ) . l e n g t h ( )>U1 . g e t ( 0 ) . t r i m () . length () ){ i n t s e l i s i h =U2 . g e t ( 0 ) . t r i m ( ) . l e n g t h ( ) −U1 . get (0) . trim ( ) . length ( ) ; S t r i n g lama = U1 . g e t ( 0 ) . t r i m ( ) ; S t r i n g tambah=” ” ; f o r ( i n t j =0; j < s e l i s i h ; j ++){ tambah+=”−” ; // tambahkan gap } U1 . s e t ( 0 , lama+tambah ) ; } s e k u e n s= new Sekuens ( ) ; s e k u e n s . setG1 (U1 . g e t ( 0 ) ) ; s e k u e n s . setG2 (U2 . g e t ( 0 ) ) ; t r e e . UpdateU (U1 . g e t ( 0 ) , U2 . g e t ( 0 ) ) ; // update i s i node t r e e . u b a h p o s i s i r o o t 2 ( ) ; // c a r i r o o t selanjutnya G1=t r e e . g e t C u r r ( ) . v a l u e ( ) . getG1 ( ) ; G2= t r e e . g e t C u r r ( ) . v a l u e ( ) . getG2 ( ) ; } clear () ; } w h i l e ( t r e e . g e t C u r r ( ) . p a r e n t ( ) != n u l l ) ; // l a k u k a n sampai r o o t a w a l p a r e n t n y a n u l l stopWaktu ( ) ; // c a t a t waktu s e l e s a i
tampil () ;
49 50
} Tabel 1: Semua Substring dan skor maksimal Gambar 10: Kode Program Algoritma GSA tree
Level level 1
Parent G1 , G2
4. Uji Coba dan Pembahasan pada bab ini akan dibahas mengenai uji coba proses dan uji coba program yang telah diimplementasikan sebelumnya. perangkat keras yang digunakan dalam uji coba adalah komputer dengan Processor Intel Pentium Dual Core 2,16 GHz, Memory DDRAM 1 GB, Hardisk 120 GB, VGA on Board 256 MB. Sedangkan perangkat lunak yang digunakan adalah Sistem Operasi Linux UBUNTU 10.10, dan bahasa pemrograman Java serta IDE NETBEANS 6.9. Terdapat 2 sekuens DNA G1 dan G2 masing-masing : G1 =AATCACACAGATCTAACAGGATTATTTC G2 =TATTACACAAATCTTAACAGGACTATTTC parameter gapopening=15 dan gapextension=1. Panjang masing-masing 28 bp dan 29 bp. Hasil dari improved simple alignment didapatkan skor maksimum 127 dengan pensejajaran R :
level 2
U11 (G1 ) U11 (G2 )
U31 (G1 ) U31 (G2 )
level 3
U12 (G1 ) U12 (G2 )
U32 (G1 ) U32 (G2 )
-AATCACACAGATCTAACAGGATTATTTC |.|.....|....||||||||.|||||| TATTACACAAATCTTAACAGGACTATTTC
Substring U11 (G1 )=AATCACACAGATC U11 (G2 )=TATTACACAAATCT C21 (G1 ) = C21 (G2 )=TAACAGGA U31 (G1 )=TTATTTC U31 (G2 )=CTATTTC
SM 72
U12 (G1 )=AATC U12 (G2 )=TATT C22 (G1 ) = C22 (G2 )=ACACA U32 (G1 )=GATC U32 (G2 )=AATCT U42 (G1 )=T U42 (G2 )=C C52 (G1 ) = C52 (G2 )=TATTTC
16
U13 (G1 )=A U13 (G2 )=T C23 (G1 ) = C23 (G2 )=AT U33 (G1 )=C U33 (G2 )=T U43 (G1 )=G U43 (G2 )=A C53 (G1 ) = C23 (G2 )=ATC U63 (G1 )= U63 (G2 )=T
-1
72 53
45 11 -1 54
18 -1 -1 27 -15
Keterangan : • Substring umum terpanjang C1 =TAACAGGA dengan k=8.
C
di
R
adalah
• substring umum terpanjang di G1 dan G2 adalah TAACAGGA dengan K=8.
String G1 dan G2
Selanjutnya di algoritma extension. karena k=K maka tidak ada substring umum yang lebih panjang maka C tetap tidak berubah. Berikut adalah tabel data semua substring dan skor maksimum dari setiap step pensejajaran ditiap level yang dapat dilihat pada tabel 1, Sedangkan representasi bentuk tree nya dapat dilihat pada gambar 11. Pada gambar 11 terlihat bahwa string G1 dan G2 terdiri dari 3 substring di level pertama sub-pensejajaran yaitu: U11 C21 U31 . Substring U11 terdiri dari 3 substring di level kedua sub-pensejajaran yaitu: U12 C22 U32 . Substring U31 terdiri dari 2 substring di level kedua sub-pensejajaran yaitu: U12 C22 . Substring U12 terdiri dari 3 substring di level ketiga sub-pensejajaran yaitu:U13 C23 U33 . Substring U32 terdiri dari 3 substring di level ketiga sub-pensejajaran yaitu: U43 C53 U63 . Sehingga Hasil pensejajaran globalnya adalah: U13 C23 U33 C22 U43 C53 U63 C21 U42 C52 .
U11
U12
U13
Hasil dalam program GSA tree dapat dilihat pada gambar 12. Panjang didapatkan dari panjang sekuens masing-masing ditambah dengan gap yang ada di masing-masing sekuens. Presentase similaritas (similarity) didapatkan dari jumlah kecocokan dibagi dengan panjang. Sedangkan presentase gaps didapatkan dari jumlah gaps dibagi dengan panjang. Skor
C23
C21
C22
U33
U32
U43
C53
U31
U42
C52
U63
Gambar 11: GSA tree dalam mensejajarkan sekuens G1 dan G2 (G1 , AATCACACAGATCTAACAGGATTATTTC; G2 , TATTACACAAATCTTAACAGGACTATTTC)
7
Tabel 3: Tabel Hasil percobaan II
Tabel 2: Tabel Hasil Percobaan I
Parameter a=15 b=1
GSA tree
a=10 b=0.5
Jemboss
a=10 b=0.5
Parameter a=15 b=1
GSA tree
a=10 b=0.5
Jemboss
a=10 b=0.5 a=10 b=0.5
EMBOSS
Gambar 12: Hasil Pensejajaran contoh 3 program GSA tree
Program GSA tree
Program GSA tree
Percobaan (I) length: 7526 similarity: 4220 (56.07) % gaps: 618 (8.21) % skor: 32126.0 length: 7859 similarity:4551 (57.9) % gaps: 1284 (16.337) % skor: 33552.5 length: 8266 similarity:4696 (56.8) % gaps: 2098 (25.4) % skor: 11547.0
Percobaan (II) length: 13862 similarity: 11312 (81.6) % gaps: 398 (2.87) % skor: 97788.0 length: 13963 similarity:11457 (82.05) % gaps: 600 (4.297) % skor: 98874.0 Died: Sequences too big. length: 13987 similarity:11620 (83.1) % gaps: 648 (4.6) % skor: 49003.0
dikarenakan data terlalu besar yang berarti memori yang digunakan harus lebih besar daripada memori yang terdapat pada komputer. Dari hasil simiritas pada percobaan II menunjukkan bahwa terdapat selisih presentase yang kecil bila dibandingkan dengan EMBOSS (needle) untuk gap open=15 dan gap extend=1 selisih presentase sebesar (83.1 -81.6) %= 1.5 % sedangkan untuk gap open=10 dan gap extend=0.5 selisih presentase sebesar (83.1 -82.05) %= 1.05 %. Selanjutnya dilakukan perbandingan menggunakan sekuens yang kecil untuk mengamati letak perbedaan gap antara Jemboss (needle) dengan GSA tree. Sekuens pertama (G1 ) dengan kode accession GY272635.1 sebagai Sequence 32 from patent US 7968697 dan sekuens kedua (G2 ) dengan kode accession GY272636.1 sebagai Sequence 33 from patent US 7968697 . G1 (ACCGAGCACCCAGGTAGGCGTGACGACCTCCAG) dan G2 (CTGGAGGTCGTCCGCGGTACCTGGGTGCTCGTT) P dengan menggunakan persamaan skor R0 ∗R−S0 ∗S− (a+bk), dengan parameter R = 9, S = 1, a = 15, dan b = 1. Hasil pensejajaran global dari algoritma GSA tree sebagai berikut:
P didapatkan dari hasil penskoran R0 ∗ R − S0 ∗ S − (a + bk). Lamanya waktu didapatkan dari selisih antara waktu selesai dengan waktu mulai. Untuk Percobaan pertama (I) Data sekuens yang diambil dari Gen bank adalah NC 014956.1 sebagai Human papillomavirus type 134, complete genome dan NC 014955.1 sebagai Human papillomavirus type 132, complete genome. Sedangkan untuk percobaan kedua (II) adalah NC 003416.2 sebagai Necator americanus mitochondrion, complete genome dan NC 003415.1 sebagai Ancylostoma duodenale mitochondrion, complete genome. Percobaan pada program GSA tree dilakukan dengan menggunakan parameter match=9 dan mismatch=1 sedangkan gap open (a) yang digunakan adalah 15 dan 10 sedangkan gap extension (b) yang digunakan adalah 1 dan 0.5. Selanjutnya untuk Jemboss dilakukan dengan menggunakan setting default dari EMBOSS (Needle) yaitu Matrix: DNAfull, gap open=10 dan gap extend=0.5. Hasil pada percobaan pertama dapat dilihat pada 2. Sedangkan hasil pada percobaan kedua dapat dilihat pada 3 Dari percobaan 1 menunjukkan bahwa tingkat similaritas GSA tree dengan gap open=10 dan gap extend=0.5 yaitu sebesar 57.9 % mendekati dengan hasil pada tools emboss sebesar 56.8 % . Sedangkan dari percobaan 2 dengan gap open=10 dan gap extend=0.5 sebesar (82.05) % mendekati dengan hasil pada tools Jemboss sebesar (83.1)%. Sedangkan pada percobaan II Jemboss tidak dapat mensejajarkan sekuens
######################################## # Program: GSA tree # Mulai: Jul 8, 2011 1:54:17 AM # Selesai: Jul 8, 2011 1:54:17 AM # Lamanya waktu: 0.002 detik ######################################## #======================================= # 1: # 2: # Match: 9 # Mismatch: 1 # Gap_open: 15 # Gap_extend: 1.0 # # length: 38 # similarity: 16 (42.10526315789474) % # gaps: 10 (26.31578947368421) % # skor: 80.0 #
8
# Score: 19.5 # # #=======================================
# #======================================= ACCGAGCA---CCCAGGTAG--GCGTGACGACCTCCAG ...|||.. ||..||||. |.||| |||... CTGGAGGTCGTCCGCGGTACCTGGGTG-----CTCGTT
33
1 ACCGAGCACCCAGGTAGG-CGTGACG----ACCTCCAG---------|.|| ||| ||| .|| |||| | 1 ----------CTGG-AGGTCGT-CCGCGGTACCT---GGGTGCTCGTT
33
#--------------------------------------#--------------------------------------Selanjutnya digunakan parameter yang sama untuk match dan mismatch masing-masing R = 9 dan S = 1, sedangkan gap open (a=10) dan gap extension (b=15). Diperoleh hasil pensejajaran sebagai berikut :
#--------------------------------------#--------------------------------------Dari hasil terlihat bahwa pada Jemboss jumlah kecocokan sama dengan GSA tree dengan parameter a=15 dan b=1 sejumlah 16 tetapi menghasilkan jumlah gap berbeda masing-masing 30 dan 10 dengan similaritas pada Jemboss sebesar 33.3 % dan GSA tree sebesar 42.1 %. Selanjutnya dengan parameter a=10 dan b=0.5 pada GSA tree jumlah kecocokan sebanyak 18, jumlah gap 12, dan similaritasnya sebesar 46.5(%). Terlihat bahwa GSA tree dengan a=10 dan b=0.5 menghasilkan pensejajaran yang lebih optimal daripada GSA tree dengan a=15 dan b=1 maupun dengan Jemboss.
######################################## # Program: GSA tree # Mulai: Jul 8, 2011 2:01:25 AM # Selesai: Jul 8, 2011 2:01:25 AM # Lamanya waktu: 0.002 detik ######################################## #======================================= # 1: # 2: # Match: 9 # Mismatch: 1 # Gap_open: 10 # Gap_extend: 0.5 # # length: 39 # similarity: 18 (46.15384615384615) % # gaps: 12 (30.76923076923077) % # skor: 99.5 # # #======================================= ACCGAG--CACCCA-GGTA---GGCGTGACGACCTCCAG ...||| |..||. |||| || ||| |||... CTGGAGGTCGTCCGCGGTACCTGG-GTG-----CTCGTT
5. KESIMPULAN DAN SARAN 5.1. Kesimpulan 1. Pengujian penggunaan parameter gap opening (a=10) dan gap extension (b=0.5) lebih baik dari pada penggunaan parameter gap opening (a=15) dan gap extension (b=1), dengan syarat parameter match R=9 dan mismatch S=1. 2. Algoritma GSA tree yang menerapkan metode heuristik ini tidak selalu dapat menghasilkan pensejajaran global yang optimal hal ini dipengaruhi oleh inisialisasi awal pensejajaran sekuens dan pemilihan parameter. 3. Perbandingan similaritas antara GSA tree dan Jemboss tidak terlalu jauh tetapi kadang-kadang similaritas Jemboss bisa lebih besar daripada GSA tree tapi juga bisa Jemboss lebih kecil daripada GSA tree. 4. Untuk sekuens besar yang ukurannya ± 13000 bp Jemboss tidak dapat mensejajarkan sekuens sedangkan pada GSA tree dapat mensejajarkan.
33 33
#--------------------------------------#---------------------------------------
5.2. Saran Kemudian digunakan Jemboss untuk menghitung hasil dari pensejajaran menggunakan sekuens sama, dengan menggunakan matrik DNAfull, a=10 dan b=0.5. Didapatkan hasil sebagai berikut :
Berdasarkan hasil yang sudah dicapai pada penelitian ini, terdapat beberapa hal yang perlu dipertimbangkan untuk pengembangan penelitian ini, antara lain sebagai berikut : 1. Untuk penelitian selanjutnya penggunaan algoritma GSA tree dapat diterapkan tidak hanya pada sekuens DNA, melainkan dapat juga digunakan untuk protein. 2. Perlu dilakukan percobaan lebih untuk menentukan parameter-parameter yang lebih cocok dari parameterparameter yang digunakan untuk mendapatkan pensejajaran yang lebih optimal. 3. Untuk penelitian selanjutnya algoritma GSA tree tidak hanya terbatas pada pensejajaran 2 sekuens saja melainkan dapat digunakan pada pensejajaran lebih dari 2 sekuens (multiple alignment). 4. Untuk perhitungan biaya running time perlu dilakukan penelitian selanjutnya khususnya masalah perhitungan do-while.
#======================================= # # Aligned_sequences: 2 # 1: # 2: # Matrix: EDNAFULL # Gap_penalty: 10.0 # Extend_penalty: 0.5 # # Length: 48 # Identity: 16/48 (33.3%) # Similarity: 16/48 (33.3%) # Gaps: 30/48 (62.5%)
9
33 33
References [1] Annibal, S. (2003). Sequence Alignment Algorithms. Advanced Computing. London: Department of Computer Science School of Physical Sciences and Engineering King’s College. [2] Krane, D. E., & Raymer, M. L. (2003). Fundamental Concepts of Bioinformatics. San Francisco: Pearson Education, Inc. [3] Qi, Z.-H., Qi, X.-Q., & chen Liu, C. (2010). New method for global alignment of 2 dna sequences by the treedata structure. Theoretical Biology, 263 , 227–236. [4] Rosenberg, M. S. (2009). Sequence Alignment Methods Models Concepts and Strategies. London: University of California Press. [5] Shaffer, C. A. (2011). A Practical Introduction to Data Structure and Algoritma Analysis volume 3.1 of Java Version. Blacksburg: Department of Computer Science Virginia Tech. [6] Shen, S. N., & Tuszynski, J. A. (2008). Theory and Mathematical Methodes for Bioinformatics. San Francisco: Springer Vierlag.
10
