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

X (+1,+0) M (+1,+1) Y (+0,+1) -e-e -d-d -d-d -e-e s(x i,y j ) X q xi M p xiyj Y q yj ε ε 1-ε1-ε 1-ε1-ε δ δ 1-δ1-δ Конечный автомат FSAHMM

Рекурсия FSA

X q xi M p xiyj Y q yj ε ε 1-ε-τ1-ε-τ δ δ 1-2δ-τ 1-ε-τ1-ε-τ δ δ τ τ τ τ Begin End 1-2δ-τ

Алгоритм Витерби – Начало: v M (0, 0) = 1. v X (0, 0) = v Y (0, 0) = 0 v * (-1, j) = v * (i, -1) = 0. – Рекурсия: i = 0,…,n, j = 0,…,m, except for(0,0); – Вывод:

Полная вероятность выравниваний Алгоритм: Forward для парных HMMs – Начало: f M (0, 0) = 1, f X (0,0) = f Y (0,0)= 0. All f (i,-1), f (-1, j) are set to 0. – Рекурсия: i = 0,…,n, j = 0,…,m except (0,0); – Вывод:

Вероятность выровненных x i и y j Forward algorithmBackward algorithm Forward algorithm

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