Sequence Motif 등장 확률

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

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

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

우연한 기회에 이 문제에 대해 생각해보게 되어 여사건의 확률 등의 방법을 생각해보다 이런 방법으로는 쉽게 풀리지 않는다는걸 알게 되었다.

검색을 해봐도 정확한 해답을 제시하는 사람은 많지 않았다 (너무 쉬운 문제여서 인지?). 여기서는 확률의 inclusion-exclusion principle을 이용한 해답을 소개하려 한다.

 

마주서기 문제

본 문제와 비슷하지만 비교적 단순한 문제를 먼저 살펴보자.

n쌍의 부부가 있다. 한 쪽에는 남편끼리, 다른 쪽에는 부인끼리 늘어 설 때, 적어도 한 쌍의 부부가 서로 마주보고 설 확률은 얼마일까?

이 문제 역시 여사건의 확률을 이용해서 풀기는 쉽지 않다 (재귀함수를 만들게 된다). 대신 inclusion-exclusion principle을 사용해서 풀어보자.

사건 A_i를 “i번째 부부가 서로 마주보고 서는 사건”이라고 하자. 그러면

\begin{array}{lcl} &&P(A_i) = \dfrac{(n-1)!}{n!} \text{, } i=1, ..., n \\ &&P(A_i \cap A_j) = \dfrac{(n-2)!}{n!} \text{, } i < j \\ && ... \\ &&P(A_1 \cap A_2 \cap ... \cap A_n) = \dfrac{1}{n!} \end{array}

이므로

\begin{array}{lcl} P(\cup_{i=1}^{n} A_i) &=& \sum_{i=1}^{n}P(A_i) - \sum_{i<j}P(A_i \cap A_j) \\ & & + ... + (-1)^{n+1}\sum_{i<j<...<l}P(A_i \cap A_j \cap ... \cap A_l) \\ &=& \sum_{i=1}^{n} (-1)^{i+1} \dfrac{1}{i!} \end{array}

이다.

 

본 문제

사건 A_i \text{, } i=1, ..., m를 “i번째 위치에 motif가 등장하는 사건”이라고 하자. 단 mnk로 나눈 몫이다. 그러면

\begin{array}{lcl} &&P(A_i) = \dfrac{4^{n-k}}{4^n} \text{, } i \leq n-(k-1) \\ &&P(A_i \cap A_j) = \dfrac{4^{n-2k}}{4^n} \text{, } i<j \text{ and } i, j \leq n-2(k-1) \\ &&P(A_i \cap A_j \cap A_k) = \dfrac{4^{n-3k}}{4^n} \text{, } i<j<k\text{ and } i, j, k \leq n-3(k-1) \\ &&... \\ &&P(A_1 \cap A_2 \cap ... \cap A_m) = \dfrac{4^{n-mk}}{4^n} \end{array}

이므로 마주서기 문제에서와 같은 방법으로

P(\cup_{i=1}^{m} A_i) = \sum_{i=1}^{m} (-1)^{i+1} \binom{n-i(k-1)}{i} 4^{-ki}

임을 알 수 있다.

 

이 방법으로 1~500 ntd의 random target sequence에 3, 4, 7-mer fixed motif가 존재할 확률을 그래프로 나타내보면 다음과 같다.

Thu Oct 25 00:15:46 2018

 


참고

 

 

4 comments

  1. 유익한 글 감사합니다. combinatorics에서 유명한 derangement[1]의 개수 세는 문제와 똑같군요. :) 저도 maple[2]로 그래프를 한 번 그러볼까 싶었는데, 엄청나게 오래 걸려서 포기했습니다. ㅎㅎㅎ 그런데 제가 문외한이라서 그런데, 이 계산이 실제로 활용되는 경우가 있나요? 아니면 순수하게 수학적인 의문으로 푸신 건가요?

    [1] https://en.wikipedia.org/wiki/Derangement
    [2] https://en.wikipedia.org/wiki/Maple_(software)

    좋아요

    1. 전산생물학 실험실에서 종종 짧은 길이 시퀀스의 등장 가능성을 계산하고 싶을 때가 있습니다. 예를 들어, DNA/RNA를 가지고 하는 몇몇 실험에서 전 과정이 계획대로 진행되었는지 확인할 때, 특정 시퀀스 쿼리가 기대만큼 빈번히 등장하는지 계산해보면 (아주)대강 감을 잡을 수 있습니다. (50nt마다 한 번 꼴로 빈번히 등장해야 할 쿼리가 1000nt를 살펴봐도 나타나지 않는다면 실험 어딘가에 문제가 있었던 것이겠죠)

      그때마다 간단히 k/4^n으로 근사(?)하곤 했는데, 어느날 친구가 “52nt 타겟에서 7nt 쿼리가 한 차례 이상 등장할 정확한 확률”이 궁금하다고 물어왔습니다.

      막상 계산을 해보려니 생각보다는 복잡한 문제였습니다. 정확한 값은 지금껏 써왔던 방법과 얼마나 차이가 나는지 (상당히 과대추정하고 있었더군요), 또 52, 7이 아닌 일반적인 경우에도 적용할 수 있을지 궁금해서 문제를 풀기 시작했습니다.

      그리 유용한 활용사례는 아닌 듯 싶습니다만ㅎㅎ 정확한 값이 필요하지는 않더라도, 이처럼 가끔가다 쿼리 등장 확률을 계산하면 실험 과정을 트러블슈팅할 때 도움될 때가 있습니다. 이렇게까지 정확하게 계산하고 싶었던건 그저 학문적인 오기 때문이었습니다 :)

      좋아요

naturale 에 답글 남기기 응답 취소

댓글을 게시하려면 다음의 방법 중 하나를 사용하여 로그인 하세요:

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중

This site uses Akismet to reduce spam. Learn how your comment data is processed.