Topology Overlap Matrix

Introduction

WGCNA(WeiGhted Correlation Network Analysis) 논문을 보다가 Topology Overlap Matrix의 이해를 돕고자 간단하게 메모하면서 정리하는 글이다. 다음 논문들을 참고하였고, 실제 내용은 [1]의 2.4절을 정리한 것이다. [2], [1]

Measure of Node Dissimilarity

논문에 나온대로 Co-expression network analysis의 목적은 node이 tightly connected이 되었는지 감지하여 clustering하는 것이라고 할 수 있다. [1]. 이를 위해 clustering method와 함께 node dissimilarity measure를 사용한다.

이중에서 Ravasz algorithm을 사용한다 [3]. Ravasz algorithm은 similarity measure을 기준으로 쓰여져있지만, WGCNA에서는 dissimlarity measure를 사용한다. 이는 simliarity measure를 먼저 정의한 다음 이를 반전시키는 방법을 쓰면 된다.

The topological overlap matrix (TOM), \(\Omega = [\omega_{ij}]\) 는 다음과 같이 정의한다.

The Topological Overlap Matrix (TOM) in Ravasz Algorithm

Node simliarity는 어떻게 정의될 수 있을까? 위 식이 어떻게 정의가 되게 되었는지 이해가 안돼서 이 글을 쓰게 되었고, Ravasz algorithm을 찾아보았다 [3].

• 노드의 connectivity가 높다면, 다시말하면 clustering이 이루어진다면 공유하는 이웃 노드(neighbor)들도 많을 것이다.
• 하지만 단순히 neighbor의 개수는 simlarity의 척도가 되지 못한다. normalization을 안했기 때문에 비교하기가 힘들기 때문이다.

• 따라서 노드의 각 페어를 \(i, j\)라 하면, TOM은 neighbor의 개수를 connectivity로 나누어주어야 한다. 이게 Ravasz algorithm에서 정의하는 TOM이다. Ravasz 논문에서의 notation을 그대로 가져다 쓰면 다음과 같이 표현할 수 있다.

  \[\Omega_{ij} = \dfrac{J_{ij}}{\min{\{k_i, k_j\}}}\]

  \(J_{ij}\)는 노드 \(i\)와 \(j\)가 공유하는 neighbor의 개수, \(k_i\) 는 \(i\) 노드에서 다른 노드로의 direct connection의 개수라고 할 수 있다 (node connectivity).

The Topological Overlap Matrix (TOM) in WGCNA

WGCNA에서는 위에서 정의한 TOM을 확장하여 다음과 같이 정의한다.

\[\omega_{ij} = \dfrac{l_{ij} + a_{ij}}{\min{\{k_i,k_j\}}+1-a_{ij}}\]

\(l_{ij}=\sum_u a_{iu} a_{uj}\)이며 \(k_i = \sum_{u} a_{iu}\)는 node connectivity를 나타낸다. \(l_{ij}\)는 Ravasz algorithm에서의 neighbor의 수, 즉 \(J_{ij}\)에 해당함을 알 수 있다. \(a_{ij}\)는 adjacency matrix의 weight이다. shared되는 neighbor수에 weight를 주고싶다면 \(0<a_{ij}<1\)의 값을 주면 되는 것이고, 그렇지 않다면 0 혹은 1을 주면 된다.

Extreme of \(\omega_{ij}\)

unweighted network라고 할 때 \(\omega_{ij}\)의 극단적인 케이스는 논문에 나온 것처럼 다음과 같다.

• \(\omega_{ij}=1\)
  1. 노드 \(i, j\) 중에서 더 적은 노드를 \(i\)라고 할 때 (\(\min{\{k_i,k_j\}}\) 때문), 노드 \(i\)의 모든 이웃 노드는 노드 \(j\)의 이웃이다.
  2. 그리고, \(i\)와 \(j\)는 연결되어있다.
• \(\omega_{ij}=0\)
  • 노드 \(i, j\)는 서로 연결되어 있지 않다.

Range of \(\omega_{ij}\)

\(0 \leq \omega_{ij} \leq 1\)인가? 그렇다.

Proof.

1. \(l_{ij} \leq \min{\{\sum_{u \neq j} a_{iu}, \sum_{u \neq i} a_{uj}\}}\) 이므로, \(l_{ij} \leq \min{\{k_i, k_j\}} - a_{ij}\) 이다. \(l_{ij}\)는 neighbor의 수이므로, 당연히 connectivity보다는 작을 수 밖에 없다.
2. 따라서 \(0 \leq a_{ij} \leq 1\)이므로 \(0 \leq \omega_{ij} \leq 1\)이다. 1.에서 \(\)\(l_{ij} \leq \min{\{k_i, k_j\}} - a_{ij}\)의 양변을 \(\min{\{k_i, k_j\}}\)로 나누면 자명하다.

Dissimilarity measure

결론적으로 심플하게 Similarity measure를 opposite하게 만들면 된다.

\[d_{ij}^\omega = 1 - \omega_{ij}\]

References

1. [1]B. Zhang and S. Horvath, “A general framework for weighted gene co-expression network analysis,” Statistical Applications in Genetics and Molecular Biology, vol. 4, p. Article17, 2005, doi: 10.2202/1544-6115.1128.
2. [2]P. Langfelder and S. Horvath, “WGCNA: an R package for weighted correlation network analysis,” BMC Bioinformatics, vol. 9, no. 1, p. 559, Dec. 2008, doi: 10.1186/1471-2105-9-559.
3. [3]E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, “Hierarchical organization of modularity in metabolic networks,” Science (New York, N.Y.), vol. 297, no. 5586, pp. 1551–1555, Aug. 2002, doi: 10.1126/science.1073374.