Hidden Markov Model(HMM)를 응용하면 유전자의 서열을 정렬하는 문제에도 적용할 수 있다. 서열을 정렬하는 문제에 HMM을 적용하기 위해서는 여기에 맞는 모델(Model)을 정의해야 하는데, 모델을 정의하기 위해서는 특정 상태에서 심벌(symbol)을 방출할 확률, 상태 사이의 변환 확률을 알고 있어야 한다. 그리고, 여기서도 기존의 서열 정렬에 사용되었던 다이나믹 프로그래밍(Dynamic Programming)이 적용될 수 있다.
즉, 2개의 서열을 정렬한다면, 가장 가능성이 높은 정렬 상태를 찾아야 하며, 이것은 HMM 문제로 변환할 수 있다. 예를 들어 어떤 유전자 서열 _ATTGTA_GC라는 것과 TAATGTAACC가 주어졌다고 했을 때, 이것을 어떻게 표현할 수 있을까? 간단하게 세가지 상태를 정의할 수 있는데 두 유전자가 일치할 경우, 첫 번째 유전자 서열이 갭(Gap)으로 표시될 경우, 두 번째 유전자 서열이 갭으로 표시될 경우를 생각해 볼 수 있다. 각각의 경우를 뜻하는 상태를 차례대로 M, I, J라고 해보자. 그렇다면, 두 유전자의 정렬 상태를 다음과 같이 표시할 수 있다.
_A_TTGTA_GC
TAAT_GTAA_C
IMIMJMMMIJM
이렇게 각각의 상태를 정의할 수 있고, 이런 시퀀스를 얻을 수 있으며, 상태들의 변환 확률을 알 수 있다면 이것은 HMM Decoding Problem으로 바뀌게 되고, 가장 최선의 확률을 계산하는 문제가 된다. 여기서 다이나믹 프로그래밍 기법이 사용될 수 있다. 즉, 이 방법으로 두 서열이 비슷한 정도를 알아볼 수 있으며, 진화상 서로가 얼마나 연관성이 있는지 짐작할 수 있으며, 유전자를 찾는 문제나, 어떤 유전자가 어느 계열(Family)에 속하는지를 알아낼 때 유용하게 사용할 수 있다.
일반적으로 classification에 맞는 문제라면 HMM을 적용한 방법은 좋은 결과를 보여준다. 유전자 서열에서 순서가 명확하고, 순서가 중요하다면 이것 또한 HMM을 적용하기 좋다. 또, 관찰되는 시퀀스에서 문법 구조 비슷한 것이 발견될 수 있다면 이것도 HMM을 적용하기 좋은 문제이다. 모델을 정의하기 쉬워지기 때문이다. 그러나 HMM은 모든 문제에 잘 적용될 수 있는 도깨비 방망이가 아니며, 어떤 문제에 HMM을 적용하기 위해서는 다음과 같은 부분을 검증해봐야 한다.
1. 구조적인지,
2. 검증이 쉽게 이루어질 수 있는지,
3. 트레이닝 데이터(Traning Data)가 필요하며,
4. 트레이닝 데이터가 얼마만큼 필요한지
여부를 검토해봐야 한다. 첫 번째 구조적인 문제는, 설계한 모델에서 필요로 하는 인자의 갯수가 어느 정도인가에 달려 있다. 만약 유전자 서열 데이터와 같은 것을 다룬다면, 서열 길이가 길어지면 서열 갯수가 조금 필요하고, 서열 길이가 짧아진다면 필요한 서열 갯수는 늘어나게 된다.
결론적으로, HMM은 다음과 같은 장점과 단점이 존재한다.
HMM은 더 큰 HMM과 조합해서 쓸 수 있고, 이미 알려진 사실이 있다면 이 사실을 HMM에 통합해서 적용하기 쉽다. 이것은 HMM의 장점이다. 그러나, HMM의 각 사건은 바로 전 단계에서만 영향을 받는다는 것, 그리고 구조적으로 지역적인 최적값에 수렴하기 쉽다는 것, 가지고 있는 트레이닝 데이터에 너무 딱 맞게 나타날 수 있다는 점이 단점으로 꼽힌다. 사실, 마지막 문제는 기계 학습에 일반적으로 나타나는 문제이다.
그리고, 다른 모델과 비교해봤을 때 모든 가능성을 계산하기 때문에, 상대적으로 느린 속도를 보인다.
즉, 2개의 서열을 정렬한다면, 가장 가능성이 높은 정렬 상태를 찾아야 하며, 이것은 HMM 문제로 변환할 수 있다. 예를 들어 어떤 유전자 서열 _ATTGTA_GC라는 것과 TAATGTAACC가 주어졌다고 했을 때, 이것을 어떻게 표현할 수 있을까? 간단하게 세가지 상태를 정의할 수 있는데 두 유전자가 일치할 경우, 첫 번째 유전자 서열이 갭(Gap)으로 표시될 경우, 두 번째 유전자 서열이 갭으로 표시될 경우를 생각해 볼 수 있다. 각각의 경우를 뜻하는 상태를 차례대로 M, I, J라고 해보자. 그렇다면, 두 유전자의 정렬 상태를 다음과 같이 표시할 수 있다.
_A_TTGTA_GC
TAAT_GTAA_C
IMIMJMMMIJM
이렇게 각각의 상태를 정의할 수 있고, 이런 시퀀스를 얻을 수 있으며, 상태들의 변환 확률을 알 수 있다면 이것은 HMM Decoding Problem으로 바뀌게 되고, 가장 최선의 확률을 계산하는 문제가 된다. 여기서 다이나믹 프로그래밍 기법이 사용될 수 있다. 즉, 이 방법으로 두 서열이 비슷한 정도를 알아볼 수 있으며, 진화상 서로가 얼마나 연관성이 있는지 짐작할 수 있으며, 유전자를 찾는 문제나, 어떤 유전자가 어느 계열(Family)에 속하는지를 알아낼 때 유용하게 사용할 수 있다.
일반적으로 classification에 맞는 문제라면 HMM을 적용한 방법은 좋은 결과를 보여준다. 유전자 서열에서 순서가 명확하고, 순서가 중요하다면 이것 또한 HMM을 적용하기 좋다. 또, 관찰되는 시퀀스에서 문법 구조 비슷한 것이 발견될 수 있다면 이것도 HMM을 적용하기 좋은 문제이다. 모델을 정의하기 쉬워지기 때문이다. 그러나 HMM은 모든 문제에 잘 적용될 수 있는 도깨비 방망이가 아니며, 어떤 문제에 HMM을 적용하기 위해서는 다음과 같은 부분을 검증해봐야 한다.
1. 구조적인지,
2. 검증이 쉽게 이루어질 수 있는지,
3. 트레이닝 데이터(Traning Data)가 필요하며,
4. 트레이닝 데이터가 얼마만큼 필요한지
여부를 검토해봐야 한다. 첫 번째 구조적인 문제는, 설계한 모델에서 필요로 하는 인자의 갯수가 어느 정도인가에 달려 있다. 만약 유전자 서열 데이터와 같은 것을 다룬다면, 서열 길이가 길어지면 서열 갯수가 조금 필요하고, 서열 길이가 짧아진다면 필요한 서열 갯수는 늘어나게 된다.
결론적으로, HMM은 다음과 같은 장점과 단점이 존재한다.
HMM은 더 큰 HMM과 조합해서 쓸 수 있고, 이미 알려진 사실이 있다면 이 사실을 HMM에 통합해서 적용하기 쉽다. 이것은 HMM의 장점이다. 그러나, HMM의 각 사건은 바로 전 단계에서만 영향을 받는다는 것, 그리고 구조적으로 지역적인 최적값에 수렴하기 쉽다는 것, 가지고 있는 트레이닝 데이터에 너무 딱 맞게 나타날 수 있다는 점이 단점으로 꼽힌다. 사실, 마지막 문제는 기계 학습에 일반적으로 나타나는 문제이다.
그리고, 다른 모델과 비교해봤을 때 모든 가능성을 계산하기 때문에, 상대적으로 느린 속도를 보인다.
