IMPLEMENTASI SUPER PAIRWISE ALIGNMENT PADA GLOBAL ALIGNMENT UNTUK SEKUENS DNA Nama Mahasiswa : Arfan Pantua NRP : 1207100704 Jurusan : Matematika FMIPA-ITS Pembimbing : Prof. DR. Mohammad Isa Irawan, MT.
Abstrak Analisis sekuen adalah inti dari bioinformatika, sedangkan pensejajaran sekuen adalah hal mendasar dalam analisis sekuen. Pemograman dinamis adalah algoritma yang sering digunakan dalam pensejajaran sekuen. Sekalipun algoritma ini menghasilkan keselarasan yang optimal namun butuh perhitungan yang lama karena kompleksitas dalam perhitungan. Untuk mengurangi kompleksitas tanpa menghilangkan akurasi, diusulkan metode Super Pairwise Alignment untuk mensejajarkan dua sekuen. Tetapi pada saat ini masih kesulitan mendapatkan software yang mengimplementasikan metode Super Pairwise Alignment (SPA) tersebut. Dalam tugas akhir ini akan diimplementasikan metode SPA dalam pensejajaran sekuen dengan tools yang digunakan untuk validasi adalah tools JEmboss. Pengujian dengan SPA menggunakan parameter sekuen lokal (a=100), θ = 0.5 dan θ0 = 0.6 mendekati hasil pada JEmboss dengan parameter yang digunakan gap opening (a=100) dan gap extension (b=10). Keywords: Super Pairwise Alignment, Pensejajaran Global, Analisis Probabilitas
1. Pendahuluan Salah satu pengenalan spesies pada bioinformatika yaitu melalui pensejajaran sekuens (sequence alignment). Pada permasalahan mutasi sekuens, solusi untuk pensejajaran sekuens dapat menggunakan program dinamik. Algoritma alignment berbasis program dinamik merupakan suatu algoritma yang seringkali digunakan untuk menyelesaikan permasalahan optimalisasi pada berbagai macam bidang. Beberapa algoritma program dinamik antara lain Needleman-Wunsch, SmithWatherman. Kedua algoritma tersebut merupakan algoritma klasik dalam analisis sekuens.[1] Berdasarkan hasil penelitian, kedua metode tersebut memiliki beberapa kelemahan salah satunya adalah tingkat kecepatan komputasinya. Dari hasil penelitiannya, ditemukan metode baru yaitu Super Pairwise Alignment. Metode ini menggabungkan metode analisis kombinatorial dan probabilitas [5]. Berdasarkan hasil penelitian ini cukup menarik untuk dikaji lebih jauh dengan tinjauan aspek matematis, biologi maupun dari segi komputasionalnya. Hal ini kemudian menjadi acuan bagi penulis untuk mengkaji lebih dalam metode super pairwise alignment dengan mengambil contoh kasus mutasi struktur sequence DNA dengan menggunakan metode super pairwise alignment. Saat ini Software Pairwise berkembang cukup pesat antara lain BLAST, EMBOSS, CS-BLAST, FASTA, HMMER [2]. Pada Tugas Akhir ini diimplementasikan metode Super Pairwise Alignment sebagai software alternatif dalam pensejajaran sekuens. Software yang diciptakan ini bisa berjalan di stand alone computer sedangkan untuk uji validasi program mengPreprint submitted to Elsevier
gunakan software EMBOSS. Tujuan yang ingin dicapai dalam Tugas Akhir ini adalah membuat perangkat lunak untuk mensejajarkan sekuen menggunakan metode Super Pairwise Alignment. Sedangkan manfaat dari Tugas Akhir ini adalah sebagai dasar untuk menciptakan software mathITS sebagai tools alternatif dalam pensejajaran sekuens disamping tools Emboss. 2. Dasar Teori 2.1. Klasifikasi Mutasi Mutasi pada sekuens DNA dapat diklasifikasikan menjadi 4 tipe [3], yaitu : 1. Tipe I Suatu mutasi yang disebabkan oleh perubahan nukleotida misalnya ”a” berubah menjadi ”g”. 2. Tipe II Suatu mutasi yang terjadi karena ada bagian nukleotida yang berubah urutan posisinya misalnya bagian ”accgu” berubah urutan menjadi ”guacc”. 3. Tipe III Suatu mutasi yang disebabkan oleh penyisipan segmen baru ke dalam sekuens misalnya penyisipan ”aa” di bagian tengah pada segmen ”gguugg” akan mengubah segmen menjadi ”gguaaugg”. 4. Tipe IV Suatu mutasi yang terjadi karena penghapusan segmen nukleotida pada sekuens, misalnya menghapus nukleotida ”ag” dari segmen ”acaguua” sehingga segmen berubah menjadi ”acuua”. July 18, 2011
Karena pada mutasi tipe I dan tipe II tidak mengubah posisi dari semua nukleotida maka mutasi ini disebut mutasi subtitusi. Sedangkan untuk mutasi tipe III dan tipe IV yang bisa mengubah posisi nukleotida, maka disebut sebagai mutasi pemindahan.
2. Pada langkah ke(1) jika w ≤ θ, yang berarti tidak ada mutasi shifting di [1,n],kita letakkan titik awal di depan dan misalkan i = j = n − τ. Selanjutnya, kita hitung w(A, B; i, j, n). Jika
2.2. Sequence Alignment Hal yang sangat penting dalam sequence alignment adalah memutuskan pemindahan mutasi. Misalkan A, B adalah dua sequence yang didefinisikan
maka misalkan i = j = 2(n − τ)dan ulangi langkah (2) hingga w(A, B; i, j, n) > θ. Misalkan, k1 adalah bilangan bulat yang memenuhi
A = (a1 , a2 , · · · , ana ), B = (b1 , b2 , · · · , bnb ), C = (c1 , c2 , · · · , cnc ) (1) Penyisipan symbol ”-” ke dalam A,B bertujuan untuk membentuk dua sekuens baru, yaitu A’ dan B’. Selanjutnya, elemenelemen dari A dan B menjadi range dari V5 = {0, 1, 2, 3, 4} = {a, c, g, t, −} dengan V4 adalah himpunan quaternary (himpunan yang terdiri dari 4 elemen) dan V5 adalah himpunan yang terdiri dari 5 elemen.
w(A, B; i, j, n) = w ≥ θ,
w(A, B; i, j, n) = w ≥ θ,
jika i = j = k1 (n − τ), dan w(A, B; i, j, n) > θ jika i = j = (k1 + 1)(n − τ). Kemudian lanjutkan ke langkah 3 atau 4. 3. Untuk i = j = (k1 + 1)(n − τ), jika w(A, B; i, j, n) > θ0 , maka tentukan iˆ1 = (k1 + 1)(n − τ). Jika tidak demikian, maka lakukan tahap (4). 4. Mengikuti langkah 1-3, kita peroleh θ < w < θ0 jika
i = j = (k1 + 1)(n − τ). Dengan demikian, untuk n yang sama, hitunglah w0 (A, B; i+h, j+h, n). Jika w0 > w, hitung iˆ1 berdasarkan persamaan
2.3. Super Pairwise Alignment(SPA) SPA mengkombinasikan estimasi statistik dan analisis kombinatorik yang berhubungan dengan mutasi tipe insersi dan penghapusan antara string. Sekuens DNA atau RNA dapat dianggap independen dan secara identik distribusi barisan variable random. Berdasarkan model statistik, SPA memprediksi keberadaan insersi maupun penghapusan dan panjang insersi maupun penghapusan tersebut bergantung pada similaritas lokal sekuens input. Pada permasalahan ini, insersi maupun penghapusan dan panjang gap pada kedua sekuens DNA (RNA) diperiksa secara sempurna dan kompleksitas perhitungan SPA adalah O(n) dimana n adalah rata-rata panjang sekuens input. Jika semua insersi maupun penghapusan telah ditemukan, sekuens input disejajarkan, baik substitusi maupun trasnposisi dapat ditemukan [3].
3 h ( − w) (2) −w 4 Jika w0 ≤ w ulangi langkah 1-4 untuk nilai h dan n yang cukup besar hingga diperoleh w0 > w. Dengan demikian, melalui langkah-langkah di atas kita dapat mengestimasi iˆ1 dan i1 . n1 =
Estimasi l1 berdasarkan estimasi iˆ1 dari posisi mutasi pertama di T. Secara khusus,
Langkah II :
w(A, B; iˆ1 + l, iˆ1 , n), w(A, B; iˆ1 , iˆ1 + l, n), l = 1, 2, 3, . . . jika pasangan (iˆ1 +l, iˆ1 ) atau pasangan (iˆ1 , iˆ1 +l) memenuhi w ≤ 0.3 atau 0.4, adalah fungsi sliding window yang berhubungan, maka l adalah panjang dari mutasi shiftingnya. Secara khusus:
2.3.1. Langkah-langkah SPA Misalkan (A, B) adalah 2 sekuen yang diketahui. Setiap algoritma memiliki penaksiran nilai parameter pada mode mutasi T. Tanpa terkecuali SPA. Secara spesifik, terlebih dahulu tentukan nilai parameter yang penting, yaitu n, h, θ, θ0 , τ. Disini n dipilih berdasarkan kekonvergenan hukum perluasan nilai atau teorema limit pusat. Secara khusus, kita tentukan n = 20, 50, 80, 100, dsb. θ, θ0 dipilih berdasarkan tingkat galat dari mutasi tipe I dan tipe II dan tingkat galat dari dua variabel bebas yang acak. Dengan demikian kita pilih 0 < θ < θ0 < 0, 75. Untuk nilai parameter h, τ sebagai dua modifikasi lokal, kita pilih sebagai nilai proporsi dari n; yaitu τ = αn, h = βn, 0 < α, β < 0.5. Langkah I :
w0
1. Jika w(A, B; iˆ1 + l, iˆ1 , n) < θ, kita catat bahwa lˆ1 = −l
dan kita masukkan l simbol maya ke dalam sekuen B mengikuti letak iˆ1 , sementara sekuen A dipertahankan invariant. 2. Jika w(A, B; iˆ1 , iˆ1 + l, n) < θ, kita catat bahwa lˆ1 = l dan kita masukkan l simbol maya ke dalam sekuen A mengikuti letak iˆ1 , sementara sekuen B dipertahankan invariant. Melalui penggunaan 2 tahap ini, kita dapat mengestimasi mode mutasi lokal T 1 = {(i1 , l1 )}, dan kesejajaran seragam lokal (C1 , D1 ) yang dijabarkan sebagai berikut:
Mengestimasi posisi mutasi pertama i1 di T
1. Tentukan i = j = 0 dan hitung w(A, B; i, j, n). Jika
C1 = (C1,1 , A2,1 ), D1 = (D1,1 , B2,1 )
w(A, B; i, j, n) = w ≥ θ0 ,
Misalkan panjang vektor C1,1 dan D1,1 adalah iˆ1 + |l1 |. Karena tidak terjadi mutasi pergeseran pada letak n pertama dari A2,1 , B2,1 , kita misalkan L = iˆ1 + |l1 | + n adalah titik awal pada kesejajaran berikutnya.
maka misalkan iˆ1 = 0. Ini berarti mutasi shifting terjadi di awal interval [1,n]. Jika tidak dilanjutkan ke langkah ke(2). 2
Setelah mendapatkan estimasi (i1 , l1 ), kita lanjutkan untuk mengestimasi i2 berdasarkan (C1 , D1 ). Kita misalkan i = j = L1 dan hitung w(A, B; i, j, n) dengan mengulangi langkah (I) langkah 1-4 untuk mendapatkan estimasi iˆ2 untuk i2 .
maka
Langkah III :
Estimasi l2 berdasarkan iˆ1 , lˆ1 , iˆ2 . menghitung
Langkah IV :
k
σ21 =
1 1 X (wk − ρ1 )2 k1 + 1 k=0
(4)
adalah error dari regresi 3. Setelah garis lurus Γ1 ditentukan, lanjutkan untuk menghitung wk , k = k1 + 1, k1 + 2, k1 + 3, . . ., jika terdapat titik k2 , k3 sedemikian hingga ( θ < wk < θ0 untuk setiap k2 < k < k3 , θ0 < wk untuk setiap k3 < k.
Disini kita
w(C1 , D1 ; iˆ2 + l, iˆ2 , n), w(C1 , D1 ; iˆ2 , iˆ2 + l, n), l = 1, 2, 3, . . . kita ulangi langkah II untuk memperoleh lˆ2 dan kesejajaran lokal (C2 , D2 ).
kemudian lakukan analisis regresi berdasarkan data: Melanjutkan proses di atas, kita peroleh sekuen iˆk , lˆk dan sekuen (Ck , Dk ) yang berhubungan untuk setiap k = 1, 2, 3, . . . . Proses akan berhenti pada suatu k0 sedemikian sehingga Ck0 = (C1,k0 , A2,k0 ) dan Dk0 = (D1,k0 , B2,k0 ) memiliki mutasi pergeseran yang terjadi pada (A2,k0 , B2,k0 ). Misalkan Lk0 menotasikan panjang sekuen C1,k0 , D1,k0 dan i = j = Lk0 . l yang berkaitan adalah panjang dari mutasi pergeseran jika pasangan (ikˆ0 + l, ikˆ0 ) atau (ikˆ0 , ikˆ0 + l) memenuhi w ≤ θ dan kemudian w(Ck0 , Dk0 ; i, j, n0 ) ≤ θ dimana n0 panjang terpendek dari A2,k0 dan B2,k0 . Langkah terakhir kita samakan panjang A2,k0 dan B2,k0 . Dengan kata lain, jika panjang A2,k0 lebih pendek dari pada B2,k0 , masukkan beberapa simbol maya diakhir A2,k0 sehingga panjangnya sama dengan B2,k0 [3].
Langkah V :
wk , k = k2 + 1, k2 + 2, . . . , k3 , k = k3 + 1, k3 + 2, k3 + 3, . . . . (5) Garis lurus (pada analisis regresi) tersebut adalah ( Γ2 : y = ρ2 x + ρ02 , Γ3 : y = ρ3 , secara berurutan, yang memenuhi kondisi : k3 X
(6) n0 n0 X X 2 2 (wk3 +k − ρ) , ρ > 0 , (wk3 +k − ρ3 ) = min k=1
(7)
k=1
dimana n0 ≤ n0 < na − k3 . Kedua persamaan di (6) dan (7) dapat diselesaikan dengan metode kuadrat minimum.
Posisi mutasi sˆ∗ adalah variable acak, dan jarak antara dua posisi mutasi yang berdekatan ik dan ik+1 adalah juga variable acak. Operasi pada (2) tida memiliki sifat yang dapat menyesuaikan diri. Dengan kata lain, tidak dapat secara otomatis mencari posisi mutasi dengan pemisahan yang berbeda. Untuk menyelesaikan dua masalah tersebut, kita gunakan algoritma pembeda pada analisis regresi sebagai berikut : Pada langkah ini digunakan wk = n10 w(k, n0 ) untuk mengestimasi posisi mutasi awal i1 di T
4. Titik potong dari garis lurus Γ2 dan Γ3 adalah nilai sˆ yang kita butuhkan. Dengan menggantikan langkah (I) pada algoritma SPA dengan langkah (III) kita peroleh untuk meningkatkan algoritma SPA, yang merupakan algoritma pembeda pada analisis regresi [3].
2.5. Perancangan Sistem dengan Metodologi Berorientasi Objek
1. Tentukan k = 0 dan hitung w(k, n0 ). Jika wk ≥ θ0 (θ0 ∈
(0.6, 0.8)), maka misalkan iˆ1 = 0. Jika tidak lanjutkan ke langkah berikutnya.
2.5.1. Bahasa Pemrograman Java Bahasa pemograman java (awalnya bernama bahasa pemograman Oak) menurut berbagai literatur, diperkenalkan ke hadapan komunitas pemograman di seluruh dunia, oleh James Gosling dari Sun Microsystem Inc. Tujuan pembuatan bahasa pemograman Java adalah untuk meningkatkan kemampuan bahasa pemograman C++ yang sebelumnya telah ada sehingga aplikasi-aplikasi (program komputer) yang dikembangkan dengan bahasa pemograman tersebut mampu berjalan di atas berbagai platform perangkat keras dan perangkat lunak (sistem operasi) yang berbeda. Hal ini merupakan terobosan yang cukup besar sebab sebelumnya aplikasi-aplikasi yang dikembangkan untuk sistem operasi(dan perangkat keras) tertentu hanya akan bisa berjalan dengan baik di atas sistem operasi (dan perangkat keras) tertentu pula [4].
2. Pada langkah ke(1) jika wk ≤ θ(θ ∈ (0.3, 0.5)), lanjutkan untuk menghitung wk+1 untuk setiap k = 0, 1, 2, . . .. Jika terdapat beberapa k yang berhubungan sedemikian hingga wk ≤ θ, wk+1 < θ,
untuk k = 0, 1, . . . , k1 , kemudian lakukan analisis regresi pada titik-titik tersebut. Garis lurus yang berhubungan adalah garis horisontal dan Γ1 : y = ρ1 , dimana nilai ρ1 adalah solusi dari persamaan
k=0
k 3 X 0 2 0 (wk − ρk − ρ ) , ρ, ρ > 0 , = min k=k2
k=k2
2.4. Peningkatan Algoritma untuk mengestimasi posisi mutasi
k k1 1 X X 2 2 (wk − ρ1 ) = min (w − ρ) , ρ > 0 k
(wk − ρ2 k − ρ02 )2
(3)
k=0
3
Gambar 2: Use Case Diagram
Gambar 1: Diagram Alur Proses Pensejajaran
2.5.2. Unified Modeling Language(UML) UML (Unified Modeling Language) saat ini adalah salah satu perkakas (tool) yang sangat bermanfaat untuk melakukan analisis dan perancangan sistem dalam konteks pemograman berorientasi objek. Dalam aplikasi-aplikasi bisnis, metodologimetodologi pengembangan aplikasi yang menggunakan bahasa pemrograman terstruktur (structured programming language), DFD, dan ERD kurang dapat beradaptasi dengan kebutuhan dan harapan pengguna (user’s needs and expectations). Dengan alasan itu, para pakar di bidang perancangan perangkat lunak pada sekitar tahun 1980-1990 mulai bekerja dengan bahasa pemrograman yang berorientasi objek (OOP [Object Oriented Programming]) seperti C++ dan Java. Dengan demikian, diperlukan metodologi dan tools yang lebih sesuai. Dalam hal ini, UML (Unified Modeling Language) yang merupakan metodologi kolaborasi antara metoda-metoda Booch, OMT (Object Modeling Technique), serta OOSE (Object Oriented Software Engineering) dan beberapa metoda lainnya, merupakan metodologi yang sering digunakan saat ini untuk mengadaptasi maraknya penggunaan bahasa pemograman berorientasi objek (OOP) [4].
Gambar 3: Class Diagram
use case diagram merupakan deskripsi tentang interaksi yang terjadi antara sistem dengan actor. Sehingga, dalam sistem ini kita dapatkan perilaku-perilaku actor adalah sebagai berikut : 1. User memasukkan input berupa dua sekuens DNA. 2. User menentukan parameter yang dibutuhkan dalam proses pensejajaran. 3. User membandingkan hasil pensejajaran dengan uji coba berbagai parameter.
3. Analisis dan Perancangan Sistem 3.1. Analisis Kerja sistem Untuk mengetahui gambaran keseluruhan dari proses kerja perangkat lunak yang akan dibuat nantinya, maka diperlukan langkah awal dalam pembuatan perangkat lunak yaitu melakukan analisis kerja sistem secara keseluruhan seperti pada 1.
3.3. Class Diagram Relasi keseluruhan kelas dalam sistem ini terlihat pada 3 3.4. Rancangan Interface Sistem Rancangan interface pada penelitian ini terdiri dari empat form yaitu : form cover, form pensejajaran, form-form hasil pensejajaran, form loading. Form pensejajaran ini merupakan form utama dalam sistem ini. User dapat berinteraksi dengan
3.2. Use Case Diagram Use Case adalah Deskripsi tentang bagaimana sistem/perangkat lunak berperilaku pada user(actor). Sedangkan 4
Gambar 4: Rancangan Interface Form Pensejajaran
Tabel 1: Tabel Data Kelas
Paket Controller Model View list
File controller.java algoritma.java Alignment.java Linklist.java
Keterangan mengontrol jalannya program berisi algoritma SPA form utama menampung data sekuens
sistem melalui Form ini. Perancangan form terlihat pada Gambar 4
k ik lk k ik lk k ik lk k ik lk k ik lk k ik lk k ik lk
Tabel 2: Tabel Data Hasil Percobaan I 1 2 3 4 5 6 59 148 588 823 861 907 -2 -1 -3 -3 -3 1 9 10 11 12 13 14 1579 1713 1756 1771 1871 2748 2 6 -3 -3 -15 -4 17 18 19 20 21 22 2851 3011 3364 3388 3585 4401 -20 -9 1 4 -1 29 25 26 27 28 29 30 6576 7888 7940 9556 9590 9640 2 11 25 -7 -1 5 33 34 35 36 37 38 10960 11163 11182 11268 11348 11872 -4 -4 8 -1 1 -41 41 42 43 44 45 46 11915 12077 12128 12159 12183 12224 -17 5 2 5 18 8 49 12701 -3
k ik lk k ik lk k ik lk k ik lk
1 2 1 454 -24 -4 9 10 3421 3589 18 3 17 18 4879 5032 3 -12 25 26 6270 6784 15 30
Tabel 3: Tabel Data Hasil Percobaan II 3 4 5 6 7 608 761 932 1176 3058 3 21 6 -9 -27 11 12 13 14 15 3742 4013 4249 4402 4558 9 33 -3 6 18 19 20 21 22 23 5194 5347 5502 5709 5862 3 5 -3 -3 6 27 28 6964 7137 -23 -26
7 983 -2 15 2793 2 23 4699 4 31 9691 2 39 11944 -2 47 12281 -7
8 1139 -2 16 2836 4 24 5841 -2 32 9811 -5 40 11993 7 48 12528 34
8 3235 36 16 4726 3 24 6108 -12
5.2. Uji Coba Program Untuk percobaan pertama, data sekuens yang diambil dari Gen Bank adalah NC 003416.2 sebagai Necator americanus mitochondrion, complete genome dan NC 003415.1 sebagai Ancylostoma duodenale mitochondrion, complete genome. Dalam pensejajaran ini, parameter yang dipilih adalah n = 20, θ = 0.4, θ0 = 0.6 dan n = 15, θ = 0.4, θ0 = 0.6. 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 dapat dilihat pada 4 dan data hasil percobaan dapat dilihat pada 2. Untuk percobaan kedua, data sekuens yang diambil dari Gen Bank adalah NC 014956.1 sebagai Human papillomavirus type 129, complete genome dan NC 014955.1 sebagai Human papillomavirus type 130, complete genome. Dalam pensejajaran ini, parameter yang dipilih adalah n = 150, θ = 0.5, θ0 = 0.6 dan n = 50, θ = 0.5, θ0 = 0.6. Selanjutnya untuk Jemboss dilakukan dengan menggunakan parameter match=9 dan mismatch=1 sedangkan gap open yang digunakan adalah 10 dan gap extension yang digunakan adalah 0.5 . Hasil pada percobaan dapat dilihat pada 5 dan data hasil percobaan dapat dilihat pada 3.
4. Implementasi Sistem Pada tahap ini akan dilakukan penulisan kode program dalam kelas-kelas. Kelas-kelas yang telah dirancang diimplementasikan dengan menggunakan bahasa pemrograman Java. Pada tabel 1 dapat dilihat daftar implementasi beberapa kelas utama yang ada pada perangkat lunak beserta keterangannya.
5. Uji Coba Sistem 5.1. Lingkungan Uji Coba Sistem Lingkungan uji coba perangkat lunak yang dibangun dalam Tugas Akhir ini meliputi perangkat keras dan perangkat lunak yang digunakan. Spesifikasinya disajikan dalam Tabel 4.1. Tabel 4.1. Lingkungan Uji Coba Sistem Perangkat Keras Prosesor : Intel Pentium Dual Core Memory : 2.20 GHz, RAM 2 GB Perangkat Lunak Sistem Operasi : Linux Ubuntu 11.04 Tools pembangun : Netbeans 7.0 5
atau (3.73%) dari panjang sekuens terakhir. Hal ini dapat disimpulkan bahwa kecepatan kebutuhan memori lebih rendah dibandingkan tools JEmboss. 2. Pemilihan parameter dalam pensejajaran menggunakan metode SPA masih menjadi kendala. Hal ini dapat terlihat dari percobaan yang dilakukan, dimana untuk parameter n = 20, θ = 0.4, θ0 = 0.6 memiliki hasil pensejajaran yang berbeda dengan parameter n = 15, θ = 0.4, θ0 = 0.6. Sekalipun dalam Tugas Akhir ini metode untuk mengoptimalkan estimasi posisi mutasi yaitu metode regresi linear dimasukkan dalam pembuatan software.
Tabel 4: Tabel Hasil percobaan
Program Super Pairwise Alignment
Super Pairwise Alignment
Jemboss EMBOSS
Parameter n=20 θ = 0.4 θ0 = 0.6 n=15 θ = 0.4 θ0 = 0.6 a=10 b=0.5 a=10 b=0.5
Percobaan length: 13971 similarity: 10701 (76.6) % gaps: 521 (3.73) % length: 13833 similarity: 5443 (39.3) % gaps: 209(1.51) % Died: Sequences too big. length: 13987 similarity:11620 (83.1) % gaps: 648 (4.6) % skor: 49003.0
6.2. Saran 1. Ketepatan pemilihan parameter berpengaruh dalam optimalisasi hasil pensejajaran. Pada permasalahan berbeda, user harus menentukan parameter yang tepat dan tentu saja hal pemilihan banyaknya parameter menimbulkan kesulitan dan waktu cukup lama dalam proses pensejajaran. Permasalahan ini dapat diatasi dengan menggunakan modifikasi lokal pada pensejajaran sekuens [3].
Tabel 5: Tabel Hasil percobaan
Program Super Pairwise Alignment
Parameter n=150 θ = 0.5 θ0 = 0.6
Percobaan length: 7534 similarity: 3662 (48.6) % gaps: 364 (1.78) %
Super Pairwise Alignment
n=50 θ = 0.5 θ0 = 0.6
length: 8384 similarity: 3290 (39.2) % gaps: 2124(25.3) %
Jemboss
a=100 b=10
length: 7446 similarity:3922 (52.7) % gaps: 285 (3.8) % skor: 2384
References [1] Attwood, T., Parry-Smith, D., 2011. Introduction to Bioinformatics. Cambridge University Press, New York. [2] Elrod, Susan L, S., D, W., 2002. Terjemahan Schaums Outline Teori dan Soal Genetika. Penerbit Erlangga, Indonesia. [3] Nankai, S. S., Tuszynski, 2008. Theory and Mathematical Methodes for Bioinformatics. Springer Vierlag, San Francisco. [4] Nugroho, A., 2009. Rekayasa Perangkat Lunak Menggunakan UML dan Java. Indonesia. [5] ShenShi-yi, Adam, Y. P.-i. H., Yang, J., 2002. Super pairwise alignment (spa): An efficient approach to global alignment for homologous sequences. Computational Biology 9 (3).
Dari percobaan pertama menunjukkan bahwa tingkat similaritas menggunakan pendekatan SPA dengan n = 20, θ = 0.4, θ0 = 0.6 yaitu sebesar 76.6 % mendekati dengan hasil pada tools Emboss sebesar 83.1 % . Namun yang perlu diperhatikan adalah penentuan parameter sangat berpengaruh terhadap hasil pensejajaran. Dimana ketika parameter yang digunakan n = 15, θ = 0.4, θ0 = 0.6, hasil yang diperoleh menjauhi hasil yang diperoleh tools Emboss. Demikian juga pada percobaan kedua dengan parameter n = 150, θ = 0.5, θ0 = 0.6 yaitu sebesar 48.6 % mendekati dengan hasil pada tools Jemboss sebesar 52.7 % , dibandingkan ketika parameter yang digunakan n = 50, θ = 0.5, θ0 = 0.6, hasil yang diperoleh menjauhi hasil yang diperoleh tools Jemboss.
6. Kesimpulan dan Saran 6.1. Kesimpulan 1. Dari hasil pensejajaran dengan menggunakan algoritma Super pairwise Alignment, Necator americanus mitochondrion, complete genome dan Ancylostoma duodenale mitochondrion, complete genome diperoleh hasil similaritas sebesar 76.6%. Berbeda dengan tools JEmboss, yang tidak mampu melakukan proses pensejajaran terhadap pasangan sekuen ini dikarenakan memori yang dibutuhkan terlalu besar. Namun jika dibandingkan dengan Emboss maka hasil pensejajaran mendekati hasil yang diperoleh oleh tools Emboss yaitu 83.1 %. Untuk perolehan gap pensejajaran dengan Emboss diperoleh jumlah gap sebanyak 648 atau (4.6 %) dari panjang sekuens terakhir, sedangkan perolehan gap pensejajaran dengan SPA diperoleh jumlah gap sebanyak 521
6
