KOREKSI DNA SEQUENCING ERROR DENGAN METODE SPECTRAL ALIGNMENT
NOVALDO CAESAR
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Koreksi DNA Sequencing Error dengan Metode Spectral Alignment adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun 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, Agustus 2013 Novaldo Caesar NIM G64090124
ABSTRAK NOVALDO CAESAR. Koreksi DNA Sequencing Error dengan Metode Spectral Alignment. Dibimbing oleh WISNU ANANTA KUSUMA dan SONY HARTONO WIJAYA. Teknologi second generation DNA sequencing mampu menghasilkan data pembacaan dalam jumlah besar dalam waktu yang relatif singkat dibandingkan dengan teknologi Sanger Shotgun. Untuk menangani jumlah data yang besar tersebut pada tahap assembly, digunakanlah teknologi DNA sequence assembly yang menggunakan pendekatan graf. Teknologi ini diketahui sensitif terhadap sequencing error. Masalah ini dapat diatasi dengan melakukan koreksi sequencing error baik sebelum atau sesudah proses assembly. Pada penelitian ini telah dihasilkan sebuah perangkat lunak yang mampu mendeteksi dan mengoreksi sequencing error pada data sekuens DNA dengan metode spectral alignment sebagai tahapan praproses. Data sekuens DNA yang mengandung error dibangkitkan dengan menggunakan perangkat lunak MetaSim. Data hasil simulasi dikoreksi dengan perangkat lunak yang dihasilkan pada penelitian ini. Hasil koreksi dievaluasi dengan mengukur kompleksitas graf yang diwakili oleh jumlah node. Dari hasil evaluasi diperoleh informasi bahwa metode spectral alignment mampu menyederhanakan graf yang dihasilkan pada tahap DNA sequence assembly, yaitu ditunjukkan dengan berkurangnya jumlah node. Kata kunci: bioinformatika, koreksi error, praproses, spectral alignment
ABSTRACT NOVALDO CAESAR. DNA Sequencing Error Correction with Spectral Alignment. Supervised by WISNU ANANTA KUSUMA and SONY HARTONO WIJAYA. Second generation DNA sequencing technology is able to generate reads in a massive amount and in a relatively short time compared to the traditional Sanger Shotgun technology. Graph based DNA sequence assembly is used to handle these big data in assembly step. However, the graph based DNA sequence assembly is sensitive to sequencing error. This problem can be solved by performing an error correction step before or after the assembly process. In this research, a software to detect and correct sequencing error in DNA sequence data was developed by employing spectral alignment technique. This technique is implemented as a pre-processing step before the DNA sequence assembly process. DNA sequences which contain error are generated using MetaSim software. Errors in the data sequences are corrected using the software developed in this research. The results are evaluated using the Velvet assembler by comparing the complexity of the graph produced, represented by the number of nodes in the graph. The evaluation results show that the data sequences with error produce more complex graph than the corrected data sequences. It can be concluded that the correction of DNA sequencing error using spectral alignment method can simplify the complexity of graph produced by the DNA sequence assembly step. Keywords: bioinformatics, error correction, pre-process, spectral alignment
Koreksi DNA Sequencing Error dengan Metode Spectral Alignment
NOVALDO CAESAR
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Ilmu Komputer pada Departemen Matematika dan Ilmu Pengetahuan Alam
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
Judul Skripsi: Koreksi DNA Sequencing Errordengan Metode Spectral Alignment N arna : N ovaldo Caesar NIM : G64090 124
Disetujui oleh
STMT
Sony Hartono Wijaya, SKorn MKorn Pernbirnbing II
MSiMKorn
Tanggal Lulus:
Judul Skripsi : Koreksi DNA Sequencing Error dengan Metode Spectral Alignment Nama : Novaldo Caesar NIM : G64090124
Disetujui oleh
Dr Wisnu Ananta Kusuma, ST MT Pembimbing I
Sony Hartono Wijaya, SKom MKom Pembimbing II
Diketahui oleh
Dr Ir Agus Buono, MSi MKom Ketua Departemen
Tanggal Lulus:
PRAKATA Puji syukur penulis panjatkan kepada Allah subhanahu wa ta’ala karena berkat rahmat, karunia, dan ridho-Nya karya ilmiah ini berhasil diselesaikan. Penelitian ini berada pada ranah bioinformatika dengan menitikberatkan pada pengoreksian error yang dihasilkan pada tahap DNA sequencing. Pesatnya kemajuan pengembangan metode-metode dalam dunia bioinformatika menjadi motivasi penulis dalam melakukan penelitian ini. Terima kasih penulis ucapkan kepada Bapak Dr Wisnu Ananta Kusuma, ST MT sebagai pembimbing pertama yang telah membimbing, mengawasi, dan mengawal penulis dalam penelitian ini. Terima kasih juga kepada Bapak Sony Hartono Wijaya, SKom MKom sebagai pembimbing kedua yang memberikan masukan serta kritik yang membangun guna memperbaiki penelitian ini. Tidak lupa penulis menyampaikan terima kasih atas kasih sayang, dukungan, dan doa yang selalu diberikan oleh ibu dan kedua kakak sepanjang pengerjaan penelitian ini. Semoga penelitian ini bermanfaat bagi perkembangan ilmu pengetahuan khususnya ilmu komputer di masa depan, serta dapat dijadikan acuan untuk perkembangan penelitian pada tema sejenis di masa mendatang. Bogor, Agustus 2013 Novaldo Caesar
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
Akuisisi Data Sekuens DNA
2
Implementasi Metode Spectral Alignment
3
Evaluasi
5
HASIL DAN PEMBAHASAN
6
Simulasi Data Sekuens DNA dengan MetaSim
6
Alur Kerja Perangkat Lunak yang Dihasilkan dalam Mengoreksi Error
7
Evaluasi Hasil Koreksi Perangkat Lunak yang Dihasilkan SIMPULAN DAN SARAN
11 13
Simpulan
13
Saran
13
DAFTAR PUSTAKA
14
RIWAYAT HIDUP
22
DAFTAR TABEL 1 Spesifikasi organisme yang digunakan pada penelitian 2 Konfigurasi parameter untuk membangkitkan data sekuens DNA dengan simulasi MetaSim 3 Informasi hasil eksekusi perangkat lunak yang dihasilkan dalam mendeteksi dan mengoreksi error 4 Hasil DNA sequence assembly menggunakan Velvet
3 6 11 13
DAFTAR GAMBAR 1 Contoh format data sekuens DNA hasil simulasi MetaSim 2 Diagram alir tahapan kerja perangkat lunak yang dihasilkan dalam melakukan DNA sequencing error 3 Hasil konstruksi graf dengan dua fragmen yang tidak mengandung error 4 Hasil konstruksi graf dengan salah satu fragmen mengandung error substitusi
7 7 11 12
DAFTAR LAMPIRAN 1 2 3
Source code program Cara menggunakan program Percobaan beberapa nilai parameter multiplicity dan pengaruhnya terhadap jumlah anggota spectrum
15 20 21
1
PENDAHULUAN Latar Belakang Kemajuan teknologi dalam ranah DNA sequencing membuka peluang pada perkembangan teknologi DNA sequence assembly. Jumlah reads yang dihasilkan teknologi DNA sequencing generasi kedua jauh lebih besar dibandingkan dengan menggunakan pendekatan tradisional Sanger Shotgun. Sedangkan panjang per fragmen yang dihasilkan lebih pendek. Hasil pembacaan sekuens pendek tersebut sering dikenal sebagai short read. Sebagai contoh Illumina Genome Analyzer mampu menghasilkan 1.5 triliun bps data sekuens dengan panjang sekuens 36, dalam satu kali menjalankan program selama 60 jam (Shi et al. 2009). Telah banyak tools mapan yang dikembangkan untuk melakukan DNA sequence assembly dari hasil DNA sequencing dengan teknologi Sanger Shotgun. Namun pada umumnya memiliki kinerja buruk untuk data sekuens yang berukuran besar. Karena itu dibutuhkan tools untuk DNA sequence assembly yang mampu menangani data dalam jumlah besar. Maka diperkenalkanlah teknik DNA sequence assembly dengan pendekatan graf, yang mampu melakukan assembly terhadap data sekuens DNA yang berukuran besar. Pendekatan graf untuk DNA sequence assembly yang paling sering digunakan dalam 20–30 tahun terakhir adalah overlap layout consensus (OLC). Namun ternyata terdapat kelemahan dalam DNA sequence assembly menggunakan pendekatan OLC, yakni kesulitan dalam menangani masalah repeat pada graf. Belum ada algoritme polinomial yang mampu mengatasi masalah repeat untuk menentukan path yang benar pada overlap graph. Untuk mengatasi masalah ini dikembangkanlah metode DNA sequence assembly dengan menggunakan pendekatan Eulerian path pada graf De-Bruijn. DNA sequence assembly dengan pendekatan graf khususnya graf De Bruijn ternyata mampu mengatasi jumlah sekuens berukuran besar serta mengatasi masalah repeat. Permasalahannya adalah setiap proses DNA sequencing pasti menghasilkan error. Sedangkan, DNA sequence assembly dengan pendekatan graf bersifat sensitif terhadap error. Terdapatnya error pada hasil DNA sequencing dapat meningkatkan kompleksitas graf yang dihasilkan. Permasalahan ini dapat diselesaikan dengan mendeteksi dan mengoreksi error yang muncul pada tahap sequencing (Chaisson et al. 2004). Untuk itu dirasakan perlu adanya upaya mendeteksi dan mengoreksi error yang muncul pada tahap DNA sequencing sebagai tahap praproses sebelum dilakukan tahap DNA assembly (Shi et al. 2009). Penelitian ini menitikberatkan pada pengembangan perangkat lunak yang mampu mendeteksi dan mengoreksi data hasil DNA sequencing dengan menggunakan metode spectral alignment. Perumusan Masalah Bagaimanakah langkah-langkah yang harus dilakukan untuk mengkoreksi data sekuens DNA hasil pembacaan pada tahap DNA sequencing menggunakan tahap praproses dengan metode spectral alignment? Apakah upaya mengoreksi error sebagai tahap praproses sebelum DNA sequence assembly mampu menyederhanakan graf yang dihasilkan pada tahap DNA sequence assembly?
2
Tujuan Penelitian Penelitian ini ditujukan untuk mengembangkan perangkat lunak untuk mengoreksi data sekuens DNA dengan menggunakan teknik spectral alignment sebagai tahap praproses sebelum dilakukan DNA sequence assembly. Selain itu, penelitian ini ditujukan untuk membandingkan kompleksitas graf hasil DNA sequence assembly antara data set yang belum dikoreksi dengan yang sudah dikoreksi. Manfaat Penelitian Perangkat lunak yang dihasilkan dalam penelitian ini dapat digunakan untuk mengoreksi DNA sequencing error pada data hasil DNA sequencing. Sehingga nantinya dihasilkan data hasil sequencing yang bersifat bebas error untuk selanjutnya dilakukan tahap DNA sequence assembly. Ruang Lingkup Penelitian Ruang lingkup pada penelitian ini antara lain: 1 Penelitian ini hanya menitikberatkan pada tahap praproses, sedangkan untuk melakukan DNA sequence assembly menggunakan assembler yang telah dikembangkan oleh Zerbino dan Birney (2008), yaitu Velvet. 2 Data sekuens DNA yang digunakan pada penelitian ini merupakan hasil simulasi dengan perangkat lunak MetaSim. Data sekuens disimulasikan dengan menyertakan error menggunakan model error Sollexa. 3 Penelitian ini menggunakan 2 jenis data set untuk dibandingkan graf hasil proses assembly-nya. Data set pertama merupakan data sekuens DNA yang sebelumnya telah dilakukan tahap praproses. Sedangkan data set kedua merupakan data sekuens DNA yang tanpa melewati tahap praproses
METODE Secara garis besar, penelitian ini terdiri atas empat tahap, yaitu akuisisi data sekuens DNA, implementasi metode spectral alignment, koreksi data sekuens DNA dan evaluasi hasil koreksi. Akuisisi Data Sekuens DNA Data yang digunakan pada penelitian ini merupakan data sekuens DNA yang dibangkitkan melalui simulasi dengan perangkat lunak MetaSim. Hasil keluaran dari perangkat lunak MetaSim adalah fragmen-fragmen DNA hasil proses DNA sequencing yang disimulasikan. Untuk itu perlu ditentukan organisme yang disimulasikan proses DNA sequencing-nya yang dipilih dari basis data MetaSim. Pada penelitian ini dipilih tiga organisme untuk disimulasikan. Ketiga organisme beserta informasinya dapat dilihat pada Tabel 1.
3
Tabel 1 Spesifikasi organisme yang digunakan pada penelitian Panjang sekuens Organisme Gi lengkap (bp) Staphylococcus aureus subsp. 1 442 262 225 764 aureus ED98 plasmid pAVY Acetobacter pasteurianus IFO 1 815 258 513 334 3283-01 plasmid pAPA01-060 Lactobacillus plantarum 1 917 54 307 228 WCFS1 plasmid pWCFS101 Implementasi Metode Spectral Alignment Lingkungan Pengembangan Perangkat Lunak Pada tahap implementasi, dibuat sebuah program komputer yang mampu menerapkan metode spectral alignment untuk mengkoreksi error pada data sekuens DNA yang telah diperoleh pada tahap akuisisi data. Lingkungan pengembangan perangkat lunak pada penelitian ini adalah sebagai berikut: : C++ Bahasa pemrograman Sistem operasi : Microsoft Windows 8 Integrated development environment : Microsoft Visual Studio 2012 Build system : CMake Source control : TortoiseSVN Penelitian ini memanfaatkan library SeqAn (Döring et al. 2008). SeqAn adalah sebuah library C++ berisi algoritme dan struktur data efisien untuk melakukan analisis sekuens yang berfokus pada data biologis. SeqAn bersifat open source dan dapat ditemukan di situs resminya pada alamat http://www.seqan.de. Solid Tuple dan Weak Tuple Setelah data sekuens DNA hasil pembacaan didapat, maka dari data tersebut dirumuskan mana saja tuple yang merupakan solid tuple dan mana yang merupakan weak tuple. Diberikan himpunan sejumlah k data sekuens hasil pembacaan yang disebut R, dengan R = {r1, r2, r3, ..., rk}, dan | ri | = L, dengan ri ∈ {A,C,G,T}L untuk seluruh i pada selang 1 ≤ i ≤ k. Simbol A, C, G dan T merupakan kode nukleotida dengan A untuk adenin, C untuk sitosin, G untuk guanin, dan T untuk timin. Diketahui pula dua bilangan bulat yang disebut multiplicity m (m > 1) dan length l (l < L). Jika sebuah l-tuple didefinisikan sebagai sebuah string DNA dengan panjang l, maka sebuah l-tuple dikatakan solid terhadap R dan m, jika l-tuple tersebut merupakan substring dari minimal m pembacaan yang terdapat pada himpunan R, dan dikatakan weak jika terjadi sebaliknya. Sebagai contoh, diberikan parameter multiplicity, m = 2 dan R = { AAAA, AAAC, AATC, ATCA }. Sebuah l-tuple dengan length 3, disebut 3-tuple berisi AAA dikatakan sebagai solid tuple, karena AAA merupakan substring dari minimal 2 anggota himpunan R, yaitu AAAA dan AAAC.
4
Penyusunan Himpunan Spectrum Sebuah spectrum dari sebuah himpunan sekuens DNA yaitu R = {r1, r2, r3, ..., rk}, parameter multiplicity m dan length l, dinotasikan sebagai Tm,l(R). Definisi dari spectrum Tm,l(R) adalah himpunan seluruh l-tuple yang solid saja dari himpunan sekuens DNA R dengan parameter multiplicity sebuah bilangan bulat m. Jadi spectrum didapat dari hasil perumusan l-tuple yang merupakan solid tuple yang telah didapatkan pada tahap sebelumnya. Setelah tahap ini dimiliki sebuah himpunan spectrum yang digunakan pada tahap penelitian selanjutnya. Deteksi dan Koreksi Error Setelah didapatkan sebuah himpunan spectrum Tm,l(R), maka selanjutnya dilakukan proses koreksi error dari data sekuens DNA dengan metode spectral alignment. Diberikan sebuah string sekuens DNA s, spectrum Tm,l(R), serta himpunan seluruh T-String. Sebuah sekuens DNA s* dikatakan sebagai sebuah TString jika setiap l-tuple pada s* merupakan elemen dari spectrum Tm,l(R). Permasalahan spectral alignment adalah mencari anggota himpunan TString s* didalam suatu himpunan seluruh T-String yang meminimumkan fungsi jarak d(s, s*). Fungsi jarak yang digunakan pada penelitian ini adalah jarak Levenshtein. Sebagai contoh jika S adalah himpunan T-String, dengan anggotanya s1 = ATCGAGCT, s2 = ATCCATCT, s3 = ATCGAACT, dan sekuens yang terdapat kesalahan pembacaan s = ATCGGGCT. Maka masalah spectral alignment adalah menemukan s* anggota S yang meminimumkan jarak Levenshtein antara s dan s* . Pada contoh tersebut yang paling dekat ialah s1 dan s*, dengan kesalahan pembacaan pada kode nukleotida ke-3 dari kiri, yang seharusnya hasil pembacaannya adalah A, tetapi dibaca sebagai G. Proses mengkoreksi error pada sekuens DNA dilakukan kepada seluruh data hasil pembacaan yang digunakan pada penelitian secara iteratif. Setelah seluruh data dikoreksi, didapatkan sebuah himpunan R* yang merupakan himpunan sekuens DNA yang telah dikoreksi error-nya dan himpunan R yang merupakan data sekuens DNA sebelum dilakukan koreksi error. Kedua himpunan sekuens DNA ini dievaluasi pada tahapan selanjutnya. Jarak Levenshtein / Edit Distance Pada metode spectral alignment, fungsi jarak digunakan untuk menentukan skor yang menyatakan kedekatan antara dua string sekuens DNA. Pada penelitian ini, fungsi jarak yang digunakan adalah jarak Levenshtein atau sering juga disebut sebagai edit distance (Levenshtein 1966). Jarak Levenshtein dihitung dengan menentukan seberapa banyak aksi single-character edit yang harus dilakukan untuk merubah suatu string menjadi string lain. Aksi yang digolongkan sebagai single-character edit adalah insertion, deletion dan substitution. Secara matematis jarak Levenshtein antara dua string a dan b dapat dirumuskan sebagai berikut : a ( le
(
) {
n{ le
le le (
( (
)
) ) )
n(
)
sela nn a [
]
5
Untuk setiap satu aksi yang diterapkan dihitung sebagai 1 skor. Sebagai contoh: 1 k tten → s tt ng, enghas lkan skor 3 ( substitution “k” enjad “s”, “e enjad “ ” dan insertion karakter “g” d akh r string) 2 s tten → s tt n, enghas lkan skor 1 ( substitution karakter “ ” enjad “e”) Dalam implementasinya pada penelitian ini, setiap aksi tidak diberikan skor 1, melainkan -1. Hal ini untuk memberikan pendekatan yang lebih intuitif, di mana skor dua string yang lebih besar menandakan tingkat kemiripan string yang lebih tinggi. Pattern Matching dengan Enhanced Suffix Array Struktur data enhanced suffix array merupakan suffix array dengan penambahan tabel longest common prefix (LCP), yang digunakan untuk menyimpan panjang maksimum dari prefix yang sama antara dua suffix suf[i] dan suf[i-1] pada suffix array. Kegiatan exact pattern matching adalah kegiatan menentukan apakah sebuah pattern P terdapat pada sebuah string S. Di dalam konteks exact pattern matching, struktur data enhanced suffix array memiliki kompleksitas waktu O(m+z) dan space 6n (Abouelhoda et al. 2002). Kompleksitas tersebut lebih baik jika dibandingkan suffix array dalam hal waktu, serta jika dibandingkan dengan suffix tree dalam hal space. Karena itu untuk metode pattern matching pada penelitian ini digunakan struktur data enhanced suffix array. Kegiatan pattern matching pada penelitian ini digunakan pada tahap penyusunan himpunan spectrum serta penentuan apakah sebuah sekuens digolongkan sebagai sebuah T-String. Pada penyusunan spectrum, data sekuens di-indeks kedalam bentuk enhanced suffix array, dengan pattern yang ingin ditemukan dalam indeks adalah seluruh kemungkinan permutasi berulang untuk tuple sepanjang l. Sedangkan pada penggolongan T-String, himpunan spectrum di-indeks ke dalam bentuk enhanced suffix array, dengan pattern yang ingin ditemukan dalam indeks adalah seluruh substring dari satu instance pada data sekuens. Teknik pattern matching yang memiliki performa baik perlu dilakukan pada penelitian ini karena data sekuens DNA umumnya berukuran besar. Dengan menggunakan struktur data enhanced suffix array diharapkan proses pattern matching dapat dilakukan dalam waktu yang optimum dan relatif cepat. Evaluasi Setelah diperoleh dua data set sekuens DNA yaitu R yang merupakan data sekuens DNA yang tidak melewati tahap koreksi error, dan R* yang melewati tahap koreksi error, maka kedua data set tersebut dievaluasi. Untuk melakukan evaluasi, diperlukan sebuah perangkat lunak DNA sequence assembler. Pada penelitian ini sequence assembler yang digunakan adalah Velvet. Velvet merupakan kumpulan algoritma untuk memanipulasi graf De Bruijn dalam rangka melakukan sequence assembly (Zerbino dan Birney 2008). Teknik evaluasi yang dilakukan adalah dengan menjadikan himpunan R dan R* sebagai input dari Velvet. Setelah diperoleh graf dari kedua data set hasil pembacaan dengan Velvet, maka dihitung jumlah node dari masing-masing graf
6 yang dihasilkan. Jumlah node merepresentasikan kompleksitas graf yang dihasilkan data. Data set yang masih mengandung error cenderung memiliki graf dengan lebih banyak node dibandingkan graf yang dihasilkan dari data set yang telah dikoreksi error-nya. Sehingga graf yang dihasilkan data set yang belum dikoreksi error-nya akan berukuran lebih besar dan lebih kompleks.
HASIL DAN PEMBAHASAN Simulasi Data Sekuens DNA dengan MetaSim Untuk setiap organisme dilakukan simulasi sebanyak satu kali. Simulasi dilakukan dengan menggunakan perangkat lunak MetaSim. Simulasi dilakukan untuk menghasilkan data sekuens DNA yang mengandung error. Data yang dibangkitkan sengaja diberikan error agar nantinya dapat dikoreksi oleh perangkat lunak yang dihasilkan pada penelitian ini. Model error yang digunakan pada MetaSim adalah model Sollexa dengan panjang per fragmen 36 bp. Pada model error yang digunakan, jenis error yang ditimbulkan dibatasi hanya pada error substitusi. Konfigurasi parameter MetaSim untuk setiap simulasi dapat dilihat pada Tabel 2. Tabel 2
Konfigurasi parameter untuk membangkitkan data sekuens DNA dengan simulasi MetaSim Number DNA clone of reads Error size Second Organisme Mean or mate model distribution parameter pairs type Staphylococcus Empirical 1500 Normal 36 0 aureus – Sollexa Acetobacter Empirical 2000 Normal 36 0 pasteurianus – Sollexa Lactobacillus Empirical 2000 Normal 36 0 plantarum – Sollexa
Keluaran proses simulasi yang dilakukan dengan MetaSim pada ketiga organisme adalah tiga fail berformat FASTA (.fna) untuk masing-masing organisme. Setiap fail berisi data set sekuens DNA yang mengandung error hasil dari simulasi dengan MetaSim. Keenam data set inilah yang digunakan pada penelitian ini. Contoh format data yang dihasilkan dari MetaSim dapat dilihat pada Gambar 1.
7
Gambar 1 Contoh format data sekuens DNA hasil simulasi MetaSim
Alur Kerja Perangkat Lunak yang Dihasilkan dalam Mengoreksi Error Penelitian ini menghasilkan sebuah perangkat lunak yang mampu mengoreksi error yang terjadi pada tahap DNA sequencing dengan metode spectral alignment. Diagram alir tahapan kerja perangkat lunak yang dihasilkan dalam mengoreksi error dapat dilihat pada Gambar 2.
Gambar 2 Diagram alir tahapan kerja perangkat lunak yang dihasilkan dalam melakukan DNA sequencing error
8 Perangkat lunak menerima input berupa path fail dengan format FASTA (.fna) berisi data fragmen DNA yang akan dikoreksi. Data masukan dibaca baris per baris yang selanjutnya disebut sebagai reads. Selanjutnya, dibangkitkan permutasi tanpa perulangan dari nukleotida A, C, G, dan T sepanjang l. Pada penelitian ini, parameter l yang digunakan adalah 5. Sehingga, banyaknya permutasi yang dihasilkan berjumlah 45 string DNA yang terdiri atas nukleotida A, C, G, dan T. Hasil permutasi ini untuk selanjutnya disebut sebagai pool. Pada tahap selanjutnya disusun himpunan spectrum dari reads dan pool. Untuk setiap string anggota pool diklasifikasikan sebagai weak atau solid dengan merujuk pada himpunan reads. Dengan begitu terbentuklah suatu himpunan spectrum di mana anggotanya merupakan seluruh anggota pool yang digolongkan solid. Dalam menentukan apakah sebuah string dari pool merupakan solid/weak dipengaruhi oleh parameter multiplicity yang digunakan. Penentuan parameter m dipilih berdasarkan percobaan dengan menghitung jumlah anggota himpunan spectrum yang dihasilkan dengan menggunakan nilai m = {2,3,4,5,6,7,8,9,10}. Pada penelitian ini dipilih parameter m = 10, karena pada nilai tersebut pengaruh perubahan nilai m terhadap perubahan jumlah anggota spectrum sudah tidak terlalu signifikan. Percobaan untuk menentukan nilai parameter m dapat dilihat pada Lampiran 3. Algoritme 1 menunjukkan prosedur penyusunan himpunan spectrum dari anggota reads yang solid saja. Algoritme 1 Prosedur penyusunan himpunan spectrum dari anggota reads yang solid saja /* Masukan : Himpunan reads, himpunan pool, m = 10 Keluaran: Himpunan spectrum */ set numOcc = 0 set indeks = 0 for i := 1...length(pool) for j := 1...length(reads) if (pool[i] equal reads[j]) numOcc++ end if if (numOcc >= m) spectrum[indeks++] = reads[j] end if end for end for return spectrum
Pada tahap selanjutnya disusun himpunan T-String dengan merujuk pada himpunan spectrum. Untuk setiap anggota reads ditentukan apakah fragmen tersebut merupakan T-String atau bukan T-String. Maka diperoleh himpunan TString dari himpunan reads. Untuk menentukan sebuah fragmen merupakan TString atau bukan T-String perlu diketahui seluruh substring dari fragmen tersebut, lalu himpunan substring tersebut dibandingkan dengan spectrum. Anggota himpunan reads yang bukan merupakan T-String dideteksi sebagai fragmen yang mengandung error. Fragmen-fragmen yang dideteksi mengandung error dikoreksi dengan menggunakan metode spectral alignment. Algoritme 2
9 menunjukkan prosedur penyusunan himpunan substrings dari sebuah read. Sedangkan Algoritme 3 menunjukkan prosedur pengklasifikasian sebuah read sebagai T-String atau bukan T-String. Algoritme 2 Prosedur penyusunan himpunan substrings dari sebuah read anggota himpunan reads /* Masukan : Sebuah read anggota himpunan reads, panjang per substring l Keluaran: Himpunan substrings dari read */ string inf int indeks for i := 1...length(read)-l inf = infix(read,i,i+1) substrings[indeks++] = infix end for return substrings
Algoritme 3 Prosedur pengklasifikasian sebuah read sebagai T-String atau bukan T-String /* Masukan : Sebuah read anggota himpunan reads, himpunan substrings dari read Keluaran: True jika read merupakan T-String, False jika read bukan T-String */ set status = 1; for i := 1...length(substrings) for j := 1...length(spectrum) if (substring[i] equal spectrum[j]) status *= 1 else status *= 0 if (status = 0) break end for if (status = 1) return true //read merupakan T-String else return false //read bukan T-String end for
Untuk setiap fragmen yang mengandung error dilakukan proses pairwise sequence alignment dengan setiap anggota dari himpunan T-String. Pada tahap alignment tersebut dilakukan proses menentukan skor kedekatan antara fragmen yang mengandung error dan setiap anggota T-String. Skor kedekatan ditentukan dengan menggunakan jarak Levenshtein. Proses alignment dan scoring pada pengembangan perangkat lunak penelitian ini memanfaatkan salah satu class pada library SeqAn yaitu class align. Pada dasarnya pairwise sequence alignment adalah permasalahan optimasi untuk menentukan solusi terbaik bagaimana sebuah sekuens diturunkan dari sekuens yang lain (Döring et al. 2008). Untuk memberikan solusi optimal dalam masalah optimasi tersebut, class align pada library SeqAn menggunakan pendekatan dynamic programming dengan algoritme Needleman dan Wunsch (1970).
10 Dengan demikian, setiap fragmen memiliki skor masing-masing untuk setiap anggota T-String. Untuk mengoreksi fragmen yang mengandung error, dicari anggota T-String manakah yang memiliki skor tertinggi, artinya memiliki jarak paling dekat dengan fragmen tersebut. Fragmen yang mengandung error tersebut dikoreksi dengan mensubstitusikan fragmen dengan T-String dengan skor tertinggi. Proses tersebut berulang untuk setiap fragmen yang mengandung error secara iteratif, hingga seluruh error yang terdeteksi berhasil dikoreksi. Hasil keluaran perangkat lunak adalah sebuah fail dengan format FASTA (.fna) yang berisi data reads di mana seluruh error yang terdeteksi telah dikoreksi. Algoritme 4 menunjukkan prosedur deteksi dan koreksi DNA sequencing error dengan metode spectral alignment. Algoritme 4 Prosedur deteksi dan koreksi DNA sequencing error dengan metode spectral alignment /* Masukan : Himpunan posisi seluruh anggota reads yang bukan T-String, himpunan T-String, himpunan reads Keluaran: Himpunan reads yang telah dikoreksi */ int pos, tstring_max_pos, max_score, count; String[] align set pos = 0 for i := 1...length(posisi) set pos = posisi[i] align[0] = pos int idx set idx = 0 set max_score = -1000 for j := 1...length(TString) align[1] = TString[j] //alignment dan scoring antar elemen pada array align int score = globalAlignment(align) if (score > max_score) max_score = score tstring_max_pos = idx idx++ end for reads[pos] = TStrings[max_pos] //himpunan reads //pada posisi ‘pos’ //dikoreksi T-String //posisi ‘max_pos’ end for return reads
Data yang mengandung error yang telah dibangkitkan sebelumnya menjadi masukan untuk perangkat lunak yang dihasilkan. Perangkat lunak inilah yang mendeteksi dan mengoreksi error yang terdapat pada ketiga data set. Maka keluaran dari perangkat lunak ini adalah tiga data set yang telah dikoreksi errornya. Informasi hasil eksekusi perangkat lunak yang dihasilkan untuk masukan data sekuens ketiga organisme dapat dilihat pada Tabel 3.
11
Tabel 3
Informasi hasil eksekusi perangkat lunak yang dihasilkan dalam mendeteksi dan mengoreksi error Jumlah reads Jumlah Jumlah Waktu Jumlah yang Organisme anggota anggota eksekusi reads terdeteksi spectrum T-String (ms) sebagai error Staphylococcus 1500 844 1198 302 166 730 aureus Acetobacter 2000 937 1816 184 172 004 pasteurianus Lactobacillus 2000 911 1763 237 203 061 plantarum Evaluasi Hasil Koreksi Perangkat Lunak yang Dihasilkan Keterkaitan Jumlah Node dengan Keberhasilan Koreksi Error Pada proses pengkonstruksian graf dalam proses DNA DNA sequence assembly, terdapatnya sequencing error yang tidak dikoreksi dapat mempengaruhi struktur dan kompleksitas graf yang dihasilkan. Adanya error dapat menimbulkan percabangan-percabangan yang tidak perlu pada graf yang dihasilkan. Dengan demikian, kompleksitas sebuah graf dapat diukur dari jumlah node dan jumlah edge yang dihasilkan proses DNA sequence assembly dari suatu data sekuens. Misalkan ingin dikonstruksi graf dari dua buah string fragmen DNA, yaitu AATGC dan GCCAGT. Jika pada fragmen yang seharusnya dibaca sebagai AATGC, tetapi terdapat sebuah error substitusi sehingga dibaca sebagai AATAC, maka graf yang dihasilkan oleh fragmen yang mengandung error lebih kompleks dibandingkan fragmen yang tidak mengandung error. Gambar 3 menunjukkan hasil konstruksi graf pada fragmen yang tidak mengandung error. Gambar 4 menunjukkan hasil konstruksi graf pada fragmen di mana terdapat error substitusi. overlap
Gambar 3 Hasil konstruksi graf dengan dua fragmen yang tidak mengandung error
12
overlap
Gambar 4 Hasil konstruksi graf dengan salah satu fragmen mengandung error substitusi Pada graf hasil konstruksi yang diilustrasikan pada Gambar 3, jumlah node yang dihasilkan adalah delapan buah node, sedangkan pada Gambar 4, jumlah node yang dihasilkan adalah Sembilan buah node. Selain itu, terlihat pada Gambar 2 akibat adanya error substitusi, graf yang dihasilkan memiliki cabang yang tidak perlu dan pada akhirnya menghasilkan jumlah node yang lebih banyak. Ilustrasi pada Gambar 1 dan Gambar 2 menunjukkan bahwa sequencing error, dalam hal ini error substitusi menyebabkan graf yang dihasilkan pada proses DNA sequence assembly menjadi lebih kompleks. Evaluasi Hasil Koreksi dengan Velvet Hasil pengoreksian error dengan metode spectral alignment dievaluasi menggunakan DNA sequence assembler yang telah dikembangkan yaitu Velvet. Data masukan yang digunakan pada Velvet adalah keenam data set yang telah dipersiapkan yang terdiri atas tiga pasang data set sekuens DNA. Setiap pasang mewakili satu organisme yang terdiri atas data sekuens yang masih mengandung error dan data sekuens yang telah melalui tahap koreksi error. Keenam data set tersebut masing-masing tersimpan dalam enam fail dengan format FASTA (.fna). Keluaran dari perangkat lunak Velvet adalah graf De Bruijn yang merupakan hasil assembly dari data sekuens yang menjadi masukan. Graf hasil keluaran Velvet untuk setiap kali melakukan DNA sequence assembly direpresentasikan ke dalam dua fail dokumen plain text bernama “PreGraph” dan “LastGraph”. Kedua fa l ber s daftar node yang merepresentasikan graf yang dihasilkan oleh Velvet. Namun yang digunakan sebaga tolak ukur e aluas pada penel t an n han alah “PreGraph”, sedangkan “LastGraph” t dak d perhat kan. Hal n d karenakan graf ang d representas kan pada “LastGraph” erupakan has l akh r dar Vel et ang telah elalu proses simplifikasi graf dan error removal yang dilakukan oleh Velvet itu sendiri. Hal ini en ebabkan has l graf pada “LastGraph” enjad t dak rele an terhadap tujuan penel t an n . Graf ang d representas kan dala fa l “PreGraph” erupakan graf hasil assembly sebelum dilakukan simplifikasi graf dan error removal oleh Velvet, sehingga dapat dijadikan tolak ukur keberhasilan perangkat lunak yang dihasilkan pada penelitian ini dalam konteks melakukan koreksi terhadap sequencing error. Dalam setiap proses DNA sequence assembly menggunakan Velvet, diharuskan untuk mentetukan parameter hash length yang disebut k. Parameter
13 hash length atau k merupakan panjang dari k-mers yang dimasukkan kedalam hash table. Nilai k haruslah bilangan ganjil, lebih kecil dari nilai MAXKMERHASH yaitu 31 bp, dan haruslah lebih kecil dibandingkan panjang per fragmen data masukan. Pada penelitian ini nilai k yang digunakan adalah 17, 19, dan 21. Hasil proses DNA sequence assembly menggunakan Velvet untuk beberapa nilai k pada ketiga organisme dapat dilihat pada Tabel 4. Tabel 4 Hasil DNA sequence assembly menggunakan Velvet Jumlah node Koreksi Organisme error k = 17 k = 19 k = 21 Staphylococcus Tidak 83 13 3 aureus Ya 44 7 2 Acetobacter Tidak 117 20 11 pasteurianus Ya 81 11 8 Lactobacillus Tidak 108 17 8 plantarum Ya 83 14 8 Dari hasil evaluasi dengan Velvet diperoleh informasi jumlah node yang dihasilkan untuk setiap data set dengan nilai k = 17, k = 19, dan k = 21. Dapat dilihat bahwa jumlah node yang dihasilkan data yang telah dikoreksi menghasilkan graf dengan jumlah node yang lebih sedikit, untuk setiap organisme, dengan ketiga nilai parameter k. Pengecualian terjadi pada Lactobacillus plantarum untuk k = 21, baik data set yang belum dikoreksi maupun yang telah dikoreksi menghasilkan graf dengan jumlah node = 8. Dari informasi yang didapat, diketahui bahwa perangkat lunak yang dihasilkan telah mampu mengoreksi error dan menyederhanakan graf yang dihasilkan pada tahap DNA sequence assembly.
SIMPULAN DAN SARAN Simpulan Penelitian ini menghasilkan perangkat lunak yang mampu melakukan koreksi terhadap sequencing error pada data sekuens DNA dengan metode spectral alignment. Graf keluaran proses DNA sequence assembly yang dihasilkan data yang masih mengandung error lebih kompleks dibandingkan dengan graf yang dihasilkan data yang telah dikoreksi error-nya. Hal ini menunjukkan bahwa upaya mengoreksi sequencing error sebagai tahap praproses mampu menyederhanakan graf yang dihasilkan pada tahap DNA sequence assembly. Saran Untuk penelitian selanjutnya disarankan menerapkan algoritma yang sama dengan menyertakan pemrosesan paralel atau GPU computing untuk memperbaiki waktu eksekusi program dalam mengoreksi DNA sequencing error. Karena
14 kegiatan koreksi error dengan metode spectral alignment sendiri secara kesuluruhan membutuhkan waktu komputasi yang tinggi. Diharapkan dengan diterapkannya konsep pemrosesan paralel maupun GPU computing mampu memperbaiki waktu eksekusi perangkat lunak dalam mengoreksi error.
DAFTAR PUSTAKA Abouelhoda MI, Ohlebusch E, Kurtz S. 2002. Optimal exact string matching based on suffix arrays. Di dalam: String Processing and Information Retrieval; 2002 Jan. Berlin (DE): Springer. hlm 31–43. Chaisson M, Pevzner PA, Tang H. 2004. DNA sequence assembly with short reads. Bioinformatics. 20(13):2067–2074. Döring A, Weese D, Rausch T, Reinert K. 2008. SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinformatics. 9(1):11. Levenshtein VI. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady. 10:707. Needleman SB, Wunsch CD. 1970. A general method applicable to the search of similarities in the amino acid sequence of two proteins. J Mol Biol. 48(3): 443–453 Shi H, Schmidt B, Liu W, Wittig WM. 2009. Accelerating error correction in high-throughput short-read DNA sequencing data with CUDA Di dalam: IEEE International Symposium on Parallel and Distributed Processing. hlm 1–8. Zerbino DR, Birney W. 2008. Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. 18(5):821–829.
15
Lampiran 1 Source code program #include #include #include #include #include #include #include #include #include #include
<string> <seqan/sequence.h> <seqan/file.h> <seqan/index.h> <seqan/align.h> <seqan/seq_io.h>
using namespace seqan; using namespace std; typedef Iterator<StringSet >::Type TStringSetIterator; //iterator untuk stringset DNA typedef Iterator<StringSet<String> >::Type TIntSetIterator; //iterator untuk stringset DNA typedef Iterator::Type TStringIterator; //iterator untuk stringset DNA typedef Align TAlign; // align type //fungsi ini untuk menyusun 1 baris elemen dari hasil generate permutasi DnaString getElemenPermutasi(const unsigned *slots, const unsigned L) { unsigned i; DnaString string = ""; for (i = 0; i < L; ++i) { if(slots[i] == 0) append(string, 'A'); else if(slots[i] == 1) append(string, 'C'); else if(slots[i] == 2) append(string, 'G'); else if(slots[i] == 3) append(string, 'T'); } return string; } //mengenerate seluruh permutasi dari N karakter, dlm kasus ini 4(A,C,G,T) dengan panjang L, misal L=5, maka permutasi menghasilkan 4^5 = 1024 kemungkinan StringSet generatePermutasi(const unsigned N, const unsigned L) { StringSet stringset; unsigned i, carry=0; unsigned *slots = (unsigned*)calloc(L, sizeof(unsigned)); //slots : memori yang dialokasikan untuk array //sebesar L, dengan ukuran sebesar sekian bytes while(!carry) { for (i=0, carry=1; i < L; ++i) { unsigned b = slots[i] + carry;
16 carry = b/N; slots[i] = b % N; } appendValue(stringset,getElemenPermutasi(slots, L)); } return stringset; } StringSet bacaSekuens(char* filename) { StringSet sekuens; DnaString sekuen; string line; ifstream myfile (filename); if (myfile.is_open()) { while ( myfile.good() ) { getline (myfile,line); sekuen = line; appendValue(sekuens, sekuen); } myfile.close(); } return sekuens; } StringSet bacaFile(char* filename) { StringSet sekuens; StringSet ids; SequenceStream seqStream(filename); if(isGood(seqStream)) { readAll(ids, sekuens, seqStream); } return sekuens; } StringSet getSpectrum(StringSet const & sekuens, StringSet & pool, unsigned M) { Index<StringSet> esaIndex(sekuens); //bangun index dari //data sekuens dalam bentuk enhanced suffix array Finder>> esaFinder(esaIndex); // buat //objek finder dari index StringSet spectrum; unsigned numOcc; //looping pool for (TStringSetIterator it = begin(pool); it != end(pool); ++it) { numOcc = 0; while(find(esaFinder, value(it))) { ++numOcc;
17 } if(numOcc >= M) { appendValue(spectrum, value(it)); } clear(esaFinder); } return spectrum; } //dapatkan seluruh substring sepanjang l dari sebuah sekuen StringSet getSubstrings(unsigned l, DnaString & sekuen) { Infix<String >::Type inf; StringSet substrings; for(unsigned i=0; i<=length(sekuen) - l; ++i) { inf = infix(sekuen, i, i+l); appendValue(substrings, inf); } return substrings; } //cek apakah sebuah sekuen merupakan T-String bool isTString(DnaString & sekuen, StringSet & spectrum, unsigned l) { unsigned status = 1; StringSet substrings = getSubstrings(l, sekuen); Index<StringSet> esaIndex(spectrum); //bangun index dari //data spektrum dalam bentuk enhanced suffix array Finder>> esaFinder(esaIndex); // buat //objek finder dari index for(TStringSetIterator it = begin(substrings); it != end(substrings); ++it) { if(find(esaFinder, value(it))) status *= 1; else status *= 0; if(status == 0) break; clear(esaFinder); } if(status == 1) return true; else return false; } //mendapatkan seluruh T-String dari set sekuens dengan suatu spectrum dan //parameter L, serta array yang menyimpan posisi sekuens yang bukan TString tuple<StringSet, vector > getTStrings(StringSet & sekuens, StringSet & spectrum, unsigned L) {
18 StringSet TStrings; vector posisi; int i = 0; for(TStringSetIterator iter = begin(sekuens); iter != end(sekuens); ++iter) { if(isTString(value(iter), spectrum, L)) appendValue(TStrings, value(iter)); else posisi.push_back(i); i++; } tuple<StringSet, vector> tuple(TStrings,posisi); return tuple; } //menghitung waktu dalam milisecond static double diffclock(clock_t clock1,clock_t clock2) { double diffticks=clock1-clock2; double diffms=(diffticks)/(CLOCKS_PER_SEC/1000); return diffms; } int main(int, char const **) { int start_time, end_time; start_time = clock(); typedef Iterator<StringSet >::Type TStringSetIterator; //iterator untuk stringset DNA StringSet sekuens, pool, spectrum, substrings, TStrings; vector posisi; std::tuple<StringSet, vector > tuple; //tuple untuk menampung Tstring dan posisi non-Tstring TAlign align; const unsigned N = 4; //A,C,G,T const unsigned L = 5; //L-tuple const unsigned M = 10; //multiplikasi //580 cout << "baca file.." <<endl; //sekuens = bacaSekuens("sekuens.txt"); //pembacaan sekuens darifile sekuens = bacaFile("input/acetoEm.fna"); cout << "generate permutasi.." << endl; pool = generatePermutasi(N,L); // pool adalah seluruh kemungkinan //permutasi untuk karakter A,C,G,T jika dibentuk string sepanjang 5 cout << "rumuskan spectrum.." << endl; spectrum = getSpectrum(sekuens, pool, M); cout << "rumuskan TStrings.." << endl; tuple = getTStrings(sekuens, spectrum, L); TStrings = std::get<0>(tuple); posisi = std::get<1>(tuple);
19 resize(rows(align), 5); cout << "panjang sekuens : " << length(sekuens) << endl; cout << "panjang himpunan spektrum : " << length(spectrum) << endl; cout << "panjang himpunan posisi salah : " << length(posisi) << endl; cout << "panjang himpunan Tstring : " << length (TStrings) << endl; cout << "scoring.." << endl; int pos = 0, tstring_max_pos, max_score, count = 1;; for(vector::iterator posit = posisi.begin(); posit != posisi.end(); ++posit) { pos = *posit; assignSource(row(align,0), sekuens[pos]); int i = 0; max_score = -1000; for(TStringSetIterator it = begin(TStrings); it != end(TStrings); ++it) { assignSource(row(align,1), value(it)); int score = globalAlignment(align, Score(0,-1,-1)); if(score > max_score) { max_score = score; tstring_max_pos = i; } i++; } sekuens[pos] = TStrings[tstring_max_pos]; //sekuens nomor pos + 1 akan digantikan dengan TString nomor //tstring_max_pos count++; } /*penulisan ke file */ cout << "Tulis ke file -> out.fna . . . " << endl; StringSet ids; for(int id=1; id<=length(sekuens); id++) { appendValue(ids, "seq" + to_string(id)); } SequenceStream seqStream("out.fna", SequenceStream::WRITE); if(!isGood(seqStream)) { std::cerr << "ERROR: Could not write file.\n"; return 1; } if (writeAll(seqStream, ids, sekuens) != 0) { std::cerr << "ERROR: Could not write to file!\n"; return 1;
20 } end_time = clock(); cout << endl << "Waktu eksekusi : "; cout << diffclock(end_time, start_time) << " ms" << endl; return 1; }
Lampiran 2 Cara menggunakan program Perangkat lunak yang dihasilkan dalam penelitian ini yaitu spectralAlignment.exe dijalankan melalui command prompt di sistem operasi Windows. Tata cara menjalankan program spectralAlignment.exe adalah sebagai berikut : 1. Letakkan program spectralAlignment.exe pada direktori yang diinginkan. 2. Buka command prompt pada sistem operasi Windows. 3. Pindahkan direktori kerja ke direktori tempat menyimpan program spectralAlignment.exe 4. Ketikkan perintah pada jendela command line dengan format sebagai berikut : spectralAlignment [path fail input] [multiplicity] Dengan tipe fail masukan adalah FASTA dan parameter multiplicity sebuah bilangan bulat lebih dari 1. 5. Jika program telah selesai, fail keluaran akan tersimpan di direktori tempat menyimpan spectralAlignment.exe dengan nama out.fna. Contoh : Jika diketahui spectralAlignment.exe dan fail masukan dengan nama fail acetoEm.fna ditempatkan pada direktori N:\spectral alignment, serta parameter multiplicity 10, maka cara menjalankan program adalah sebagai berikut : spectralAlignment acetoEm.fna 10 Contoh hasil keluaran program dapat dilihat pada gambar berikut :
Isi direktori setelah selesai menjalankan program dapat dilihat pada gambar berikut :
21 Lampiran 3 Percobaan beberapa nilai parameter multiplicity dan pengaruhnya terhadap jumlah anggota spectrum Jumlah anggota spectrum 996 966 947 930 923 917 914 913 911
Multiplicity 2 3 4 5 6 7 8 9 10
Jumlah anggota T-String 1981 1935 1894 1843 1819 1794 1780 1774 1763
Jumlah reads yang terdeteksi sebagai error 19 65 106 157 181 206 220 226 237
Tren pengaruh perubahan nilai parameter m terhadap jumlah anggota spectrum : 1050 1000 jumlah anggota 950 spectrum 900 850 2
3
4
5
6 7 multiplicity
8
9
10
22
RIWAYAT HIDUP Penulis lahir di Pontianak pada tanggal 16 November 1991. Penulis merupakan bungsu dari 3 bersaudara dari pasangan Bapak Agus dan Ibu Sukarni. Penulis menghabiskan masa pendidikan dasar, menengah dan atas di kota kelahirannya, Pontianak. Tahun 2009 menjadi tahun kelulusan penulis dari SMA Negeri 1 Pontianak. Di tahun yang sama pula penulis diterima sebagai mahasiswa Institut Pertanian Bogor di departemen Ilmu Komputer lewat jalur SNMPTN. Selama menjalani kuliah di IPB penulis aktif berorganisasi di Himpunan Mahasiswa Ilmu Komputer selama 2 periode. Periode 2010/2011 penulis menjabat sebagai penanggung jawab komunitas .NET dan periode 2011/2012 sebagai ketua divisi edukasi. Penulis juga aktif mengikuti kompetisi-kompetisi antara lain Alpha Innovation di Universitas Bina Nusantara, Nokia Lumia Apps Olympiad yang diadakan oleh Nokia Indonesia, dan program kreativitas mahasiswa yang dihelat oleh DIKTI. Penulis juga sempat melaksanakan praktek kerja lapang selama 2 bulan di Badan Pemeriksa Keuangan RI pada tahun 2012.
