IDENTIFIKASI SINGLE NUCLEOTIDE POLYMORPHISM PADA GENOM KEDELAI MENGGUNAKAN METODE GENETIC PROGRAMMING
MUHAMMAD ABRAR ISTIADI
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2015
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa tesis berjudul Identifikasi Single Nucleotide Polymorphism pada Genom Kedelai Menggunakan Metode Genetic Programming 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 tesis ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Januari 2015 Muhammad Abrar Istiadi NIM G651120401
RINGKASAN MUHAMMAD ABRAR ISTIADI. Identifikasi Single Nucleotide Polymorphism pada Genom Kedelai Menggunakan Metode Genetic Programming. Dibimbing oleh WISNU ANANTA KUSUMA dan I MADE TASMA. Salah satu usaha peningkatan produksi kedelai (Glycine max) adalah melalui pemuliaan tanaman untuk memaksimalkan potensi genetik yang ada pada tanaman kedelai. Pemuliaan tanaman mutakhir berbasis marka molekuler atau marka DNA mampu membuat proses pemuliaan menjadi lebih efisien dibandingkan pemuliaan tanaman konvensional yang berbasis fenotipe. Salah satu marka molekuler mutakhir yang mulai banyak diteliti adalah Single Nucleotide Polymorphism (SNP) yang berupa perubahan atau variasi satu basa nukleotida pada sekuens DNA. Penelitian ini bertujuan mengidentifikasi SNP yang ada pada genom tanaman kedelai dengan menerapkan teknik Genetic Programming (GP) yang merupakan metode evolutionary untuk membangun classifier berbasis rule. Data yang digunakan pada penelitian ini merupakan sekuens DNA genom kedelai dari beberapa aksesi kedelai budidaya. Data tersebut dijajarkan (alignment) dengan sekuens DNA rujukan, kemudian dilakukan perhitungan sejumlah fitur statistik, antara lain kualitas basa dan kedalaman penjajaran. Hasil ekstraksi fitur tersebut diolah dengan GP sehingga dihasilkan rule klasifikasi yang optimal untuk membedakan true SNP (variasi basa yang benar ada dalam genom) dan false SNP (variasi basa yang timbul akibat kesalahan data sekuens). Hasil percobaan menunjukkan bahwa classifier berbasis rule yang dihasilkan oleh GP mampu mengklasifikasikan true dan false SNP dengan sensitivity rata-rata di atas 90% dan specificity rata-rata di atas 80%. Hal ini menandakan bahwa true SNP dapat teridentifikasi dengan baik. Namun demikian, nilai precision hanya sekitar 30% yang berarti banyak terdapat false positive. Hal ini berimplikasi bahwa banyak false SNP yang teridentifikasi sebagai true. Banyaknya false positive ini disebabkan oleh distribusi kelas yang tidak seimbang, yaitu perbandingan kelas true:false sekitar 1:9. Dari sisi rule yang dihasilkan, GP dapat membentuk rule yang sederhana dan dapat diinterpretasi dengan mudah. Salah satu pengetahuan hasil interpretasi yang dapat diambil dari rule yang dihasilkan adalah bahwa faktor atau fitur yang paling berperan dalam membedakan true dan false SNP adalah kualitas basa dari sekuens DNA. Jika kualitas basa tinggi, maka cenderung merupakan true SNP karena berarti kemungkinan kesalahan pada data sekuensnya kecil. Kinerja dari classifier berbasis rule yang dihasilkan oleh GP juga dibandingkan dengan algoritme klasifikasi C4.5 dan SVM dengan dataset yang sama. Hasil perbandingan menunjukkan bahwa classifier GP secara umum memiliki kinerja yang setara dengan C4.5 dan SVM, namun dengan keunggulan bahwa classifier GP berupa rule yang sederhana dan dapat diinterpretasi dibandingkan dengan decision tree hasil C4.5 yang cenderung kompleks dan model SVM yang bersifat black box. Kata kunci: genetic programming, single nucleotide polymorphism
SUMMARY MUHAMMAD ABRAR ISTIADI. Single Nucleotide Polymorphism Discovery from Soybean Genome using Genetic Programming. Supervised by WISNU ANANTA KUSUMA and I MADE TASMA. Plant breeding is a way to improve soybean (Glycine max) crop production by maximizing the genetic potentials of the soybean plant. Modern plant breeding method is based on molecular genetic markers found in the DNA. This genetic marker-based breeding is proven to be more efficient than traditional phenotypebased breeding. The current popular genetic marker is Single Nucleotide Polymorphism (SNP), which is defined as single base substitution or variation found in the DNA sequence. The purpose of this study was to identify SNPs from soybean genome using Genetic Programming (GP) method. GP is an evolutionary computation technique to build and optimize a rule-based classifier. The data used in this study were DNA sequences of soybean genome from some cultivated soybean accessions. The data were aligned with a reference sequence, and then some statistical features were computed, for example base quality score and alignment depth, among others. The feature extraction results were then processed by GP which generated an optimal rule-based classifier. This classifier was used to distinguish true SNPs (the true variations in the genome) and false SNPs (the variations caused by errors in the sequence). Experiment showed that the rule-based classifier built by GP was able to classify true and false SNP with average sensitivity over 90% and average specificity over 80%. These values mean that most of the true SNPs could be identified. However, the precision value was just about 30% which implied that there were many false positives. The high rate of false positives means that there were many false SNPs identified as true. This condition occurred because of the imbalance in the class distribution of the data (the ratio of true:false is about 1:9). Looking at the classification rules generated by GP, it could be seen that GP was able to generate simple and comprehensible rules. One of the knowledge that could be extracted from the generated rules was that the most important factor to determine true or false SNPs were the base quality of the DNA sequence. A high base quality tended to be a true SNP, which mean that the probability of error was low. The performance of rule-based classifier generated by GP was also compared with C4.5 and SVM classification algorithm with the same dataset. The comparison result showed that the GP-generated classifier was able to achieve similar performance with C4.5 and SVM. Moreover, GP-generated classifier had advantages of being a set of simple and understandable rules, compared to the complex C4.5 decision tree and the black-box model of SVM. Key words: genetic programming, single nucleotide polymorphism
© Hak Cipta Milik IPB, Tahun 2015 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB
IDENTIFIKASI SINGLE NUCLEOTIDE POLYMORPHISM PADA GENOM KEDELAI MENGGUNAKAN METODE GENETIC PROGRAMMING
MUHAMMAD ABRAR ISTIADI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Ilmu Komputer pada Program Studi Ilmu Komputer
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2015
Penguji Luar Komisi pada Ujian Tesis:
Dr Ir Agus Buono, MSi MKom
Judul Tesis Nama NIM
: Identifikasi Single Nucleotide Polymorphism pada Genom Kedelai Menggunakan Metode Genetic Programming : Muhammad Abrar Istiadi : G651120401
Disetujui oleh Komisi Pembimbing
Dr Eng Wisnu Ananta Kusuma, ST, MT Ketua
Dr Ir I Made Tasma, MSc Anggota
Diketahui oleh
Ketua Program Studi Ilmu Komputer
Dekan Sekolah Pascasarjana
Dr Eng Wisnu Ananta Kusuma, ST, MT
Dr Ir Dahrul Syah, MScAgr
Tanggal Ujian:
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga tesis berjudul Identifikasi Single Nucleotide Polymorphism pada Genom Kedelai Menggunakan Metode Genetic Programming ini dapat diselesaikan. Terima kasih penulis ucapkan kepada Dr Eng Wisnu Ananta Kusuma, ST, MT serta Dr Ir I Made Tasma, MSc yang telah memberi saran dan masukan selaku Komisi Pembimbing. Terima kasih pula kepada Bapak Habib Rijzaani, MSi dan Bapak Dani Satyawan, MSi dari Balai Besar Litbang Bioteknologi dan Sumberdaya Genetik Pertanian (BB-Biogen) Kementan yang telah memberi arahan terkait topik yang diangkat dalam penelitian ini. Ucapan terima kasih juga penulis sampaikan kepada Direktorat Jenderal Pendidikan Tinggi yang telah membiayai penulis melalui program Beasiswa Unggulan, serta Kementan RI yang telah membiayai penelitian dalam rangka Kerjasama Kemitraan Penelitian dan Pengembangan Pertanian Nasional (KKP3N) 2014. Ungkapan terima kasih juga disampaikan kepada ayah, ibu, serta istri dan putri tercinta, atas segala doa dan kasih sayangnya selama penulis menyusun karya ilmiah ini. Semoga karya ilmiah ini bermanfaat.
Bogor, Januari 2015 Muhammad Abrar Istiadi
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
GLOSARIUM
vii
PENDAHULUAN Latar Belakang Perumusan Masalah Tujuan Penelitian Manfaat Penelitian Ruang Lingkup Penelitian
1 1 3 3 4 4
TINJAUAN PUSTAKA Genomika Kedelai Sequencing DNA Marka Molekuler Single Nucleotide Polymorphism SNP Calling Genetic Programming
4 4 4 6 6 7 8
METODE PENELITIAN Alur Metode Penelitian Data Sekuens Rujukan Data Sekuens Reads Data SNP Pelatihan Penjajaran Sekuens Ekstraksi Fitur Optimasi Genetic Programming Lingkungan Implementasi
10 10 11 11 11 12 12 14 17
HASIL DAN PEMBAHASAN Ketidakseimbangan Distribusi Kelas Pembangkitan Rule dengan GP Klasifikasi dengan Rule Hasil Optimasi GP Modifikasi Fungsi Fitness Visualisasi dan Interpretasi Rule Set Perbandingan dengan Penelitian Sebelumnya
18 18 18 23 28 33 36
KESIMPULAN DAN SARAN Kesimpulan Saran
38 38 38
DAFTAR PUSTAKA
39
LAMPIRAN
42
DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11 12
Fitur-fitur SNP yang digunakan Perbandingan algoritme optimasi GP Parameter percobaan dengan GP Kombinasi percobaan dengan GP Rule set hasil optimasi masing-masing algoritme Hasil klasifikasi dengan algoritme Bojarczuk Hasil klasifikasi dengan algoritme De Falco Hasil klasifikasi dengan algoritme Tan Kombinasi percobaan dengan fungsi fitness modifikasi Rule set algoritme De Falco dengan fungsi fitness modifikasi Hasil klasifikasi dengan fungsi fitness Fss Hasil klasifikasi dengan fungsi fitness Fpr
13 15 16 17 21 25 26 27 28 30 31 32
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Workflow umum metode NGS (Shendure dan Ji 2008) Transition dan transversion Ilustrasi SNP dari beberapa sekuens Alur umum SNP calling Contoh individu GP dalam bentuk rule (Espejo et al. 2010) Ilustrasi operator crossover Ilustrasi operator mutation Metode penelitian Alur optimasi dengan GP Distribusi kelas pada setiap kromosom Grafik fitness algoritme Bojarczuk Grafik fitness algoritme De Falco Grafik fitness algoritme Tan Perbandingan waktu eksekusi algoritme Confusion matrix untuk klasifikasi dua kelas Plot sensitivity dan specificity dari seluruh percobaan Grafik nilai fitness algoritme De Falco dengan fungsi fitness sensitivity dan specificity Grafik nilai fitness algoritme De Falco dengan fungsi fitness sensitivity dan precision Plot perbandingan hasil evaluasi algoritme De Falco dengan fungsi fitness modifikasi Visualisasi rule set dalam bentuk tree Bagian pada hasil penjajaran dengan kedalaman tinggi Perbandingan kinerja dengan metode C4.5 Perbandingan kinerja dengan metode SVM
5 6 7 8 9 9 9 10 16 18 19 20 20 23 23 28 29 30 32 34 35 36 37
GLOSARIUM Aksesi Satuan dari koleksi plasma nutfah atau variasi dalam satu spesies yang dapat disepadankan dengan genotipe, varietas, atau strain. Alel Bentuk-bentuk alternatif dari gen pada suatu lokasi tertentu di dalam kromosom. Contohnya, individu pertama memiliki alel T pada lokasi tertentu, sedangkan individu kedua memiliki alel G pada lokasi yang sama. Alignment Proses penjajaran dari sekuens-sekuens kemiripannya.
DNA untuk
dicari
Basa Nukleotida Komponen penyusun bahan genetik yang pada DNA terdiri atas empat jenis: A (adenin), G (guanin), T (timin), dan C (sitosin). Base Pairs Satuan panjang sekuens yang dihitung berdasarkan jumlah basa nukleotida yang menyusun sekuens tersebut. DNA Bahan genetik makhluk hidup yang terdiri atas deretan basa nukleotida yang menentukan sifat-sifat makhluk hidup tersebut. Exome Bagian dari genom yang hanya terdiri atas exon, yaitu bagian genom yang menyandikan protein. Fenotipe Hasil dari ekspresi gen berupa sifat-sifat yang tampak dari makhluk hidup, seperti warna kulit pada manusia atau ukuran buah pada tanaman. Gen Unit pewarisan sifat makhluk hidup berupa segmen DNA yang fungsional untuk mengkodekan protein tertentu. Genom Seluruh bahan genetik (DNA) dari makhluk hidup yang juga mencakup seluruh gen. Genotipe Keadaan genetik dari individu berupa sifat yang ditentukan oleh gen. Contohnya, individu dengan genotipe “AA” memiliki sifat warna bunga ungu, sedangkan genotipe “aa” memiliki sifat warna bunga putih. Indel Insertion dan deletion, variasi genetik yang berupa penambahan atau pengurangan basa pada sekuens DNA. Kedalaman Penjajaran Jumlah sekuens yang dijajarkan dengan sekuens rujukan pada posisi tertentu. Kromosom Struktur di dalam inti sel makhluk hidup yang terdiri atas molekul DNA dan protein yang dipadatkan.
Reads Sekuens hasil pembacaan DNA makhluk hidup tertentu oleh mesin pembaca DNA (sequencer) yang pada umumnya berukuran pendek. Resequencing Proses mensekuens kembali bahan genetik makhluk hidup tertentu yang sebelumnya sudah pernah disekuens, dengan tujuan mencari variasi genetik. Scaffold Bagian dari genom yang telah direkonstruksi dari reads yang berukuran pendek sehingga menjadi sekuens yang lebih panjang. Sequencing Proses pembacaan bahan menggunakan mesin pembaca DNA.
genetik
makhluk
hidup
dengan
SNP Single Nucleotide Polymorphism, perbedaan satu basa pada sekuens DNA antar-individu. STS Sequence Tagged Sites, sekuens DNA pendek yang telah diketahui susunan basa dan letaknya di dalam genom untuk dijadikan penanda.
1
PENDAHULUAN Latar Belakang Kedelai (Glycine max (L.) Merr) merupakan salah satu komoditas pertanian penting di pasar internasional. Tanaman yang pertama kali dilaporkan berasal dari Cina ini telah dibudidayakan selama lebih dari 5000 tahun (Mishra dan Verma 2010). Kedelai kaya akan protein dan minyak (sekitar 70% protein dan 30% minyak) yang membuatnya termasuk tanaman yang memiliki banyak manfaat. Selain itu, kemampuan simbiosis kedelai dalam hal fiksasi nitrogen menjadikan kedelai elemen penting dalam pertanian yang berkelanjutan (Chan et al. 2012). Indonesia termasuk salah satu produsen kedelai di pasar internasional (Mishra dan Verma 2010). Di Indonesia, produksi kedelai pernah mencapai puncaknya pada tahun 1992 sebanyak 1.87 juta ton. Namun, produksi terus mengalami penurunan hingga pada tahun 2013 hanya sebanyak 0.78 juta ton (BPS 2014). Sebaliknya, konsumsi kedelai cenderung meningkat dari tahun ke tahun. Kebutuhan konsumsi ini tidak dapat dipenuhi oleh produksi lokal yang menurun sehingga impor kedelai harus terus dilakukan dan mengalami peningkatan. Impor ini dapat berdampak pada hilangnya devisa negara (Atman 2009). Untuk memperbaiki keadaan tersebut, produksi kedelai di tingkat petani perlu ditingkatkan. Selain dengan memperbaiki harga jual dan memanfaatkan potensi lahan, produksi dapat ditingkatkan dengan strategi peningkatan proses produksi. Salah satu hal yang dapat ditingkatkan dalam proses produksi ialah penyediaan benih bermutu dari varietas unggul dalam jumlah yang cukup dan mudah dijangkau oleh petani. Kultivar unggul baru dapat diperoleh melalui pemuliaan tanaman yang mengeksploitasi potensi genetik tanaman untuk memaksimumkan ekspresi genetik tanaman pada suatu kondisi lingkungan tertentu (Azrai 2005). Untuk tanaman kedelai, peningkatan produktivitas, kualitas, dan ketahanan terhadap stres merupakan tujuan utama dalam pemuliaan (Chan et al. 2012). Teknologi pemuliaan tanaman telah terbukti berhasil meningkatkan produksi tanaman. Pemuliaan tanaman dengan metode konvensional bergantung pada seleksi fenotipe tanaman serta dipengaruhi oleh keadaan lingkungan dan interaksi dengan lingkungan. Adanya pengaruh lingkungan tersebut terkadang membuat fenotipe yang sesungguhnya sulit diamati jika keadaan lingkungannya tidak sesuai. Kendala lain yaitu sebagian fenotipe yang perlu waktu yang lama untuk bisa diamati, misalnya harus menunggu sampai tanaman berbunga. Hal tersebut membuat proses pemuliaan tanaman secara konvensional membutuhkan waktu yang lama dan biaya yang besar (Moose dan Mumm 2008). Kendala-kendala dari pemuliaan tanaman dengan metode konvensional tersebut mulai teratasi dengan ditemukannya marka molekuler atau marka DNA. Seleksi dengan memanfaatkan marka DNA (marker assisted selection) hanya didasarkan pada sifat genetik tanaman dan tidak dipengaruhi faktor lingkungan sehingga kegiatan pemuliaan menjadi lebih tepat, cepat, hemat biaya, serta hemat waktu (Azrai 2005). Genotipe yang dihasilkan melalui marka molekuler dapat dikombinasikan dengan informasi fenotipe untuk meningkatkan perolehan seleksi. Pemanfaatan marka molekuler dapat meningkatkan efisiensi pemuliaan sebanyak
2 dua kali lipat dibandingkan seleksi berdasarkan fenotipe saja (Moose dan Mumm 2008). Contoh pemanfaatan marker assisted selection pada pemuliaan kedelai ialah identifikasi SNP yang berhubungan dengan gen sifat ketahanan dari hama tertentu (Mammadov et al. 2012) dan ketahanan terhadap kondisi kekeringan (Vidal et al. 2012). Pengembangan marka DNA secara komprehensif untuk pemuliaan kedelai memerlukan adanya data sekuens DNA untuk dianalisis. Kebutuhan ini didukung dengan berkembangnya teknologi next-generation sequencing (NGS) untuk membaca data sekuens DNA dari tanaman kedelai yang diteliti. Teknologi NGS membuat proses sequencing DNA genom menjadi lebih efisien, lebih murah, dan menghasilkan data genomik dengan kuantitas yang sangat besar dalam waktu yang singkat untuk dianalisis dibandingkan dengan teknologi sequencing DNA konvensional (Metzker 2010). Pemuliaan kedelai berbasis genetika juga memerlukan informasi terkait genetika dan genomika kedelai. Terkait hal tersebut, penelitian genetika dan genomika kedelai telah banyak dilakukan. Salah satu terobosan penting ialah sekuens genom rujukan yang telah berhasil disusun dari kedelai budidaya varietas Williams 82 pada tahun 2010 (Schmutz et al. 2010). Genom kedelai yang telah disusun ini dijadikan sebagai sekuens genom rujukan (reference genome) untuk penelitian-penelitian selanjutnya (Chan et al. 2012). Selain itu, telah dilakukan resequencing genom 31 aksesi kedelai liar dan budidaya untuk mengidentifikasi pola keragaman genetik (Lam et al. 2010). Resequencing genom tersebut telah berhasil mengidentifikasi variasi genetik dalam jumlah besar antara kedelai liar dan kedelai budidaya. Li et al. (2013) juga melakukan resequencing terhadap 25 aksesi kedelai yang terdiri atas kedelai liar, ras lokal Cina, dan kedelai budidaya modern. Penelitian tersebut juga mengidentifikasi variasi genetik dan hubungan kekerabatan antar-aksesi kedelai yang diteliti. Untuk kedelai Indonesia, Balai Besar Litbang Bioteknologi dan Sumber Daya Genetik Pertanian (BB Biogen) Kementerian Pertanian telah melakukan resequencing aksesi-aksesi kedelai lokal untuk melakukan karakterisasi variasi genom dengan tujuan penemuan gen (gene discovery) dan marka DNA berbasis sekuens genom (Satyawan et al. 2014). Terdapat beberapa jenis marka DNA yang dapat mendukung proses pemuliaan tanaman (Azrai 2005). Salah satu marka yang mutakhir dan mulai banyak diteliti ialah Single Nucleotide Polymorphism (SNP). SNP merupakan perbedaan satu basa nukleotida antar-sekuens DNA dari individu-individu yang dibandingkan. SNP dapat mencakup lebih dari 90% dari variasi genetik, sehingga mampu menjadi penanda pada perbedaan antar-varietas dari suatu spesies. Selain itu, SNP juga jauh lebih melimpah jumlahnya dibandingkan dengan marka DNA lain (Matukumalli et al. 2006). Studi analisis SNP pada kedelai telah mengidentifikasi banyak SNP yang memiliki efek signifikan terhadap sifat tanaman (Zhu et al. 2003; Chan et al. 2012). Identifikasi SNP dilakukan secara komputasional dengan program komputer (Oeveren dan Janssen 2009). Terdapat beberapa program yang telah tersedia dengan spesifikasi yang berbeda-beda, antara lain Samtools, GATK, dan SOAPsnp, yang dirancang untuk data berukuran besar yang dihasilkan dari sequencing DNA genom total dengan teknologi NGS (Nielsen et al. 2011; O‟Fallon et al. 2013). Program-program tersebut berbasis model probabilistik dan memiliki peluang untuk ditingkatkan akurasinya dengan menggunakan fitur atau
3 ciri dari sekuens yang belum tercakup oleh model probabilistik. Teknik klasifikasi dengan machine learning telah diterapkan untuk tujuan peningkatan akurasi tersebut. Matukumalli et al. (2006) menggunakan metode decision tree untuk mengelompokkan SNP menjadi true SNP dan false SNP berdasarkan sejumlah fitur dari data sekuens DNA. Penelitian tersebut menggunakan data STS (Sequence-Tagged Sites) kedelai dari 6 kultivar, namun belum menggunakan teknologi NGS untuk sequencing DNA-nya. Hasil klasifikasi menunjukkan akurasi sebesar 84.8%, yaitu peningkatan hampir 5 kali lipat jika dibandingkan dengan identifikasi SNP dengan program PolyBayes (tanpa menggunakan machine learning). O‟Fallon et al. (2013) menggunakan metode support vector machine (SVM) untuk tujuan yang sama, yakni membedakan SNP yang sesungguhnya dengan SNP yang teridentifikasi karena adanya error pada sekuens DNA. Penelitian tersebut menggunakan sejumlah fitur dari sekuens DNA yang berupa ukuran statistik, misalnya rata-rata kualitas basa, ragam posisi basa, dan peluang binomial. Data sekuens yang digunakan adalah data exome dari genom manusia yang disekuens dengan teknologi NGS, dan didapatkan nilai sensitivity sebesar 96.9%. Kong (2007) menggunakan metode yang sama (SVM) pada data genom manusia yang berasal dari Japan SNP Database (JSNP). Data pada JSNP adalah data whole genome manusia dari populasi negara Jepang. Fitur yang digunakan pada penelitian tersebut adalah fitur sekuens DNA dari aspek termofisika, misalnya entalpi, entropi, energi bebas, dan suhu leleh. Penelitian tersebut memberikan akurasi sebesar 75.9%. Selain metode-metode tersebut, dapat diterapkan juga metode machine learning yang berbasis evolutionary computation, yaitu genetic programming (GP). GP merupakan salah satu varian dari algoritme genetika (GA) yang dapat digunakan untuk masalah klasifikasi. GP merupakan metode yang fleksibel dan efektif untuk mengoptimalisasi suatu classifier yang dapat dimodelkan dalam bentuk rule atau decision tree. Salah satu kelebihan GP adalah rule yang jelas dan dapat diinterpretasi dengan mudah oleh pakar dibandingkan dengan metode black box seperti SVM (Espejo et al. 2010). Penelitian ini menggunakan GP untuk membangun suatu classifier dalam mengidentifikasi SNP dari genom kedelai. Perumusan Masalah Masalah yang diteliti dalam penelitian ini yaitu cara merepresentasikan fitur dari data SNP agar dapat diukur oleh classifier. Setelah fitur didapatkan, perlu dirancang rule yang dioptimasi oleh GP beserta representasi rule-nya. Dengan demikian, akan didapatkan suatu model classifier yang optimal dan dapat memberikan hasil identifikasi SNP dengan akurasi tinggi. Tujuan Penelitian Tujuan penelitian ini yaitu: 1 Mengoptimalisasi rule untuk identifikasi SNP dengan metode GP. 2 Menerapkan rule hasil dari GP dalam identifikasi SNP pada tanaman kedelai. 3 Mengukur kinerja GP dalam melakukan identifikasi SNP.
4 Manfaat Penelitian Hasil identifikasi SNP dan implementasi dalam bentuk program dari penelitian ini diharapkan dapat memberikan informasi bagi peneliti dalam pemuliaan tanaman kedelai dengan bantuan marka SNP. Selain itu, rule hasil optimalisasi GP dapat menjadi rujukan bagi pakar dalam identifikasi SNP. Ruang Lingkup Penelitian Ruang lingkup penelitian ini mencakup data sekuens aksesi kedelai budidaya yang diambil dari penelitian Lam et al. (2010). Identifikasi SNP dilakukan dalam lingkup seluruh genom (whole genome) dan tidak mencakup identifikasi indel (insertion dan deletion). Selain itu, proses identifikasi menggunakan GP dibatasi sampai SNP putatif tanpa dilakukan validasi secara biologi.
TINJAUAN PUSTAKA Genomika Kedelai Genom kedelai, yaitu keseluruhan bahan genetik dari kedelai terdiri atas 20 kromosom (Chan et al. 2012). Ukuran genom kedelai ini diperkirakan sebesar 1115 Mb (Mega base pair, juta pasang basa). Dari ukuran total genom tersebut, sekitar 950 Mb telah berhasil disekuens dari kedelai varietas Williams 82 dan dirakit menjadi sekuens rujukan (reference sequence) (Schmutz et al. 2010). Kedelai adalah organisme palaeopolyploid, artinya nenek moyang dari kedelai dipercaya merupakan organisme polyploid atau memiliki kromosom yang terduplikasi sebanyak dua, tiga, atau empat. Namun demikian, kedelai tergolong organisme diploid, yakni setiap kromosom memiliki satu pasangan (Chan et al. 2012). Selain itu, pada genom kedelai terdapat banyak perulangan dan duplikasi. Sekitar 59% dari genom adalah elemen repetitif (berulang), dan sekitar 75% dari gen terduplikasi di lebih dari satu lokasi (Schmutz et al. 2010). Sequencing DNA Sequencing (pengurutan) DNA adalah proses pembacaan atau penentuan urutan basa nukleotida (A, adenin; T, timin; G, guanin; atau C, sitosin) dari DNA. Selain menentukan urutan atau sekuens basa dari suatu DNA, proses sequencing juga memberikan nilai kualitas pada setiap basa yang dibaca tersebut. Nilai kualitas menunjukkan tingkat kepercayaan bahwa basa dari DNA dibaca dengan benar oleh alat yang digunakan untuk sequencing (Altmann et al. 2012). Metode sequencing pertama kali diperkenalkan oleh Sanger yang populer dan terus berkembang sejak dua dekade terakhir. Metode Sanger menggunakan teknologi berbasis kapiler, elektroforesis, dan deteksi fluorescence yang berjalan secara otomatis. Metode ini disebut juga metode konvensional atau metode sequencing generasi pertama (Metzker 2010).
5 Teknologi sequencing baru yang berkembang saat ini disebut nextgeneration sequencing (NGS), high-throughput sequencing (HTS), atau metode sequencing generasi kedua. NGS merupakan suatu kelompok metode sequencing baru yang berbeda dengan metode Sanger. Teknik yang diterapkan di dalam NGS beragam tergantung pada teknologi yang digunakan oleh perusahaan pembuat platform. Beberapa platform NGS yang tersedia di pasaran antara lain Roche/454, Illumina/Solexa, dan Helicos/HeliScope (Shendure dan Ji 2008). Meskipun platform-platform NGS tersebut beragam dalam hal teknik biokimia yang diterapkan, terdapat kemiripan dalam hal konsep dan workflow seperti yang diilustrasikan pada Gambar 1 (Shendure dan Ji 2008). Workflow tersebut meliputi pemotongan DNA secara acak, pelekatan adapter untuk menyusun pustaka, amplifikasi misalnya dengan PCR (polymerase chain reaction) serta pembentukan cluster, dan pembacaan basa misalnya dengan deteksi fluorescence untuk mendapatkan data sekuens. Pemotongan DNA
Pelekatan adapter
Amplifikasi dan pembentukan cluster
Pembacaan basa
Gambar 1 Workflow umum metode NGS (Shendure dan Ji 2008)
6 Metode sequencing generasi pertama dan NGS memiliki kelebihan dan kekurangan masing-masing. Metode Sanger mampu menghasilkan reads (hasil pembacaan basa) berukuran panjang dan akurat, namun memerlukan waktu lama, biaya mahal, serta kuantitas data yang rendah. Sebaliknya, metode NGS mampu menghasilkan kuantitas data yang jauh lebih besar dengan waktu yang lebih singkat dan biaya lebih murah, namun hanya mampu menghasilkan reads berukuran pendek dan tidak seakurat metode Sanger (Shendure dan Ji 2008). Oleh karena itu, pada penelitian yang menggunakan NGS untuk sequencing, metode Sanger umumnya masih digunakan untuk memvalidasi hasil analisis dari data tersebut karena akurasinya yang lebih baik (Lam et al. 2010; O‟Fallon et al. 2013). Marka Molekuler Marka molekuler (molecular marker) didefinisikan sebagai bagian tertentu dari DNA yang mampu merepresentasikan perbedaan genetik dalam tingkat genom yang dapat berkorelasi dengan fenotipe (Agarwal et al. 2008). Beberapa marka molekuler yang dikenal yaitu RFLP (restriction fragment length polymorphism), AFLP (amplified fragment length polymorphism), RAPD (random amplified polymorphic DNA), SSR (simple sequence repeat), STS (sequence tagged site), dan SNP (single nucleotide polymorphism). Single Nucleotide Polymorphism Single Nucleotide Polymorphism (SNP) merupakan marka molekuler yang merepresentasikan perbedaan atau perubahan pada satu basa nukleotida DNA antara dua individu pada lokasi tertentu di dalam genom. Satu basa nukleotida (A, T, G, atau C) dapat berubah menjadi basa lain. Perubahan basa dapat berupa transition atau transversion yang diilustrasikan pada Gambar 2. Transition adalah perubahan C menjadi T atau G menjadi A dan sebaliknya. Sementara itu, transversion adalah perubahan C menjadi G, A menjadi T, C menjadi A, atau T menjadi G dan sebaliknya. Selain perubahan basa, terdapat juga variasi yang disebut indel (insertion dan deletion) yang berupa penambahan atau pengurangan basa. SNP pada umumnya bersifat bialel, yakni hanya terdapat dua jenis alel (satu basa berubah menjadi satu basa yang lain), namun tidak menutup kemungkinan adanya SNP yang memiliki lebih dari dua alel meskipun jarang ditemukan (Duran et al. 2009).
A
G Jenis perubahan basa: Transition Transversion
T
C Gambar 2 Transition dan transversion
7 SNP Rujukan Sekuens 1 Sekuens 2 Sekuens 3 Sekuens 4 Sekuens 5
ACCGTACACTAC CCT-AC GTAGACT GTACAC TAGACTCA TAGACTCAC
Gambar 3 Ilustrasi SNP dari beberapa sekuens Ilustrasi adanya SNP ditunjukkan pada Gambar 3. SNP dapat ditemukan dengan menjajarkan (alignment) sekuens-sekuens genom suatu individu dengan sekuens rujukan (Bafna et al. 2013). Insertion atau deletion pada Gambar 3 ditunjukkan dengan adanya posisi kosong pada Sekuens 1 (karakter “-“). Marka SNP sangat berguna dalam biologi molekuler dan pemuliaan tanaman karena jumlahnya yang melimpah dan sesuai dengan teknologi NGS. Aplikasi SNP dalam genomika tanaman antara lain dalam pembuatan peta genetik, analisis pemetaan asosiasi seluruh genom (genome-wide association analysis), serta studi evolusi (Kumar et al. 2012). Namun demikian, terdapat tantangan tersendiri dalam analisis marka SNP untuk tanaman dengan genom yang kompleks seperti kedelai. Sifat bialel pada SNP harus didukung dengan frekuensi SNP yang tinggi untuk menyamai informasi polimorfisme dari jenis marka lain. Selain itu, sifat polyploid memiliki konsekuensi bahwa jumlah SNP yang benarbenar berguna hanya sebagian kecil dari keseluruhan polimorfisme. Tantangan lain yaitu banyaknya elemen repetitif dan duplikasi sekuens yang ditemukan pada genom tanaman pangan termasuk kedelai (Mammadov et al. 2012). Satyawan et al. (2014) melaporkan bahwa pada genom kedelai terdapat rata-rata satu SNP atau indel per 308 basa. SNP Calling Identifikasi SNP, atau lebih umum disebut SNP calling, adalah proses ekstraksi SNP dari data sekuens (Altmann et al. 2012). Diberikan data penjajaran reads dari individu-individu dengan sekuens rujukan, SNP calling melakukan identifikasi lokasi yang memiliki variasi. SNP calling berbeda dengan genotype calling yang mengidentifikasi genotipe dari setiap individu pada lokasi tertentu (Nielsen et al. 2011). Pendekatan umum untuk SNP calling yang menggunakan sekuens rujukan digambarkan dalam Gambar 4. Pertama, sekuens DNA rujukan dan sekuens reads setiap individu dijajarkan (alignment). Kemudian, dari hasil penjajaran tersebut, variasi sekuens diidentifikasi dan diklasifikasikan menjadi SNP putatif (potensial) (Oeveren dan Janssen 2009). Alur umum seperti ini berlaku bagi teknologi sequencing terdahulu maupun teknologi high-throughput sequencing.
8
Rujukan
Reads
Alignment atau Mapping
Identifikasi Variasi Sekuens
SNP Putatif Gambar 4 Alur umum SNP calling Genetic Programming Genetic Programming (GP) merupakan varian dari algoritme genetika (GA), yaitu algoritme pencarian probabilistik yang mengambil basis dari teori evolusi. GP pada asalnya digunakan untuk evolusi program komputer. GP berbeda dengan GA dalam hal representasi individu, yakni menggunakan representasi yang kompleks untuk mengkodekan individu. Representasi individu pada GP biasanya menggunakan skema tree. Namun, pemodelan GP berkembang untuk skema yang lain, misalnya ekspresi matematis maupun sistem berbasis rule (Espejo et al. 2010). GP dapat digunakan untuk menemukan rule klasifikasi dalam berbagai bidang penerapan (Kuo et al. 2007). Rule ini dimodelkan dalam bentuk decision tree yang dioptimasi oleh GP untuk menemukan rule klasifikasi eksplisit dalam bentuk yang paling sederhana untuk berbagai masalah klasifikasi. Rule klasifikasi yang dikombinasikan dengan pengetahuan pakar menghasilkan pengambilan keputusan yang jelas (De Falco et al. 2002), dan pada kasus identifikasi SNP, rule tersebut dapat digunakan untuk mengetahui cara pakar mengevaluasi hasil identifikasi SNP (Matukumalli et al. 2006). Contoh rule klasifikasi dalam bentuk decision tree untuk klasifikasi biner (hanya ada dua kelas) terdapat pada Gambar 5 (Espejo et al. 2010). Tree tersebut merepresentasikan rule berikut untuk suatu atribut NP, PG, dan TT: IF ((NP < 3) OR ((NP ≥ 3) AND (PG ≥ 50) AND (TT < 72))) THEN Class 1. Rule tersebut merupakan satu individu GP yang akan dioptimalisasi dengan operator crossover dan mutation pada tree. Operator crossover menukar sebagian dari induk dengan induk lainnya (dalam hal ini subtree) untuk membentuk individu baru seperti diilustrasikan pada Gambar 6. Sementara itu, operator mutation mengganti subtree dari suatu individu dengan subtree acak seperti diilustrasikan pada Gambar 7 (Kuo et al. 2007).
9
Gambar 5 Contoh individu GP dalam bentuk rule (Espejo et al. 2010) Induk 1
Anak 1
Induk 2
Crossover
Anak 2
Gambar 6 Ilustrasi operator crossover Individu awal
Hasil mutasi
Subtree acak
Gambar 7 Ilustrasi operator mutation
10
METODE PENELITIAN Alur Metode Penelitian Gambaran umum alur metode penelitian yang dilakukan diberikan pada Gambar 8 yang terdiri atas tiga langkah. Langkah pertama ialah pembentukan data pelatihan dengan prosedur penjajaran (alignment) yang disesuaikan dengan yang dilakukan oleh Lam et al. (2010). Prosedur disesuaikan dengan penelitian tersebut karena data SNP yang telah diverifikasi juga menggunakan hasil penelitian tersebut. Setelah didapatkan data alignment pelatihan, dilakukan ekstraksi fitur dari SNP yang digunakan untuk pelatihan. Pembentukan Data Pelatihan
Hasil Penjajaran Pelatihan
Penjajaran Sekuens
Ekstraksi Fitur
Data Genom
SNP Pelatihan
Proses Pelatihan
Optimasi Genetic Programing
Rule Klasifikasi Optimal Proses Evaluasi
SNP Pengujian
Ekstraksi Fitur
Evaluasi Hasil Identifikasi Gambar 8 Metode penelitian
Alignment Pengujian
11 Langkah kedua ialah proses pelatihan dengan menggunakan GP untuk optimasi rule klasifikasi. Proses ini menghasilkan rule klasifikasi SNP yang dioptimalkan untuk identifikasi SNP kedelai. Langkah terakhir yaitu pengujian rule yang telah terbentuk dengan data pengujian, akan dihasilkan SNP hasil identifikasi yang dievaluasi kinerja klasifikasinya. Detail dari setiap tahapan dijelaskan pada subbab-subbab berikut. Data Sekuens Rujukan Data sekuens rujukan yang digunakan merupakan data genom total yang diambil dari kedelai budidaya varietas Williams 82 (Schmutz et al. 2010). Data sekuens diberikan dalam format FASTA dan diperoleh melalui alamat web http://www.phytozome.net/soybean.php. Versi data genom yang digunakan ialah rilis v1.98 dengan 8x coverage (Lam et al. 2010). Data genom kedelai ini terdiri atas 1168 scaffold dengan panjang total 973.3 Mb. Dari 1168 scaffold yang ada, sebanyak 20 scaffold skala kromosom dipetakan menjadi 20 kromosom kedelai, sedangkan sisanya sebanyak 1148 scaffold yang berukuran pendek merupakan scaffold yang tidak dipetakan sehingga tidak digunakan dalam penelitian. Dengan tidak mengikutsertakan scaffold yang tidak dipetakan tersebut dan menyertakan 20 scaffold kromosom, didapatkan data sekuens sepanjang 955.6 Mb. Kromosom dalam data sekuens tersebut diberi label mulai dari Gm01 (Glycine max, kromosom 1) sampai Gm20 (kromosom 20). Data Sekuens Reads Data reads, yaitu sekuens pendek DNA hasil pembacaan oleh mesin sequencing diperoleh dari data whole-genome resequencing aksesi kedelai budidaya oleh Lam et al. (2010) yang disekuens dengan platform mesin Illumina Genome Analyzer II. Data tersebut diperoleh melalui alamat http://public.genomics.org.cn/BGI/soybean_resequencing. Data diberikan dalam format FASTQ. Setiap hasil sequencing dari satu aksesi diwakili dua buah file karena prosesnya menggunakan paired-end sequencing (berpasangan). Data aksesi kedelai liar (G. soja) tidak digunakan karena objek penelitian ini adalah kedelai budidaya (G. max). Terdapat dua jenis data reads berdasarkan panjangnya, yakni reads dengan panjang 44 pasang basa dan reads dengan panjang 75 pasang basa. Data yang digunakan ialah reads dengan panjang terbesar, yaitu 75 pasang basa agar didapatkan hasil yang lebih akurat. Secara keseluruhan, terdapat 14 aksesi kedelai budidaya yang data sekuensnya digunakan (kode C01, C02, C08, C12, C14, C16, C17, C19, C24, C27, C30, C33, C34, dan C35). Data SNP Pelatihan Data SNP yang telah divalidasi berasal dari hasil penelitian Lam et al. (2010), namun hanya mengambil SNP yang teridentifikasi pada aksesi kedelai budidaya. Data tersebut berupa posisi dalam kromosom yang teridentifikasi sebagai SNP, serta perbedaan basa yang terjadi antara sekuens rujukan dan sekuens reads pada posisi tersebut.
12 Seluruh SNP yang tercantum pada data ini dianggap sebagai kelas true SNP, yaitu SNP yang dianggap benar. Sebaliknya, jika ada kandidat SNP yang tidak tercantum pada data ini, maka dianggap sebagai kelas false SNP. Penentuan kelas SNP dengan cara seperti ini sesuai dengan O‟Fallon et al. (2013) yang mengambil data SNP dari database dbSNP pada manusia. Data SNP beserta kelasnya ini yang digunakan dalam proses pelatihan. Penjajaran Sekuens Sekuens reads dari setiap sampel dijajarkan (alignment) dengan sekuens rujukan. Penjajaran dilakukan dengan software Short Oligonucleotide Alignment Program 2 (SOAP2) sesuai Lam et al. (2010). Sebelum dilakukan penjajaran, sekuens rujukan harus diindeks terlebih dahulu oleh SOAP2 untuk mempercepat proses penjajaran. Selain itu, pada data reads perlu dilakukan kontrol kualitas sebelum dijajarkan untuk memastikan bahwa reads yang akan dijajarkan memiliki nilai kualitas sequencing yang baik (Altmann et al. 2012). Software yang digunakan untuk kontrol kualitas serta memotong atau membuang sekuens yang memiliki nilai kualitas rendah ialah PRINSEQ (Schmieder dan Edwards 2011). Penjajaran dilakukan dengan metode paired-end (berpasangan) karena reads yang digunakan merupakan sekuens yang berpasangan. Parameter insert size minimum dan maksimum yang digunakan untuk penjajaran berpasangan diperoleh bersama data reads (Lam et al. 2010). Ekstraksi Fitur Ekstraksi fitur dilakukan dengan membaca hasil penjajaran. Fitur dari setiap kandidat SNP dihitung setiap ditemukan adanya basa pada reads yang berbeda dengan basa pada sekuens rujukan pada posisi tertentu (posisi adanya variasi). Jika perbedaan basa pada posisi tersebut ada pada daftar true SNP, maka perbedaan basa tersebut beserta hasil perhitungan fiturnya diberi label kelas true SNP. Sebaliknya, jika perbedaan basa pada posisi tersebut tidak ada pada daftar true SNP, label kelasnya ialah false SNP. Daftar fitur yang digunakan dan dihitung dari setiap kandidat SNP dicantumkan pada Tabel 1. Fitur-fitur tersebut merupakan fitur yang bersifat statistik yang dirangkum dari Matukumalli et al. (2006), Oeveren dan Janssen (2009), dan O‟Fallon et al. (2013). Fitur yang bersifat termofisika (Kong 2007) tidak digunakan karena memiliki akurasi yang cukup rendah dibandingkan dengan fitur statistik. Contoh cara perhitungan fitur dilampirkan pada Lampiran 1. Satu fitur dapat memiliki lebih dari satu nilai, misalnya fitur nomor 3 (ratarata kualitas alel mayor dan minor) yang terdiri atas dua nilai, yaitu alel mayor dan alel minor. Selain itu, fitur dapat berupa tipe numerik atau ordinal. Contoh nilai dengan tipe ordinal adalah fitur nomor 1 (tipe variasi). Seluruh fitur pada Tabel 1 digunakan dalam proses pelatihan. Namun demikian, hanya sebagian fitur saja yang akan muncul di dalam rule hasil optimasi GP. Hal ini disebabkan GP mampu melakukan seleksi fitur secara implisit (Espejo et al. 2010), sehingga hanya fitur yang paling signifikan saja yang digunakan untuk membentuk rule.
13 Tabel 1 Fitur-fitur SNP yang digunakan No
Fitur
Referensi
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Tipe variasi Maksimum kualitas alel mayor dan minor Rata-rata kualitas alel mayor dan minor Jarak relatif dengan ujung reads Kedalaman penjajaran (depth) Kualitas alignment Jarak kandidat SNP terdekat Peluang error Banyaknya perulangan dinukleotida Strand bias Total mismatch area Panjang homopolimer Keragaman nukleotida Banyaknya mismatch pada read Keseimbangan alel Kualitas basa pengapit
[1] [1] [1] [1], [2] [1], [2], [3] [1], [3] [2] [3] [3] [3] [3] [3] [3] [3] [3] [3]
Keterangan: [1] Matukumalli et al. (2006), [2] Oeveren dan Janssen (2009), [3] O‟Fallon et al. (2013).
Deskripsi singkat dari masing-masing fitur sebagai berikut: 1 Tipe variasi (ts.tv) Tipe variasi dapat berupa transition atau transversion bergantung pada perbedaan basa pada posisi adanya variasi. 2 Maksimum kualitas alel mayor dan minor (max.qual.major, max.qual.minor) Alel mayor adalah alel yang paling sering muncul, sedangkan alel minor adalah alel kedua yang paling sering muncul setelah alel mayor. Dari kedua alel dihitung nilai kualitas basa maksimum dari reads yang dijajarkan pada posisi adanya variasi. 3 Rata-rata kualitas alel mayor dan minor (mean.qual.major, mean.qual.minor) Sama seperti sebelumnya, namun yang dihitung adalah nilai kualitas basa ratarata dari alel mayor dan minor. 4 Jarak relatif dengan ujung reads (rel.dist) Jarak relatif dari posisi adanya variasi ke kedua ujung dari reads, kemudian dibagi dengan panjang reads. 5 Kedalaman penjajaran (total.depth) Jumlah keseluruhan reads yang dijajarkan pada posisi adanya variasi. 6 Kualitas alignment (mean.mapping.qual) Kualitas penjajaran dari masing-masing reads pada posisi adanya variasi. Nilai kualitas tersebut diberikan oleh program yang melakukan penjajaran. 7 Jarak kandidat SNP terdekat (nearest.flank) Jarak dari posisi adanya variasi ke kandidat variasi lainnya yang terdekat, yaitu kandidat pada posisi sebelum dan sesudahnya. 8 Peluang error (error.prob) Nilai peluang bahwa jumlah reads yang mengandung variasi diambil dari sebaran binomial dengan parameter tertentu.
14 9 Banyaknya perulangan dinukleotida (dinuc.repeat) Jumlah dinukleotida (dua basa nukleotida, misalnya “AT”) yang berulang di sekitar posisi adanya variasi. 10 Strand bias (strand.bias) Nilai chi-square antara reads yang memiliki basa sama dengan rujukan dan reads yang memiliki basa berbeda dengan rujukan di posisi adanya variasi. 11 Total area mismatch (area.mismatch) Rata-rata jumlah basa varian (basa yang berbeda dengan rujukan) pada setiap reads yang dijajarkan pada posisi adanya variasi. 12 Panjang homopolimer (homopolymer.length) Panjang total dari homopolimer (deretan basa yang sama dan berurutan, misalnya “AAAAAA”) di sekitar posisi adanya variasi. 13 Keragaman nukleotida (nuc.diversity) Simpangan dari frekuensi basa rujukan terhadap rata-rata seluruh genom. Nilai simpangan dihitung pada rentang 20 pasang basa di sekitar posisi adanya variasi. 14 Banyaknya mismatch pada read (mismatch.alt) Banyaknya mismatch (basa yang berbeda dengan rujukan) pada reads di posisi adanya variasi. 15 Keseimbangan alel (allele.balance) Rasio jumlah reads yang memiliki basa berbeda dengan rujukan terhadap kedalaman pada posisi adanya variasi. 16 Kualitas basa pengapit (mean.nearby.qual) Rata-rata kualitas dari basa yang mengapit basa di posisi adanya variasi (2 basa sebelum dan 2 basa sesudah). Optimasi Genetic Programming Dari fitur-fitur yang telah didapatkan, dibangun suatu classifier berbasis rule yang dioptimasi dengan GP. Pada penelitian ini, diterapkan tiga algoritme optimasi rule GP, yaitu algoritme Bojarczuk et al. (2004), De Falco et al. (2002), dan Tan et al. (2000) untuk dicari yang paling baik. Masing-masing algoritme tersebut memiliki himpunan fungsi, operator genetik, dan fungsi fitness yang berbeda-beda. Perbandingan parameter algoritme optimasi GP yang digunakan pada penelitian ini disajikan pada Tabel 2. Ketiga algoritme memiliki fungsi fitness yang berbeda. Pada algoritme De Falco dan Bojarczuk, ukuran dari individu berpengaruh terhadap fitness, yakni semakin kompleks ukuran tree, semakin rendah fitness-nya (Bojarczuk et al. 2004; De Falco et al. 2002). Selain itu, himpunan fungsi internal dari ketiga algoritme juga berbeda. Ketiga algoritme tidak menggunakan operator aritmatika, tetapi hanya operator boolean dan perbandingan. Algoritme Bojarczuk hanya menggunakan operator boolean AND dan OR; algoritme Tan hanya menggunakan operator boolean AND dan NOT; sedangkan algoritme De Falco menggunakan seluruh operator boolean (AND, OR, NOT) serta operator IN dan OUT yang menyatakan keanggotaan dalam suatu rentang nilai.
15 Pada algoritme De Falco dan Tan, optimasi GP dilakukan pada setiap kelas secara terpisah. Dengan kata lain, algoritme akan mencari satu rule terbaik untuk satu kelas, baru kemudian dilanjutkan pada kelas yang lain. Khusus pada algoritme Tan, setiap kelas dapat memiliki lebih dari satu rule. Sementara itu, algoritme Bojarczuk hanya berjalan satu kali untuk semua kelas. Bagian konsekuen (label kelas) dari rule pada algoritme Bojarczuk ditentukan berdasarkan kelas yang memiliki fitness terbaik untuk rule tersebut. Tabel 2 Perbandingan algoritme optimasi GP Algoritme
Fungsi fitness
Bojarczuk
Maksimumkan F = Sensitivity × Specificity × Simplicity dengan
De Falco
( axn de-0.5)(nu n de-0.5)
Simplicity =
maxnode = Jumlah node maksimum numnode = Jumlah node
axn de-1
Minimumkan F = ( - (
-
)) + ( e th + ze)
dengan N = Jumlah data sampel CC = Jumlah data yang diklasifikasikan dengan benar IC = Jumlah data yang diklasifikasikan dengan salah Depth = Kedalaman tree Size = Jumlah node Tan
Maksimumkan F =
+
* w1
+
* w2
dengan w1, w2 = Pembobotan TP, TN = True positive, true negative FP, FN = False positive, false negative Algoritme
Fungsi internal
Operator genetik
Seleksi
Bojarczuk De Falco
AND, OR, =, ≠, ≤, > AND, OR, NOT, IN, OUT, <, ≤, =, ≥, > AND, NOT, <, ≤, =, ≠, ≥, >
Crossover Crossover, mutation Crossover, mutation
Roulette wheel Tournament
Tan
Tournament
Meskipun digunakan tiga algoritme yang berbeda, secara umum optimasi GP dilakukan dengan alur yang sama seperti yang tercantum pada Gambar 9. Proses optimasi dilakukan sampai kondisi henti terpenuhi, yaitu jumlah generasi maksimum tercapai.
16
Mulai
Pembangkitan Populasi Awal Individu generasi awal
Evaluasi Individu Awal Seleksi Individu Tetua (Induk) Individu terpilih
Operasi Genetik Individu generasi baru
Evaluasi Individu Baru
Generasi maksimum?
Tidak
Ya
Selesai Gambar 9 Alur optimasi dengan GP Parameter yang digunakan dalam percobaan disajikan pada Tabel 3. Pada penelitian ini digunakan tiga jenis jumlah populasi (50, 100, dan 200) serta tiga jenis peluang crossover (0.7, 0.8, dan 0.9). Peluang mutation dibuat sama (0.1) karena tidak semua algoritme optimasi GP yang digunakan melibatkan operator mutation. Selain itu, jumlah generasi maksimum juga dibuat sama, yaitu 100 generasi. Tabel 3 Parameter percobaan dengan GP Parameter
Nilai parameter
Jumlah generasi maksimum Jumlah populasi Peluang crossover Peluang mutation Parameter fitness De Falco Parameter fitness Tan
100 50, 100, dan 200 0.7, 0.8, dan 0.9 0.1 = 0.5 w1= 0.7 w2 = 0.8
17 Dengan parameter-parameter tersebut, disusun kombinasi percobaan seperti yang disajikan pada Tabel 4. Masing-masing algoritme dijalankan dengan kombinasi tiga jenis peluang crossover dan tiga jenis jumlah populasi sehingga terdapat sembilan percobaan per algoritme. Selain itu, pada setiap percobaan dilakukan perulangan sebanyak lima kali untuk dicari hasil yang terbaik. Tabel 4 Kombinasi percobaan dengan GP Algoritme Bojarczuk
De Falco
Tan
Kode Peluang Jumlah percobaan* crossover populasi B1 0.7 50 B2 0.7 100 B3 0.7 200 B4 0.8 50 B5 0.8 100 B6 0.8 200 B7 0.9 50 B8 0.9 100 B9 0.9 200 F1 0.7 50 F2 0.7 100 F3 0.7 200 F4 0.8 50 F5 0.8 100 F6 0.8 200 F7 0.9 50 F8 0.9 100 F9 0.9 200 T1 0.7 50 T2 0.7 100 T3 0.7 200 T4 0.8 50 T5 0.8 100 T6 0.8 200 T7 0.9 50 T8 0.9 100 T9 0.9 200
* Setiap percobaan dilakukan perulangan sebanyak lima kali
Lingkungan Implementasi Implementasi dilakukan pada komputer dengan spesifikasi prosesor Intel Core i3 3.2 GHz, memori 4 GB, dan harddisk 2 TB. Perangkat lunak sistem operasi yang digunakan ialah Linux Ubuntu versi 14.04. Bahasa pemrograman yang digunakan untuk implementasi algoritme ialah Java dengan library SAMtools. Implementasi GP dilakukan dengan library JCLEC (Java Class Library for Evolutionary Computation) (Ventura et al. 2007).
18
HASIL DAN PEMBAHASAN Ketidakseimbangan Distribusi Kelas Dari hasil pembangkitan data pelatihan, didapatkan distribusi kelas (true dan false) pada setiap kromosom kedelai seperti yang disajikan pada Gambar 10. Dari hasil tersebut dapat dilihat bahwa persentase kelas true hanya sekitar 5–10% dari keseluruhan data, sedangkan sisanya merupakan kelas false. Adanya ketidakseimbangan distribusi kelas ini dapat membuat hasil klasifikasi hanya baik pada kelas mayoritas (false), sedangkan pada kelas minoritas (true) hasil klasifikasi cenderung tidak baik (He dan Garcia 2009). Oleh karena itu, pada pembangunan model klasifikasi dengan GP, diperlukan fungsi fitness yang dirancang sedemikian rupa untuk menangani data yang distribusi kelasnya tidak seimbang (Bhowan et al. 2010). Kelas True
Kelas False
Jumlah kandidat (dalam ribu)
3000 2500 2000 1500 1000 500 0
Gambar 10 Distribusi kelas pada setiap kromosom Dari Gambar 10, dapat dilihat juga bahwa jumlah kandidat per kromosom ada dalam satuan juta, yakni paling sedikit berjumlah sekitar 1.5 juta data (Gm16), dan paling banyak berjumlah sekitar 2.6 juta data (Gm18). Jika seluruh data digunakan, maka akan didapatkan total sekitar 40 juta data. Jumlah ini sangat besar dan akan membuat algoritme klasifikasi berjalan dengan tidak efisien. Oleh karena itu, pada penelitian ini hanya digunakan sebagian dari data. Untuk fase pelatihan, digunakan data kromosom Gm18 yang memiliki jumlah data paling banyak, sedangkan untuk fase pengujian, digunakan data kromosom Gm01 yang jumlah datanya kedua terbanyak. Pembangkitan Rule dengan GP Dengan data pelatihan yang digunakan (Gm18), dilakukan pembangkitan rule klasifikasi dengan optimasi GP. Untuk optimasi, digunakan ketiga algoritme (Bojarczuk, De Falco, dan Tan) untuk dibandingkan hasilnya.
19
Algoritme Bojarczuk Dari setiap percobaan (B1 sampai B9) diambil hasil yang memiliki nilai fitness terbaik dari lima kali ulangan. Grafik fitness maksimum per generasi pada pembangkitan rule dengan algoritme Bojarczuk dapat dilihat pada Gambar 11. Dari grafik tersebut, terlihat bahwa seluruh kombinasi percobaan menghasilkan nilai fitness yang konvergen ke nilai sekitar 0.724. Terdapat tiga percobaan (B2, B6, dan B9) yang memiliki nilai fitness paling tinggi dibandingkan percobaan lain namun tidak signifikan perbedaannya, yaitu nilai fitness 0.725. Selain itu, dapat dilihat juga bahwa algoritme Bojarczuk dapat konvergen dengan cepat, yaitu pada sekitar generasi ke-10. Kekonvergenan yang cepat menuju satu nilai fitness yang sama ini disebabkan algoritme Bojarczuk tidak menggunakan operator mutation pada saat melakukan optimasi (Bojarczuk et al. 2004). Tidak adanya mutation menyebabkan populasi pada GP memiliki keragaman yang rendah karena hanya bergantung pada keragaman individu pada populasi awal. Akibatnya, tidak ditemukan material genetik baru pada saat proses evolusi individu GP yang mungkin dapat meningkatkan keragaman dan mengubah fitness. 0.8
Fitness maksimum
0.7 0.6 0.5 0.4 0.3
B1
B2
B3
0.2
B4
B5
B6
0.1
B7
B8
B9
0 0
10
20
30
40
50 60 Generasi
70
80
90
100
Gambar 11 Grafik fitness algoritme Bojarczuk Algoritme De Falco Dari setiap percobaan (F1 sampai F9) diambil hasil yang memiliki nilai fitness terbaik dari lima kali ulangan. Pada Gambar 12 disajikan grafik fitness minimum per generasi untuk algoritme De Falco. Grafik menunjukkan nilai fitness yang cenderung menurun seiring meningkatnya generasi karena fungsi fitness algoritme De Falco bertujuan meminimumkan kesalahan klasifikasi. Oleh karena itu, semakin rendah fitness suatu individu (semakin sedikit kesalahan klasifikasinya) maka semakin optimal individu tersebut. Dari grafik, terlihat bahwa setiap percobaan memberikan fitness akhir yang bervariasi. Hasil percobaan yang menggunakan jumlah populasi rendah cenderung memiliki fitness yang kurang optimal dibandingkan percobaan dengan jumlah populasi lebih besar. Hal ini disebabkan semakin banyaknya jumlah populasi, maka keragaman genetik pada populasi semakin besar sehingga dimungkinkan
20 adanya bahan genetik yang memberikan fitness yang lebih unggul. Selain itu, adanya operator mutation pada algoritme De Falco menyebabkan banyaknya variasi pada populasi. Hal ini dapat dilihat dari grafik fitness yang terkadang naik atau turun dan tidak konvergen dengan cepat. Jika jumlah generasi ditingkatkan, maka dimungkinkan akan didapatkan nilai fitness yang lebih baik. Secara umum, pada generasi paling akhir nilai fitness paling optimal diperoleh dari percobaan F2 (peluang crossover 0.7, jumlah populasi 100) dengan nilai fitness 389.9. Percobaan F9 (peluang crossover 0.9, jumlah populasi 200) memberikan hasil yang tidak jauh berbeda sampai generasi ke-99, namun pada generasi ke-100 fitness-nya menurun. 460 F1
F2
F3
440
F4
F5
F6
430
F7
F8
F9
Fitness minimum
450
420 410 400 390 380 370 360 0
10
20
30
40
50 60 Generasi
70
80
90
100
Gambar 12 Grafik fitness algoritme De Falco Algoritme Tan Setiap percobaan dengan algoritme Tan (T1 sampai T9) diambil hasil yang memiliki nilai fitness terbaik dari lima kali ulangan. Grafik fitness maksimum per generasi dari algoritme Tan disajikan pada Gambar 13. 0.9
Fitness maksimum
0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1
T1
T2
T3
T4
T5
T6
T7
T8
T9
0 0
10
20
30
40
50 60 Generasi
70
80
Gambar 13 Grafik fitness algoritme Tan
90
100
21 Algoritme Tan menggunakan operator mutation di dalam optimasinya. Meskipun demikian, nilai-nilai fitness pada algoritme Tan cenderung stabil dan tidak fluktuatif seperti algoritme De Falco. Hal ini dapat disebabkan oleh adanya elitisme pada algoritme Tan yang mempertahankan individu dengan fitness terbaik sehingga tidak mengalami perubahan selama proses evolusi (Tan et al. 2000). Seluruh percobaan pada algoritme Tan cenderung konvergen di atas generasi ke-20 dengan nilai fitness sekitar 0.815. Percobaan T9 dengan peluang crossover 0.5 dan jumlah generasi 200 memberikan nilai fitness akhir terbaik meskipun perbedaannya tidak signifikan dengan percobaan lain, yaitu nilai fitness sebesar 0.819. Rule Set Hasil Optimasi Rule set hasil optimasi GP dengan ketiga algoritme ditampilkan pada Tabel 5. Dari masing-masing algoritme, diambil percobaan yang memiliki nilai fitness terbaik. Dari rule yang dihasilkan, dapat dilihat bahwa tidak semua fitur yang digunakan untuk pelatihan (lihat Tabel 1) muncul di dalam rule. Hal ini menandakan bahwa dengan algoritme GP, secara implisit telah dilakukan proses seleksi fitur karena hanya sebagian fitur saja yang signifikan untuk membedakan true dan false SNP. Tabel 5 Rule set hasil optimasi masing-masing algoritme Algoritme Percobaan Rule set Bojarczuk B6 IF (max.qual.minor <= 58.990874) THEN (class = false) ELSE IF (max.qual.minor > 58.990874) THEN (class = true) ELSE (class = false) De Falco F2 IF ((allele.balance IN [0.974, 0.156]) AND (max.qual.minor OUT [6.498, 63.871]) AND (total.depth <= 136.940)) THEN (class = true) ELSE IF ((allele.balance OUT [0.921, 0.170]) OR (max.qual.minor <= 62.710)) THEN (class = false) ELSE (class = false) Tan T9 IF (NOT ((NOT (total.depth > 46.690)) AND (max.qual.minor OUT [4.400, 56.187]))) THEN (class = false) ELSE IF ((NOT ((max.qual.minor > 8.191) AND (max.qual.minor IN [59.879, 13.588]))) AND (max.qual.minor OUT [38.760 13.588])) THEN (class = true) ELSE IF ((NOT ((nearest.flank < 1304.846) AND (strand.bias IN [798.362, 1319.737]) AND (mean.nearby.qual > 37.335))) AND (allele.balance <= 0.115)) THEN (class = false) ELSE (class = true)
22 Rule yang dibentuk oleh algoritme GP merupakan gabungan operator logika (AND, OR, dan NOT) serta perbandingan aritmatika (misalnya kurang dari, lebih dari, IN yang berarti di dalam rentang, dan OUT yang berarti di luar rentang) antara fitur data dengan suatu nilai. Nilai yang dibandingkan ini merupakan nilai paling optimal yang dipilih secara acak oleh GP berdasarkan data pelatihan yang digunakan. Masing-masing algoritme menghasilkan rule dengan karakteristik berbedabeda yang dipengaruhi oleh fungsi internal (operator logika dan perbandingan aritmatika) dan fungsi fitness yang digunakan. Algoritme Bojarczuk menghasilkan rule yang sangat sederhana yang hanya terdiri atas satu kondisi per rule. Hal ini disebabkan oleh adanya faktor simplicity pada fungsi fitness-nya (lihat Tabel 2) yang membuat individu atau rule yang memiliki kompleksitas lebih kecil akan memiliki nilai fitness lebih tinggi. Dari hasil tersebut juga dapat dilihat bahwa fitur SNP yang paling optimal untuk klasifikasi berdasarkan algoritme Bojarczuk adalah max.qual.minor (maksimum kualitas alel minor). Pada rule set hasil algoritme De Falco, dapat dilihat bahwa rule yang dihasilkan lebih kompleks, yaitu dua atau tiga kondisi per rule. Dari rule set tersebut, dapat dilihat terdapat beberapa fitur SNP lain selain max.qual.minor yang digunakan sebagai penentu hasil klasifikasi, misalnya allele.balance (keseimbangan alel) dan total.depth (kedalaman penjajaran). Algoritme Tan menghasilkan rule set yang paling kompleks. Hal ini disebabkan algoritme Tan dapat membangkitkan lebih dari satu rule untuk setiap kelas, yang dapat dilihat dari hasil percobaan bahwa terdapat 2 rule untuk kelas false (selain bagian ELSE yang merupakan kelas default). Adanya lebih dari satu rule ini digunakan untuk mensimulasikan fungsi OR, karena algoritme Tan hanya menggunakan fungsi logika AND dan NOT di dalam rule yang dihasilkannya (Tan et al. 2002). Selain karena adanya lebih dari satu rule untuk setiap kelas, fungsi fitness pada algoritme Tan juga tidak memasukkan unsur kompleksitas atau ukuran rule, sehingga ukuran individu rule dapat terus membesar atau dikenal dengan istilah bloating (Espejo et al. 2010). Namun demikian, pada library JCLEC yang digunakan telah ditetapkan ukuran rule maksimum individu yang dapat dibangkitkan sehingga ukuran individu tidak terlalu besar. Rule hasil algoritme Tan juga memiliki redundansi, yaitu pada bagian ELSE IF pertama yang mengandung kondisi: (max.qual.minor IN [59.879, 13.588]) AND (max.qual.minor OUT [38.760 13.588]) Kedua kondisi tersebut memiliki syarat yang beririsan sehingga dapat digabungkan menjadi (max.qual.minor IN [38.760, 59.879]). Selain itu, operatoroperator NOT dapat diringkas dengan membalik operator perbandingan (misalnya „<‟ menjadi „>=‟) atau menerapkan hukum De Morgan untuk operator logika. Perbandingan Waktu Eksekusi Algoritme Perbandingan waktu eksekusi ketiga algoritme disajikan pada Gambar 14. Dari grafik tersebut, dapat dilihat bahwa algoritme Bojarczuk memiliki waktu eksekusi yang paling singkat, yaitu 30.8 menit. Hal ini disebabkan algoritme Bojarczuk melakukan optimasi pada seluruh kelas sekaligus. Sebaliknya,
23 algoritme yang melakukan optimasi pada masing-masing kelas secara terpisah (De Falco dan Tan), waktu eksekusinya lebih lama karena pada masing-masing kelas harus dilakukan optimasi untuk menemukan rule terbaik. Algoritme Tan memiliki waktu eksekusi paling lama, yaitu 509.7 menit atau sekitar 8 jam. Hal ini disebabkan algoritme Tan perlu menentukan beberapa rule sekaligus untuk setiap kelas. Selain itu, terdapat mekanisme tambahan untuk seleksi individu yang disebut dengan token competition untuk memilih rule sedemikian rupa sehingga tidak ada rule yang redundan dari beberapa rule untuk suatu kelas tertentu (Tan et al. 2002). Perbandingan Waktu Eksekusi Bojarczuk De Falco Tan 0
100
200 300 400 Waktu eksekusi (menit)
500
600
Gambar 14 Perbandingan waktu eksekusi algoritme Dari perbandingan hasil pembangkitan rule dan waktu eksekusi, dapat dilihat bahwa algoritme Bojarczuk memiliki waktu eksekusi paling singkat dan rule set paling sederhana, dan algoritme De Falco memiliki waktu eksekusi sedang dan rule set dengan kompleksitas sedang. Sementara itu, algoritme Tan memiliki waktu eksekusi paling lama sekaligus rule set yang paling kompleks. Klasifikasi dengan Rule Hasil Optimasi GP Metrik Evaluasi Evaluasi hasil klasifikasi dilakukan berdasarkan confusion matrix seperti pada Gambar 15. Seluruh kandidat SNP hasil klasifikasi dikelompokkan menjadi empat jenis: true positive, yaitu true SNP yang benar diidentifikasi sebagai true; false positive, yaitu false SNP namun diidentifikasi sebagai true; false negative, yaitu true SNP namun diidentifikasi sebagai false; dan true negative, yaitu false SNP yang benar diidentifikasi sebagai false.
Kelas aktual
Kelas diprediksi True
False
True
TP
FN
False
FP
TN
TP FP FN TN
: true positive : false positive : false negative : true negative
Gambar 15 Confusion matrix untuk klasifikasi dua kelas
24 Dari keempat kelompok tersebut, dapat diturunkan beberapa metrik untuk evaluasi hasil klasifikasi. Metrik-metrik yang digunakan sebagai berikut (He dan Garcia 2009): 1 Akurasi Akurasi adalah perbandingan jumlah data yang diklasifikasikan benar dengan jumlah seluruh data. Metrik akurasi kurang baik untuk kasus distribusi kelas yang tidak seimbang. Akurasi dihitung dengan persamaan: Akurasi =
+ +
+ + 2 Sensitivity Sensitivity, disebut juga recall atau true positive rate, adalah perbandingan jumlah kelas true yang diklasifikasikan benar dengan jumlah seluruh kelas true. Sensitivity dapat disebut juga sebagai akurasi untuk kelas true. Sensitivity dihitung dengan persamaan: ens t v ty =
+
3 Specificity Specificity adalah perbandingan jumlah kelas false yang diklasifikasikan benar dengan jumlah seluruh kelas false. Specificity dapat disebut juga sebagai akurasi untuk kelas false. Specificity dihitung dengan persamaan: ec f c ty =
+
4 Precision Precision, disebut juga positive predictive value (PPV), adalah perbandingan jumlah kelas true yang diklasifikasikan benar dengan jumlah seluruh data yang diklasifikasikan sebagai true. Precision dihitung dengan persamaan: ec s n =
+
Algoritme Bojarczuk Hasil evaluasi algoritme Bojarczuk pada seluruh percobaan dengan data pelatihan (Gm18) dan data pengujian (Gm01) disajikan pada Tabel 6. Dari tabel tersebut, diketahui bahwa akurasi keseluruhan berkisar antara 81–87%. Akurasi untuk kelas true (sensitivity) memiliki nilai berkisar antara 89–93%, yang cenderung lebih besar dari kelas false (specificity) yang berkisar antara 80–87%. Hasil tersebut menunjukkan bahwa classifier mampu mengidentifikasi true SNP dengan cukup baik walaupun dengan rule yang sederhana. Sementara itu, nilai precision rendah, hanya berkisar antara 27–35%, yang berarti terdapat banyak false positive, yaitu false SNP yang diidentifikasi sebagai true SNP.
25 Tabel 6 Hasil klasifikasi dengan algoritme Bojarczuk Percobaan B1 B2 B3 B4 B5 B6 B7 B8 B9
Data evaluasi Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01
Akurasi 84.65 87.95 83.17 86.51 82.47 85.82 81.82 85.16 82.47 85.82 83.17 86.51 82.47 85.82 84.65 87.95 83.17 86.51
Metrik (%) Sensitivity Specificity 90.43 84.09 89.80 87.83 93.13 82.20 92.62 86.13 93.97 81.34 93.57 85.34 94.56 80.57 94.19 84.60 93.97 81.34 93.57 85.34 93.13 82.20 92.62 86.13 93.97 81.34 93.57 85.34 90.43 84.09 89.80 87.83 93.13 82.20 92.62 86.13
Precision 35.78 31.54 33.90 29.42 33.05 28.49 32.31 27.63 33.05 28.49 33.90 29.42 33.05 28.49 35.78 31.54 33.90 29.42
Algoritme De Falco Hasil evaluasi algoritme De Falco pada seluruh percobaan dengan data pelatihan (Gm18) dan data pengujian (Gm01) disajikan pada Tabel 7. Jika dibandingkan dengan algoritme Bojarczuk, hasil dari algoritme De Falco memiliki akurasi keseluruhan yang lebih tinggi, yaitu sekitar 92% untuk data latih dan 95% untuk data uji. Namun demikian, jika dilihat akurasi per kelas, didapati bahwa akurasi kelas true atau nilai sensitivity-nya rendah (berkisar antara 32–49%), sedangkan akurasi kelas false atau nilai specificity-nya tinggi (berkisar antara 97–98%). Hal ini disebabkan fungsi fitness pada algoritme De Falco yang hanya menghitung jumlah data yang diklasifikasikan dengan benar seperti halnya metrik akurasi, tanpa melihat keseimbangan distribusi kelasnya. Sebagai akibatnya, karena kelas false merupakan kelas mayoritas, maka classifier dari algoritme De Falco hanya baik hasilnya pada kelas false. Nilai precision pada hasil algoritme De Falco lebih besar dari hasil algoritme Bojarczuk, yaitu berkisar antara 60–66%. Hal ini selaras dengan tingginya nilai specificity yang berarti jumlah false positive tidak terlalu banyak. Tetapi, rendahnya nilai sensitivity juga berarti bahwa banyak true SNP yang tidak berhasil diidentifikasi.
26 Tabel 7 Hasil klasifikasi dengan algoritme De Falco Percobaan F1 F2 F3 F4 F5 F6 F7 F8 F9
Data evaluasi Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01
Akurasi 92.37 95.05 92.56 95.16 92.54 95.11 92.40 95.11 92.44 95.08 92.46 95.08 92.51 95.13 92.45 95.09 92.44 95.08
Metrik (%) Sensitivity Specificity 42.56 97.26 38.64 98.57 49.83 96.75 46.90 98.17 40.27 97.66 36.55 98.77 42.31 97.32 38.81 98.62 42.66 97.32 38.92 98.59 36.65 97.93 32.85 98.97 36.91 97.96 35.28 98.87 42.84 97.32 39.35 98.57 44.20 97.17 40.28 98.50
Precision 60.34 62.74 60.08 61.55 62.83 64.95 60.72 63.74 60.94 63.22 63.43 66.53 63.94 66.08 61.01 63.22 60.48 62.66
Algoritme Tan Hasil evaluasi algoritme Tan pada seluruh percobaan dengan data pelatihan (Gm18) dan data pengujian (Gm01) disajikan pada Tabel 8. Dapat dilihat bahwa hasil dari algoritme Tan secara umum mirip dengan hasil dari algoritme Bojarczuk, baik dalam hal akurasi keseluruhan (83–87%), sensitivity (90–94%), specificity (82–87%), serta precision (28–36%). Hal ini disebabkan kemiripan fungsi fitness pada kedua algoritme yang keduanya menggunakan faktor sensitivity dan specificity yang dimaksimumkan. Hasil ini menunjukkan bahwa rule set yang dibangun dengan algoritme Tan mampu mengidentifikasi true SNP dengan cukup baik (sensitivity tinggi), namun masih terdapat banyak false SNP yang diidentifikasi sebagai true (precision rendah). Nilai precision 30% dapat diartikan bahwa dari seluruh SNP yang diidentifikasi sebagai true, hanya 30% yang benar-benar true, sedangkan sisanya sebanyak 70% merupakan false positive. Nilai precision yang rendah ini diakibatkan oleh distribusi kelas yang tidak seimbang. Dari kemiripan hasil tersebut dapat dilihat juga bahwa pada kasus identifikasi SNP kedelai ini, kinerja dari rule set kompleks hasil algoritme Tan dapat didekati dengan rule set yang lebih sederhana seperti hasil algoritme Bojarczuk. Pada kasus demikian, prinsip cca ’s az dapat diterapkan dengan memilih model yang lebih sederhana (Espejo et al. 2010).
27 Tabel 8 Hasil klasifikasi dengan algoritme Tan Percobaan T1 T2 T3 T4 T5 T6 T7 T8 T9
Data evaluasi Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01
Akurasi 83.10 86.44 84.67 87.70 84.15 86.79 82.41 85.77 83.77 87.11 83.69 87.03 84.45 87.34 83.81 87.15 85.02 87.45
Metrik (%) Sensitivity Specificity 93.20 82.10 92.71 86.05 91.32 84.02 90.67 87.51 92.60 83.32 92.08 86.46 94.02 81.27 93.64 85.28 91.98 82.96 91.42 86.84 92.49 82.83 91.95 86.73 92.00 83.71 91.48 87.08 92.30 82.98 91.78 86.86 92.30 84.30 91.86 87.17
Precision 33.80 29.32 35.90 31.19 35.25 29.80 32.99 28.42 34.61 30.24 34.56 30.19 35.63 30.65 34.71 30.36 36.57 30.90
Sensitivity dan Specificity Perbandingan sensitivity dan specificity dari seluruh percobaan dengan menggunakan data pengujian Gm01 digambarkan pada Gambar 16. Ukuran dari tiap lingkaran pada grafik tersebut menunjukkan precision dari tiap percobaan relatif terhadap percobaan lain. Dari grafik tersebut, dapat dilihat bahwa algoritme Bojarczuk dan algoritme Tan memberikan hasil yang serupa dalam hal sensitivity dan specificity seperti yang telah disebutkan. Sementara itu, algoritme De Falco memberikan specificity yang lebih tinggi, namun sensitivity-nya jauh lebih rendah dari kedua algoritme yang lain. Nilai sensitivity yang rendah dapat berakibat pada banyaknya true SNP yang tidak berhasil diidentifikasi sehingga tidak dapat digunakan untuk analisis selanjutnya (untuk pemanfaatan SNP dalam studi genetika). Dari segi precision, algoritme De Falco memiliki nilai precision sekitar dua kali lipat dari algoritme Bojarczuk dan Tan yang ditandai dengan ukuran lingkaran yang juga dua kali lipatnya. Hal ini terkait dengan algoritme De Falco yang kinerjanya hanya baik pada kelas false (kelas mayoritas) sehingga specificity serta precision-nya lebih tinggi.
28 100.00
Specificity (%)
96.00
92.00
88.00
Bojarczuk De Falco
84.00
Tan * Ukuran lingkaran menunjukkan precision relatif
80.00 0.00
20.00
40.00 60.00 Sensitivity (%)
80.00
100.00
Gambar 16 Plot sensitivity dan specificity dari seluruh percobaan Modifikasi Fungsi Fitness Algoritme De Falco menghasilkan rule yang tidak terlalu kompleks seperti algoritme Tan dan tidak terlalu sederhana seperti algoritme Bojarczuk. Namun demikian, fungsi fitness-nya membuat classifier yang dihasilkannya hanya baik dalam mengidentifikasi kelas false. Oleh karena itu, fungsi fitness algoritme De Falco dimodifikasi agar menghasilkan kinerja yang lebih baik. Tabel 9 Kombinasi percobaan dengan fungsi fitness modifikasi Fungsi fitness Sensitivity dan specificity
Sensitivity dan precision
Kode percobaan FS1 FS2 FS3 FS4 FS5 FS6 FS7 FS8 FS9 FP1 FP2 FP3 FP4 FP5 FP6 FP7 FP8 FP9
Peluang Jumlah crossover populasi 0.7 50 0.7 100 0.7 200 0.8 50 0.8 100 0.8 200 0.9 50 0.9 100 0.9 200 0.7 50 0.7 100 0.7 200 0.8 50 0.8 100 0.8 200 0.9 50 0.9 100 0.9 200
29 Sama seperti percobaan-percobaan sebelumnya, pada percobaan dengan fungsi fitness baru diterapkan tiga jenis peluang crossover (0.7, 0.8, dan 0.9) serta tiga jenis jumlah populasi (50, 100, dan 200) dengan kombinasi seperti ditampilkan pada Tabel 9. Jumlah generasi maksimum yang digunakan sebanyak 100 generasi. Setiap percobaan dilakukan perulangan lima kali untuk diambil hasil fitness yang terbaik. Fungsi Fitness Berbasis Sensitivity dan Specificity Untuk menghasilkan sensitivity dan specificity yang tinggi, fungsi fitness dimodifikasi menjadi perkalian antara sensitivity dan specificity. Fungsi ini mirip dengan fungsi fitness algoritme Bojarczuk, namun tanpa adanya faktor simplicity. Fungsi tersebut didefinisikan sebagai berikut: Maksimumkan Fss = Sensitivity × Specificity Grafik nilai fitness disajikan pada Gambar 17. Berbeda dengan fungsi fitness asli algoritme De Falco, fungsi ini bertujuan memaksimumkan sehingga semakin besar nilainya maka semakin baik. Dari grafik tersebut, dapat dilihat bahwa seluruh percobaan konvergen menuju nilai fitness antara 0.76–0.77. Terdapat sedikit fluktuasi seperti algoritme De Falco pada Gambar 12, namun fitness dapat menuju kekonvergenan di sekitar generasi ke-60. Secara umum hasil terbaik didapatkan dari percobaan FS3 dengan nilai fitness akhir sebesar 0.777. 0.9 0.8 Fitness maksimum
0.7 0.6 0.5 0.4 0.3 0.2 0.1
FS1
FS2
FS3
FS4
FS5
FS6
FS7
FS8
FS9
0 0
10
20
30
40
50 60 Generasi
70
80
90
100
Gambar 17 Grafik nilai fitness algoritme De Falco dengan fungsi fitness sensitivity dan specificity Fungsi Fitness Berbasis Sensitivity dan Precision Karena pada percobaan-percobaan sebelumnya didapatkan nilai precision yang rendah, maka dibuat fungsi fitness baru dengan harapan dapat memaksimumkan nilai precision sekaligus sensitivity. Fungsi ini merupakan perkalian antara sensitivity dan precision yang didefinisikan sebagai berikut: Maksimumkan Fpr = Sensitivity × Precision
30 0.6
Fitness maksimum
0.5 0.4 0.3 0.2 0.1
FP1
FP2
FP3
FP4
FP5
FP6
FP7
FP8
FP9
0 0
10
20
30
40
50 60 Generasi
70
80
90
100
Gambar 18 Grafik nilai fitness algoritme De Falco dengan fungsi fitness sensitivity dan precision Grafik nilai fitness disajikan pada Gambar 18. Dari seluruh percobaan, didapatkan bahwa nilai fitness tidak cepat konvergen dan lebih bervariasi dengan fitness akhir berada pada rentang 0.33–0.39. Nilai fitness akhir ini masih cukup rendah yang menunjukkan bahwa pada kasus klasifikasi SNP dengan distribusi kelas yang tidak seimbang ini, algoritme GP masih cukup sulit mendapatkan nilai precision yang tinggi. Secara umum hasil terbaik didapatkan oleh percobaan FP3 dengan nilai fitness akhir 0.390. Rule Set Hasil Fungsi Fitness Modifikasi Rule set yang dihasilkan dengan fungsi fitness yang dimodifikasi disajikan pada Tabel 10. Rule set yang ditampilkan hanya yang memiliki fitness terbaik dari masing-masing fungsi modifikasi, yaitu FS3 dan FP3. Rule set ini secara umum memiliki kompleksitas yang serupa dengan algoritme De Falco asli (lihat Tabel 5), namun dengan komposisi yang berbeda. Tabel 10 Rule set algoritme De Falco dengan fungsi fitness modifikasi Percobaan FS3
FP3
Rule set IF ((NOT ((total.depth >= 47.256) OR (NOT (max.qual.minor >= 58.341)))) AND (max.qual.major >= 46.184)) THEN (class = true) ELSE IF (NOT ((max.qual.minor > 58.933) AND (max.qual.major >= 48.921) AND (total.depth < 63.330))) THEN (class = false) ELSE (class = false) IF ((max.qual.minor > 59.699) AND (total.depth <= 82.149) AND (NOT (allele.balance < 0.067))) THEN (class = true) ELSE IF ((total.depth > 60.973) OR (max.qual.minor <= 60.101) OR (NOT (allele.balance IN [0.048, 0.930]))) THEN (class = false) ELSE (class = false)
31 Hasil Klasifikasi dengan Fungsi Fitness Modifikasi Fungsi fitness modifikasi yang digunakan memberi pengaruh pada hasil evaluasi klasifikasi. Hasil klasifikasi dengan menggunakan rule set yang dioptimasi dengan fungsi Fss memberikan nilai sensitivity rata-rata 91.43% dari seluruh percobaan, dan nilai specificity rata-ratanya sebesar 85.92%. Hasil evaluasi secara rinci untuk Fss dapat dilihat pada Tabel 11. Sementara itu, rule set yang dioptimasi dengan fungsi Fpr memberikan hasil yang berkebalikan, yaitu nilai sensitivity rata-rata sebesar 72.50% dan specificity 93.43%. Hasil evaluasi secara rinci untuk Fpr dapat dilihat pada Tabel 12. Nilai-nilai tersebut adalah hasil pengujian menggunakan data pengujian Gm01. Tabel 11 Hasil klasifikasi dengan fungsi fitness Fss Percobaan FS1 FS2 FS3 FS4 FS5 FS6 FS7 FS8 FS9
Data evaluasi Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01
Akurasi 85.75 88.25 83.92 86.69 84.58 86.97 83.17 86.51 85.22 87.63 84.51 86.92 88.77 91.83 85.13 87.55 84.27 86.80
Metrik (%) Sensitivity Specificity 90.34 85.30 89.76 88.16 93.08 83.02 92.62 86.32 92.84 83.77 92.39 86.63 93.13 82.20 92.62 86.13 91.73 84.59 91.24 87.41 92.98 83.68 92.54 86.57 86.64 88.98 85.11 92.25 91.80 84.47 91.33 87.31 93.06 83.41 92.60 86.44
Precision 37.60 32.12 34.96 29.71 35.93 30.14 33.90 29.42 36.85 31.14 35.84 30.08 43.53 40.66 36.70 31.00 35.49 29.89
Dari hasil tersebut, dapat dilihat bahwa fungsi Fss memiliki akurasi yang cenderung lebih besar pada kelas true, sedangkan fungsi Fpr memiliki akurasi yang cenderung lebih besar pada kelas false. Sementara itu, jika dilihat dari metrik precision, hasil yang menggunakan fungsi Fss memiliki nilai precision yang lebih rendah dibandingkan dengan hasil yang menggunakan fungsi Fpr, dengan rata-rata nilai precision masing-masing sebesar 34.16% dan 49.02%. Hal ini tergambar dari plot pada Gambar 19. Pada plot tersebut, dapat dilihat bahwa rule set yang dioptimasi fungsi Fpr memiliki nilai precision yang lebih baik walaupun nilai sensitivity-nya lebih rendah. Dapat dikatakan bahwa fungsi fitness berbasis sensitivity dan precision dapat digunakan untuk menghasilkan rule set yang memiliki nilai precision lebih tinggi.
32 Tabel 12 Hasil klasifikasi dengan fungsi fitness Fpr Percobaan FP1 FP2 FP3 FP4 FP5 FP6 FP7 FP8 FP9
Data evaluasi Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01 Gm18 Gm01
Akurasi 86.36 88.73 91.75 94.41 91.22 93.99 86.85 89.28 92.14 94.80 91.40 94.08 92.15 94.85 91.49 94.14 92.11 94.65
Metrik (%) Sensitivity Specificity 85.80 86.42 84.65 88.99 70.42 93.84 68.47 96.03 77.32 92.59 75.49 95.14 87.59 86.78 86.92 89.42 62.75 95.02 60.52 96.94 75.52 92.95 73.62 95.36 56.25 95.67 52.55 97.49 75.01 93.10 73.26 95.44 70.39 94.24 68.43 96.29
Precision 38.25 32.42 52.85 51.85 50.56 49.25 39.38 33.91 55.29 55.26 51.24 49.75 56.01 56.65 51.60 50.07 54.51 53.50
100.00
Specificity (%)
96.00
92.00
88.00
Fitness asli Fitness Fss
84.00
Fitness Fpr * Ukuran lingkaran menunjukkan precision relatif
80.00 0.00
20.00
40.00 60.00 Sensitivity (%)
80.00
100.00
Gambar 19 Plot perbandingan hasil evaluasi algoritme De Falco dengan fungsi fitness modifikasi
33 Dari plot pada Gambar 19, dapat disimpulkan juga bahwa hasil dengan menggunakan fungsi fitness asli De Falco dapat ditingkatkan dengan menggunakan fungsi fitness Fss jika ingin memaksimumkan sensitivity dan specificity, atau Fpr jika ingin memaksimumkan precision tanpa menurunkan sensitivity terlalu jauh. Selain itu, dapat disimpulkan juga bahwa terdapat tradeoff antara sensitivity dan specificity atau precision pada kasus ini, yakni hanya salah satu metrik saja yang dapat ditingkatkan dengan konsekuensi metrik lain akan turun nilainya. Visualisasi dan Interpretasi Rule Set Visualisasi Rule Set Salah satu kelebihan GP untuk klasifikasi ialah mampu menghasilkan rule yang jelas dan dapat diinterpretasi (Espejo et al. 2010). Hal ini tergambar dari rule set yang dihasilkan oleh algoritme GP yang dapat diatur kompleksitasnya. Classifier dalam bentuk rule set dapat divisualisasikan dalam bentuk tree. Contoh visualisasi rule set ditampilkan pada Gambar 20 untuk rule set hasil percobaan FS3 dan FP3. Visualisasi tersebut dibuat setelah dilakukan penyederhanaan rule dan eliminasi kondisi yang redundan. Contoh penyederhanaan yaitu membuang operator logika NOT dengan menegasikan operator perbandingan (misalnya operator „ < ‟ diubah menjadi „ ≥ ‟) dan menerapkan hukum De Morgan dalam operator logika. Interpretasi Rule Set Pada Gambar 20a, berdasarkan rule set FS3, terdapat 3 kondisi untuk mengidentifikasi kelas true. Kondisi tersebut yaitu jika kondisi maksimum kualitas alel minor (max.qual.minor) lebih dari 58.341, kualitas alel mayor (max.qual.major) lebih dari 46.184, atau kedalaman penjajaran (total.depth) kurang dari 47.256. Ketiga kondisi tersebut dihubungkan dengan operator logika AND sehingga ketiganya harus terpenuhi agar suatu kandidat diidentifikasi sebagai kelas true. Sebaliknya, untuk mengidentifikasi kelas false (pada bagian ELSE IF) juga didasarkan pada ketiga atribut tersebut. Ketiga kondisi dihubungkan dengan operator logika OR, sehingga jika salah satu saja terpenuhi maka akan diidentifikasi sebagai kelas false. Kondisi-kondisi yang harus terpenuhi tersebut jika ditelaah merupakan kebalikan dari kondisi pada kelas true, misalnya jika pada kelas true nilai max.qual.minor tinggi (> 58), maka pada kelas false nilai max.qual.minor rendah (< 58). Selanjutnya, jika ditelaah lebih lanjut, ada kemungkinan bahwa antara rule untuk kelas true dan rule untuk kelas false memiliki kondisi yang tumpang tindih atau overlap (De Falco et al. 2002). Sebagai contoh, jika suatu kandidat memiliki nilai max.qual.major = 47.0, maka nilai tersebut benar di kedua rule (terjadi ambiguitas). Namun, karena rule untuk kelas true dijalankan terlebih dahulu, kandidat tersebut akan diidentifikasi sebagai kelas true. Adanya overlap ini merupakan salah satu kelemahan classifier berbasis rule yang dibangkitkan dengan GP. Oleh karena itu, perlu diterapkan metode tertentu untuk mengatasi kasus overlap seperti ini.
34 Dari kondisi-kondisi tersebut, dapat disimpulkan berdasarkan rule set FS3 bahwa suatu kandidat SNP akan digolongkan sebagai true jika kualitas alelnya (mayor dan minor) tinggi dan kedalaman penjajarannya tidak terlalu tinggi. Kualitas alel tinggi berarti bahwa pembacaan basa DNA memiliki peluang kesalahan yang rendah. Hal ini sesuai dengan hasil-hasil penelitian bahwa kualitas basa merupakan penentu utama untuk membedakan true dan false SNP (Nielsen et al. 2011). a. Visualisasi rule set FS3
b. Visualisasi rule set FP3
Gambar 20 Visualisasi rule set dalam bentuk tree
35 Rule set FP3 (Gambar 20b) memiliki struktur yang mirip dengan rule set FS3, namun dengan perbedaan adanya kondisi terkait keseimbangan alel (allele.balance). Jika keseimbangan alel lebih dari 0.067, maka kandidat akan diidentifikasi sebagai true SNP. Sebaliknya, jika keseimbangan alel kurang dari 0.048 atau lebih dari 0.930 maka akan diidentifikasi sebagai false SNP. Keseimbangan alel yang semakin tinggi berarti bahwa basa yang berbeda dengan rujukan didukung oleh semakin banyak reads (tidak hanya satu reads yang berbeda), sehingga kecil kemungkinannya bahwa perbedaan tersebut timbul karena error (Oeveren dan Janssen 2009). Oleh karena itu, fitur keseimbangan alel ini signifikan untuk membedakan antara true dan false SNP (O‟Fallon 2013). Salah satu aturan yang menarik ialah mengenai kedalaman penjajaran, yaitu jika kedalaman tinggi (lebih dari 60 reads yang dijajarkan pada posisi ditemukannya perbedaan basa) maka cenderung merupakan false SNP. Padahal, disebutkan dalam Oeveren dan Janssen (2009) bahwa jika kedalaman semakin tinggi, maka suatu kandidat SNP semakin berpeluang merupakan true SNP karena didukung oleh banyak reads. Hal ini dapat dijelaskan dengan meninjau suatu bagian dari hasil penjajaran yang ditampilkan pada Gambar 21. Pada bagian tersebut (posisi Gm18:34885676– 34886429), terdapat area yang memiliki kedalaman jauh lebih tinggi dari yang lain (tiga bagian yang diberi tanda panah). Namun, bagian tersebut banyak diisi oleh reads dengan kualitas penjajaran nol (reads yang dijajarkan berwarna putih). Kualitas penjajaran yang bernilai nol disebabkan oleh adanya kesalahan penjajaran (misalignment), sehingga kandidat SNP yang ditemukan pada posisi tersebut cenderung merupakan false SNP. Selain itu, disebutkan juga dalam Nielsen et al. (2011) bahwa kedalaman yang terlalu tinggi dapat mengindikasikan suatu penyimpangan sehingga SNP yang ditemukan pada daerah tersebut perlu difilter.
Gambar 21 Bagian pada hasil penjajaran dengan kedalaman tinggi
36 Perbandingan dengan Penelitian Sebelumnya
Nilai metrik (%)
Perbandingan Kinerja dengan Metode C4.5 Penelitian awal untuk identifikasi SNP berbasis machine learning telah dilakukan dengan dataset yang sama dan menggunakan metode decision tree C4.5 (Istiadi et al. 2014). Dengan algoritme C4.5, didapati bahwa algoritme tersebut sensitif terhadap data yang memiliki ketidakseimbangan distribusi kelas, sehingga algoritme hanya baik dalam mengklasifikasikan kelas false (kelas mayoritas). Untuk mengatasi masalah tersebut, diterapkan metode random undersampling untuk menyeimbangkan distribusi kelas. Random undersampling bekerja dengan cara menghapus secara acak data dengan kelas mayoritas (kelas false) sehingga jumlahnya sama dengan kelas minoritas (kelas true) pada data latih. Model C4.5 dilatih dengan data yang telah diseimbangkan tersebut, dan model hasil pelatihan diuji dengan data uji yang sama dengan penelitian ini (Gm01). Pada data pengujian untuk C4.5 tidak dilakukan undersampling seperti pada data pelatihan agar dapat dibandingkan kinerjanya dengan classifier hasil metode GP. Hasil perbandingan kinerja GP dengan hasil model C4.5 disajikan pada Gambar 22. Classifier yang digunakan untuk mewakili GP adalah hasil percobaan FS3 dan FP3. Hasil dari FS3 sedikit lebih rendah dibandingkan dengan C4.5 pada seluruh metrik. Namun demikian, hasil dari FP3 lebih unggul dari C4.5 kecuali dalam hal sensitivity. 100 90 80 70 60 50 40 30 20 10 0 Akurasi
Sensitivity
C4.5 (Undersampling)
Specificity GP - FS3
Precision
GP - FP3
Gambar 22 Perbandingan kinerja dengan metode C4.5 Secara umum, ketiga metode yang dibandingkan menghasilkan pola nilai metrik evaluasi yang serupa. Selain itu, algoritme C4.5 dapat menghasilkan decision tree yang juga dapat diolah menjadi sekumpulan rule (Matukumalli et al. 2006). Namun demikian, tree yang dihasilkan pada penelitian tersebut berukuran cukup besar (187 node), yang jika diolah menjadi rule set akan membentuk 94 rule. Jumlah tersebut terlalu banyak untuk dapat diinterpretasi dengan mudah, dibandingkan dengan rule set hasil GP yang relatif sedikit dan sederhana.
37
Nilai metrik (%)
Perbandingan Kinerja dengan Metode SVM O‟Fallon et al. (2013) membangun program identifikasi SNP berbasis metode SVM yang disebut dengan SNPSVM. Program SNPSVM bersifat open source (dapat diunduh di alamat https://github.com/brendanofallon/SNPSVM) sehingga dapat digunakan untuk dibandingkan kinerjanya dengan penelitian ini. SNPSVM memiliki modul pelatihan dan modul pengujian. Pada modul pelatihan, digunakan dua jenis data pelatihan, yaitu Gm18 yang asli (distribusi kelas tidak seimbang) dan Gm18 yang telah diseimbangkan dengan metode random undersampling. Dengan demikian, terdapat dua model SVM yang dihasilkan (SVM-u untuk model yang dibangun dengan data yang telah diundersampling). Untuk pengujian, digunakan data yang sama, yaitu Gm01 yang diujikan ke dalam kedua model SVM. 100 90 80 70 60 50 40 30 20 10 0 Akurasi SVM
Sensitivity SVM-u
Specificity GP - FS3
Precision
GP - FP3
Gambar 23 Perbandingan kinerja dengan metode SVM Perbandingan hasil kedua model GP (FS3 dan FP3) dengan kedua model SVM dengan ditampilkan pada Gambar 23. Kedua model SVM unggul dalam hal specificity dibandingkan kedua model GP. Model SVM yang dilatih dengan data kelas tidak seimbang memiliki nilai sensitivity yang cukup rendah (kurang dari 40%), sehingga dapat dikonfirmasi bahwa SVM juga sensitif terhadap data yang distribusi kelasnya tidak seimbang. Perbaikan dengan melakukan undersampling terhadap data (SVM-u) hanya menaikkan sensitivity dengan selisih yang tidak terlalu signifikan (menjadi 52%), dan sebagai akibatnya membuat metrik-metrik lain nilainya sedikit menurun. Secara umum, model yang dihasilkan GP unggul dalam hal sensitivity, sedangkan pada metrik-metrik lain kinerjanya bervariasi tergantung pada kasus. Dari sisi model, SVM bersifat black-box, artinya model tidak dapat diinterpretasi karena berupa deretan angka yang menyatakan support vector, dan tidak dapat diketahui bagaimana model dapat mengeluarkan suatu output. Sebagai implikasinya, dalam kasus identifikasi SNP menggunakan SVM, tidak dapat diketahui aturan untuk membedakan true dan false SNP, dan sulit untuk mengetahui fitur-fitur dari SNP yang signifikan untuk klasifikasi.
38
KESIMPULAN DAN SARAN Kesimpulan Dari hasil yang didapatkan, dapat disimpulkan bahwa identifikasi SNP tanaman kedelai dari data yang dihasilkan dengan teknologi NGS dapat dilakukan dengan menggunakan sejumlah fitur statistik yang dihitung dari hasil penjajaran sekuens DNA. Dengan menggunakan algoritme GP yang mengoptimasi rule set untuk klasifikasi dengan fungsi fitness tertentu, ditemukan subset dari fitur-fitur tersebut yang paling signifikan untuk membedakan antara true SNP dan false SNP, yaitu kualitas alel minor, kedalaman penjajaran, dan keseimbangan alel. Fitur-fitur tersebut disusun sedemikian rupa dengan menggunakan operator logika dan perbandingan untuk membentuk rule set yang dapat digunakan untuk identifikasi SNP. Rule set yang dihasilkan oleh algoritme GP telah digunakan untuk melakukan identifikasi SNP pada salah satu kromosom dari genom tanaman kedelai (Gm01) dengan hasil evaluasi terbaik berupa sensitivity sebesar 92.39% dan specificity sebesar 86.63%, yang berarti sebagian besar dari true SNP dan false SNP dapat teridentifikasi. Namun, dari sisi precision masih didapatkan hasil yang cukup rendah sebesar 30.14% yang berarti masih banyak terdapat false positive dengan sebab adanya ketidakseimbangan distribusi kelas. Jika dibandingkan dengan metode yang digunakan pada penelitian-penelitian sebelumnya, didapatkan bahwa metode GP memiliki kinerja yang setara, namun dengan kelebihan didapatkannya rule set yang jelas dan dapat diinterpretasi.
Saran Saran-saran untuk penelitian selanjutnya yaitu: 1 Data mentah yang digunakan (genom kedelai) hanya berasal dari satu sumber (Lam et al. 2010) yang kemudian disusun ulang pada penelitian ini dengan metode yang tidak persis sama dengan referensi, sehingga validitasnya juga tidak sama. Oleh karena itu, akan lebih baik jika pembangunan model GP untuk identifikasi SNP dilakukan dengan data genom yang telah diolah, lebih valid, dan lebih terverifikasi, misalnya genom manusia. 2 Hasil evaluasi yang didapatkan masih mengalami masalah dengan banyaknya false positive atau rendahnya precision yang diakibatkan ketidakseimbangan distribusi kelas. Untuk itu, pada pelatihan dengan GP perlu dikembangkan fungsi fitness atau parameter optimasi yang lebih baik. Selain itu, perbaikan dapat juga dilakukan dengan menyeimbangkan distribusi kelas pada data pelatihan dengan metode sampling tertentu yang lebih mutakhir.
39
DAFTAR PUSTAKA Altmann A, Weber P, Bader D, Preuss M, Binder EB, Müller-Myhsok B. 2012. A beginners guide to SNP calling from high-throughput DNA-sequencing data. Hum Genet. 131(10):1541–54. Agarwal M, Shrivastava N, Padh H. 2008. Advances in molecular marker techniques and their applications in plant sciences. Plant Cell Reports. 27(4): 617–31. Atman. 2009. Strategi peningkatan produksi kedelai di Indonesia. J Ilmiah Tambua. 8(1):39-45. Azrai M. 2005. Pemanfaatan markah molekuler dalam proses seleksi pemuliaan tanaman. J AgroBiogen. 1(1):26-37. Bafna V, Deutsch A, Heiberg A, Kozanitis C, Ohno-Machado L, Varghese G. 2013. Abstractions for genomics. Commun ACM. 56(1):83-93. Bhowan U, Zhang M, Johnston M. 2010. Genetic programming for classification with unbalanced data. Di dalam: Esparcia-Alcázar AI, Ekárt A, Silva S, Dignum S, Uyar AS, editor. Genetic Programming Lecture Notes in Computer Science. Berlin (DE): Springer Berlin Heidelberg. hlm 1-13. Bojarczuk CC, Lopes HS, Freitas AA, Michalkiewicz EL. 2004. A constrainedsyntax genetic programming system for discovering classification rules: application to medical data sets. Artificial Intelligence in Medicine. 30(1):27– 48. [BPS] Badan Pusat Statistik. 2014. Statistik Tanaman Pangan [diunduh 29 Nov 2014]. Tersedia dari: http://www.bps.go.id/tnmn_pgn.php. Chan C, Qi X, Li MW, Wong FL, Lam HM. 2012. Recent developments of genomic research in soybean. J Genet Genomics. 39:317-324. De Falco I, Della Cioppa A, Tarantino E. 2002. Discovering interesting classification rules with genetic programming. Appl Soft Comput. 1(4):257–269. Duran C, Appleby N, Edwards D, Batley J. 2009. Molecular genetic markers: discovery, applications, data storage and visualisation. Curr Bioinf. 4:16-27. Espejo PG, Ventura S, Herrera F. 2010. A survey on the application of genetic programming to classification. IEEE Trans Syst, Man, Cybern. 40(2):121–144. He H, Garcia EA. 2009. Learning from imbalanced data. IEEE Trans Knowl Data Eng. 21(9):1263–1284. Istiadi MA, Kusuma WA, Tasma IM. 2014. Application of decision tree classifier for single nucleotide polymorphism discovery from next-generation sequencing data. Di dalam: Proceedings of International Conference on Advanced Computer Science and Information Systems, ICACSIS 2014; 2014 Okt 18-19; Jakarta, Indonesia. Jakarta (ID): IEEE. hlm 85-89. Kong W. 2007. Predicting single nucleotide polymorphisms (SNP) from DNA sequence by support vector machine. Front Biosci. 12(1):1610-14. Kumar S, Banks TW, Cloutier S. 2012. SNP discovery through next-generation sequencing and its applications. Int J Plant Genomics [Internet]. [diunduh 2013 Feb 28]; 2012:831460. Tersedia pada: http://www.hindawi.com/journals/ijpg/ 2012/831460/. Kuo CS, Hong TP, Chen CL. 2007. Applying genetic programming technique in classification trees. Soft Comput. 11(12):1165–1172.
40 Lam HM, Xun X, Xin L, Wenbin C, Guohua Y, Fuk-Ling W, Man-Wah L, Weiming H, Nan Q, Bo W, et al. 2010. Resequencing of 31 wild and cultivated soybean genomes identifies patterns of genetic diversity and selection. Nat Genet. 42(12):1053–9. Li YH, Zhao SC, Ma JX, Li D, Yan L, Li J, Qi XT, Guo XS, Zhang L, He WM, et al. 2013. Molecular footprints of domestication and improvement in soybean revealed by whole genome re-sequencing. BMC Genomics [Internet]. [diunduh 2013 Sep 21]; 14(1):579. Tersedia pada: http://www.biomedcentral.com/14712164/14/579. Mammadov J, Aggarwal R, Buyyarapu R, Kumpatla S. 2012. SNP markers and their impact on plant breeding. Int J Plant Genomics [Internet]. [diunduh 2013 Mar 11]; 2012:728398. Tersedia pada: http:// www.hindawi.com/journals/ijpg/ 2012/728398/. Matukumalli LK, Grefenstette JJ, Hyten DL, Choi IY, Cregan PB, Van Tassell CP. 2006. Application of machine learning in SNP discovery. BMC Bioinf [Internet]. [diunduh 2013 Feb 28]; 7:4. Tersedia pada: http://www.biomedcentral.com/1471-2105/7/4. Metzker ML. 2010. Sequencing technologies - the next generation. Nat Rev Genet. 11(1):31–46. Mishra SK, Verma VD. 2010. Soybean genetic resources. Di dalam: Singh G, editor. The Soybean: Botany, Production, and Uses. Oxfordshire (UK): CAB International. hlm 74-91. Moose SP, Mumm RH. 2008. Molecular plant breeding as the foundation for 21st century crop improvement. Plant Physiol. 147(3):969–77. Nielsen R, Paul JS, Albrechtsen A, Song YS. 2011. Genotype and SNP calling from next-generation sequencing data. Nat Rev Genet. 12(6):443–51. Oeveren JV, Janssen A. 2009. Mining SNPs from DNA sequence data; computational approaches to SNP discovery and analysis. Di dalam: Komar AA, editor. Single Nucleotide Polymorphisms. New Jersey (US): Humana Pr. hlm 73-91. O‟Fallon BD, Wooderchak-Donahue W, Crockett DK. 2013. A support vector machine for identification of single-nucleotide polymorphisms from nextgeneration sequencing data. Bioinformatics. 29(11):1361–6. Satyawan D, Rijzaani H, Tasma IM. 2014. Characterization of genomic variation in Indonesian soybean (Glycine max) varieties using next-generation sequencing. Plant Genetic Resources. 12:S109–S113. Schmieder R, Edwards R. 2011. Quality control and preprocessing of metagenomic datasets. Bioinformatics. 27(6):863–4. Schmutz J, Cannon SB, Schlueter J, Ma J, Mitros T, Nelson W, Hyten DL, Song Q, Thelen JJ, Cheng J, et al. 2010. Genome sequence of the palaeopolyploid soybean. Nature. 463(7278):178–83. Shendure J, Ji H. 2008. Next-generation DNA sequencing. Nature Biotech. 26(10):1135–45. Tan KC, Tay A, Lee TH, Heng CM. 2002. Mining multiple comprehensible classification rules using genetic programming. Di dalam: Proceedings of the 2002 Congress on Evolutionary Computation, E ’02; 2002 Mei 12-17; Honolulu, Hawaii. Honolulu (HI): IEEE. hlm 1302–1307.
41 Ventura S, Romero C, Zafra A, Delgado JA, Hervás C. 2007. JCLEC: a Java framework for evolutionary computation. Soft Comput. 12(4):381–392. Vidal RO, Do Nascimento LC, Mondego JMC, Pereira GAG, Carazzolle MF. 2012. Identification of SNPs in RNA-seq data of two cultivars of Glycine max (soybean) differing in drought resistance. Genet Mol Biol. 35:331-334. Zhu YL et al. 2003. Single-nucleotide polymorphism in soybean. Genetics. 163:1123-1134.
42
LAMPIRAN Lampiran 1 Contoh cara perhitungan dari masing-masing fitur
Tipe Variasi Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC G berubah menjadi A, GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC maka tipe variasi = transition GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC A
G Jenis perubahan basa: Transition Transversion
T
ts.tv = transition
C
Maksimum Kualitas Alel Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads 70 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 76 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC 72 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 75 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 71 74 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC
Alel mayor Alel minor
: G (4 reads) : A (2 reads)
Max mayor Max minor
= max(70, 72, 71, 74) = 74 = max(76, 75) = 76
max.qual.major = 74 max.qual.minor = 76
43 Lanjutan
Rata-rata Kualitas Alel Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads 70 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 76 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC 72 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 75 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC 71 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC 74 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC
mean.qual.major = 71.75 mean.qual.minor = 75.5
Alel mayor Alel minor
: G (4 reads) : A (2 reads)
Rataan mayor Rataan minor
= average(70, 72, 71, 74) = 71.75 = average(76, 75) = 75.5
Kualitas Basa Pengapit Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Seluruh basa yang mengapit posisi adanya variasi dihitung rata-rata kualitasnya
Rata-rata = average(73, 75, …, 71) = 73.5
mean.nearby.qual = 73.5
44 Lanjutan
Keseimbangan Alel Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC
Variant = 2 (jumlah reads yang memiliki perbedaan basa) Total =6
allele.balance = 0.333
Keseimbangan alel = 2/6 = 0.333
Jarak Relatif Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCCTTCGGC Posisi = 14/25 = 0.56 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Jarak = 1-0.56 = 0.44 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGCGG C Posisi = 11/25 = 0.44 Jarak = 0.44 Rata-rata = (0.44 + 0.44) / 2 = 0.44
rel.dist = 0.44
45 Lanjutan
Kedalaman Penjajaran Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCCTTCGGC 6 reads GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGCGG C Terdapat 6 reads yang dijajarkan pada posisi ditemukannya perbedaan
total.depth = 6
Kualitas Penjajaran Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCCTTCGGC Q= 30 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGCGG C Q = 30
mean.mapping.qual = 30
Rata-rata = 30 Kualitas diberikan oleh program penjajaran (SOAP2)
46 Lanjutan
Peluang Error Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Variant : 2 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTCTTCGGC Total :6 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Peluang binomial:
(
)
( (
) )
error.prob = 0.117
Strand Bias Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTG GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGG GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTC ForwardALT = 2 GACTTCCTACTCACAGTCGGTCACATTGGACTACTCCTTGGGTGC ReverseALT = 0 GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTC GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTC Forward =2
→ → ← → ← →
REF
ReverseREF = 2 Nilai chi-square:
strand.bias = 5
47 Lanjutan
Perulangan Dinukleotida Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGCGGC Jumlah perulangan dinukleotida: Kiri =0 Kanan = 2 Jumlah
dinuc.repeat = 2
= 0 +2 = 2
Panjang Homopolimer Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGCGGC Panjang homopolimer: Kiri =2 Kanan = 0 Jumlah
= 2 +0 = 2
homopolymer.run = 2
48 Lanjutan
Keragaman Nukleotida Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCTTCGGC Rasio per basa: GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCCTTCGGC A = 2/20 = 0.1 GACTTCCTACTCACAGTCGGTCACATTGGACTCTCCTTGGGTCCTTCGGC G = 5/20 = 0.25 GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGC T = 7/20 = 0.35 GACTTCCTACTCACAGTCGGTCACATTGGGCTCTCCTTGGGTCTTCGGCGGC C = 6/20 = 0.3
Diversity = (0.1-0.3)^2 + (0.25-0.2)^2 + (0.35-0.3)^2 + (0.3-0.2)^2
nuc.diversity = 0.055
Jarak ke Kandidat Terdekat Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCCGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTGCTTGGGTCTTCGGC GACTTCCTACTCACAGT GTCACATTGGGCTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGT GTCACATTGGACTACTGCTTGGGTCCTTCGGC GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC Nearest = min(11, 6) = 6
11
6
nearest.flank = 6
49 Lanjutan
Banyaknya Mismatch pada Reads Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCCGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTGCTTGGGTCTTCGGC GACTTCCTACTCACAGT GTCACATTGGGCTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGT GTCACATTGGACTACTGCTTGGGTCCTTCGGC Jumlah mismatch = 2 + 2 = 4 GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC
mismatch.alt = 4
Total Area Mismatch Sekuens rujukan
GACTTCCTACTCACAGTCGGTCACATTGGGCTACTCCTTGGGTCTTCGGC Reads GACTTCCTACTCACAGTCCGTCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGTCGGTCACATTGGACTACTGCTTGGGTCTTCGGC GACTTCCTACTCACAGT GTCACATTGGGCTACTCCTTGGGTCCTTCGGC GACTTCCTACTCACAGT GTCACATTGGACTACTGCTTGGGTCCTTCGGC GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC GACTTCCTACTCACAGT TCACATTGGGCTACTCCTTGGGTCTTCGGC Kedalaman = 6 Total mismatch = 1 + 2 + 2 = 5 Area mismatch = 5/6 = 0.833
area.mismatch = 0.833
50
RIWAYAT HIDUP Penulis, Muhammad Abrar Istiadi, lahir di Klaten, Jawa Tengah pada tanggal 29 Agustus 1990. Penulis merupakan putra pertama dari dua bersaudara pasangan Oni Setiyadi dan Istinah Laksiastuti. Penulis menempuh pendidikan S1 di Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor (IPB) pada tahun 2008-2012. Pada akhir tahun 2012, penulis meneruskan pendidikan ke Program Magister Ilmu Komputer di Institut Pertanian Bogor atas bantuan Beasiswa Unggulan DIKTI 2012. Saat karya ilmiah ini disusun, penulis bekerja sebagai asisten di Departemen Ilmu Komputer dan mengajar praktikum beberapa mata kuliah seperti Algoritme dan Pemrograman, Bahasa Pemrograman, Basis Data, dan Grafika Komputer. Penulis juga aktif sebagai anggota Lab Komputasi Terapan Departemen Ilmu Komputer dengan peminatan bioinformatika. Penulis juga diangkat menjadi Komisi Teknologi Informasi di Departemen Ilmu Komputer sejak Desember 2014. Selama mengikuti program magister, penulis telah menyajikan karya ilmiah berjudul Application of Decision Tree Classifier for Single Nucleotide Polymorphism Discovery from Next-Generation Sequencing Data dalam konferensi internasional ICACSIS 2014 yang bertempat di Jakarta pada bulan Oktober 2014. Karya ilmiah tersebut merupakan bagian dari tesis penulis.