모티프(Motif)란 DNA, RNA, Protein 어떤 것의 조각이든, 비교적 반복적으로 나타나는 아주 짧은 서열 조각을 말한다. Regulatory Motif의 특징으로, 작고(tiny), 변화가 심하며(highly variable), 서로 거의 비슷한 크기에(constant size) 아주 빈번하게 나타난다.
이 작은 서열 조각은, 다중 서열 정렬을 하는데 아주 중요한 역할을 한다. 일반적으로, 다중 서열 정렬에 관한 문제는 다이나믹 프로그래밍(Dynamic Programming)을 적용하더라도 매우 어려운 문제로 알려져 있다. 어느 정도의 시간이 필요한지, 이것을 효과적으로 계산할 수 있는 다항시간 내의 알고리즘이 존재하는지 여부조차 알 수 없는, NP 문제에 속한다. 그런데, 모티프를 이용하면 이 문제를 통계학적인 방법에 의해 처리할 수 있다.
예를 들어, 어떤 서열들이 주어졌을 때 서열의 길이를 L이라 하고, 모티프의 길이를 W, 시퀀스의 수를 N이라 하자. 서열의 길이가 30, 모티프의 길이는 7, 주어진 서열의 수는 10이라고 할 때, 이들을 모두 정렬하는 것은 (30 - 7 + 1)^10의 어마어마한 시간복잡도를 필요로 한다. 즉, 일반적인 다이나믹 프로그래밍 기법으로는 시도할 가치조차 없는 문제라고 할 수 있다.
그래서, 통계학적인 방법을 응용한 다중 서열 정렬 방법을 사용하는데, 그 중 하나가 Gibbs Sampling이다. 모티프를 탐색하는 방법으로, 갭(Gap)을 허용하지 않는 부분 정렬(Local Alignment)에 아주 잘 적용된다. 즉, 전체 서열을 탐색하는 대신, 임의로 선택한 위치의, 가장 적절한 모티프를 탐색하는 방법으로 서열 정렬을 하게 된다.
Gibbs Sampling을 적용하는 절차는 다음과 같다.
1. 복수개의 DNA나 Protein 서열이 있어야 하고, 모티프의 길이가 주어져야 하며, 얼마나 많은 모티프가 필요한지 결정해야 한다.
2. 전체 서열에서 모티프를 제외한 Background에서 A, C, G, T(또는 amino acid)의 출현 빈도를 계산해야 한다. 예를 들어, A, C, G, T = {0.350, 0.177, 0.210, 0.233}의 Background 출현 빈도를 가진다고 하자.
3. 각각의 서열에서, 임의로 모티프의 시작 위치를 생성한다. 예를 들어 10개의 시퀀스가 주어졌고, 30 bp, 모티프의 길이는 7이라고 했을 때, { 2, 6, 9, 14, 5, 7, 20, 20, 6, 22 }의 시작 위치를 생성했다고 하자. 이것은 최적의 모티프 시작 위치를 판단하기 위한 것이다. 각각의 위치에서 계산된 모티프의 확률 중 가장 좋은 것이 예전 값을 대체해나가며, 결국 가장 좋은 값이 최적의 모티프 추정 위치가 된다.
4. 전체 시퀀스로부터 하나를 제외한 나머지로부터 PSSM(Position Specific Score Matrix)을 구성한다. PSSM은 이들 나머지의 출현 빈도에 따라 다르게 계산된다.
다음 예를 보자. 만약 5개의 시퀀스가 주어졌고, 모티프의 길이 l은 8이라 했을 때, 시퀀스는 다음과 같다.
Seq 1. GTAAACAATATTTATAGC
Seq 2. AAAATTTACCTTAGAAGG
Seq 3. CCGTACTGTCAAGCGTGG
Seq 4. TGAGTAAACGACGTCCCA
Seq 5. TACTTAACACCCTGTCAA
여기서 3에서 생성한 모티프 시작값으로 각 시퀀스에서 모티프로 추정되는 시퀀스를 잘라낸다. 시작값이 2일 때 모티프 길이는 8이므로, 2번째부터 10번째까지 시퀀스에서의 값이 사용할 모티프 시퀀스가 된다. 여기서 각각의 시퀀스에 대한 시작값은 {s1, s2, s3, s4, s5 | 7, 11, 9, 4, 1}이다.
여기서 하나를 제외한 나머지 시퀀스로만 P를 구성하는데, A, C, G, T에 대해서 이 시퀀스가 나타나는 빈도를 계산한다. 예를 들어, 1, 3, 4, 5 시퀀스에 대해서 처음에 A가 나타나는 빈도는 1 / 4이며, T는 2번 나타났기 때문에 2 / 4, G는 1번, C는 나타나지 않았기 때문에 0이 된다. 이런 식으로 P를 구성한다.
5. 선택한 Seq 2에 대해서 각 위치에서 해당 모티프들이 시작할 확률을 계산한다. Seq 2는 AAAATTTACCTTAGAAGG이며, 각각의 위치에 대해서 계산한 확률은 다음과 같다.
그리고, 의미 있는 값에 대해서 그 비율을 계산하면,
Starting position 1 = 0.000732 / 0.000122 = 6
Starting position 2 = 0.000122 / 0.000122 = 1
Starting position 8 = 0.000183 / 0.000122 = 1.5
대략 6 : 1: 1.5의 비율로 나타나게 되며, 가장 높은 모티프의 시작 위치가 될 확률이 높은 곳은 6 / (6 + 1 + 1.5) = 0.706인 1이 된다. 이제, s2에 대한 시작 위치를 {s1, s2, s3, s4, s5 | 7, 1, 9, 4, 1}로 바꾼다.
6. 그리고 이 과정을 많이 반복하면, 더 이상 변화가 없는, 안정적인 시작 위치로 수렴할 것이다. 시작 위치가 더 이상 변화가 없을 때까지 이 과정을 반복한다. 즉, 모티프의 시작 위치가 어떤 값으로 수렴되었다면, 이 값에 기초하여 다중 서열 정렬에 대한 문제에 접근할 수 있다.
Gibbs Sampling 방법의 단점으로는, 결과가 전역적 최적값에 수렴해야 하지만 지역적 최적값에 수렴할 수 있다는 점이고, 반복되는 서열이 언제나 모티프가 아닐 수도 있다는 점에서 발생하는 오차 정도를 꼽을 수 있다. 이 현상을 수정하려면 Background Model을 수정해야 한다. 또, 각각의 뉴클리오타이드가 같은 확률로 분포되어 있지 않다면, 대단히 복잡해질 수 있다.
