히든 마코프 모델

히든마코프모델(Hidden Markov Model)은 우리가 모델링(모사)하려는 시스템이 마코프체인 과정에 속하는데,
그 변수가 숨어있어서 모르는 경우를 통계적으로 모델링한 것을 말한다.
여기서 핵심 문제는 우리가 관찰할 수있는 변수들로부터 숨어있는 변수들을
잘 계산(유추)해내는 것이다. 그렇게 찾아낸 숨어있는 변수를 잘 이용하면,
그것을 사용하여, 패턴인식등에 사용할수 있다. 히든 마코프모델은 아주
간단한 베이지안 네트워크의 하나라고 생각할 수 있다.

일반적 마코프과정의 모델에서는 상태(state)는 계측이 된다. 그래서, 그 상태에서
다음 상태로 변화하는 확률만 계산하면 된다. 히든마코프모델에서는, 이름에서도
알수 있듯이, 상태(state)가 직접적으로 계측이 안된다. 다만, 그런 숨어있는 변수들에
의해 영향을 받은 상태만 계측이 된다. 그래서, 각각의 계측 가능한 상태들은 타나날
수 있는 결과들의 확률분포로 표시될수 있다. 그래서, 히든마코프모델에 의해서
생겨난 결과물(token)의 줄(서열)은 우리가 계측하고자 하는 상태들의 서열에
대한 정보를 간접적으로 준다. 그래서, 히든 마코프모델은 특히 시간과 관계된
문제들에 많이 적용된다. 필체분석, 음성분석, 몸동작분석, 음악분석,
생정보학서열분석등에 많이 쓰인다.

위의 히든마코프모델 그림에서 X는 우리가 볼수 없는 숨어있는 상태들이다.
이 상태들이 어떤 숨어있는 기작으로 Y라는 관찰가정한 결과를 낸다. 예를 들면,
단백질 서열의 아미노산들이다. 우리는 관찰된 아미노산들(Y)들을 보고, X1 에서 X2, X3,
숨어있는 상태들이 다음에 올 아미노산의 확률을 추측해낸다. 이것을 일종의 기계로
생각을 하면, X로 표현되는 기계들이 아미노산을 내뱉는데, 그 기계들이 어떤
수학공식을 가지고 내뱉는지는 아무도 모른다. 그리고, 아미노산을 내뱉을때,
현 상태와 똑같은 것을 낼수 도 있고, 20개의 아미노산중에서 다른 것을 내뱉을
수도 있다. 첫번째 아미노산이 M 이었을때, 특정한 기계시스템에서,
그 다음으로 M이 나올 확률은 많은 수의 단백질 서열의 Y값들을 보면 확률적으로
계산을 할수가 있다. 이렇게 표를 만들어 나가면, 원래 X 상태들이 결국 한 단백질
군에서는 어떤 아미노산을 뱉어내는지 모델 혹은 프로파일을 만들수가 있다.
그래서, 위의 그림에서 a 는 X의 상태에서 다음 상태로 넘어가는 확률을 나타내고,
b는 어떤 결과물이 나올지의 확률이다. 그러므로, 각각의
단배질가족(protein family)에 하나씩의 히든마코프모델을 수학적으로 만들어 낸다.

히든마코프모델의 생정보학 응용 (Hidden Markov Models in Bioinformatics)
히든 마코프 모델은 특히 음성인식 분야에 널리 쓰였다. 케임브리지대의 유명한
물리학자 스티브 호킹박사와 같은 장애인도 이러한 음성인식 및 재생기술을
이용하여 말을 하거나 들을 수 가 있다. 컴퓨터가 책을 읽어주는 것도,
히든마코프 모델이나 신경망 회로를 사용한다. 1980-90년대, 영국 케임브리지의 공학부는
세계최고의 히든마코프모델 기술과 전산 라이브러리를 가지고 있었는데,
우연히도, 1990년 중반에 케임브리지의 MRC에 유학하든 숀 에디(Sean Eddy)는
미국의 데이비드 하우슬러그룹, 덴마크의 안더스 크로 등과 함께,
매우 쓸모 있는 히든마코프 모델 프로그램을 C 언어로 만들어 낸다.
최초의 생물학적 응용은 이미 그 이전에 있었으나, 실용적으로 많이
히든마코프모델이 생정보학에서 쓰이게 된 계기는 케임브리지의 MRC의
숀 에디의 프로그램을 활용한 팀 허버드와 박종화가 1995년 최초의 단백질
구조 예측 대회에 참여하여 서열기반 상동체(Homolog)를 가장 많이 찾아내는
결과를 내었기 때문이다. 그 이후, 숀 에디의 프로그램인 HMMER는 Pfam과
같은 오늘날 많이 쓰이는 데이타베이스를 만드는데 쓰인다.

