Kajian Model Hidden Markov Diskret dengan Algoritme Rabiner dan Aplikasinya pada DNA

Abstract

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 (X, Y) adalah sebuah model yang dibangun oleh rantai Markov X = {Xk;k E N} yang tidak diamati, serta proses observasi Y = {Ykik E N} yang dipengaruhi oleh X. Ciri model Hidden Markov adalah: {X} yaitu sebuah rantai Markov dengan ruang state berhingga Sx = {1,2,...,N} yang homogen dan ergodic. aij = P(Xk+1 = j |Xk = i), untuk i,j = 1,2, ... N. ANXN = (aij) adalah matriks transisi dari X dengan a¿; ≥ 0 N dan Σ=1αij = 1. π; = P(X₁ = j) dengan π = (π1,...,πN). π = E[X] dan memenuhi Aл = π dan Σ=1; = 1. {Ykik E N} yaitu sebuah proses observasi dengan ruang state Sy = {1, 2,..., M}. Proses {Xk, Yk; k E N}, dihubungkan oleh distribusi peluang bersyarat b; (j) = P(Yk = j |Xk = i), j = 1,2, ... M; i = 1,2, ..., N. BNXM = (b)), dengan b; (j) ≥ 0, 1 b; (i) = 1, untuk i = 1,2,..., N. Diasumsikan {YKIXk} saling bebas. Dari ketiga ciri tersebut, diperoleh karakteristik model Hidden Markov yaitu: 2 λ = (A, B, π). Diberikan barisan observasi y₁, Y2, ... Yk; Yk € Sy untuk k = 1,2,..., K dan λ = (A, B, π). Masalah dasar dari model Hidden Markov, yaitu: 1. Menghitung peluang munculnya barisan observasi y1, V2, ... YK- 2. Memilih barisan state yang memaksimumkan peluang observasi. 2. Memilih barisan state yang memaksimumkan peluang observasi. 3. Melakukan pendugaan terhadap parameter-parameter model Hidden Markov λ = (A, B, π), sehingga P(Y₁ = 1, ..., YK = уK2) 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, a (j) = P(Y₁ = Y1, ..., Yk = Yk, Xk = j|λ). Dengan induksi, ak (j) dapat dihitung sebagai berikut: 1. Inisialisasi: a₁(j) = P(Y₁ = Y₁, X1 = jλ) = πjbj(y1), j = 1,2,... N. 2. Induksi: ak+1) = P(Y₁ = Y1,..., Yk+1 = Yk+1, Xk+1 = jλ) = [=1 αk (i) αij]bj (k+1), j = 1,2, ... N; 1 ≤ k ≤ K − 1. Li=1 3. Terminasi: P(Y₁ = Y1,..., YK = Yk|2) = Σ=1 P(Y₁ = Y1,..., YK = YK, XK = j]) = Σ=1αk(j) K Pada masalah kedua, akan dipilih barisan state {x}=1 sehingga P(Y₁ = y1,..., YK = YK, X1 X1, ..., XK = xx 2) adalah maksimum. Didefinisikan, Sk (j) = maxx1,x2, xk-1 P(Y1 = Y1, ..., Yk = Yk, X1 X1, ..., Xk = j|λ). = Barisan yang menghasilkan (i) yaitu, j) = arg maxi=1,...,N Sk-1 (i)αij......dst