본문 바로가기
연구관련/Bioinfo류

dense subgraph 찾기 구현 (MCODE)

by adnoctum 2010. 12. 3.

 

   지난 번 글에서 언급했던 알고리즘을 C++로 직접 구현해 보자. 실제로 사용한 예는 다음과 같다.


원래의 network 은 다음과 같다. 우리는 다음과 같은 network 에서 dense 한 sub-graph 즉, edge가 많이 연결된 sub-graph를 뽑아 내어야 한다.

원래의 network.


source network 의 sif 파일은 다음과 같다.


위에서 dense한 subgraph 를 지금 설명할 코드로 뽑아 내면 다음과 같다. 


아래의 코드로 찾아낸 cluster1 번.

아래의 코드로 찾아낸 cluster2 번.

아래의 코드로 찾아낸 cluster36 번.


node 를 score로 정렬한 이후 seed로 사용되는데, 높은 점수를 갖는 노드부터 sub-graph (난 계속 cluster 라는 이름을 사용했다. 이 글 이후에도 sub-graph 나 cluster를 사용한다)를 찾기 때문에 cluster 번호가 커질수록 cluster의 density 가 낮아 지는 양상을 보여야 한다. 위의 그림에서 보면 이런 패턴이 보이는 것을 알 수 있다. 위의 그래프는 Cytoscape 으로 그린 것이다. MCODE 를 이용하여 위에서 source 로 사용한 네트워크에서 dense 한 cluster를 찾아 보면 default parameter를 사용할 경우 7 개가 찾아 진다. 이것은 각 sub-graph 간에 node 가 절대 겹치지 않게 구하기 때문이다. 즉, MCODE는 disjoint dense sub-graph 를 찾게 된다. 나는 바로 이 disjoint 라는 조건을 버리고, 각 cluster 간에 노드가 중복되도록 해야 했기 때문에 결국 직접 구현하게 되었다.


  전체적인 구조는 다음과 같다.


 

find_complexes 함수가 main 함수이다. 일단 각 node를 scoring 을 한 후, 이 점수를 기준으로 dense 한 지역을 찾게 된다. scoring 을 할 때 k-core 를 이용하는데, 우선 k-core 가 되는 k에 대하여 가장 큰 k 를 찾아야 한다. 이 때, 원 논문에서는 별 말이 없는데, 우리는 k 의 최대값이 node 의 수가 되고, 최소값이 3이라는 것을 알고 있으므로 binary search 를 할 수 있게 된다. 따라서 아래의 코드에서 find_highest_core_k_density 함수에서는 binary search 를 하고 있다. 이제 각 함수를 상위 레벨에서 살펴 보자.

 

find_complexes

find_complex

score_node

find_highest_core_k_density

find_k_core_density



이제 실제 코드를 보자.

find_complexes

위 코드는 역시나 직관적이다[각주:1]. 위의 pseudo code 와 비교해 가면서 코드를 보면 별로 무리없이 이해할 수 있다.

find_complex

score_node

실제로 부여되는 score는 the highest k-core 에서의 k 와 그 k-core의 density 인 d 를 곱한 값으로 부여하고 있음을 알 수 있다.

find_highest_core_k_density

최대 k-core 를 찾는 것은 원래 O(N3) 이지만 위처럼 하면 그나마 O(N2logN) 으로 줄일 수 있기는 하다.

find_k_core_density


이제, 실제로 위의 routine 들을 이용하여 dense한 sub-graph 를 뽑아 내는 루틴을 살펴 보자.

조금 복잡할 수 있는데, 위 실행 파일이 입력으로 받는 파일은 다음과 같은 구조를 갖고 있다.

EDGE    06436:EDD1    07443:AZIN1    0.996634    0.999722    0.98847    0.999654   
EDGE    00549:EGR1    01270:FOSB    0.999896    0.999962    0.99939    0.999643   
EDGE    01473:PROS1    03443:MEIS2    0.997933    0.99907    0.963672    0.908679
EDGE    00549:EGR1    03881:EGR3    0.996599    0.999486    0.999541    0.998022
...

예제 파일은 다음에 있다.

