랜덤 워드에서 특정 워드가 등장할 확률

게시일: 유닼님이 작성

zariski님의 블로그의 글에 언급된 naturale님의 글을 읽고.

전체 n ntd로 이루어진 target RNA 한 가닥이 있다고 하자. 이 RNA는 완전히 랜덤하게 만들어진 가닥이라고 가정한다. 즉, 각 위치에 A, U, G, C가 같은 확률로 존재할 수 있다.

이제 k-mer sequence motif가 하나 있다고 하자. 이 sequence motif는 특정되어 있다.

이 때 Target RNA 가닥에서 이 motif가 한 번이라도 등장할 확률은 얼마일까?

즉 알파벳 집합의 크기가 4이고 길이가 n인 랜덤 워드에서 길이가 k인 특정 워드 w가 등장할 확률을 구하는 문제이다.

naturale님의 포함-배제의 원리를 이용한 풀이는 많은 경우 옳지만, 일부 워드의 경우 정확한 확률값과 맞아떨어지지는 않는다. 이 풀이대로라면 처음에 주어지는 워드가 어떻게 주어지더라도 그 확률은 동일하게 나와야 한다. 하지만 n=3, k=2이고 알파벳이 2개로 주어진 경우 (편의상 a,b라 한다) 랜덤워드는 aaa,aab,aba,abb,baa,bab,bba,bbb에서 균일하게 뽑혀야 하고, aa가 등장할 확률은 3/8이 되지만 ab가 등장할 확률은 1/2가 된다.

이것은 i번째 위치에서 w가 나타날 사건을 A_i라 할 때, Pr(A_i \vee A_j)가 항상 \frac{1}{4^{2k}} \binom{n-2k+2}{2}로 나오지 않기 때문이다. 이 식은 i번째와 j번째 위치에서 동시에 w가 나타나지 않는다는 것을 가정했지만, 만약 w의 맨 처음 subword가 맨 마지막에도 다시 등장한다면 겹쳐서 나타나는 것이 가능하고, Pr(A_i \vee A_j)의 값은 조금 더 복잡하게 표현되어야 한다. (앞의 예시에서 aa가 이 복잡해지는 경우에 해당한다.) 마찬가지로 Pr(A_i \vee A_j \vee A_k) 등 나머지 항들도 겹쳐지는 경우를 고려하면 복잡하게 바뀐다.

그래서 일반적인 경우를 따지기 위해서는 다른 방법론이 좋은데, 여기서는 Markov chain을 이용하는 것을 설명하고자 한다. (기본적으로 naturale님이 말미에 언급한 DFA(deterministic finite automata) 모델과 대동소이) 쉽게 표현하자면 유한개의 state들을 잡고 한 state에서 다른 state으로 가는 확률을 지정하는 모델을 뜻한다. 원래 문제처럼 알파벳 집합이 A, U, G, C로 주어져 있고, 여기서 길이 3인 워드 AUG가 등장할 확률을 구하는 것을 생각해본다.

이제 비어있는 워드 \emptyset에서 1/4의 확률로 letter가 하나씩 붙어 n회 뒤에 길이 n의 랜덤 워드가 생긴다고 생각한다. 이 때 고려할 state는 다음과 같은 4가지이다.

  • State 1: 현재 완성되어있는 워드가 A로 끝난다.
  • State 2: 현재 완성되어있는 워드가 AU로 끝난다.
  • State 3: AUG를 찾았다. (PROFIT!)
  • State 0: 이도저도 아니다.

여기서 초기 워드 \emptyset은 State 0에 해당된다고 본다. 그러면 각각의 state에서 letter 하나가 더 붙으면 다음과 같이 다음 state으로 이동한다.

  • State 0에서 다음에 올 값이 A이면 State 1으로 가고,(확률 1/4) 아니면 계속 State 0에 머문다.(확률 3/4)
  • State 1에서 다음에 올 값이 A이면 머무르고,(확률 1/4) U이면 State 2로 가고,(확률 1/4) 둘 다 아니면 State 0로 간다.(확률 1/2)
  • State 2에서 다음에 올 값이 A이면 State 1으로 가고,(확률 1/4) G이면 State 3로 가고,(확률 1/4) 둘 다 아니면 State 0로 간다.(확률 1/2)
  • State 3에서는 무조건 다시 State 3로 간다.(확률 1)

