BAB III ANALISIS DAN PERANCANGAN Pada bab ini dijabarkan hasil analisis dan perancangan yang dilaksanakan selama pengerjaaan Tesis. Analisis yang dilakukan diawali dengan analisis input dan output yang diharapkan dari sistem. Dari hasil yang diperoleh, ditentukan proses yang harus dilakukan untuk memperoleh output dari input. Analisis kemudian dilanjutkan dengan analisis arsitektur umum sistem yang diperoleh berdasarkan proses. Kemudian, dilakukan analisis ranah permasalahan untuk menentukan kelas masalah dan pemecahan masalah yang digunakan untuk sistem berbasis pengetahuan yang dibangun. Setelah itu, dilakukan analisis untuk tiap sub proses yang mencakup analisis penyimpanan model ke basis data, pembentukan basis pengetahuan, teknik dan algoritma inferensi, serta analisis kebutuhan perangkat lunak yang dibangun. Setelah tahapan analisis selesai, dijabarkan hasil perancangan yang meliputi perancangan prototipe perangkat lunak dan pemodelan pengetahuan.
3.1 Analisis Proses Input dari sistem berbasis pengetahuan yang dibangun adalah sebuah model. Model yang digunakan merupakan hasil dari komponen learning. Berdasarkan model yang dimiliki ini, ingin dihasilkan keluaran berupa hasil inferensi dengan Bayesian network sesuai dengan evidences dari pengguna sistem. Evidences masukan pengguna berupa kondisi sel pada saat tertentu. Secara spesifik, kondisi sel dinyatakan sebagai level ekspresi sejumlah gen yang diketahui. Hasil inferensi Bayesian network ini berupa prediksi level ekspresi gen dan probabilitasnya yang dipengaruhi oleh kondisi sel masukan pengguna. Komponen learning yang menghasilkan model merupakan komponen yang terpisah dari sistem. Pada komponen ini, setelah dilakukan proses learning, model yang dihasilkan tidak disimpan. Untuk efisiensi proses, perlu dilakukan proses penyimpanan model. Solusi yang dipilih untuk permasalahan ini adalah dengan menyimpan model ke dalam suatu basis data. Solusi ini dipilih karena penyimpanan ke basis data memudahkan akses dan modifikasi yang mungkin perlu dilakukan. Dengan menggunakan Database Management System (DBMS), akses terhadap data dari aplikasi dapat dilakukan dengan menggunakan prosedur yang sudah tersedia. Dengan menggunakan prosedur yang sudah merupakan standar, diharapkan sistem yang dibangun memiliki kelemahan yang lebih
III-1
III-2
sedikit. Selain itu, dalam pengembangannya, proses penyimpanan hasil learning sebaiknya
dapat
dilakukan
langsung
melalui
komponen
pembelajaran.
Untuk
mempermudah modifikasi yang perlu dilakukan terhadap komponen learning, hasil learning sebaiknya disimpan dengan suatu model penyimpanan yang sudah merupakan standar. Namun, dalam kaitannya dengan sistem berbasis pengetahuan yang dibangun, terdapat hal yang harus diperhatikan dengan penyimpanan model ke basis data. Model yang disimpan ke basis data berfungsi sebagai pengetahuan yang digunakan untuk melakukan inferensi. Model ini diakses setiap kali inferensi dilakukan. Dengan demikian, setiap proses inferensi melibatkan akses ke basis data. Akses langsung berulang kali ke basis data merupakan task yang membutuhkan resource yang cukup besar, apalagi bila melibatkan data yang besar dan query yang sulit. Untuk efisiensi proses, perlu dilakukan penyimpanan antara model ke dalam suatu representasi yang dapat diakses dengan resource yang lebih kecil. Solusi yang dipilih untuk permasalahan ini adalah: 1. Pada saat start-up sistem, dilakukan akses model ke basis data. Model ini kemudian direkonstruksi menjadi Bayesian network dan disimpan ke dalam sebuah file. 2. Setiap proses inferensi dilakukan dengan mengakses file berisi Bayesian network tersebut, tidak melalui akses langsung ke basis data. Dengan demikian, keseluruhan proses dalam sistem dapat dikelompokkan menjadi dua kelas yaitu: 1. Proses Offline Tasks yang dilakukan dalam proses ini adalah penyimpanan model ke basis data dan proses representasi pengetahuan. Proses representasi pengetahuan terdiri dari rekonstruksi Bayesian network dari model dan penyimpanan Bayesian network tersebut ke dalam file. Akses ke basis data hanya perlu dilakukan satu kali pada saat ini. 2. Proses Online Task yang dilakukan pada proses ini adalah task inferensi. Pengguna memberikan input berupa evidences pada sistem yang digunakan sistem sebagai fakta dari inferensi yang dilakukan. Proses inferensi inilah yang terjadi berulang kali sesuai
III-3
penggunaan sistem. Dalam proses ini, tidak perlu dilakukan akses ke basis data melainkan cukup dengan mengakses Bayesian network yang sudah disimpan pada file.
Gambar III-1 Deskripsi Proses
Secara umum, proses yang terjadi dari sistem menerima model hingga dapat menghitung hasil inferensi dari evidences masukan pengguna dapat digambarkan pada Gambar III-1. Pada gambar tersebut, terdapat tiga proses utama yaitu: 1. Penyimpanan model ke basis data Pada proses ini, model yang tersedia disimpan kedalam basis data agar model dapat diakses dan dimodifikasi dengan lebih mudah seperti telah dijelaskan sebelumnya.
III-4
2. Representasi pengetahuan Model yang ada pada database kemudian direpresentasikan ke dalam representasi yang sesuai untuk inferensi dengan Bayesian network. Model direpresentasikan sebagai graf Bayesian network lengkap dengan conditional probability table-nya. Proses representasi pengetahuan terbagi menjadi dua tahap yaitu rekonstruksi Bayesian network dari model dan penyimpanan pengetahuan berupa Bayesian network tersebut kedalam file. 3. Inferensi Evidences masukan pengguna digunakan untuk melakukan inferensi. Inferensi yang dilakukan merupakan inferensi Bayesian network pada Bayesian network hasil rekonstruksi model yang telah disimpan. Analisis mendetail tentang setiap proses yang ada dijelaskan kemudian.
3.2 Arsitektur Sistem Berdasarkan analisis proses yang sudah dilakukan, dilakukan analisis untuk memperoleh arsitektur umum dari sistem berbasis pengetahuan yang dibangun.
Gambar III-2 Arsitektur Sistem
Seperti terlihat pada Gambar III-2, terdapat lima komponen utama dalam sistem yaitu: 1. Model Komponen ini merupakan model hasi pembelajaran yang telah disimpan pada suatu basis data untuk memudahkan akses dan modifikasi. Komponen ini merupakan sumber data bagi Bayesian network converter.
III-5
2. Bayesian Network Converter Bayesian network converter berfungsi untuk merepresentasikan pengetahuan dalam model ke dalam representasi Bayesian network sesuai dengan kebutuhan inferensi. Bayesian network yang diperoleh kemudian disimpan sebagai basis pengetahuan. 3. Basis Pengetahuan Basis pengetahuan menyimpan pengetahuan berupa basis pengetahuan jaringan regulatori genetik hasil rekonstruksi dari model. 4. Inference Engine Inference engine menerima input berupa evidences dan kemudian melakukan inferensi Bayesian network berdasarkan evidences tersebut. 5. User Interface User interface merupakan komponen yang berinteraksi langsung dengan pengguna. Komponen ini menerima evidences dari pengguna dan meneruskannya pada inference engine. Komponen ini pulalah yang bertugas menampilkan hasil inferensi berupa prediksi level ekspresi setiap gen yang terlibat dan nilai probabilitasnya pada pengguna.
3.3 Kelas Masalah dan Pemecahan Masalah Pada sistem berbasis pengetahuan yang dibangun diberikan input berupa kondisi sel pada saat tertentu. Sistem kemudian memberikan output berupa nilai probabilitas level ekspresi gen yang berubah sebagai akibat kondisi sel input. Dengan demikian, dapat dikatakan bahwa sistem diberikan input berupa situasi dan menghasilkan keluaran berupa akibat dari situasi tersebut. Menurut Hayes-Roth, masalah yang diselesaikan dengan sistem berbasis pengetahuan tersebut termasuk kelas masalah prediction. Sistem dapat dikatakan pula memberikan interpretasi terhadap kondisi sel pada saat tertentu. Interpretasi dilakukan dengan melakukan simulasi berdasarkan input berupa kondisi sel dan deskripsi sistem berupa relasi regulasi yang ada jaringan regulatori genetik untuk menghasilkan output berupa nilai probabilitas level ekspresi gen. Dengan demikian, menurut Clancey, masalah yang diselesaikan dengan sistem berbasis pengetahuan ini tergolong kedalam kelas masalah interpret, khususnya predict.
III-6
Untuk menghasilkan solusi, sistem menentukan bagaimana nilai probabilitas level ekspresi gen berdasarkan input berupa evidences dari pengguna. Evidences berupa himpunan satu atau lebih level ekspresi gen yang diketahui. Dengan demikian, dapat dikatakan bahwa pemecahan masalah yang digunakan pada sistem berbasis pengetahuan ini adalah classification. Dalam classification, solusi dipilih dari himpunan solusi dari domain berupa himpunan observasi dan himpunan solusi. Masalah yang diselesaikan merupakan subset observasi yang dapat bersifat tidak lengkap. Hasil yang diberikan berupa satu atau lebih solusi. Dalam permasalahan inferensi jaringan regulatori genetik, himpunan observasi merupakan himpunan semua level ekspresi gen yang mungkin. Sedangkan, himpunan solusi adalah nilai probabilitas kemungkinan level ekspresi gen. Himpunan observasi dipetakan terhadap himpunan solusi berdasarkan teorema Bayes.
3.4 Penyimpanan Model ke Basis Data Pada Tesis ini, model yang digunakan berupa basis pengetahuan mengenai jaringan regulatori genetik organisme ragi. Model yang tersedia merupakan hasil dari proses learning. Namun pengetahuan tersebut belum tersimpan dalam struktur yang mudah diakses. Relasi regulasi dan nilai probabilitas masih belum tersimpan dan harus dibangkitkan dari proses learning. Dengan demikian, setiap kali digunakan, harus dilakukan proses learning terlebih dahulu untuk membentuk model terlebih dahulu. Untuk mengatasi hal tersebut, model yang ada disimpan pada suatu basis data. Berdasarkan analisis pada sub bab 3.5.2.2 selanjutnya, perlu dilakukan modifikasi pada komponen learning agar model yang dihasilkan tidak hanya memiliki informasi mengenai gen dan relasi regulasi, melainkan juga telah memiliki informasi join distribution sesuai relasi regulasi. Oleh karena itu, skema basis data dirancang untuk mengakomodasi penambahan informasi ini. Entity Relationship Diagram (ERD) untuk model jaringan regulatori genetik dapat dilihat pada Gambar III-3. Hanya terdapat sebuah entitas pada ERD yaitu entitas Gene. Entitas ini merepresentasikan gen yang merupakan random variable pada Bayesian network yang dibangun. Entitas ini memiliki tiga atribut yaitu: 1. id : primary key, merepresentasikan identitas dari gen. 2. name : nama gen sesuai dengan ilmu biologi molekuler 3. cpt : join probability distribution yang dinyatakan sebagai Conditional Probability Table (CPT) dari setiap gen sesuai relasi regulasinya.
III-7
Terdapat relasi siklik has_parents pada entitas Gene. Relasi regulasi dapat dinyatakan sebagai relasi parent-child yang ada antar variabelnya. Relasi ini dinyatakan sebagai relasi siklik has_parents pada entitas Gene dengan kardinalitas n..n. Pada dasarnya, jumlah entri pada CPT masing-masing gen berbeda sesuai dengan relasi regulasi dan state yang dimiliki. Sesuai analisis pada 3.5.2.2, level ekspresi setiap gen dikuantiasai menjadi tiga states yaitu Low (L), Medium (M), dan High (H). Dengan demikian, untuk gen dengan jumlah parents n , terdapat CPT dengan jumlah entri 3 n +1 . Misal, bila diketahui simpul dengan jumlah parents dua, maka CPT untuk simpul tersebut memiliki 3 2 +1 = 3 3 = 27 entri.
Gambar III-3 Entity Relationship Diagram
Karena jumlah entri CPT yang bervariasi sesuai dengan jumlah parents simpul, masingmasing CPT yang ada harus disimpan sebagai tabel terpisah pada basis data bila diinginkan CPT tetap disimpan sebagai bentuk tabel utuh. Dengan kata lain, jumlah tabel yang ada pada basis data semakin besar sesuai dengan jumlah simpul. Hal ini tidak efisien karena diantara tabel-tabel tersebut terdapat tabel yang hanya menyimpan sedikit entri. Misalnya, untuk simpul yang tidak memiliki parent, CPT hanya terdiri dari tiga entri sesuai dengan jumlah state simpul. Selain itu, perubahan yang terjadi sebagai hasil dari proses pembangkitan model dapat mengakibatkan tidak hanya berubahnya entri basis data, tapi juga pada skema basis data. Perubahan skema basis data dapat terjadi bila terjadi perubahan relasi regulasi. Untuk mengatasi permasalahan tersebut, maka CPT direpresentasikan dalam format serupa comma separated value (CSV) yang disimpan sesuai dengan urutan entri pada CPT. Pengurutan entri pada CPT dimulai dengan variabel child untuk setiap himpunan
III-8
states, baru kemudian variabel parents. Misalkan, simpul A memiliki dua parents yaitu simpul B dan C. CPT untuk simpul tersebut memiliki 3 2 +1 = 3 3 = 27 entri seperti terlihat pada Tabel III-1. Tabel III-1 Conditional Probability Table A L M H L M H L M H L M H L M H L M H L M H L M H L M H
B L L L M M M H H H L L L M M M H H H L L L M M M H H H
C L M H L M H L M H L M H L M H L M H L M H L M H L M H
Probability 0.02 0.3 0.5 0.2 0.2 0.01 0.02 0.59 0.2 0.6 0.01 0.03 0.06 0.025 0.1 0.02 0.03 0.04 0.02 0.32 0.21 0.2 0.12 0.1 0.03 0.11 0.12
CPT disimpan dalam format serupa CSV sebagai berikut: 0.02,0.3,0.5;0.2,0.2,0.01;0.02,0.59,0.2;0.6,0.01,0.03;0.06,0.025,0.1;0.02,0.03,0.04;0.02, 0.32,0.21;0.2,0.12,0.1;0.03,0.11,0.12 Pada format tersebut, setiap entri dipisahkan dengan karakter koma (‘,’). Selain itu, dilakukan juga pemisahan antar himpunan states variabel child dengan karakter titik koma (‘;’). Pada contoh, dilakukan pemisahan antar himpunan states variabel A, yaitu setiap tiga entri. Untuk n jumlah parents, nilai state parent pertama berulang sebanyak
3 n −1 , nilai state parent kedua berulang setiap 3 n − 2 , begitu seterusnya. Pada contoh, setiap 3 2 −1 = 3 entri memiliki nilai state parent pertama yaitu variabel B yang sama. Sedangkan, setiap 3 2 − 2 = 1 entri memiliki nilai state parent kedua yaitu variabel C yang sama.
III-9
Gambar III-4 ERD dengan Penambahan Indeks Parent
Gambar III-5 Skema Basis Data
Dengan format serupa CSV tersebut, CPT dapat disimpan sebagai atribut untuk entitas Gene. Dengan menambahkan informasi indeks urutan parent pada relasi has_parents, CPT dapat direkonstruksi. Penambahan informasi tersebut menyebabkan perubahan pada ERD seperti dapat dilihat pada Gambar III-4. Berdasarkan ERD pada Gambar III-4, dapat diturunkan skema basis data pada Gambar III-5. Pada skema tersebut, terdapat dua tabel yaitu tabel Gene yang merepresentasikan entitas Gene dan tabel Gene_has_parents yang merepresentasikan relasi has_parents.
III-10
Relasi ini direpresentasikan sebagai tabel tersendiri karena merupakan relasi banyak ke banyak. Satu Gen dapat berperan sebagai child yang memiliki sejumlah nol sampai n parents. Selain itu, setiap gen juga dapat memiliki nol sampai n childs pada perannya sebagai parent. Pada tabel ini, primary key berupa kombinasi dari identitas gen yang berperan sebagai child dan identitas gen yang berperan sebagai parent. Terdapat sebuah atribut lain yaitu idx yang menyatakan indeks urutan parent. Tabel Gene memiliki atribut sesuai pada ERD. CPT dalam format serupa CSV direpresentasikan sebagai field pada tabel Gene.
3.5 Representasi Pengetahuan Pada sub bab ini dilakukan analisis yang diperlukan untuk merepresentasikan pengetahuan pada model yang telah disimpan pada basis data ke dalam representasi yang sesuai untuk inferensi dengan Bayesian network. Analisis diawali dengan analisis rekonstruksi Bayesian network dari model. Kemudian dilakukan pula analisis untuk menyimpan pengetahuan berupa Bayesian network untuk efisiensi proses pada sistem. Untuk melakukan rekonstruksi Bayesian network dari model, dilakukan analisis untuk mengetahui bagaimana cara merepresentasikan jaringan regulatori genetik dalam Bayesian network. Analisis kemudian dilakukan untuk mengetahui apakah model dapat digunakan untuk merekonstruksi Bayesian network dan bagaimana cara melakukan rekonstruksi tersebut.
3.5.1 Representasi dalam Bayesian Network Untuk merepresentasikan jaringan regulatori genetik dengan menggunakan Bayesian network perlu dilihat karakteristik dari keduanya untuk memperoleh kesamaan yang ada. Pada Bayesian network, simpul pada graf merupakan random variable yang merupakan elemen dasar dari probabilistic reasoning. Tiap random variable memiliki state dan nilai probabilitas sendiri yang dapat berubah sesuai dengan hasil observasi. Dalam jaringan regulatori genetik, yang menjadi elemen dasar adalah gen. Setiap gen memiliki beberapa level ekspresi yang dapat berubah sesuai dengan kondisi sel, sama seperti karakteristik random variable. Dengan demikian, dalam pemodelan jaringan regulatori genetik dengan Bayesian network, yang menjadi random variable adalah gen. Pada Bayesian network, setiap random variable memiliki relasi independensi dan conditional independence. Relasi independensi dinyatakan dengan tidak adanya sisi berarah dari satu random variable ke random variable yang lain. Dengan adanya relasi
III-11
ini berarti perubahan pada suatu random variable tidak mempengaruhi random variable lainnya. Sisi berarah pada Bayesian network menggambarkan adanya pengaruh langsung dari suatu random variable ke random variable yang dituju. Dalam ranah permasalahan jaringan regulatori genetik, tidak adanya relasi regulasi antara dua buah gen merupakan relasi independensi. Dengan tidak adanya relasi regulasi antara dua buah gen, perubahan level ekspresi suatu gen tidak mempengaruhi level ekspresi gen lainnya. Relasi regulasi pada jaringan regulatori genetik digambarkan dengan adanya sisi berarah dari gen asal ke gen tujuan. Hal ini sesuai dengan sisi berarah pada Bayesian network. Dengan demikian, pada pemodelan jaringan regulatori genetik dengan Bayesian network, sisi berarah pada Bayesian network ekivalen dengan relasi regulasi pada jaringan. Dalam Bayesian network, terdapat uncertainty pada ranah permasalahan. Pada ranah permasalahan jaringan regulatori genetik, uncertainty ditimbulkan oleh faktor-faktor minor selain gen yang mempengaruhi relasi regulasi. Sentence berupa level ekspresi suatu gen. Degree of belief untuk sentence dikonstruksi berdasarkan hasil observasi yang berupa level ekspresi satu atau lebih gen yang terlibat. Prior probability merupakan nilai probabilitas setiap level ekspresi yang mungkin untuk setiap gen. Bila gen A memiliki kemungkinan level ekspresi gen Low, Medium, dan High, maka probability distributionnya terdiri dari nilai probabilitas gen A memiliki level ekspresi Low, nilai probabilitas gen A memiliki level ekspresi Medium, dan nilai probabilitas gen A memiliki level ekspresi High. Join probability distribution untuk gen A dan gen B terdiri dari nilai-nilai probabilitas untuk semua kemungkinan level ekspresi gen A dan gen B. Hal yang harus diperhatikan dalam memodelkan jaringan regulatori genetik dengan Bayesian network adalah adanya kemungkinan jaringan memiliki relasi siklik. Relasi siklik dapat dihilangkan dengan melakukan unrolling. Proses unrolling dilakukan dengan memindahkan sisi berarah yang menyebabkan relasi siklik hingga mengarah ke variabel tujuan di time slice selanjutnya. Pemindahan ini didasarkan pada fakta bahwa terdapat delay antara proses ekspresi gen dan pengaruhnya terhadap ekspresi gen lain. Dengan melakukan unrolling, setiap time slice pada gambar tersebut merupakan satu graf dynamic Bayesian network. Sebagai contoh, untuk relasi siklik seperti terdapat pada Gambar III-6, dapat dilakukan unrolling untuk membentuk graf Bayesian network seperti terdapat pada Gambar III-7. Selain itu, hal lain yang perlu diperhatikan adalah level ekspresi gen yang bersifat kontinu. Inferensi Bayesian network yang melibatkan variabel kontinu memiliki kompleksitas yang lebih tinggi bila dibandingkan dengan inferensi yang melibatkan
III-12
variabel diskrit. Untuk memudahkan representasi jaringan regulatori genetik dengan Bayesian network, level ekspkresi gen yang bersifat kontinu dikuantisasi menjadi beberapa state.
Gambar III-6 Contoh Relasi Siklik
Gambar III-7 Hasil Unrolling
3.5.2 Rekonstruksi Bayesian Network Pada sub bab ini dijabarkan hasil analisis rekonstruksi model menjadi Bayesian network. Pertama, perlu diketahui apakah model yang tersedia sudah memenuhi kebutuhan informasi yang dibutuhkan untuk melakukan inferensi dengan Bayesian network. Untuk mengetahui hal tersebut, dilakukan analisis untuk mengetahui karakteristik model yang sudah tersedia. Kemudian, dilakukan analisis kebutuhan inferensi dengan Bayesian network. Setelah itu, dilakukan analisis bagaimana merekonstruksi Bayesian network dari model yang ada.
III-13
3.5.2.1 Analisis Kelayakan Rekonstruksi Untuk membangun Bayesian network, informasi yang dibutuhkan yaitu: 1. Random variable. 2. Relasi conditional independence dan independensi yang ada antar variabel. 3. Full join probability distribution random variables berdasarkan relasi yang ada. Model yang sudah tersedia memiliki informasi sebagai berikut: 1. Gen yang terlibat dalam jaringan regulatori genetik. 2. Relasi regulasi yang ada antar gen Berdasarkan analisis sebelumnya, gen memiliki kemiripan karakteristik dengan random variable pada Bayesian network, sedangkan relasi regulasi memiliki kemiripan karakteristik dengan sisi berarah pada Bayesian network. Namun, belum tersedia distribusi probabilitas yang ekivalen dengan join distribution pada Bayesian network. Kedua informasi yang tersedia pada model sudah dapat digunakan untuk merekonstruksi graf Bayesian network. Namun, setelah memperoleh graf, conditional probability table dari setiap variabel pada Bayesian network harus didefinisikan. Untuk memperoleh nilainilai ini, dapat dilakukan proses learning atau akuisisi pengetahuan dari pakar. Sub bab selanjutnya memuat rekonstruksi model menjadi Bayesian network. 3.5.2.2 Rekonstruksi Model Rekonstruksi model menjadi Bayesian network dilakukan berdasarkan hasil analisis berupa ekivalensi antara model dengan Bayesian network. Rekonstruksi Bayesian network dari model yang sudah tersedia dilakukan dengan cara sebagai berikut: 1. Gen pada model dengan random variable pada Bayesian network. 2. Relasi regulasi pada model dengan sisi berarah pada Bayesian network. 3. Membentuk dummy join distribution berdasarkan graf yang diperoleh dengan mempertimbangkan aksioma probabilitas. Pada sub bab 3.4 telah dijelaskan bahwa hal yang harus diperhatikan dalam merepresentasikan jaringan regulatori genetik dalam Bayesian network adalah relasi siklik dan level ekspresi gen yang kontinu. Permasalahan relasi siklik diatasi dengan melakukan unrolling hingga memperoleh snapshot yang mencukupi. Graf pada setiap time slice-nya merupakan graf dynamic Bayesian network. Pada model yang digunakan,
III-14
telah terdapat data berupa gen dan relasi regulasi namun masih mengandung relasi siklik. Oleh karena itu, diperlukan proses penghilangan relasi siklik. Untuk melakukan proses ini, informasi gen dan relasi regulasi pada model direpresentasikan sebagai satu time slice dynamic Bayesian network. Kemudian, dilakukan unrolling menjadi dua time slice. Setiap relasi siklik yang ada direpresentasikan sebagai relasi antar time slice. Dynamic Bayesian network yang telah di-unrolled menjadi dua time slice inilah yang merupakan graf Bayesian network yang digunakan dalam proses inferensi. Dari graf Bayesian network yang diperoleh, langkah selanjutnya adalah menentukan dummy join distribution. Penggunaan dummy join distribution ini dipilih sebagai solusi karena: 1. Belum ditemukan pakar di bidang jaringan regulatori genetik yang dapat dijadikan sumber informasi untuk menentukan join distribution melalui akuisisi pengetahuan. 2. Telah terdapat komponen learning terpisah yang membentuk model jaringan regulatori genetik. Secara modular, penentuan join distribution akan lebih mudah ditambahkan sebagai fitur dari komponen ini sehingga pada pengembangan selanjutnya, model yang dihasilkan sudah memiliki nilai probabilistik yang lengkap. Dalam pembentukan dummy join distribution, untuk mempermudah setiap level ekspresi gen dianggap sudah dikuantisasi menjadi tiga states yaitu Low, Medium, dan High. Dengan demikian, untuk setiap kombinasi state parent, terdapat tiga kemungkinan nilai variabel gen. Sesuai dengan aksioma probabilitas, nilai probabilitas ketiga kemungkinan ini apabila dijumlahkan bernilai 1. Aturan ini yang digunakan untuk menentukan nilai probabilitas dummy. Untuk setiap kemungkinan nilai parents, dibangkitkan array 3 elemen bilangan acak yang apabila setiap elemennya dijumlahkan akan bernilai 1.
3.5.3 Penyimpanan Pengetahuan Bayesian network yang direkonstruksi dari model berperan sebagai basis pengetahuan pada sistem berbasis pengetahuan yang dibangun. Fungsi utama dari sistem adalah melakukan inferensi Bayesian network tersebut berdasarkan evidences masukan pengguna. Apabila rekonstruksi Bayesian network harus dilakukan setiap kali dilakukan inferensi, proses yang dilakukan dari pengguna memasukkan evidences hingga memperoleh hasil inferensi membutuhkan waktu yang lebih lama. Oleh karena itu, untuk mengefisienkan pemrosesan, pada saat pertama kali inferensi dilakukan, Bayesian
III-15
network yang telah direkonstruksi disimpan pada sebuah file. Inferensi selanjutnya hanya perlu mengakses Bayesian network dari file ini dan tidak perlu melakukan rekonstruksi ulang Bayesian network dari model. Agar Bayesian network yang tersimpan pada file dapat dipergunakan untuk melakukan inferensi dengan mudah, Bayesian network harus disimpan dalam format yang terstruktur. Dengan format yang terstruktur, informasi yang tersimpan pada file lebih mudah diparsing untuk membentuk kembali Bayesian network. Informasi yang harus direpresentasikan dalam file untuk membentuk kembali Bayesian network yaitu: 1. Random variable dan state yang terdefinisi. 2. Relasi antar random variable. 3. CPT dari masing-masing random variable berdasarkan keterhubungannya. Struktur yang digunakan untuk merepresentasikan informasi Bayesian network adalah Extensible Markup Language (XML). XML adalah sebuah markup language yang digunakan untuk menyimpan informasi secara terstruktur. Semantik dari sebuah dokumen XML didefinisikan oleh aplikasi yang memprosesnya kemudian. XML dipilih sebagai representasi yang digunakan karena: 1. XML dapat digunakan untuk menyimpan informasi secara terstruktur. Informasi terstruktur ini terdiri dari isi dari informasi itu sendiri dan role dari informasi tersebut. 2. XML menyediakan fasilitas untuk mendefinisikan tag-tag dan relasi struktural yang ada diantara tag-tag tersebut. Hal ini dapat digunakan untuk merepresentasikan relasi antar random variable dan CPT-nya 3. Telah banyak library dalam bahasa pemrograman yang mampu melakukan parsing XML dengan mudah. Kelebihan lain yang didapatkan dengan menggunakan format XML adalah dokumen XML dapat dibuat dengan sintaks yang selain dapat dimengerti oleh mesin juga dapat dimengerti oleh manusia. XML menggunakan markup bertipe elemen untuk menyimpan informasi. Setiap elemen didefinisikan dengan tag yang diberi nama elemen. Nama elemen dapat ditentukan sendiri oleh pembangun. Nama elemen yang didefinisikan dapat berbentuk string literal apapun. Oleh karena itu, dapat didefinisikan sebuah nama elemen
III-16
dengan string term bahasa alami yang memiliki makna yang mewakili elemen tersebut pada dunia nyata sehingga lebih mudah dimengerti manusia. Spesifikasi dokumen XML yang digunakan untuk menyimpan informasi Bayesian network dapat dilihat pada Tabel III-2. Contoh file XML dapat dilihat pada lampiran. Tabel III-2 Representasi Bayesian Network dalam Dokumen XML
1
Nama Elemen NETWORK
2
VARIABLE
3
DEFINITION
4
NAME
5
OUTCOME
6
FOR
7
GIVEN
8
table
No
Keterangan merepresentasikan Bayesian network keseluruhan merepresentasikan random variable merepresentasikan relasi antar random variable dan CPT nya merepresentasikan nama random variable merepresentasikan state yang dimiliki random variable merepresentasikan nama variabel yang menjadi child pada relasi antar variable merepresentasikan nama variabel yang menjadi parent pada relasi antar variabel sesuai urutan parentnya. merepresentasikan CPT random variable
Tipe Content element
string
Content Model Content Multiplicity variable 1..n definition 1..n name 1..1 outcome 1..n for 1..1 given 0..n table 1..1 #PCDATA
string
#PCDATA
string
#PCDATA
string
#PCDATA
string
#PCDATA
element element
3.6 Teknik dan Algoritma Inferensi Pada sub bab ini dijabarkan hasil analisis mengenai teknik dan algoritma apa yang digunakan untuk melakukan proses inferensi pada Bayesian network yang dibangun. Pemilihan algoritma dibatasi pada algoritma yang telah dijabarkan pada sub bab 2.4. Algoritma-algoritma yang telah dijabarkan pada sub bab tersebut merupakan algoritma state-of-the-art untuk melakukan inferensi pada Bayesian network. Pemilihan teknik dan algoritma dilakukan dengan mempertimbangkan karakteristik ranah permasalahan dan tujuan pemodelan jaringan regulatori genetik.
3.6.1 Karakteristik Ranah Permasalahan Jumlah gen yang terlibat dalam jaringan regulatori genetik untuk suatu sel biasanya berjumlah cukup besar. Untuk organisme Saccharomyces cerevisae, jaringan regulatori genetik yang ada melibatkan 30 buah gen. Sesuai dengan analisis sebelumnya, dalam inferensi dengan Bayesian network, gen menjadi random variable. Dengan demikian,
III-17
pada Bayesian network yang direkonstruksi, terdapat sejumlah besar random variable. Dengan semakin banyaknya jumlah variabel, inferensi yang dilakukan juga semakin kompleks. Selain banyaknya jumlah gen yang mengakibatkan banyaknya jumlah random variable pada Bayesian network yang direkonstruksi, pada jaringan regulatori genetik, relasi regulasi yang terdefinisi juga biasanya berjumlah besar. Dengan relasi regulasi yang ekivalen dengan sisi berarah pada Bayesian network, pada saat dilakukan rekonstruksi Bayesian network, graf yang terbentuk berbentuk multiply connected network. Banyaknya sisi berarah dan struktur graf yang termasuk multiply connected network dapat mengakibatkan meningkatnya kompleksitas inferensi. Selain karakteristik fisik dari jaringan regulatori genetik, hal lain yang perlu diperhatikan dalam pemilihan teknik dan algoritma inferensi adalah output yang diinginkan dari sistem berbasis pengetahuan yang dibangun. Sistem berbasis pengetahuan yang dibangun bertujuan untuk melakukan prediksi bagaimana pengaruh kondisi sel tertentu terhadap level ekspresi gen-gen yang terlibat didalamnya. Melalui sistem yang dibangun, ingin diketahui apakah kondisi sel tertentu mengakibatkan level ekspresi suatu gen berada pada state Low, Medium, atau High. Dalam bidang biologi molekuler, mekanisme jaringan regulatori genetik yang dapat dipahami hingga saat ini masih berada pada level pemahaman yang bisa digambarkan dengan pernyataan-pernyataan kualitatif. Pernyataan-pernyataan tersebut misalnya merepresentasikan relasi level ekspresi gen A yang tinggi menyebabkan gen B terekspresi pada level rendah, kecuali bila tidak terjadi ekspresi gen C. Dengan demikian, dapat disimpulkan bahwa dalam inferensi pada jaringan regulatori genetik, nilai probabilitas yang tepat tidak perlu diketahui. Dalam inferensi jaringan regulatori genetik, hasil inferensi yang diinginkan adalah state level ekspresi apa yang sedang dimiliki suatu gen akibat dari kondisi sel tertentu. Dengan demikian, dapat dikatakan bahwa pemodelan jaringan regulatori genetik bertujuan untuk mempelajari relasi kualitatif yang ada antara gen-gen dalam sel. Dari karakteristik jaringan regulatori genetik dan tujuan pemodelan, dapat disimpulkan bahwa teknik dan algoritma inferensi yang dipilih harus memiliki karakteristik sebagai berikut: 1. Mampu melakukan inferensi pada graf yang kompleks. Graf Bayesian network yang direkonstruksi dari model melibatkan sejumlah besar simpul dan sisi serta memiliki struktur multiply connected network.
III-18
2. Tidak perlu menghasilkan nilai probabilitas level ekspresi gen secara tepat, hanya perlu mendekati nilai sebenarnya saja. Pada dua sub bab selanjutnya dilakukan analisis mengenai dua teknik inferensi yang ada pada Bayesian network yaitu exact dan approximate inference. Untuk setiap teknik dilakukan pula analisis berbagai algoritma inferensi state-of-the-art yang ada. Kemudian, dilakukan perbandingan untuk memilih teknik dan algoritma inferensi yang paling sesuai digunakan pada inferensi Bayesian network untuk jaringan regulatori genetik.
3.6.2 Exact Inference Inferensi dengan teknik exact inference melakukan perhitungan secara tepat conditional probability yang ada pada jaringan berdasarkan evidences yang ada. Pada dasarnya, inferensi dengan teknik ini pada Bayesian network merupakan permasalahan yang membutuhkan kompleksitas yang eksponensial. Exact inference antara lain dapat dilakukan dengan algoritma enumerasi variabel atau algoritma variable elimination. Inferensi dengan enumerasi melibatkan penghitungan conditional probability dengan expression tree. Kompleksitas ruang untuk algoritma ini linear terhadap jumlah variabel. Namun, kompleksitas waktu algoritma masih bersifat eksponensial sehingga tidak memungkinkan diterapkan untuk jaringan dengan jumlah variabel yang banyak. Selain itu, dengan penelusuran depth first recursion pada expression tree banyak terdapat subekspresi yang diulangi penghitungannya sehingga memperumit komputasi. Algoritma variable elimination lebih efisien dibandingkan inferensi dengan enumerasi karena mampu menghindari penghitungan berulang dari subekspresi dan menghilangkan variabel yang tidak relevan. Kebutuhan waktu dan ruang untuk algoritma ini sangat ditentukan oleh urutan eliminasi variabel dan struktur jaringan. Untuk singly connected network/polytree dimana terdapat paling banyak satu path tidak langsung antara dua simpul, kompleksitas waktu dan ruang algoritma variable elimination linear terhadap ukuran jaringan. Ukuran jaringan dinyatakan sebagai jumlah entri pada CPT. Sebaliknya, untuk multiply connected network, algoritma ini dapat memiliki kompleksitas waktu dan ruang yang eksponensial. Dari analisis tersebut, dapat disimpulkan algoritma yang lebih efisien untuk teknik exact inference adalah algoritma variable elimination. Dalam ranah permasalahan jaringan regulatori genetik, mungkin terjadi suatu gen diregulasi oleh dua buah gen yang ternyata diregulasi oleh sebuah gen yang sama. Bila direkonstruksi menjadi graf Bayesian network, relasi antar gen-gen tersebut membentuk graf dengan tipe multiply connected
III-19
network. Untuk multiply connected network, algoritma variable elimination memiliki kompleksitas waktu dan ruang yang eksponensial. Untuk menghindari kompleksitas eksponensial pada multiply connected network, dapat digunakan teknik clustering. Teknik ini disebut juga sebagai teknik pembentukan junction tree. Ide dasar dari clustering adalah menggabungkan simpul individual pada jaringan untuk membentuk simpul cluster sedemikian sehingga jaringan yang ada berbentuk singly connected network. Dengan jaringan yang sudah berbentuk singly connected network, inferenso dapat dilakukan dengan kompleksitas yang linear. Dengan demikian, untuk melakukan inferensi dengan teknik exact inference pada jaringan regulatori genetik, algoritma yang dapat memberikan performansi yang paling baik adalah algoritma yang melakukan pembentukan junction tree. Algoritma inferensi dengan junction tree yang paling cepat hingga saat ini adalah algoritma Lauritzen-Spiegelhalter. Namun, seperti algoritma yang melakukan pembentukan junction tree lainnya, algoritma ini memiliki kompleksitas yang eksponensial bila pembentukan junction tree sebelum inferensi memiliki kompleksitas yang eksponensial.
3.6.3 Approximate Inference Teknik approximate inference melakukan inferensi pada Bayesian network tidak menghasilkan nilai conditional probability yang tepat seperti pada exact inference. Namun, teknik ini memungkinkan dilakukannya inferensi pada jaringan yang melibatkan banyak variabel dan relasi karena kompleksitasnya lebih rendah dari exact inference. Pada dasarnya, teknik ini melakukan inferensi dengan melakukan sampling berdasarkan prior probability distribution. Akurasi hasil inferensi sangat bergantung pada jumlah sampling yang digunakan. Terdapat beberapa metode inferensi yang dapat digunakan seperti direct sampling, rejection sampling, dan likelihood weighting. Metode direct sampling dilakukan dengan melakukan sampling secara acak. Proses sampling acak yang paling sederhana pada Bayesian network adalah membangkitkan event dari jaringan dimana tidak terdapat evidence yang berkaitan dengan event tersebut hingga saat ini. Sampling dilakukan pada setiap variabel secara bergantian sesuai urutan topologinya. Nilai distribusi probabilitas sampel bergantung pada nilai yang telah diberikan pada variabel parents. Permasalahan dengan metode ini adalah metode ini belum dapat dipastikan memberikan estimasi yang konsisten. Rejection sampling adalah metode umum yang digunakan untuk menghasilkan sampel dari distribusi yang sulit di-sampling bila diberikan distribusi yang mudah untuk di-
III-20
sampling. Permasalahan utama rejection sampling adalah algoritma ini mengeliminasi terlalu banyak sampel. Fraksi dari sampel yang konsisten dengan evidence menurun secara eksponensial seiring dengan pertambahan variabel evidence. Dengan demikian, metode ini tidak dapat digunakan untuk permasalahan yang kompleks seperti jaringan regulatori genetik. Likelihood weighting mampu mengeliminasi kelemahan rejection sampling dengan hanya membangkitkan events yang konsisten dengan evidence. Sama seperti rejection sampling, likelihood weighting juga memberikan estimasi yang konsisten terhadap distribusi probabilitas sebenarnya. Bobot yang ada menyatakan perbedaan antara distribusi probabilitas estimasi dan sebenarnya. Karena likelihood weighting menggunakan seluruh sampel yang dibangkitkan, algoritma ini jauh lebih efisien dibandingkan dengan rejection sampling. Namun, performansi algoritma menurun seiring dengan pertambahan jumlah variabel evidence karena hanya sedikit sampel yang memiliki bobot penuh. Performansi approximate inference dengan menggunakan Markov Chain Monte Carlo (MCMC) tidak menurun seiring dengan pertambahan evidences seperti pada likelihood weighting. Pada ranah permasalahan jaringan regulatori genetik, tidak dapat dipastikan jumlah evidences yang diperoleh. Ada kemungkinan dapat diperoleh evidences dalam jumlah yang banyak. Namun, MCMC memiliki kelemahan karena harus dilakukan penghitungan Markov blanket untuk setiap simpul pada saat sampling. Bila Markov blanket berukuran besar, perhitungan untuk sampel tidak memberikan peningkatan performansi yang berarti. Padahal, pada jaringan regulatori genetik, relasi yang terdefinisi mungkin berjumlah besar sehingga mengakibatkan besarnya ukuran Markov blanket untuk suatu simpul. Dari hasil analisis tersebut, dapat disimpulkan bahwa algoritma inferensi yang dapat memiliki performansi yang baik untuk teknik approximate inference pada domain jaringan regulatori genetik adalah likelihood weighting dan MCMC. Namun, dari keduanya, tidak dapat ditentukan algoritma mana yang lebih baik secara teoritis. Oleh karena itu, perlu dilakukan pembandingan kedua algoritma untuk domain jaringan regulatori genetik
3.6.4 Perbandingan Untuk menghitung nilai probabilitas posterior, dilakukan perhitungan dengan teknik exact inference. Namun, teknik ini memiliki kompleksitas yang eksponensial. Untuk menghindari hal tersebut, inferensi dilakukan dengan teknik approximate inference. Tidak semua algoritma approximate inference mampu menghasilkan perkiraan distribusi
III-21
yang konsisten dengan distribusi sebenarnya. Walaupun beberapa metode approximate inference seperti rejection sampling dan likelihood weighting mampu memberikan estimasi probabilitas yang konsisten, akurasi nilai probabilitas sangat ditentukan oleh banyaknya jumlah sample. Semakin banyak jumlah sample maka nilai estimasi probabilitas semakin tepat. Tabel III-3 Kompleksitas Algoritma No 1 2 3 4 5 6
Algoritma Enumerasi Variable Elimination Clustering (Junction Tree) Rejection Sampling Likelihood Weighting Markov Chain Monte Carlo
Kompleksitas Waktu O(kn) O(n) - O(kn) O(n) - O(kn) O(n) O(n) O(n)
Kompleksitas Ruang O(n) O(n) - O(kn) O(n) - O(kn) O(n) O(n) O(n)
Keterbatasan exact inference terdapat pada sisi kompleksitas ruang dan waktu seperti ditabulasikan pada Tabel III-3. Exact inference melakukan inferensi dengan kompleksitas yang eksponensial. Algoritma variable elimination hanya mampu melakukan inferensi dengan kompleksitas linear pada singly connected network. Dengan menggunakan algoritma clustering yang mengubah terlebih dahulu multiply connected network menjadi singly connected network, inferensi pada multiply connected network dapat dilakukan dengan kompleksitas yang linear. Namun, apabila pembentukan junction tree memiliki kompleksitas yang eksponensial, proses inferensi tetap memiliki kompleksitas yang eksponensial sehingga tidak dapat digunakan pada jaringan yang kompleks seperti pada jaringan regulatori genetik. Berdasarkan analisis tersebut, diperoleh hipotesis bahwa teknik exact inference tidak dapat digunakan untuk ranah permasalahan jaringan regulatori genetik. Dalam pengerjaan Tesis ini, digunakan teknik approximate inference untuk mendekati nilai exact. Teknik ini juga dapat diimplementasikan untuk jaringan yang kompleks seperti pada jaringan regulatori genetik. Penggunaan approximate inference juga didasarkan pada output inferensi yang diinginkan dimana tidak dibutuhkan nilai probabilitas yang exact. Algoritma yang digunakan untuk melakukan inferensi adalah algoritma likelihood weighting dan MCMC. Dari hasil analisis, kedua algoritma ini mampu memberikan estimasi probabilitas yang konsisten. Selain itu, bila dibandingkan dengan algoritma approximate inference lainnya, kedua algoritma ini memberikan performansi yang paling baik. Dengan menggunakan algoritma ini diharapkan dapat diperoleh nilai probabilitas yang mendekati nilai exact dan konsisten. Namun, dari hasil analisis, belum dapat
III-22
disimpulkan algoritma mana yang memberikan performansi yang paling baik dari kedua algoritma ini. Untuk membandingkan kedua algoritma yang dipilih, dilakukan perbandingan dari sisi kebutuhan memori dan waktu. Selain itu, karena kedua algoritma merupakan algoritma approximate inference yang hanya memperkirakan nilai distribusi sebenarnya, perbandingan dilakukan juga dengan membandingkan nilai probabilitas yang dihasilkan masing-masing algoritma dengan nilai probabilitas sebenarnya yang dihasilkan teknik exact inference. Performansi kedua algoritma approximate inference diukur terhadap pertambahan kompleksitas data. Selain itu, karena performansi teknik approximate inference juga sangat bergantung pada jumlah sampel yang digunakan, dilihat pula pengaruh jumlah sampel yang digunakan dasn jumlah evidences terhadap performansi algoritma. Untuk dapat menjamin bahwa perkiraan distribusi yang dihasilkan benar-benar mendekati distribusi yang sebenarnya, perlu diukur kedekatan distribusi probabilitas dengan distribusi probabilitas sebenarnya. Nilai probabilitas sebenarnya yang digunakan dalam pengujian dihitung dengan menggunakan teknik exact inference. Berdasarkan hasil analisis, algoritma exact inference yang memberikan performansi yang paling baik adalah algoritma clustering. Oleh karena itu, hasil inferensi dibandingkan dengan hasil inferensi yang diperoleh melalui algoritma clustering Lauritzen-Spiegelhalter. Pembandingan distribusi probabilitas dilakukan dengan mengukur dua besaran sebagai berikut: 1. Average Kullback-Leibler Distance Untuk membandingkan distribusi probabilitas, dilakukan pengukuran KullbackLeibler Distance (KL distance) [KUL51] dari nilai probabilitas approximate terhadap nilai probabilitas exact untuk setiap simpul query. Nilai KL distance ini kemudian dirata-rata untuk memperoleh gambaran perbedaan distribusi probabilitas keseluruhan. KL distance dari distribusi probabilitas approximate P’ terhadap distribusi probabilitas exact P untuk setiap variabel dapat dirumuskan dalam persamaan ( III-1). Nilai ini menyatakan directed divergence dari distribusi probabilitas approximate P’ terhadap distribusi probabilitas exact P. KL distance selalu bernilai non-negatif dan hanya sama dengan 0 bila P = P’. Dengan kata lain, KL distance hanya bernilai nol bila distribusi hasil perkiraan sama persis dengan distribusi sebenarnya. Semakin kecil nilai KL distance,
III-23
semakin baik perkiraan distribusi yang dihasilkan. Dengan mengukur besaran ini, dapat diketahui bagaimana perkiraan distribusi yang dihasilkan kedua algoritma approximate inference mendekati nilai distribusi yang sebenarnya.
KL( P, P' ) = ∑ P( s) log s
P( s ) P' ( s ) ( III-1)
2. Average Symmetric KL Distance Selain menggunakan KL distance, besaran lain yang digunakan adalah symmetric KL distance. Symmetric KL distance antara distribusi probabilitas P dan P’ didefinisikan dalam persamaan ( III-2). Besaran ini digunakan untuk mengukur jarak antara kedua distribusi probabilitas. Pengukuran dengan KL distance belum dapat didefinisikan sebagai jarak antara dua probabilitas karena sifatnya yang tidak simetrik. Nilai KL distance dari nilai probabilitas P terhadap P’ berbeda dengan nilai KL distance dari nilai probabilitas P’ terhadap P. Nilai symmetric KL distance untuk setiap variabel ini kemudian dirata-rata untuk memperoleh jarak antar kedua distribusi. Dengan mengukur nilai tersebut, dapat diketahui bagaimana jarak rata-rata antara distribusi probabilitas sebenarnya dan distribusi hasil perkiraan.
SymKL ( P , P ' ) = KL ( P , P ' ) + KL ( P ' , P ) ( III-2)
3.7 Analisis Kebutuhan Perangkat Lunak Pada sub bab ini dijabarkan hasil analisis terhadap kebutuhan prototipe perangkat lunak yang dibangun dengan metode analisis perangkat lunak berorientasi objek. Analisis diawali dengan deskripsi umum sistem yang kemudian diturunkan dalam pemodelan use case. Hasil pemodelan use case dianalisis lebih lanjut untuk menentukan struktur modul perangkat lunak.
3.7.1 Deskripsi Umum Sistem Perangkat lunak yang dibangun merupakan sistem berbasis pengetahuan jaringan regulatori genetik. Perangkat lunak ini memiliki fitur-fitur sebagai berikut: 1. Mampu melakukan rekonstruksi basis data model jaringan regulatori genetik menjadi Bayesian network.
III-24
2. Mampu menampilkan graf jaringan regulatori genetik yang direkonstruksi dari model jaringan regulatori genetik. 3. Mampu menerima masukan evidences/observasi dari pengguna berupa level ekspresi gen-gen yang terlibat dalam jaringan regulatori genetik. 4. Mampu melakukan exact inference dengan algoritma junction tree berdasarkan evidences dari pengguna. 5. Mampu melakukan approximate inference dengan algoritma likelihood weighting dan Markov Chain Monte Carlo dengan jumlah sampel dan evidences sesuai masukan pengguna. 6. Mampu membandingkan hasil inferensi yang dihasilkam dengan nilai probabilitas sebenarnya yang dihitung dengan teknik exact inference. Masukan dari pengguna sistem berupa evidences/observasi level ekspresi dari satu atau lebih gen yang terlibat dalam jaringan regulatori genetik. Pengguna kemudian dapat memilih untuk melakukan inferensi dengan menggunakan salah satu teknik inferensi atau langsung membandingkan keduanya. Selain itu, untuk approximate inference, pengguana dapat memberikan input jumlah sampel yang diinginkan. Sistem memberikan keluaran hasil inferensi berupa probabilitas level ekspresi gen-gen yang terlibat. Sistem juga memberikan keluaran berupa perbedaan distribusi probabilitas yang dihasilkan dengan distribusi sebenarnya. Secara umum, arsitektur sistem dapat dilihat pada Gambar III-2.
3.7.2 Pemodelan Perangkat Lunak Dari deskripsi umum sistem dan asumsi yang telah ditetapkan, dilakukan pemodelan perangkat lunak dengan menggunakan notasi UML. Fungsionalitas perangkat lunak yang dibangun dapat dilihat melalui diagram use case pada Gambar III-8. Pada diagram tersebut terlihat bahwa hanya terdapat satu aktor yaitu user yang merupakan pengguna aplikasi. Aktor berkomunikasi dengan sebuah use case yaitu use case inferNetwork. Dengan use case inferNetwork, aktor melakukan inferensi Bayesian network jaringan regulatori genetik berdasarkan evidences yang dimasukkan oleh aktor. Use case ini melibatkan
use
case
inputEvidences
dimana
aktor
memberikan
masukan
evidences/observasi pada sistem. Berdasarkan pemodelan use case yang telah dilakukan, hanya terdapat satu aktivitas aktor pada perangkat lunak. Diagram aktivitas yang berkaitan dengan use case monitorGRN dapat dilihat pada Gambar III-9. Selain itu, dapat didefinisikan tiga package dan dua
III-25
subsistem pada sistem yang dibangun. Ketiga package terdefinisi, layer dan tanggung jawabnya dapat dilihat pada Tabel III-4. Tabel III-4 Deskripsi Package Aplikasi No 1
Package display
Layer presentation
2 3
generator inference
application application
Tanggung Jawab melakukan interaksi dengan pengguna sistem dan menampilkan hasil pemrosesan sistem. membangkitkan Bayesian network dari model. melakukan inferensi pada Bayesian network berdasarkan input evidences.
Tabel III-5 Deskripsi Kelas Aplikasi No 1
Nama ModelApp
Jenis Facade
2
UIMonitorGRN
Boundary
Package <default package> display
3
BNGenerator
Control
generator
4
InferenceEngine
Control
inference
5
Evidence
Entity
inference
6
Evidences
Entity
inference
7
BN
Entity
generator
8
Result
Entity
inference
Tanggung Jawab Kelas utama, menyembunyikan semua kerumitan yang terjadi dalam sistem. Melakukan interaksi dengan pengguna, antarmuka antara pengguna dengan sistem Membangkitkan Bayesian network dari pengetahuan pada basis pengetahuan. Melakukan inferensi dari Bayesian network yang dibangun berdasarkan input pengguna Abstract data type untuk merepresentasikan evidence. Abstract data type untuk merepresentasikan himpunan evidences. Abstract data type untuk merepresentasikan Bayesian network. Abstract data type untuk merepresentasikan hasil inferensi
Subsistem yang digunakan pada sistem ini adalah subsistem Bayesian Network Tools in Java versi 2, release 7 [KAN04] yang bertanggung jawab untuk melakukan inferensi pada jaringan dengan algoritma inferensi junction tree, likelihood weighting, dan Markov Chain Monte Carlo. Selain itu, terdapat pula subsistem jGraphLayout [JGR08] yang berfungsi untuk menampilkan graf Bayesian network. Kelas yang didefinisikan pada tahap analisis dapat dilihat pada Gambar III-8. Tanggung jawab masing-masing kelas dapat dilihat pada Tabel III-5.
Gambar III-8 Diagram Use Case
III-26
Gambar III-9 Diagram Aktivitas Use Case inferNetwork
Gambar III-10 Diagram Kelas Tahap Analisis
3.8 Perancangan Perangkat Lunak Sesuai dengan hasil analisis perangkat lunak, dibangun sebuah sistem berbasis pengetahuan untuk jaringan regulatori genetik dengan Bayesian network. Perangkat lunak yang dibangun diberi nama Genetsim. Perangkat lunak ini memiliki fitur-fitur dan arsitektur seperti yang telah didefinisikan pada sub bab 3.7.
III-27
Genetsim dirancang sebagai aplikasi web dan bukan sebagai aplikasi desktop. Pertimbangan pengembangan sebagai aplikasi web ini antara lain: 1. Masih terbatasnya sistem berbasis pengetahuan dengan ranah permasalahan serupa Genetsim. Agar Genetsim dapat memberikan kontribusi yang optimal pada bidang biologi molekuler, maka Genetsim harus dapat diakses dengan mudah. Dengan mengembangkan Genetsim sebagai aplikasi web, sistem berbasis pengetahuan ini dapat lebih mudah diakses daripada ketika dikembangkan sebagai aplikasi desktop. 2. Kemudahan update dan maintenance Salah satu latar belakang mengapa Genetsim dikembangkan sebagai sistem berbasis pengetahuan adalah pengetahuan mengenai jaringan regulatori genetik yang masih dapat berubah. Apabila Genetsim dikembangkan sebagai aplikasi desktop, proses update dan maintenance lebih sulit untuk dilakukan. Dengan mengembangkan Genetsim sebagai aplikasi web, cukup dilakukan update dan maintenance terhadap satu aplikasi. 3. Tidak terbatas digunakan pada satu sistem operasi tertentu Dengan mengembangkan Genetsim sebagai aplikasi web, untuk mengakses Genetsim, pengguna hanya membutuhkan browser sehingga sistem tidak terbatas digunakan pada satu sistem operasi tertentu. Sesuai dengan hasil analisis, perangkat lunak ini memiliki dua layer yaitu layer application dan layer presentation. Package yang terdefinisi untuk setiap layer dapat dilihat pada Tabel III-6. Package core berisi kelas untuk merepresentasikan abstract data type gen. Package database berisi kelas-kelas untuk melakukan koneksi dan pengambilan data dari basis data. Package generator berisi kelas-kelas untuk melakukan rekonstruksi Bayesian network dari model. Package inference berisi kelas-kelas untuk melakukan inferensi pada Bayesian network. Sedangkan package bnj berisi kelas-kelas pada subsistem Bayesian Network in Java dan package jgraph berisi kelas-kelas dari subsistem jGraphLayout. Kelas-kelas yang terdapat pada setiap package dan tanggung jawabnya dapat dilihat pada Tabel III-7. Kelas analisis lain seperti Evidence, Evidences, dan Result direpresentasikan sebagai kelas yang telah terdapat pada subsistem Bayesian Network in Java. Sedangkan,
III-28
karena Genetsim dirancang sebagai aplikasi web, package display bukan merupakan kelas tapi berupa script halaman web. Tabel III-6 Alokasi Package No 1
Layer Application
2
Presentation
Package core generator inference database bnj display jgraph
Tabel III-7 Kelas Perancangan No 1
Kelas Gene
Package core
Kelas Analisis -
2
DBConfiguration
database
-
3 4
DBConnection Model
database generator
BN
5
Parser
generator
BNGenerator
6
Engine
inference
InferenceEngine
7
EngineServlet
inference
-
Tanggung Jawab Abstract data type untuk data gen yang disimpan pada basis data Menyimpan konfigurasi basis data yang digunakan Melakukan koneksi ke basis data Abstract data type untuk merepresentasikan Bayesian network Mengkonstruksi Bayesian network dan menyimpannya ke file untuk pengaksesan selanjutnya. Melakukan inferensi dari Bayesian network berdasarkan evidences masukan pengguna. Melakukan wrapping hasil inferensi menjadi HTTP response.
Rancangan user interface berupa halaman web dengan tampilan tiga kolom. Kolom pertama merupakan kolom yang berisi tree view untuk memasukkan evidences. Kolom kedua berfungsi untuk menampilkan graf Bayesian network, dan kolom terakhir berfungsi untuk menampilkan hasil inferensi dalam bentuk treeview. Pada kolom terakhir juga dicantumkan kebutuhan waktu, memori, dan perbedaan distribusi probabilitas kedua teknik inferensi. Rancangan user interface dapat dilihat pada Gambar III-11.
III-29
Gambar III-11 Rancangan User Interface