Simplified motif background model provides significant speed-up for regulatory activity inference

Motivation

• Known: miRNA 활성은 target motif가 expression-ranked mRNA 서열에서 클러스터링되는 정도를 통해 비지도 방식으로 추론할 수 있으며, Sylamer, miReact, bayesReact 같은 방법들이 이를 위해 background Markov model 기반 SSP를 사용해 무작위 motif 발생과 실제 조절 신호를 구분해왔다.
• Gap: 기존 Regmex 등 exact Markov background model은 motif(k-mer) 길이가 커질수록 embedded state space와 TPM 차원이 급격히 커져 계산 비용이 기하급수적으로 증가하므로, 대규모 k-mer screen이나 single-cell 규모 적용에는 확장성이 부족하다.
• Why: scRNA-seq 등 대규모·고차원 데이터에서 miRNA 조절 활성을 실시간에 가깝게 추론하려면 SSP 계산의 계산 효율이 핵심 병목이므로, 정확도를 크게 희생하지 않으면서 속도를 획기적으로 높이는 background model은 single-cell 규모의 regulatory profiling 실용화에 중요한 기여이다.
• Approach: 저자들은 motif 발생을 absorbing Markov chain 대신 독립 Bernoulli trial들의 합으로 근사하는 binomial approximation을 도입하고, 이를 단일 사이트 motif 확률(single-site motif probability)과 서열 길이만으로 파라미터화하여 0th-order 및 1st-order(di-nucleotide) background model 모두에 적용했다.

Achievement

Figure 3. 7-mer motif probabilities and distribution. (a) Pearson correlation between SSPs from 0th-order exact Markov m

1. 속도 개선: binomial approximation이 7-mer motif 기준 exact Markov model 대비 50배 이상, 전체 k-mer screen에서는 최소 9배 이상 빠른 계산 속도를 달성했다.
2. 정확도 유지: 근사된 SSP 값이 exact Markov model의 SSP 값과 높은 Pearson 상관관계를 보이며 downstream Bayesian activity inference 결과에 거의 영향을 주지 않음을 확인했다.
3. 1st-order 확장: di-nucleotide 기반 1st-order background model로 확장하여 AT-biased 3' UTR 서열에서 AT-rich 및 GC-rich motif 간 SSP 기대값을 더 잘 구분해냈다.
4. 실데이터 검증: TCGA 간암(liver cancer) 샘플에 적용해 binomial approximation이 실제 miRNA 활성 추정치를 exact model과 유사하게 보존함을 입증했다.

How

Figure 2. Resource consumption of background motif models. (a) Elapsed running times for different k-mer lengths and SSP

• hg38 참조 유전체(GENCODE v32 주석) 기반 human 3' UTR 서열(20~10,000nt, gene당 최장 isoform)을 구축
• TCGA 9,640개 primary tumor 샘플의 paired mRNA/miRNA 발현 데이터를 정규화, log2 변환 후 fold-change(FC) 기반 유전자 순위화(식 1)로 18,559개 3' UTR 서열 확보
• 0th-order 및 1st-order Markov background model의 exact SSP를 absorbing Markov chain(TPM, 식 2-3)으로 계산
• 각 motif의 single-site probability P(m)을 0th-order(식 4, 독립 nucleotide frequency 곱) 또는 1st-order(식 6, di-nucleotide conditional probability) 방식으로 계산
• t = L-k+1개의 독립 Bernoulli trial로 motif start site를 모델링하여 binomial 분포(식 5)로 SSP = P(nm≥1) 근사
• k=4~9의 전체 k-mer set(4^k개 motif)에 대해 exact model과 approximation model의 elapsed time, 메모리 사용량(MaxRSS), SSP 상관관계, downstream Bayesian activity score를 비교

Originality

• SSP 계산을 위한 고차원 embedded Markov chain(TPM 지수 연산) 문제를 독립 Bernoulli trial의 binomial 분포로 재구성하여 O(k) 수준의 계산 복잡도로 낮춘 근사적 접근
• 0th-order뿐 아니라 di-nucleotide 기반 1st-order background model에도 동일한 binomial framework를 확장 적용하여 compositionally biased sequence 보정 개선
• bayesReact 등 기존 Bayesian activity inference framework와 결합 가능하도록 설계하여 실용적 대체재로 제시

Limitation & Further Study

• motif occurrence를 non-overlapping 독립 Bernoulli trial로 가정하는 binomial approximation은 실제로는 겹침(overlap) 및 자기상관을 완전히 반영하지 못해 특정 motif 구조(예: 반복적 서열)에서 편향이 발생할 가능성이 있음
• 검증이 주로 7-mer 및 liver cancer 단일 코호트에 집중되어 있어 다양한 motif 길이, RE 기반 복잡 motif, 다른 암종·조직에 대한 일반화 검증이 부족함
• 1st-order 확장은 di-nucleotide 수준에 그쳐 더 높은 차수의 국소 서열 의존성(2nd-order 이상)에 대한 개선 여지가 남아 있으며, 후속 연구로 고차 Markov 근사나 single-cell 실데이터 적용 검증이 필요함

Evaluation

총평: 계산 효율성과 정확도 간의 균형을 잘 맞춘 실용적인 방법론적 기여로, single-cell 규모의 regulatory activity inference 확장에 실질적인 도움이 될 것으로 보이나 검증 범위의 확장이 필요하다.