최근에 여러 가지 자료 구조와 알고리즘을 보다가 은닉 마르코프 모델과 비터비 알고리즘을 보게 되었다. 이런 알고리즘을 왜 사용하는 걸까? 라는 고민에 이것 저것 찾아 보다가 정리를 할 수 있게 되어 간략하게 적게 되었다.
가령 생물 정보학에서 자주 다루게 되는 DNA 염기서열이 다음과 생성(output)이 되었다고 하자.
s = "ATCGATCGTTTCATTAGTATTCATGCT"
이 서열에는 총 4가지 문자가 사용되었다. 그렇다면, 이런 서열을 생성하는 동안 각 순간에 염기 변이 확률 같은 것이 있지 않을까? 확률로써 염기의 전이들을 표현하고 싶다면, 그에 합당한 모델이 있어야 한다. 이 때 우리는 은닉 마르코프 모델(HMM)을 사용할 수 있다.
예를 들어, 우리는 다음과 같이 은닉 마르코프 모델을 정의할 수 있다.
이런 전이에서 3가지 상태가 있다고 하자. 즉 엑손(exon, 실제 전사가 일어날 수 있는 서열), 스플라이스(splice, exon 중 일부를 선택), 인트론(intron, 기본적으로는 전사에 직접 이용되지 않는 서열)의 상태라고 하자. 이 상태라는 말은 특정 시점에 한 염기가 이 3 가지 상태 중 한 가지에 있다는 것을 말한다. 이걸 그래프로 보자면, 각 상태는 정점(Vertex)가 되고 상태에서 머무는 확률은 그래프의 에지에 할당된다.
다음으로 염기가 전이할 때, 맨 처음은 엑손 상태에서 시작한다고 하자. 그리고 엑손 상태나 인트론 상태에서 머물러 있을 확률은 0.9이라고 하자. 인트론에서 엑손으로 전이할 때는 스플라이스 상태에 있는 문자 중 딱 한 개의 문자가 생성되면서 스위칭이 이뤄진다고 가정한다. 또한, 최종적으로 0.1의 확률로 인트론 상태에서 종결되게 된다고 하자.
edge1: 초기 상태 - 엑손 상태(1.0)
edge2: 엑손 상태 - 엑손 상태(0.9)
edge3: 엑손 상태 - 스플라이스 상태(0.1)
edge4: 스플라이스 상태 - 인트론 상태(1.0)
edge5: 인트론 상태 - 인트론 상태(0.9)
edge6: 인트론 상태 - 종결 상태(0.1)
위 모델을 간단히 요약 해보면, 위의 초록 부분처럼 될 것이다. 이해하기 쉽게 다시 풀어서 설명하면, 초기 상태에선 엑손 상태로 무조건 들어가고(1의 확률), 0.9의 높은 확률로 전이가 계속 일어나다가, 한 순간에 높은 확률로 G를 스위치로 이용해서 스플라이스 상태로 갔다가 그 직후 바로 인트론 상태로 무조건 가고(1의 확률), 인트론 상태에서도 엑손 상태와 마찬가지로 0.9의 높은 확률로 서열들이 쓰이다가, 0.1의 확률로 종결 상태에 들어가게 된다. 그리고 그 확률 중에 ACTG 중 한 염기가 선택될 확률을 다음과 같이 정의해준다. 이것을 발산 확률(emission probabilities)라고 한다.
|
A |
C |
G |
T |
엑손 상태 |
0.25 |
0.25 |
0.25 |
0.25 |
스플라이스 상태 |
0.05 |
0.0 |
0.95 |
0.0 |
인트론 상태 |
0.4 |
0.1 |
0.1 |
0.4 |
이런 은닉 마르코프 모델이 정의된 상태에서 우리는 비터비 알고리즘이라는 것을 써서 무엇을 알 수 있는가? 우리는 비터비 경로 라는 것을 계산할 수 있다. 이 경로가 의미하는 바는, 주어진 출력을 생성하기 위해서 필요한 상태의 서열이다. 말하자면, 각 선택이 이뤄지는 순간의 상태들을 한 염기 마다 적어 놓은 경로라고 보면 된다. 그리고 얼마나 그것이 그럴싸한가 하는 확률 값도 출력할 수 있다. 이 경우는 다음과 같은 결과를 얻었다.
얼마나 그럴싸 한가?
1.24155e-18
비터비 경로
0(시작),1,1,1,1,1,1,1,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4(종결)
이게 뭔가 할 수도 있지만, 이것을 쉽게 보기 위해서 스플라이스 라는 상태를 넣었다. 숫자 2번이고, 출력된 DNA 염기 서열에서 8번째 G의 값이 이 스플라이스 상태를 나타낸다. 발산 확률 표에 보이듯이 스플라이스 상태에서 G는 높은 확률로 G의 값을 나타내고 있고, 그 양쪽으로 엑손과 인트론 서열이 나뉘는 것이 가장 이 서열을 잘 설명해준다는 결과로 이해할 수 있다.
댓글