이 확률들을 행렬로 표현해, State i에서 State j로 가는 확률을 i행 j열에 배치한 행렬 T를 잡는다.(transition matrix) 이 예시의 경우는

\displaystyle T = \begin{bmatrix}3/4 & 1/4 & 0 & 0 \\ 1/2 & 1/4 & 1/4 & 0 \\ 1/2 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 1\end{bmatrix}

가 된다. 이 transition matrix가 왜 유용하냐면, T^n의 i행 j열 원소가 바로 State i에서 n번의 턴을 거쳐 State j로 갈 확률과 같아지기 때문이다. (행렬의 곱의 정의로 바로 증명된다) 따라서 원래 문제로 돌아가면 처음 State 0의 \emptyset에서 시작해 n 턴 이후 State 3에 도착할 확률을 구해야 하므로, T^n_{0,3}을 구하면 된다. (편의상 행렬의 index를 0,1,2,3으로 둘 경우)

AUG는 앞서 언급한 “복잡하지 않은” 경우에 해당되며, 그렇지 않은 경우라면 transition matrix는 조금 다르게 나타난다. (state 개수는 똑같이 4개로 구현할 수 있다) 예컨대 만약 w가 AUA였다면

\displaystyle T = \begin{bmatrix}3/4 & 1/4 & 0 & 0 \\ 1/2 & 1/4 & 1/4 & 0 \\ 3/4 & 0 & 0 & 1/4 \\ 0 & 0 & 0 & 1\end{bmatrix}

이 된다.

그래서 구하고자 하는 확률은 k+1 \times k+1 행렬의 거듭제곱의 (0,k)-entry를 구하는 문제로 reduce되고, 이는 계산만을 원하면 Matlab 등으로 쉽게 구할 수 있다. 만약 정확한 식을 구하고 싶다면, 해당 transition matrix의 Jordan normal form을 구한 후 식을 얻을 수 있게 된다. 참고로 이 행렬의 eigenvalue가 \lambda_1^{m_1},\ldots,\lambda_l^{m_l}이라 하면 (m_i는 multiplicity) 원하는 값은 반드시 \lambda_1^n P_1(n)+\cdots+\lambda_l^n P_l(n) 꼴이 되어야 한다. (P_i는 차수가 m_i보다 작은 다항식) 또한 이 transition matrix는 반드시 eigenvalue 1을 갖고(각 행마다 원소의 합이 1) 부가적으로 Perron-Frobenius theorem에 의해 모든 eigenvalue의 절대값이 1 이하임을 보일 수 있다. 그런데 생각해보면 n \rightarrow \infty일 때 확률은 1로 수렴하므로 결국 1^n의 항에 곱해질 다항식은 상수함수 1인 것까지 확인할 수 있다.

Wolfram Alpha의 계산에 의하면 AUG 케이스의 transition matrix의 특성방정식은 (\lambda-1)(\lambda^3-\lambda^2+\frac{1}{64})가 되며, n=10에서 AUG, AUA가 등장할 확률은 각각 12.14%와 11.59%, n=100에서 AUG AUA가 등장할 확률은 각각 79.69%와 77.59%라고 한다.

“랜덤 워드에서 특정 워드가 등장할 확률”의 6개의 생각

    1. 넵, 마지막 문단에 AUA의 케이스를 추가했는데 조금 차이가 나타나게 됩니다. 더불어 부가적으로, 각 state에 해당하는 길이 m의 중간 워드의 개수를 각각 수열로 정의하여 정리하면 연립 선형 점화식이 되고 이를 정리해서 State 3에 대한 수열로만 표현할 수 있는 선형 점화식 꼴로 바꾸는 것도 가능하며 그 때도 같은 특성 방정식을 얻게 됩니다.

      좋아요

      응답
  2. 핑백: 랜덤 워드에서 특정 워드가 등장할 확률 (2) – udaqueness
  3. 핑백: 랜덤 워드에서 특정 워드가 등장할 확률 (3) – udaqueness
  4. 핑백: Sequence Motif 등장 확률 | De novo

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

Gravatar
WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. ( 로그아웃 /  변경 )

취소

%s에 연결하는 중