PEMBENTUKAN OVERLAP GRAPH MENGGUNAKAN ACGT WORDS TREE PADA SEKUENS DNA
WISNU FEBRY PRADANA
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Pembentukan Overlap Graph Menggunakan ACGT Words Tree pada Sekuens DNA adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Januari 2016
Wisnu Febry Pradana NIM G64090057
ABSTRAK WISNU FEBRY PRADANA. Pembentukan Overlap Graph Menggunakan ACGT Words Tree pada Sekuens DNA. Dibimbing oleh WISNU ANANTA KUSUMA. DNA sequence assembly memiliki peran yang sangat penting dalam analisis genom. Salah satu metode yang digunakan dalam DNA sequence assembly untuk penggabungan potongan-potongan fragmen adalah overlap layout consensus. Teknik overlap layout consensus yang digunakan adalah overlap graph. Pada graf ini, node merepresentasikan fragmen dan edge merepresentasikan overlap. Penelitian ini mengembangkan sebuah perangkat lunak untuk menyusun overlap graph menggunakan ACGT words tree. Evaluasi dilakukan dengan menghitung waktu eksekusi yang kemudian dibandingkan dengan penyusunan menggunakan suffix tree dengan nilai 15, 20, dan 25 pada minimum overlap. Minimum overlap didefinisikan sebagai panjang minimum dari substring yang diperhitungkan dalam overlap di antara 2 fragmen. Hasil evaluasi menunjukkan bahwa penyusunan overlap graph menggunakan ACGT words tree memberikan nilai output pada waktu eksekusi yang lebih cepat dibandingkan dengan penyusunan overlap graph menggunakan suffix tree. Kata kunci: DNA sequence assembly, overlap graph, Overlap Layout Consensus, pendeteksian overlap.
ABSTRACT WISNU FEBRY PRADANA. Overlap Graph Constructing on DNA Sequence Using ACGT Words Tree. Supervised by WISNU ANANTA KUSUMA. The DNA sequence assembly is very important in genome analysis. One of the methods used in DNA sequence assembly to combine pieces of fragments is overlap layout consensus. The overlap layout consensus technique used in this research is overlap graph. In this graph, nodes represent fragments and edges represent overlap. This research developed a software for constructing an overlap graph using ACGT words tree. The evaluation was conducted by measuring the execution time and comparing it with the suffix tree as the overlap graph constructor with 15, 20, and 25 in values of minimum overlap. The minimum overlap is defined as the minimum length of a substring which is considered as the overlap region between 2 fragments. The evaluation results showed that the constructing overlap graph using ACGT words tree will give faster execution time than using suffix tree as the overlap graph constructor. Keywords: DNA sequence assembly, overlap detection, overlap graph, Overlap Layout Consensus.
PEMBENTUKAN OVERLAP GRAPH MENGGUNAKAN ACGT WORDS TREE PADA SEKUENS DNA
WISNU FEBRY PRADANA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER Penguji : Toto Haryanto, SKom, MSi dan Muhammad Abrar Istiadi, SKom, FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM MKom INSTITUT PERTANIAN BOGOR BOGOR 2015
Penguji : 1. Toto Haryanto, SKom MSi 2. Muhammad Abrar Istiadi, SKom MKom
PRAKATA Alhamdulillahirabbil’alamin, Penulis ucapkan atas segala nikmat dan keberkahan serta kekuatan yang telah diberikan Allah Subhanahuwata’ala sehingga Penulis dapat menyelesaikan skripsi ini. Shalawat dan salam tak lupa diucapkan untuk tuntunan dan suri tauladan Rasulullah Shallallahu‘alaihiwasallam beserta keluarga dan para sahabat beliau yang senantiasa menjunjung tinggi nilai-nilai Islam yang sampai saat ini dapat dinikmati oleh seluruh manusia di dunia. Skripsi ini dibuat sebagai salah satu syarat untuk mendapat gelar sarjana komputer dari Program Studi Ilmu Komputer Institut Pertanian Bogor. Judul skripsi ini adalah “Pembentukan Overlap Graph menggunakan ACGT words tree pada Sekuens DNA”. Terima kasih kepada Bapak Dr. Wisnu Ananta Kusuma, ST MT selaku pembimbing atas segala ilmu, motivasi, nasihat, dan bantuan yang telah diberikan sehingga penulis dapat menyelesaikan penelitian tugas akhir hingga penyelesaian penulisan skripsi ini. Juga terima kasih untuk seluruh staf dan dosen pengajar Program Studi Ilmu Komputer, terutama Bapak Toto Haryanto, SKom MSi dan Bapak Muhammad Abrar Istiadi, SKomp MKom selaku penguji. Ucapan terima kasih yang tiada tara untuk kedua orang tua penulis. Untuk Ayah dan Ibu telah menjadi orang tua yang selalu memberikan kesempatan, dukungan moril dan materil, kasih sayang serta doa yang tentu takkan bisa penulis balas. Semoga Allah Subhanahuwata’ala membalas kasih sayang kalian, sebagaimana kalian menyayangi penulis. Untuk kedua adik penulis, Nikita Dwie Septiana dan Junior Trinanda Pamungkas terima kasih atas segala kepercayaan, kerja sama, kasih sayang, dan dukungan sentilan-sentilun serta doanya. Terima kasih banyak telah menjadi bagian dari keluarga yang luar biasa sehingga penulis dapat menyelesaikan penelitian ini. Tidak lupa untuk teman-teman Ilmu Komputer IPB angkatan 46, 47, 48, 49, dan 50 yang tidak bisa penulis sebutkan satu per satu. Penulis ucapkan terima kasih atas kepercayaan, kerja sama, dukungan sentilan-sentilun dan doa yang sudah kalian berikan pada penulis sehingga penyelesaian penelitian ini bisa tercapai.
Bogor, Januari 2016 Wisnu Febry Pradana
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
PENDAHULUAN
1
Latar Belakang
1
Perumusan Masalah
1
Tujuan Penelitian
2
Manfaat Penelitian
2
Ruang Lingkup Penelitian
2
METODE
2
Menyiapkan Data Sekuens DNA
3
Membentuk ACGT Words Tree dari Data Sekuens DNA
4
Mendeteksi Overlap Graph
7
Membandingkan Kinerja ACGT Words Tree dengan Suffix tree
7
Lingkungan Pengembangan
7
HASIL DAN PEMBAHASAN
8
Mengumpulkan dan Menyiapkan Data Sekuens DNA
8
Membentuk ACGT Words Tree dari Data Sekuens DNA
8
Membandingkan Waktu Eksekusi SIMPULAN DAN SARAN Kesimpulan
10 13 13
DAFTAR PUSTAKA
14
RIWAYAT HIDUP
15
DAFTAR TABEL 1 2
Informasi organisme yang digunakan Hasil Split (S) pada sekuens ATACACGAT
3 5
DAFTAR GAMBAR 1 2 3
Metode penelitian Database organisme hasil unduhan pada MetaSim Tampilan split data DNA sekuens: (a) data sekuens masukan; (b) merubah variabel dan mengeksekusi words 4 Diagram alir prosedur Insert 5 Ilustrasi pembentukan tree: (a) AT; (b) AC; (c) CA; (d) ACG; (e) TACACGA; (f) AT (Hu 2003) 6 Ilustrasi (lanjutan) pembentukan tree: (g) CGAT; (h) GAT; (i) T. (Hu 2003) 7 Pseudocode prosedur Split 8 Pseudocode prosedur insert 9 Perbandingan waktu eksekusi lactobacillus antara suffix tree dan ACGT words tree 10 Perbandingan waktu eksekusi untuk acetobacter antara suffix tree dan ACGT words tree 11 Perbandingan waktu eksekusi untuk staphylococcus antara suffix tree dan ACGT words tree
2 3 4 5 6 7 9 11 12 12 13
1
PENDAHULUAN Latar Belakang Basis data sekuens genom sering digunakan secara luas oleh peneliti biologi untuk memecahkan beberapa masalah terkait dengan pencarian homology. Untuk mendapatkan suatu data sekuens genom harus dilakukan suatu proses DNA sequencing. Aplikasi-aplikasi komputer telah banyak berkembang salah satunya digunakan untuk membantu para peneliti biologi dalam memecahkan masalah seperti membandingkan sekuens DNA, meneliti struktur protein, dan merakit DNA (DNA assembly) (Maftuhah 2007). Salah satu metode yang sering digunakan sebagai pendekatan untuk melakukan perakitan DNA adalah pendekatan Hamiltonian path menggunakan overlap graph. Problem Hamiltonian path adalah pencarian jalur terpendek dengan mengunjungi setiap node tepat satu kali dalam suatu graf (Abegunde 2010). Penelitian sebelumnya oleh Rahim et al. (2014) membuktikan bahwa dengan melakukan proses indexing, pembentukan suffix tree dapat dilakukan pendeteksian lebih cepat dibandingkan pendeteksian tanpa proses indexing sebelumnya. Selain itu, suffix tree adalah representasi tree yang dapat menghasilkan suatu algoritme yang lebih efisien untuk mendeteksi overlap pada suatu string dengan kompleksitas linier (Gusfield 1997). Dalam penelitian oleh Rahim et al. (2014), ditemukan masalah baru yaitu proses indexing dengan suffix tree membutuhkan alokasi penyimpanan data yang cukup besar dan memiliki tingkat kompleksitas O(n3). Persamaan komplesitas seperti itu menunjukkan bahwa indexing dengan menggunakan suffix tree akan mengalami kendala proses komputasi yang cukup lama pada saat menggunakan data berukuran besar, maka munculah suatu pendekatan yang lebih baik yaitu ACGT words tree, yang secara efektif mendukung proses query, dalam basis data genome dan diharapkan menjadi solusi untuk menampilkan performa yang lebih unggul dari suffix tree (Hu 2003). Pada penelitian ini dikembangkan suatu perangkat lunak pembentukkan overlap graph DNA (Rahim et al. 2014), namun diimplementasikan dengan menggunakan metode ACGT words tree. Data masukan pada perangkat lunak ini berupa data sekuens DNA. Perumusan Masalah Perumusan masalah pada penelitian ini adalah: 1 Bagaimana cara untuk mengimplementasikan ACGT words tree dalam mendeteksi overlap graph DNA? 2 Seberapa baik waktu eksekusi ACGT words tree dibandingkan dengan metode suffix tree pada penelitian Rahim et al. (2014)?
2 Tujuan Penelitian Penelitian ini bertujuan untuk membangun perangkat lunak untuk membentuk overlap graph DNA menggunakan metode ACGT words tree dan membandingkan waktu eksekusi metode ACGT words tree dengan metode suffix tree. Manfaat Penelitian Penelitian ini diharapkan mampu mengefisienkan proses perakitan sekuens DNA. Ruang Lingkup Penelitian Ruang lingkup penelitian ini antara lain adalah: 1 Penelitian ini berfokus kepada pembentukan overlap graph dengan mengimplementasikan metode ACGT words tree. 2 Membandingkan kinerja waktu eksekusi pembentukan overlap graph antar metode ACGT words tree dengan metode suffix tree dari percobaan Rahim et al. (2014). 3 Data sekuens DNA yang digunakan adalah data yang diunduh melalui website National Center for Biotechnology Information (NCBI) dan dipilih 3 organisme seperti pada penelitian Rahim et al. (2014). 4 Data sekuens DNA yang digunakan pada penelitian ini adalah data yang tidak mengandung sequencing error hasil simulasi menggunakan perangkat lunak MetaSim (Richter et al. 2008) seperti pada penelitian Rahim et al. (2014).
METODE Penelitian ini dilakukan dalam beberapa tahapan agar tujuan penelitian ini dapat tercapai. Pada penelitian ini dilakukan 4 tahapan pengerjaan yang akan dijelaskan oleh diagram alir berikut: Menyiapkan data DNA sekuens
Membentuk ACGT words tree
Membandingkan waktu eksekusi ACGT words tree dengan suffix tree
Mendeteksi overlap graph
Gambar 1 Metode penelitian
3 Menyiapkan Data Sekuens DNA Data yang digunakan pada penelitian ini adalah data dari web ftp://ftp.ncbi.nlm.nih.gov/genomes/Bacteria/all.fna.tar.gz. Gambar 2 yang telah berhasil dimasukan pada perangkat lunak MetaSim. Data hasil unduhan tersebut adalah data hasil sequencing DNA dari makhluk hidup tertentu. Sequencing adalah suatu proses dalam perakitan DNA yang bertujuan untuk mendapatkan data sekuens genom (Maftuhah 2007). Data sekuens ini terdiri atas fragmen-fragmen DNA yang memiliki panjang tertentu dan dijadikan file masukan.
Gambar 2 Database organisme hasil unduhan pada MetaSim Data sekuens DNA diperoleh dari simulasi menggunakan perangkat lunak yang bernama MetaSim. Dengan menggunakan MetaSim, keberadaan sequencing error pada suatu sekuens DNA dapat dibangkitkan ataupun tidak. Data masukan dari sebuah aplikasi perakitan sekuens DNA yang menggunakan pendekatan graf sangat sensitif terhadap error. Oleh karena itu, data sekuens DNA pada penelitian ini perlu disimulasikan agar data sekuens tersebut tidak memiliki kesalahan (error free). Pemilihan organisme yang disimulasikan menggunakan MetaSim tersaji pada Tabel 1. Tabel 1 Informasi organisme yang digunakan No.
Nama Organisme
Panjang Sekuens Gi** Asli (bp)* 1 Staphylococcus aureus subsp. 1442 262225764 aureus ED98 plasmid pAVY 2 Acetobacter pasteurianus IFO 1815 258513334 3283-01 plasmid pAPA01-060 3Lactobacillus plantarum 1917 54307232 WCFS1 plasmid pWCFS102 * bp (base pair): satuan jumlah pasangan protein DNA **Gi (Genomeindex): identitas genom dalam website NCBI
4 Membentuk ACGT Words Tree dari Data Sekuens DNA ACGT words adalah struktur data yang merepresentasikan bentuk string, dengan fungsi sekuens karakter alfabet dimulai dengan k, k = {A, C, G, T}, dan terus membaca sekuens karakter berikutnya yang diwakilkan dengan yi hingga karakter yi = k atau $ (Hu 2003). Sebagai contoh jika diberikan data sekuens AGAGACT$ maka ACGT words akan merepresentasikan AG, GA, AG, GACT, ACT, CT, dan T. Dalam pembentukan ACGT words tree dibutuhkan dua buah prosedur, Split (S) dan Insert (R, W, indeks), dengan nilai S adalah data sekuens masukan untuk membentuk tree; W adalah ACGT words, R adalah node denganr words W dikunjungi, indeks menunjukkan posisi awal dari ACGT words W. Jika diberikan sebuah sekuens S = ATACACGAT$ maka untuk menyusun ACGT words tree pertama-tama lakukanlah prosedur Split (S) yang ditunjukkan pada Gambar 3 (a) dan Gambar 3 (b)
Gambar 3 Tampilan split data DNA sekuens: (a) data sekuens masukan; (b) merubah variabel dan mengeksekusi words Asumsikan P adalah indeks dari sekuens S dan Pos[P] menunjukkan posisi indeks. Tersedia empat variabel, A_num, C_num, G_num, T_num yang masingmasing menyimpan posisi awal words dimulai dari A, C, G, dan T secara berurutan. Mula-mula P akan menunjuk pada data sekuens S dan variabel A_num, C_num, G_num, T_num diberi nilai -1. Karakter pertama pada data sekuens S adalah A. Kemudian kita mengecek apakah variabel A_num bernilai -1 atau tidak. Jika ya, maka kita ubah nilai A_num menjadi posisi nilai Pos[P], maka nilai A_num menjadi nol (0). Jika tidak, maka words akan dihasilkan. Setelah mengubah nilai dari variabel A_num, indeks P akan menuju ke karakter berikutnya dalam data sekuens S. Kata berikutnya dalam sekuens S adalah T, nilai variabel T_num adalah -1, maka akan berubah menjadi posisi nilai Pos[P] yaitu satu (1). Selanjutnya posisi indeks akan menuju ke karakter berikutnya. Sekarang indeks P berada di Pos[P] = 2, dan karakternya adalah A. Karena nilai dari variabel A_num adalah nol (0) bukan -1, maka ACGT words W0 = AT dibentuk. Proses yang serupa akan dilakukan berulang sampai indeks P menemukan karakter $ dan tidak ada nilai variabel A_num, C_num, G_num, T_num yang masih bernilai -1. Jika masih ada salah satu nilai dari keempat variabel yang bernilai -1, hal ini mengindikasikan bahwa masih
5 ada ACGT words (Wn) yang belum terbentuk. Tabel 2 akan menunjukkan hasil Split (S) pada sekuens S. Tabel 2 Hasil Split (S) pada sekuens ATACACGAT W0 W1 W2 W3 W4 W5 W6 W7 W8
ACGT-Words AT AC CA ACG TACACGA AT CGAT GAT T
Gambar 4 Diagram alir prosedur Insert
6 Setelah melakukan Split (S) dan susunan ACGT words sudah terbentuk, prosedur Insert (R, W, indeks) dimulai untuk membentuk tree. Gambar 4 menunjukkan diagram alir prosedur Insert. Dari diagram alir tersebut, dapat diketahui bahwa pada prosedur Insert dihasilkan 5 kasus yang dijelaskan sebagai berikut: Kasus 1: kasus ini terjadi ketika k = 0. Hal ini menunjukkan tidak ada sekuens prefix umum antara W dan E.label dengan E = e0 e1…en-1 merupakan urutan edge pada tree, yang diilustrasikan dengan Gambar 5 (a), Gambar 5 (c), dan Gambar 5 (e). Kasus 2: kasus ini terjadi ketika nilai k < |W|, dan k < |E.label| dengan k > 0 dan |W| adalah panjang words W dan |E.label| adalah panjang E.label. Hal ini menunjukkan sekuens prefix umum antara W dan E.label tidak tepat sama dengan W dan E.label, yang akan diilustrasikan pada Gambar 5 (b). Kasus 3: kasus ini terjadi ketika |W| = k < |E.label|, dengan k > 0. Hal ini menunjukkan words W adalah sekuens prefix dari E.label, yang diilustrasikan pada Gambar 6 (i). Kasus 4: kasus ini terjadi ketika |W|> k = |E.label|, dengan k > 0. Hal ini menunjukkan bahwa E.label merupakan sekuens prefix dari words W namun tidak setara dengan words W, yang diilustrasikan pada Gambar 5 (d). Kasus 5: kasus ini terjadi ketika |W| = |E.label| = k > 0. Hal ini menunjukkan bahwa tree sudah memiliki edge E dengan memiliki label yang sama dengan words W, yang akan diilustrasikan pada Gambar 5 (e), dan Gambar 5 (f).
Gambar 5 Ilustrasi pembentukan tree: (a) AT; (b) AC; (c) CA; (d) ACG; (e) TACACGA; (f) AT (Hu 2003)
7
.
Gambar 6 Ilustrasi (lanjutan) pembentukan tree: (g) CGAT; (h) GAT; (i) T. (Hu 2003)
Mendeteksi Overlap Graph Pada proses ini, penyusunan overlap graph dapat dilakukan jika semua fragmen pada data DNA sekuens sudah ter-index ke dalam memori. Setelah proses pembentukan ACGT words tree selesai, penyusunan ataupun pendeteksian overlap graph pada masing-masing fragmen pun lebih mudah dilakukan (Rahim et al. 2014). Hal ini dikarenakan setiap string yang mewakili words pada setiap fragmen dibandingkan dengan awalan (prefix) dari fragmen lainnya. Jika words pada fragmen yang satu cocok atau match dengan awalan pada fragmen lainnya, dua fragmen tersebut saling overlap Membandingkan Kinerja ACGT Words Tree dengan Suffix tree ACGT words tree selalu memberikan jumlah node yang lebih sedikit dibandingkan dengan suffix tree tidak peduli berapa besarnya nilai probabilitas (Ɵ), maka ACGT words tree akan selalu membutuhkan lokasi penyimpanan yang lebih sedikit dibandingkan suffix tree (Hu 2003). Dengan sedikitnya alokasi penyimpanan, ACGT words tree diharapkan mampu mempercepat waktu eksekusi dibandingkan dengan suffix tree Lingkungan Pengembangan Spesifikasi perangkat lunak yang digunakan untuk penelitian ini adalah perangkat lunak MetaSim yang digunakan untuk simulasi error free DNA sekuens, perangkat lunak Visual Studio dengan bahasa pemrograman C++ dengan library tambahan seqan, OS Windows 8 Pro 64-bit. Spesifikasi perangkat keras yang digunakan, prosessor Intel Core 2 Duo 1.8 GHz, RAM 3 GB.
8
HASIL DAN PEMBAHASAN Mengumpulkan dan Menyiapkan Data Sekuens DNA Penelitian ini menggunakan 3 organisme yang dipilih pada basis data MetaSim. Tiga organisme yang terpilih adalah staphylococcus aureus, acetobacter pasteurianus, dan lactobacillus plantarum. Organisme ini dipilih karena panjang sekuens yang dimiliki organisme tersebut relatif lebih pendek dibandingkan dengan organisme yang lainnya, sehingga waktu eksekusi yang didapatkan tidak terlalu lama. Dari setiap organisme yang dipilih, dilakukan sebuah simulasi untuk setiap organisme sebanyak satu kali. Setiap satu kali simulasi menghasilkan sebuah fail berformat FASTA (.fna). Dari hasil simulasi tersebut didapatkan 3 fail yang selanjutnya digunakan sebagai data masukan pada penelitian ini. Data masukan ini adalah data sekuens DNA yang dijamin tidak memiliki error. Maksud dari error ini adalah setiap nukleotida pada fragmen atau reads tidak ada yang diganti dengan nukleotida lainnya, namun simulasi ini tidak dapat menghilangkan fragmen yang saling redundant dengan fragmen lainnya. Untuk mendapatkan data sekuens DNA yang tidak memiliki kesalahan, error model yang dipilih adalah exact dengan panjang setiap fragmen 35 bp. Membentuk ACGT Words Tree dari Data Sekuens DNA Setelah mendapatkan data sekuens DNA, langkah selanjutnya adalah membentuk ACGT words tree dari setiap fragmen-fragmen pada data sekuens DNA. Perangkat lunak yang dikembangkan pada penelitian ini menerima data masukan berupa fail dengan format FASTA (.fna) dalam suatu path file. Kemudian perangkat lunak ini membaca satu per satu fragmen yang terdapat pada fail tersebut. ACGT words tree, segera terbentuk setiap kali perangkat lunak ini selesai membaca 1 fragmen. Node hasil tree tersebut disimpan dalam suatu memori, yang akan digunakan kembali oleh perangkat lunak ini dalam pendeteksian overlap pada fragmen yang lainnya. Pseudocode pembentukan ACGT words tree berupa prosedur Split dan Insert tersaji pada Gambar 7 dan Gambar 8 . Prosedur Split Prosedur Split pada ACGT words tree merupakan tahapan awal pemisahan potongan kata 1 huruf pada data masukan. Pemisahan kata atau huruf dilakukan bila kata pembacaan selanjutnya adalah huruf yang sama dengan huruf bacaan awal prosedur. Pembacaan terus dilakukan sampai semua huruf telah menjadi huruf bacaan awal prosedur dan telah menemukan lambang $. Kata atau huruf yg dipisahkan kemudian diberikan nomor words sesuai urutuan pemisahan kata. Pseudocode prosedur Split disajikan pada Gambar 7. .
9 Prosedur split (S); /*Generate kata dalam masukan sekuens (S)*/ /*P adalah indeks dari masukan sekuens S.*/ /*W menyimpan ACGT words.*/ /*Substring(S,Ns,Ne) adalah fungsi return subsekuens dari S dimulai dari Ns dan berakhir di Ne.*/ 1 Begin 2 P:=0; 3 While (S[P]≠’$’)do 4 begin /*membentuk Node dan Edge baru*/ 5 if(S[P]=’A’)then 6 begin 7 if(A_num ≠ -1)then 8 begin 9 W:=Substring(S,A_num,(P-1)); 10 Insert(R,W,A_num); 11 end; 12 A_num:=P; 13 end 14 else if(S[P]=’C’)then 15 begin 16 if(C_num ≠ -1)then 17 begin 18 W:=Substring(S,C_num,(P-1)); 19 Insert(R,W,C_num); 20 end; 21 C_num:=P; 22 end 23 else if(S[P]=’G’)then 24 begin 25 if(G_num ≠ -1)then 26 begin 27 28 W:=Substring(S,G_num,(P-1)); 29 Insert(R,W,G_num); 30 end; 31 G_num:=P; 32 end 33 else if(S[P]=’T’)then 34 begin 35 if(T_num ≠ -1)then 36 begin 37 W:=Substring(S,T_num,(P-1)); 38 Insert(R,W,T_num); 39 end; 40 T_num:=P; 41 end; 42 P:=P+1; 43 end; 44 InsertRemainingWord(); 45 end;
Gambar 7 Pseudocode prosedur Split
10 Baris kedua memberikan instruksi untuk mengubah nilai indeks masukan awal sekuens S menjadi 0. Baris ketiga merupakan syarat apabila nilai indeks P bukan $ maka dilakukan pembentukan node dan indeks baru. Baris kelima sampai ketiga belas (5-13) menentukan apakah sekuens masukan bernilai ‘A’? beserta prosedur penyimpanan dan pengolahan masukan jika sekuens masukan bernilai ‘A’. Baris keempat belas sampai dua puluh dua (14-22) menentukan apakah sekuens masukan bernilai ‘C’? beserta prosedur penyimpanan dan pengolahan masukan jika sekuen masukan bernilai ‘C’. Baris kedua puluh tiga sampai tiga puluh dua (23-32) menentukan apakah sekuens masukan bernilai ‘G’? beserta prosedur penyimpanan dan pengolahan masukan jika sekuen masukan bernilai ‘G’. Baris ketiga puluh tiga sampai empat puluh satu (33-41) menentukan apakah sekuens masukan bernilai ‘T’, beserta prosedur penyimpanan dan pengolahan masukan jika sekuens masukan bernilai ‘T’. Baris keempat puluh dua sampai empat puluh lima (42-45) merupakan prosedur lanjutan pembacaan sekuens masukan sampai nilai indeks (P) adalah tanda $. Prosedur Insert Prosedur Insert pada ACGT words tree merupakan prosedur lanjutan dari prosedur Split. Prosedur ini dilakukan setiap prosedur Split telah menambahkan potongan kata atau huruf yang telah diberikan nomor urut. Pada prosedur ini dilakukan pemberian nilai bobot untuk menentukan posisi kata atau huruf dari root ACGT words tree. Selain menentukan posisi, prosedur ini juga menentukan tingkat kedalaman ACGT words tree. Pseudocode prosedur Insert disajikan pada Gambar 8. Baris kedua bertujuan mengubah nilai fungsi i menjadi fungsi First dengan kata masukan pertama bernilai W. Baris ketiga merupakan syarat apabila nilai R.Edgei.label adalah null maka akan dilakukan penempatan posisi masukan dalam tree. Baris ketiga sampai sembilan (3-9) menempatkan kata tepat setelah root. Baris kesepuluh sampai dua puluh satu (10-21) menempatkan kata tepat satu node setelah kata masukan sebelumnya dengan dua node baru akan terbentuk berisi kata masukan baru dan pecahan node sebelumnya. Baris kedua puluh dua sampai dua puluh enam (22-26) memecahkan node sebelumnya sehingga membentuk satu node baru dengan kata masukan baru menjadi node yang levelnya lebih dekat ke root, dan node pecahannya menjadi node yang levelnya satu tingkat di bawah node kata masukan baru. Baris kedua puluh tujuh sampai tiga puluh dua (27-32) menempatkan node baru di bawah node sebelumnya dengan kata masukan baru yang merupakan bagian dari node sebelumnya dari satu jalur edge yang sama. Baris ketiga puluh tiga sampai empat puluh satu (33-41) dilakukan jika pada tree sudah memiliki edge dan node yang sama dengan kata masukan baru. Membandingkan Waktu Eksekusi Gambar 9 menjelaskan hasil perbandingan waktu eksekusi metode suffix tree dengan ACGT words tree pada organisme lactobacillus. Berdasarkan data Gambar 9 dapat diketahui bahwa eksekusi metode ACGT words tree pada organisme lactobacillus membutuhkan waktu yang lebih cepat dibandingkan dengan waktu eksekusi metode suffix tree pada organisme lactobacillus
11 Prosedur insert (R,W,indeks); /*Masukan words ke dalam ACGT words tree.*/ /*CompareSameEdge (W1,W2) adalah fungsi return dari panjang yang sama antara W1 dan W2.*/ /*First(W) adalah fungsi return karakter pertama pada W.*/ /*Shift(W,com_len) adalah fungsi return hasil W dari com_len ke posisi akhir word.*/ /*SplitEdge(Edge,length) adalah fungsi return node baru setelah proses splitting.*/ /*Sibling() adalah fungsi return karakter s yang menandakan edge dari dua words yang sama.*/ /*CreateNode(indeks) adalah fungsi return node baru dengan suffix_num bagian indeks.*/ 1 begin 2 i:=First(W); 3 if(R.Edgei.label=NULL)then 4 /*Case 1*/ 5 begin 6 N:=CreateNode(indeks); 7 R.Edgei.label:=W; 8 R.Edgei.endnode:=N; 9 end 10 else 11 begin 12 k:=CompareSameEdge(R.Edgei.labe,W); 13 if(k
Gambar 8 Pseudocode prosedur insert
and
length
12 2370.37
2500
2000
Waktu (ms)
1627.88
2336.16
2316.25
1768.553
1728.429
1500 Suffix 1000
ACGT
500
0 15
20
25
Overlap Minimum
Gambar 9 Perbandingan waktu eksekusi lactobacillus antara suffix tree dan ACGT words tree Pada minimum overlap 15, metode ACGT words tree membutuhkan waktu eksekusi selama 1627.88 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2370.37 ms. Pada minimum overlap 20, metode ACGT words tree membutuhkan waktu eksekusi selama 1768.553 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2336.16 ms. Pada minimum overlap 25, metode ACGT words tree membutuhkan waktu eksekusi selama 1728.429 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2316.25 ms. 2500
2239.21
2102.934
2070.22
2000
Waktu (ms)
1579.19
1577.511
1589.159
1500 Suffix
1000
ACGT 500 0 15
20
25
Overlap Minimum
Gambar 10 Perbandingan waktu eksekusi untuk acetobacter antara suffix tree dan ACGT words tree
13 Berdasarkan data pada Gambar 10 dapat diketahui bahwa eksekusi metode ACGT words tree pada organisme acetobacter membutuhkan waktu yang lebih cepat dibandingkan dengan waktu eksekusi metode suffix tree pada organisme acetobacter. Pada minimum overlap 15, metode ACGT words tree membutuhkan waktu eksekusi selama 1579.19 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2239.21 ms. Pada minimum overlap 20, metode ACGT words tree membutuhkan waktu eksekusi selama 1577.511 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2102.934 ms. Pada minimum overlap 25, metode ACGT words tree membutuhkan waktu eksekusi selama 1589.159 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 2070.22 ms 1600
1462.57
1395.31
1400
1392.95
Waktu (ms)
1200 1000
900.92
909.36
902.21
800
Suffix
600
ACGT
400 200 0 15
20
25
Overlap Minimum
. Gambar 11 Perbandingan waktu eksekusi untuk staphylococcus antara suffix tree dan ACGT words tree Berdasarkan data pada Gambar 11 dapat diketahui bahwa eksekusi metode ACGT words tree pada organisme staphylococcus membutuhkan waktu yang lebih cepat dibandingkan dengan waktu eksekusi metode suffix tree pada organisme staphylococcus. Pada minimum overlap 15, metode ACGT words tree membutuhkan waktu eksekusi selama 900.92 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 1462.57 ms. Pada minimum overlap 20, metode ACGT words tree membutuhkan waktu eksekusi selama 909.369 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 1359.31 ms. Pada minimum overlap 25, metode ACGT words tree membutuhkan waktu eksekusi selama 1392.95 ms, sedangkan metode suffix tree membutuhkan waktu eksekusi selama 902.211 ms.
SIMPULAN DAN SARAN Kesimpulan Proses pembentukan overlap graph menggunakan metode ACGT words tree pada sekuens DNA membutuhkan 2 tahap proses, proses Split dan Insert.
14 Berbeda dengan metode suffix tree, ACGT words tree memberikan hasil eksekusi waktu dan alokasi penyimpanan yang lebih baik. Hal ini disebabkan oleh jumlah words hasil bentukan proses ACGT words tree lebih sedikit dibandingkan suffix tree. Dengan demikian pembentukan overlap graph menggunakan ACGT words tree mampu memberikan waktu eksekusi yang lebih cepat. Saran Penggunaan metode ACGT words tree terbukti lebih baik dalam waktu eksekusi dikarenakan adanya prosedur Split dan prosedur Insert saat pengolahan data masukan menggunakan ACGT words tree. Dengan menggabungkan metode ini pada prosedur Split dengan menggunakan komputasi paralel, diharapkan bisa menghasilkan proses overlap lebih baik dan lebih cepat.
DAFTAR PUSTAKA Abegunde T. 2010. Comparison of DNA sekuens assembly algorithms using mixed data sources [tesis]. Saskatoon (CA): University of Saskatchewan Gusfield D. 1997. Algorithms on Strings, Trees, and Sequences. University of California (US): Cambridge University Press. Hu JW. 2003. An ACGT-Words tree for efficient data access in genomic databases [tesis]. Taiwan (TW): National Sun Yat-sen University. Maftuhah DN. 2007. Pencarian string dengan menggunakan metode indexing pada data genomic [skripsi]. Depok (ID): Universitas Indonesia. Rahim A, Kusumah WA, Wijaya SH. Penyusunan overlap graph menggunakan suffix tree pada DNA sekuens. Di dalam: Prosiding Seminar Ilmiah Ilmu Komputer; 8 Nov 2014; Bogor. Indonesia. Bogor (ID): Institut Pertanian Bogor. Richter DC, Ott F, Auch AF, Huson DH, Schmid R. 2008. MetaSim – A sequencing simulator for genomics and metagenomics. PLOS ONE. 3(10):e3373. doi:10.1371/journal.pone.0003373.
15
RIWAYAT HIDUP Penulis bernama Wisnu Febry Pradana, adalah putra pertama dari pasangan Bapak Imam Gunawan dan Ibu Kusumasti Suryaningrum. Penulis lahir di Jakarta pada tanggal 1 Februari 1991. Penulis memiliki 2 saudara, Nikita Dwie Septiana sebagai adik pertama dan Junior Trinanda Pamungkas sebagai adik kedua. Penulis mengenyam pendidikan di Sekolah Menengah Atas Negeri 37 Jakarta Selatan. Setelah lulus dari sekolah menengah atas, penulis mendaftarkan diri ke Institut Pertanian Bogor (IPB) melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima di program studi Ilmu Komputer fakultas Matematika dan Ilmu Pengetahuan Alam. Selama menjalani kegiatan perkuliahan di IPB, penulis sempat aktif di kegiatan kemahasiswaan, salah satunya menjadi Ketua Badan Pengawas Himpunan Keprofesian Ilmu Komputer pada tahun 2012-2013. Pada tahun 2012-2013 penulis mendapatkan prestasi sebagai Badan Pengawas Himpunan Keprofesian terbaik dari Dewan Perwakilan Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam.
