Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

Beranda arrow Akademik arrow S-1 Matematika arrow Karya Ilmiah Alumni
 
Data Tesis
 
Judul : KAJIAN MODEL HIDDEN MARKOV DISKRET DENGAN ALGORITME RABINER DAN APLIKASINYA PADA DNA
Jenis :
Penulis : Hagni Wijayanti
NRP : G551070041
Tanggal Lulus : 12 July 2010
Tanggal Seminar :
Tanggal Sidang :
Pembimbing :


Ringkasan : Setiap kejadian berkaitan erat dengan penyebab kejadian. Jika penyebab kejadian tersebut tidak diamati secara langsung dan membentuk rantai Markov, maka pasangan kejadian dan penyebabnya dapat dimodelkan dengan model Hidden Markov (Hidden Markov Model, HMM). Model Hidden Markov adalah sebuah model yang dibangun oleh rantai Markov yang tidak diamati, serta proses observasi yang dipengaruhi oleh . Ciri model Hidden Markov adalah: yaitu sebuah rantai Markov dengan ruang state berhingga yang homogen dan ergodic. untuk . adalah matriks transisi dari dengan dan . dengan dan memenuhi dan yaitu sebuah proses observasi dengan ruang state . Proses , dihubungkan oleh distribusi peluang bersyarat , dengan untuk Diasumsikan saling bebas. Dari ketiga ciri tersebut, diperoleh karakteristik model Hidden Markov yaitu: . Diberikan barisan observasi untuk dan . Masalah dasar dari model Hidden Markov, yaitu: 1. Menghitung peluang munculnya barisan observasi . 2. Memilih barisan state yang memaksimumkan peluang observasi. 3. Melakukan pendugaan terhadap parameter-parameter model Hidden Markov , sehingga maksimum. Solusi dari 3 masalah di atas berturut-turut dapat diperoleh dengan algoritme forward, algoritme Viterbi dan algoritme Baum-Welch re-estimation (Rabiner 1989). Didefinisikan peubah forward, Dengan induksi, dapat dihitung sebagai berikut : 1. Inisialisasi: . 2. Induksi: , 3. Terminasi: Pada masalah kedua, akan dipilih barisan state sehingga adalah maksimum. Didefinisikan, Barisan yang menghasilkan yaitu, . Prosedur lengkap algoritme Viterbi adalah sebagai berikut: Diberikan barisan observasi untuk dan . 1. Inisialisasi, Hitung untuk setiap . . 2. Rekursi. Hitung . Untuk Gunakan selanjutnya untuk dan lanjutkan terus sampai 3. Terminasi. P* = ; 4. Penelusuran balik barisan state. Barisan state terbaik diperoleh dengan . Pendugaan barisan observasi berdasarkan barisan state { yang memiliki nilai peluang maksimum. Untuk setiap dibangkitkan secara acak anggota ruang state dengan nilai peluang sesuai dengan parameter Pada masalah ketiga, akan dimaksimumkan nilai peluang untuk memperoleh nilai parameter model Hidden Markov yang dapat dengan baik mendeskripsikan rangkaian observasi yang terjadi. Untuk permasalahan ini, terdapat prosedur iteratif algoritme Baum-Welch. Dengan menggunakan prosedur iteratif algoritme Baum-Welch, dapat diperoleh yaitu penduga parameter model. Model adalah model yang lebih baik dari model , jika berlaku: . Didasari oleh prosedur di atas, jika secara iteratif menggunakan sebagai dan selanjutnya diulang maka dapat diperoleh nilai peluang yang semakin baik. Hasil akhir dari prosedur re-estimasi ini disebut penduga maksimum likelihood dari model Hidden Markov. Formula reestimasi di atas selanjutnya dapat dinyatakan sebagai implementasi dari algoritme Expectation Maximization (EM) . Model Hidden Markov diskret di atas diaplikasikan pada urutan basa DNA pada spesies Aspergillus niger. Suatu program komputasi dibuat untuk menyelesaikan masalah tersebut dengan menggunakan software Mathematica versi 7.0. Pendugaan barisan observasi pada urutan DNA dilakukan dengan membangkitkan bilangan acak pada parameter yang dicatat oleh SeedRandom. Parameter juga ditentukan oleh nilai N, yaitu banyaknya faktor penyebab kejadian yang hidden. Ternyata dengan nilai N yang semakin besar, persentase ketepatan dugaan maksimum barisan observasi cenderung membesar secara linear dan frekuensi parameter yang dibangkitkan oleh bilangan acak tercatat (SeedRandom) yang menduga urutan DNA dengan ketepatan dugaan lebih besar dari 40%, juga meningkat. Hasil komputasi terbaik pada penelitian ini yaitu diperoleh dugaan barisan observasi dengan persentase ketepatan dugaan barisan observasi 68% dan dugaan untuk setiap basa nitrogen c, g, t, a, minimum 61%, di . Kata kunci: Rantai Markov, model Hidden Markov diskret, algoritme forward, algoritme Viterbi, algoritme Baum-Welch.

Random Quotes

menunda berarti mencuri waktu

anonim