각 line 은 edge 정보를 갖고 있다. 두 번째 column 과 세 번째 column 이 각각의 node 이고, 그 두의 숫자는 어떤 계산된 값[각주:2]인데 일단 무시하자. 위에서 load_graph 는 위의 edge_file.txt 파일을 읽어서 bool ** 형태의 adjacency matrix 를 채우게 된다. 단, 이 때 위처럼 입력 파일이 text 로 되어 있기 때문에 이것을 숫자로 바꾸는 작업을 하게 된다. 내부적으로 모든 계산은 숫자로 하게 되고, 출력을 할 때만 다시 그 숫자에서 위의 문자열들을 뽑아 내는 형태로 되어 있다. 위의 모든 내용을 담은 cpp 파일은 다음에 있다.

컴파일은 간단하다. 필요한 부분을 저 파일에 모두 몰아 넣었기 때문에 간단히 다음과 같이 컴파일 하면 된다.
[adnoctum@bioism dense_graph]$ g++ dense_graph2.cpp -o dense_graph2
[adnoctum@bioism dense_graph]$

dense_graph2.cpp 파일의 95 번째 줄부터가 실제로 위에 필요한 내용들이다[각주:3]. 위처럼 하고, 다음과 같이 실행시키면 각 cluster 가 sif 파일로 저장이 된고, edge_file.txt.cluster.txt 에는 각 cluster 의 정보들이 들어가 있게 된다. 다음과 같다.

[adnoctum@bioism dense_graph]$ ll
total 380
-rwxrwxr-x 1 adnoctum adnoctum 126101 Dec  3 19:54 dense_graph2
-rw-rw-r-- 1 adnoctum adnoctum  11516 Dec  3 19:19 dense_graph2.cpp
-rw-rw-r-- 1 adnoctum adnoctum  33507 Dec  3 19:33 edge_file.sif
-rw-rw-r-- 1 adnoctum adnoctum 201552 Dec  3 19:10 edge_file.txt
[adnoctum@bioism dense_graph]$ ./dense_graph2 edge_file.txt
edge_file.txt   138     1256
[adnoctum@bioism dense_graph]$ ll
total 560
-rwxrwxr-x 1 adnoctum adnoctum 126101 Dec  3 19:54 dense_graph2
-rw-rw-r-- 1 adnoctum adnoctum  11516 Dec  3 19:19 dense_graph2.cpp
-rw-rw-r-- 1 adnoctum adnoctum  33507 Dec  3 19:33 edge_file.sif
-rw-rw-r-- 1 adnoctum adnoctum 201552 Dec  3 19:10 edge_file.txt
-rw-rw-r-- 1 adnoctum adnoctum   1469 Dec  3 19:57 edge_file.txt_Cluster10.sif
-rw-rw-r-- 1 adnoctum adnoctum   1279 Dec  3 19:57 edge_file.txt_Cluster11.sif
-rw-rw-r-- 1 adnoctum adnoctum   3263 Dec  3 19:57 edge_file.txt_Cluster12.sif
-rw-rw-r-- 1 adnoctum adnoctum   3515 Dec  3 19:57 edge_file.txt_Cluster13.sif
-rw-rw-r-- 1 adnoctum adnoctum   4793 Dec  3 19:57 edge_file.txt_Cluster14.sif
-rw-rw-r-- 1 adnoctum adnoctum   3594 Dec  3 19:57 edge_file.txt_Cluster15.sif
-rw-rw-r-- 1 adnoctum adnoctum   1337 Dec  3 19:57 edge_file.txt_Cluster16.sif
-rw-rw-r-- 1 adnoctum adnoctum   1176 Dec  3 19:57 edge_file.txt_Cluster17.sif
-rw-rw-r-- 1 adnoctum adnoctum   5156 Dec  3 19:57 edge_file.txt_Cluster18.sif
-rw-rw-r-- 1 adnoctum adnoctum    847 Dec  3 19:57 edge_file.txt_Cluster19.sif
-rw-rw-r-- 1 adnoctum adnoctum   4429 Dec  3 19:57 edge_file.txt_Cluster1.sif
-rw-rw-r-- 1 adnoctum adnoctum   3536 Dec  3 19:57 edge_file.txt_Cluster20.sif
-rw-rw-r-- 1 adnoctum adnoctum   7499 Dec  3 19:57 edge_file.txt_Cluster21.sif
-rw-rw-r-- 1 adnoctum adnoctum   1482 Dec  3 19:57 edge_file.txt_Cluster22.sif
-rw-rw-r-- 1 adnoctum adnoctum   4018 Dec  3 19:57 edge_file.txt_Cluster23.sif
-rw-rw-r-- 1 adnoctum adnoctum   1201 Dec  3 19:57 edge_file.txt_Cluster24.sif
-rw-rw-r-- 1 adnoctum adnoctum   1865 Dec  3 19:57 edge_file.txt_Cluster25.sif
-rw-rw-r-- 1 adnoctum adnoctum   1259 Dec  3 19:57 edge_file.txt_Cluster26.sif
-rw-rw-r-- 1 adnoctum adnoctum   1588 Dec  3 19:57 edge_file.txt_Cluster27.sif
-rw-rw-r-- 1 adnoctum adnoctum   1469 Dec  3 19:57 edge_file.txt_Cluster28.sif
-rw-rw-r-- 1 adnoctum adnoctum    594 Dec  3 19:57 edge_file.txt_Cluster29.sif
-rw-rw-r-- 1 adnoctum adnoctum   2103 Dec  3 19:57 edge_file.txt_Cluster2.sif
-rw-rw-r-- 1 adnoctum adnoctum    894 Dec  3 19:57 edge_file.txt_Cluster30.sif
-rw-rw-r-- 1 adnoctum adnoctum   2833 Dec  3 19:57 edge_file.txt_Cluster31.sif
-rw-rw-r-- 1 adnoctum adnoctum    790 Dec  3 19:57 edge_file.txt_Cluster32.sif
-rw-rw-r-- 1 adnoctum adnoctum    864 Dec  3 19:57 edge_file.txt_Cluster33.sif
-rw-rw-r-- 1 adnoctum adnoctum   1137 Dec  3 19:57 edge_file.txt_Cluster34.sif
-rw-rw-r-- 1 adnoctum adnoctum    664 Dec  3 19:57 edge_file.txt_Cluster35.sif
-rw-rw-r-- 1 adnoctum adnoctum    536 Dec  3 19:57 edge_file.txt_Cluster36.sif
-rw-rw-r-- 1 adnoctum adnoctum   2323 Dec  3 19:57 edge_file.txt_Cluster3.sif
-rw-rw-r-- 1 adnoctum adnoctum   3126 Dec  3 19:57 edge_file.txt_Cluster4.sif
-rw-rw-r-- 1 adnoctum adnoctum   6002 Dec  3 19:57 edge_file.txt_Cluster5.sif
-rw-rw-r-- 1 adnoctum adnoctum   3263 Dec  3 19:57 edge_file.txt_Cluster6.sif
-rw-rw-r-- 1 adnoctum adnoctum   1196 Dec  3 19:57 edge_file.txt_Cluster7.sif
-rw-rw-r-- 1 adnoctum adnoctum   1518 Dec  3 19:57 edge_file.txt_Cluster8.sif
-rw-rw-r-- 1 adnoctum adnoctum   7844 Dec  3 19:57 edge_file.txt_Cluster9.sif
-rw-rw-r-- 1 adnoctum adnoctum   8773 Dec  3 19:57 edge_file.txt.cluster.txt
[adnoctum@bioism dense_graph]$