히든마코프모델을 이용한 단백질 상동체 검색 (Protein homolog detection using Hidden Markov Model)
히든마코프모델은 이미 알려진 상태인 단백질 서열들로부터, 그 속에
숨겨진 진화적 상동성의 확률을 계산해 놓고 일종의 표를 만든다.
이런 표를 흔히들 프로파일(profile)이라고 한다. 이런 프로파일을
얼마나 정확히 만드는가에 따라서, 그 프로파일을 이용한 서열 검색의
정확도가 결정된다. 예를 들면, 독자가 80세가 되기 전에 걸리게 될 위장암에
결정적인 역할을 하는 CAG1 이라는 단백질이 있다고 하자.
이 단백질은 원숭이에게도 있고, 쥐에도 있고, 지렁이에게도 있다.
그런데, 파리, 낙타, 물고기, 새, 박테리아에게도 이 단백질이 있는지
없는지 궁금할 경우, 이미 알려진 사람, 쥐에 있는 CAG1 유전자의
서열을 바탕으로, 히든마코프모델을 만든다. 그다음 그 모델을 파리,
낙타, 물고기의 모든 단백질 서열들과 하나씩 비교를 해나가면,
상동성이 있는 CAG1 상동체가 찾아지게 된다. 이 과정에서 핵심은
기존의 상동체(homolog)들을 잘 모아서 서열정렬을 하여, 숨어있는
정보까지 잘 표현한 모델 혹은 프로파일을 만드는 것이다.
잘 만들어진 프로파일은 진화적 거리가 먼 박테이아에서도, 사람 몸에서
같은 조상을 가지거나, 같은 기능을 하는 단백질을 찾아낼수 있다.

히든마코프모델을 이용한 단백질 데이타베이스 구축(Protein database construction using Hidden Markov Model)
히든마코프모델을 많이 만들어 놓으면, 좋은 점이 많다. 그중의 하나가,
새로운 단백질 찾기이다. 사람의 몸속의 3 만개이상의 모든 단백질을
위해서 만들어 놓으면, 새로운 단백질 서열이 알려졌을때, 3만개의
이미 알려진 것들과 비교해 보면, 어떤 것들과 상동성이 있는지 금방
알게 된다. 그래서, 어떤 사람들은 이런 히든마코프모델들을
데이타베이스로 구축한다. 대표적인 것이 영국 케임브리지의
생어연구소의 Pfam이다. Pfam 만드는 사람들은 히든마코프모델뿐만
아니라, 그것을 이용했을때, 찾아지는 다른 생물종의 단백질도 저장을 한다.
그래서, 모든 생명체의 단백질 서열들이 서로 서로 어떤 친족성(상동성)이
있는지를 계속 분석해간다. 히든마코프모델 참고문헌 (References for hidden markov models)

What is a hidden Markov model? Sean R Eddy, Nature Biotechnology 22, 1315 - 1316 (2004), doi:10.1038/nbt1004-1315
Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.
Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1999. ISBN 0-521-62971-3
Lior Pachter and Bernd Sturmfels. "Algebraic Statistics for Computational Biology". Cambridge University Press, 2005. ISBN 0-521-85700-7
Olivier Cappé, Eric Moulines, Tobias Rydén. Inference in Hidden Markov Models, Springer, 2005. ISBN 0-387-40264-0
Kristie Seymore, Andrew McCallum, and Roni Rosenfeld. Learning Hidden Markov Model Structure for Information Extraction. AAAI 99 Workshop on Machine Learning for Information Extraction, 1999 (also at CiteSeer: Tutorial from University of Leeds[2.
J. Li, A. Najmi, R. M. Gray, Image classification by a two dimensional hidden Markov model, IEEE Transactions on Signal Processing, 48(2):517-33, February 2000.
Y. Ephraim and N. Merhav, Hidden Markov processes, IEEE Trans. Inform. Theory, vol. 48, pp. 1518-1569, June 2002.
B. Pardo and W. Birmingham. Modeling Form for On-line Following of Musical Performances. AAAI-05 Proc., July 2005.
http://citeseer.ist.psu.edu/starner95visual.html
L.Satish and B.I.Gururaj.Use of hidden Markov models for partial discharge pattern classification.IEEE Transactions on Dielectrics and Electrical Insulation, Apr 1993.