HiddenMarkovModel에서 Most probable state path를 찾는 알고리즘. Decoding의 방법으로 널리 사용되며, DynamicProgramming과 밀접한 관련이 있다.

unknown서열에서 CpG_island를 찾는다는 것은, 각 발생 문자들이 어떤 state에서 발생하였는지를 보는것이며, 이것이 바로 state path 찾기이고, JointProbability P(x, π)를 최대로 하는 π를 찾는것이며, 이것이 ViterbiAlgorithm.

π* = argmax P(x, π)

Most probable path π*는 Recursion에 의해 계산될 수 있다. state k와 observation i에서의 most probable path ending의 Probability를 vk(i)라고 하면, xl(i+1)에서는 다음처럼 계산된다.

vl(i+1) = el(x(i+1)) max(vk(i) akl)

ViterbiAlgorithm

Initialisation (i=0):   v0(0)=1, vk(0)=0 for k>0.

Recursion (i=1,...,L):  vl(i) = el(xi) max(k)(vk(i-1)akl);
                        ptri(l) = argmax(k)(vk(i-1)akl).

Termination:            P(x,π*) = max(k)(vk(L)ak0);
                        π*L = argmax(k)(vk(L)ak0).

Traceback (i=L,...,1):  π*(i-1) = ptri(π*i).

ViterbiAlgorithm이 항상 적절한 값을 주는 것은 아니다. 특히도, most probable path와 유사한 많은 path들이 있을 경우가 그렇다. 따라서, ForwardAlgorithm, BackwardAlgorithm, PosteriorDecoding의 방법을 사용한다.