standard out 으로 출력된 위의 붉은 글씨는, 입력 파일과 node 수, edge의 수이다. 그냥 보려고 출력했다.



아... 써 놓고 보니 조금 복잡해 보인다. 아마도 pseudo code 과 직접적으로 비교해 보면 실제 코드의 이해가 어느 정도 수월하리라 생각한다. 나는 될 수 있으면 직관적으로 코딩하려 하기 때문에... 만약 위의 실제 코드 내용 중 난해한 부분에 대한 지적이 있으면 좀 더 자세한 설명을 추가한다.




  1. 나는 어지간히 시간을 잡아 먹는 코드가 아닌 경우에는 위처럼 매우 직관적으로 코드를 짠다. 다소 비효율적으로 보이는 것 같은 것을 알고 있는 경우라 하더라도 직관적인 코드가 가능하면 그렇게 한다. [본문으로]
  2. 실제로는 pearson's correlation coefficient 에 대한 rank 이다. 이것은 내 연구주제에 관련된 것이기 때문에 여기서 말할 필요는 없으므로 그냥 넘어 간다. [본문으로]
  3. dense_graph2.cpp 에서 왜 2 라는 숫자가 붙었느냐 하면, 원래 나는 그래프를 multimap 으로 표현하고 그것이 dense_graph 였는데, 너무 느려서 위처럼 이중포인터를 이용한 자료형으로 바꾸면서 2 를 붙이게 되었다. [본문으로]