HMM выравнивание

1. HMM выравнивание

2.

s(xi,yj)
s(xi,yj)
X
(+1,+0)
-e
1-ε
-d
1-δ
M
(+1,+1)
Y
(+0,+1)
M
pxiyj
δ
1-ε
-e
Конечный автомат FSA
ε
δ
-d
s(xi,yj)
X
qxi
Y
qyj
HMM
ε

3. Рекурсия FSA

V M (i 1, j 1)
X
M
V (i, j ) s ( xi , yi ) max V (i 1, j 1)
V Y (i 1, j 1)
M
V
(i 1, j ) d
X
V (i, j ) max X
V (i 1, j ) e
M
V
(i, j 1) d
Y
V (i, j ) max Y
V (i, j 1) e

4.

δ
ε
δ
1-2δ-τ
Begin
X
qxi
1-ε-τ
M
pxiyj
τ
τ
1-ε-τ
1-2δ-τ
δ
δ
Y
qyj
End
τ
ε
τ

5. Алгоритм Витерби

– Начало:
vM(0, 0) = 1. vX(0, 0) = vY(0, 0) = 0 v*(-1, j) = v*(i, -1) = 0.
– Рекурсия: i = 0,…,n, j = 0,…,m, except for(0,0);
v M (i, j ) p xi y j
(1 2 )v M (i 1, j 1)
max (1 )v X (i 1, j 1)
(1 )v Y (i 1, j 1)
v M (i 1, j )
v (i, j ) q xi max X
v (i 1, j )
v M (i, j 1)
Y
v (i, j ) q y j max X
v (i, j 1)
X
– Вывод: v
E
max( v M (n, m), v X (n, m), v Y (n, m))

6. Полная вероятность выравниваний

Алгоритм: Forward для парных HMMs
– Начало:
fM(0, 0) = 1, fX(0,0) = fY(0,0)= 0.
All f•(i,-1), f•(-1, j) are set to 0.
– Рекурсия: i = 0,…,n, j = 0,…,m except (0,0);
f M (i, j ) p xi y j [(1 2 ) f M (i 1, j 1)
(1 )( f X (i 1, j 1) f Y (i 1, j 1))];
f X (i, j ) q xi [ f M (i 1, j ) f X (i 1, j )];
f Y (i, j ) q y j [ v M (i, j 1) v X (i, j 1)].
– Вывод:
f E (n, m) [ f M (n, m) f X (n, m) f Y (n, m)];

7. Вероятность выровненных xi и yj

P( xi y j | x, y)
P( x, y, xi y j )
P( x, y)
Forward algorithm
P( x, y, xi y j ) P( x1... i , y1... j , xi y j ) P( xi 1... n , y j 1... m | x1... i , y1... j , xi y j )
P( x1... i , y1... j , xi y j ) P( xi 1... n , y j 1... m | xi y j )
Forward algorithm
Backward algorithm

8. Backward Algorithm

Алгоритм: Backward для парных HMMs
– Начало:
bM(n, m) = bX(n, m) = bY(n,m) = τ.
All b•(i, m+1), b•(n+1, j) are set to 0.
– Рекурсия: i = 1,…,n, j = 1,…,m except (n, m);
b M (i, j ) (1 2 ) p xi 1 y j 1 b M (i 1, j 1)
[q xi 1b X (i 1, j ) q y j 1b Y (i, j 1)];
b X (i, j ) (1 ) p xi 1 y j 1 b M (i 1, j 1) q xi 1 b X (i 1, j )];
b Y (i, j ) (1 ) p xi 1 y j 1 b M (i 1, j 1) q y j 1 b Y (i, j 1)].