1.1 그래프 이론의 동향 2 - edge connectivity 등이다. 그리고 이들에 관련된 알고리즘적 이슈들, 예를 들어 특정한 그래프의 성질을 확인하는데 걸리는 시간복잡도는 무엇인가, 그것이 최적의 복작도 (Optimal Complexity)인가를 따지는 일들이

Transcription

1 그래프 모형을 활용한 생물 네트워크 분석법 개요 A Survey on Biological Network Analysis with Graph Model 조환규, hgcho@pusan.ac.kr 1 그래프 이론과 그 응용 그래프 이론 (Graph Theory) 는 수학의 한 갈래인 조합론 (Combinatorial Theory) 의 일 부로서 매우 오래전 부터 연구되어 왔다. 그래프 이론이 본격적으로 현실문제에 활용되기 시작한 것은 2 차대전으로 탄생한 OR(Operations Research) 의 영향일 것이다. 예를 들어 지금도 산업공학에서 많이 활용되고 있는 max-flow를 이용한 최적화 계산모형은 그래프의 현실적 활용의 예라고 할 것이다. 이후 계산능력 (computation power)의 빠른 발전과 더불어 그래프 이론은 전산학의 전 분야에서 다양하게 활용되기 시작했으며, 지금은 전산학 뿐만 하나라 현대수학에서 중요한 이론적 도구가 되고 있다. 전통적인 그래프 이론과 현대적 그래프 이론 1 을 나누는 기준은 따로 있지는 않지 만 전통적인 그래프 이론은 주로 조합론적인 문제, 예를 들면 특정한 성질을 가지는 그래프 구조는 어떤 것인가에 집중하고 있다. 예를 들면 오일러 그래프나 해밀토니안 (Hamiltonian) 그래프가 가지는 특성을 규명하는 연구에 여기에 해당한다. 이런 조합론적 인 그래프 문제는 대부분을 표준적인 그래프 교재(text)에서 다루고 있는 주제들이다. 그 주제를 나열하면 Degree Sequence, Vertex Coloring, Edge Coloring, Planarity 2, Vertex 1 수리과학의 특성상 1980년대 이후에 새롭게 소개된 대부분의 그래프 관련 연구주제는 현대 그래프 이론이라고 볼 수 있다. 2 어떤 그래프를 에지의 교차없이 2차원 평면에 그릴 수 있는지의 여부를 확인하는 문제 1

2 1.1 그래프 이론의 동향 2 - edge connectivity 등이다. 그리고 이들에 관련된 알고리즘적 이슈들, 예를 들어 특정한 그래프의 성질을 확인하는데 걸리는 시간복잡도는 무엇인가, 그것이 최적의 복작도 (Optimal Complexity)인가를 따지는 일들이 여기에 속한다. 일반적으로 볼 때 전통적인 그래프 이론은 특정 그래프 클래스 (graph class) 의 성격을 규명 (Characterization) 하는 작업이라고해도 무방할 것이다. 예를 들어 모든 vertex의 degree가 5이상이면 가장 짧은 Cycle 의 길이는 k 이다 - 와 같은 명제는 특성화의 전형적인 표현이다. 그러나 이런 단순한 성질 규명은 현실에서 별로 유용성이 없다. 근대 그래프 이론은 컴퓨터의 등장으로 이전과 다르게 엄청나게 복잡한 계산문제를 실제 풀 수 있었기 때문에 보다 새로운 주제가 그래프 연구에 나타나기 시작하였다. 1.1 그래프 이론의 동향 최근의 그래프 이론은 앞서 설명한 전통적인 주제 이외에 계산적 측면과 확륙적 모형을 중 심으로 그 영역을 확장해왔다. 특히 다른 분야와 마찬가지로 컴퓨터를 이용한 계산과학의 발전으로 이전에는 단순히 모형연구에만 그친 주제들이 현실에 직접 응용되기 시작한다. 그 중 일반적인 그래프 이론 강의 3 에서 다루지 않는 몇 가지 새로운 연구 주제에 대하여 간략히 설명한다 무작위 그래프 이론 (Random Graph Theory) 전통적인 그래프 이론에서는 정점 4 (vertex)와 에지(edge)가 이미 결정적(deterministic) 으로 주어지고 그 안에서 어떤 특성을 규명하는 작업이 주를 이루었다. 그런데 무작위 (랜덤)그래프 이론에서 vertex와 edge는 확률변수로 주어지기 때문에 그와 관련된 모든 값들, 예를 들어 연결성(connectedness), 특정 크기의 subgraph의 존재 등도 확률적으로 결정된다. 랜덤 그래프도 에지가 생성되는 방법에 따라서 Erdös-Rényi 모형이나 Watts- Strogatz(WS) 모형 등으로 그 안에서 다시 세분된다. 이 모형에 대해서는 그림-5에서 다시 설명될 예정이다. 램덤 그래프 모형은 실제 그 연결구조를 확정할 수 없는 자연계, 3 대부분 대학의 학부에서 그래프 이론만 따로 강의하는 전산학 관련 대학은 없다. 보통은 이산치 수학에서 부분적으로 다루거나 대학원에서 전통적인 주제 중심의 그래프 이론이 있다. 조합론을 강의하는 수학과에서 그래프 이론을 다루기도 하지만 계산과 알고리즘 측면에서는 많이 다루지 않고 주로 특성규명 (characterization) 에 집중하고 있다. 4 본 보고서에서는 정점과 노드를 같은 의미로 사용한다.

3 1.1 그래프 이론의 동향 3 금융계, 시회현상을 모델링할 때나 실험이 불가능한 모형의 특징을 예측할 때 매우 유용하게 쓰일 수 있다. 예를 들어 인터넷에서 악성 바이러스가 퍼지는 속도나 예상되는 피해 규모, 또 그것이 안정화되는데까지 걸리는 시간을 예상하는데 랜덤 그래프는 좋은 모형이 된다. 최근에는 온라인 상에서의 이상조직 (outlier) 을 탐지하여 사기조직이나 테러집단을 추적하는데에도 사용된다. 랜덤 그래프 이론은 가장 중요한 그래프 이론의 한 분야가 되고 있다. 특히 같은 실험에 의해서도 서로 다른 결과가 측정되는 분자생물학 연구에는 랜덤 그래프 모형은 가장 중요한 도구가 될 것이므로 랜덤 그래프 분야에 대한 지속적인 연구가 필요하다 극단 그래프 이론 (Extremal Graph Theory) 그래프의 특성지표 중 가장 대표적인 것이 에지나 정점의 수이다. 그리고 연결도나 그 래프 지름(graph diameter), 가장 긴 사이클, 짧은 사이클(girth), 클릭(clique 5 도 중요한 지표이다. 그리고 이런 지표들간에는 다양한 부등식이 성립한다. 예를 들어 에지의 수가 늘어나면 연결도 (vertex connectivity) 도 증가한다. 그리고 최소 차수 ()degree) 가 올라가도 연결도는 증가한다. 이들간의 관계식 중에서 등호가 성립할 때의 조건에 대해서 집중적으로 탐색하는 것이 이 분야의 주제이다. edge의 수가 N 개 일 때 vertex connectivity의 최대, 최소값을 N 의 함수로 표현하라는 식의 문제는 극단 그래프 관련 문제의 전형적인 형식이다. 또는 vertex connectivity가 k 일 때 edge수의 최소치는 몇 개인가, 이런 류의 문제에 여기에 포함된다. 좀 쉬운 문제로는 다음과 같은 것을 생각해 볼 수 있다. 어떤 그래프 G(V ) 의 연결성 (connectedness) 을 보장하기 위한 최소의 에지 갯수는 몇 개인가 6. 극단 그래프 이론의 원조격인 이론은 램지이론 (Ramsey theory 7 ) 이다. 이 분야는 어떤 특성 (property P (a)) 을 가지기 위해서 (또는 가지지 않기 위해서 P (a)) 필요한 최소한의 원소의 갯수는 몇개인가- 와 같은 식의 문제를 탐구하는 것이다. 가장 잘 알려진 5 subgraph중에서 complete graph인 것 중 가장 vertex size가 큰 것 6 G = n 이라고 하자. 그래프가 연결되어있지 않으면서 가장 많은 edge를 가지는 경우는 전체가 K 1 하나와 K n 1 로 분리되어 있는 경우이다. 따라서 n(n 1)/2 + 1 개의 edge를 가지면 반드시 하나로 연결되어 있을 수 밖에 없다. 따라서 그 하한치는 n(n 1)/2 + 1이다 7 영국 수학자이며 철학자인 Frank P. Ramsey의 이름를 따서 붙인 이름이다. 램지 이론 문제의 전형은 다음과 같다. how many elements of some structure must there be to guarantee that a particular property will hold?

4 1.1 그래프 이론의 동향 4 명제는 6명의 사람이 모이면 그 안에서 반드시 3명 이상은 서로 알거나, 3명 이상은 서로 모르는 사이다 - 라는 명제이다. 이것은 K 3 을 clique으로 가지거나 그 complement graph가 K 3 를 가지는 그래프의 최소 크기는 G(V ) =6 이다 - 명제로 정의된다. 램지 이론은 현대 수학에 매우 큰 영향력을 미친 조합론의 한 분야이다 스펙트럴 그래프 이론 (Spectral Graph Theory) 그래프의 정점간 연결관계는 G G 의 행렬로 표현할 수 있다. 이 행렬의 특성을 바 탕으로 그래프의 다양한 성질을 연구하는 분야를 algebraic graph theory라고 하는데, 그 한 갈래가 이 연구이다. 이 연구는 그래프를 다양한 대수적 방법과 군론(Group Theory) 를 활용하여 그 대수적 특성을 분석한다. 주된 연구 소재는 입력 graph의 characteristic polynomial, eigenvalue 등이다. 1950년대부터 시작된 스펙트럴 그래프 이론은 당시에는 마땅한 응용분야가 없어 주목받지 못했지만 현대에 와서 Web graph와 같이 이 이론을 적용할 수 있는 다양한 그래프 모형과 엄청난 파워의 계산 8 이 가능해짐에 따라서 매우 활성화되고 있다. 주어진 그래프의 인접행렬 (adjacency matrix) 이나 라플라시안 행렬 (Laplacian matrix)의 고유값(eigenvalue)은 그래프의 연결 component의 갯수와 그 연결 정도에 대한 흥미로운 정보를 제공해준다. 예를 들어 어떤 그래프의 라플라시안 행렬의 행렬값은 그 그래프에 포함되어 있는 모든 non-isomorphic spanning tree를 갯수와 동일하다는 놀라운 사실 9 도 이 이론으로는 아주 간결하게 증명될 수 있다. 물론 그것을 하나씩 나열하는 (enumeration)하는 과정을 갯수를 단순히 산출하는 일과는 다르지만 여하튼 Matrix-Tree Theorem은 spectral graph 이론의 유용성을 보여주는 좋은 예가 된다. 이 이론을 응용하면 우리가 일일이 확인할 수 없는 크기의 그래프, 예를 들어 전 세계의 컴퓨터들이 얽혀있는 Web graph라든지, 또는 Facebook의 친구간 그래프라든지 그 전체의 확정된 모습을 알지 못하는 경우 그 일부분의 행렬구조를 분석하여 전체의 모습을 재구성할 수 있다. 특히 요즘의 사회연결망 (Social Network) 연구에서 이 이론 은 가장 중요한 분석도구가 쓰이고 있다. 양자화학 (Quantum Chemistry) 연구에서도 스펙트럴 그래프 이론은 핵심적인 도구로 활용된다고 한다. SNS 연구가 활발해짐에 8 예를 들면 형렬의 determinant 값을 구할 수 있는 일 9 Matrix-Tree Theorem으로 알려져 있다.

5 1.1 그래프 이론의 동향 5 따라서 이 이론은 더욱 주목을 받는 분야가 됟 것이다. 대표적인 세계적 대가로는 중국인 F.R.K. Chung을 들 수 있으며 미국수학회(MAA)에서 발간된 그녀의 주요 monograph 를 참조하면 이 분야를 보다 체계적으로 접할 수 있을 것이다[1]. 이 분야는 전통적인 그래프 이론(그림으로 표시되는)과 매우 상이하여 대수학에 대한 지식이 많이 요구되어 진입장벽이 상당히 높은 편이다. 입문용 서적으로는 R.B.Bapat이 쓴 수학과 고학년 교재 정도가 가장 적절할 것이다[2] 하이퍼 그래프 이론 (Hypergraph Theory) 전기회로를 그래프로 모형화할 때 한가지 어려운 점이 생긴다. 그것은 하나의 edge에 2 개 이상의 정점이 연결되기 때문이다. 즉 하나의 등전위 전선 위에 3개 이상의 소자가 연결되기 때문에 일반적인 그래프 이론과 같이 2개의 정점으로 하나의 edge가 이루어지는 형식으로는 표현할 수 없다. 그렇다고 해서 모든 쌍에 대하여 각각의 edge를 지정하면 많은 갯수의 clique이 생기기 때문에 원하는 분석을 할 수 없다. 따라서 하나의 edge 에 2개 이상의 정점을 허용하는 보다 일반화된 그래프 모형이 필요하게 되었고 이것을 집중적으로 다루는 분야가 바로 이 연구분야이다. 이런 일반적인 그래프 모형을 하이퍼 그래프라고 부르고, 어떤 연구자들은 fractional graph 라고또 부른다. 이런 모형이 회로도와 같은 데이터를 다룰 때에는 편리하긴하지만 분석에서 많은 어려움이 있다. 기존의 거의 모든 그래프 알고리즘이 두 노드를 연결한 기본 (x, y) 에지 모형을 가정하고 있기 때문에 이 유용한 도구들을 하이퍼 그래프 이론에 바로 활용할 수 없는 단점이 있다. 아래 그림-1는 하이퍼 그래프의 한가지 예를 보여준다. 중간에 vertex 없이 선이 연결된 점은 vertex가 아니며 그 위치는 의미가 없다. 그 점은 3개 이상의 vertex가 하나의 edge에 연결되어 있음을 보여주는 가상의 위치일 뿐이다 완전 그래프 이론(Perfect Graph Theory) 완전 그래프 이론은 알고리즈믹 그래프 이론 (algorithmic graph theory)의 한 분야로서 성질을 규명하는데 집중하는 앞서의 전통적인 그래프 연구와는 목적에서 좀 다르다고 할 수 있다. 알려진대로 대부분은 의미있는 그래프 문제, 예를 들면 그래프 색수문제 (graph coloring problem) 나 Hamiltonian cycle 문제는 잘 알려진 NP-complete에 속한 다. 알고리즘 측면으로 볼 때 그래프 연구는 서로 다른 2방향에서 진행되고 있다. 하나는

6 1.1 그래프 이론의 동향 6 a b c f g d e V = {a,b,c,d,e,f} E = {(a,b,c,d), (b,c), (c,e,f), (f,g)} Figure 1: 두개 이상의 vertex가 하나의 edge를 구성하는 것이 허용되는 하이퍼 그래프 (hypergraph) 의 예. 정점은 6개이며 edge는 4개이다. 전통적인 방법으로 그래프 문제의 알고리즘의 복잡도를 다항시간으로 내리려는 노력이 그것이다. 즉 다향시간에 해결이 가능한 다양한 그래프 문제, 특히 실제 현실에서 사용할 수 있는 그래프 문제를 발굴하기 위한 연구가 그것이다. 다른 하나의 연구방향은 일반 그래프가 아니라 그래프 class를 제한해서 기존의 NP-complete가 다항시간에 해결되는 좁은 그래프 클래스를 찾아내고 이것을 확장하는 것이다. 예를 들어 대부분의 그래프의 문제는 트리 (tree) 에서는 다항시간에 풀린다. 따라서 tree보다 좀 더 일반적인 그래프 클래스 중에서 대부분의 NP-complete graph problem 이 다항시간에 풀리는 그래프를 찾아내서 그것을 확장하는 것은 의미있는 작업이다. 그런데 우리의 예상과는 달리 상당한 제약조건이 있음에도 불구하고 그 문제가 그래도 NP-complete에 남아있는 경우는 허다하다. 예를 들어 평면 그래프 (planar graph)가 전 형적인 예인데, 대부분의 NP-complete 문제는 평면 그랴프에서도 변함없이 NP-complete 로 남아있다. 아주 부분적인 그래프 클래스에 대하여 다항시간의 알고리즘이 제시되었 지만 그런 결과는 매우 trivial한 불과했다. 이후 쿨롱[3]등 많은 그래프 이론가에 의해서 주요한 NP-complete 그래프 문제가 다항시간에 풀리는 상당히 일반적인 그래프 클래스가 제시되었는데, 그것이 바로 완전 그래프(perfect graph)라는 새로운 클래스이다. G가 완전(perfect) 그래프라는 것은 G의 모든 subgraph에서 maximum clique number 와 chromatic number가 같음을 말한다. 현재까지 알려진 완전 그래프의 종류는 매우 많다. 그 중 중요한 class만 소개하면 구간 그래프(interval graph), compatibility graph, triangulated graph, chordal graph, permutation graph, k-tree, (line) intersection graph

7 1.2 그래프 문제의 알고리즘적 이슈 7 등이 있다. 그런데 제시된 위의 그래프들은 응용에서 흔히 나타나는 그래프들이다. 이런 현실적으로 쉽게 접하는 그래프에서 이전에는 NP-complete라고 생각되어 시도하지 못한 clique number, graph coloring 등의 문제를 다항시간에 해결할 수 있게 된 것은 큰 의미를 가진다. 완전 그래프 이론는 M.C. Golumbic에 의해서 완성되었는데 이 이론은 그의 역작을 통해서 확인할 수 있다[4]. 이 연구 덕분에 다항시간에 해결할 수 있는 그래프 클래스는 매우 넓어졌다고 할 수 있으며 NP-complete라고 짐작되어 피한 여러 응용분야에서 알고리즘적으로 큰 진보가 이루어졌다. 이 이론은 Parameterized Complexity Theory와 함께 알고리즘 연구의 최신 분야가 되고 있다. 1.2 그래프 문제의 알고리즘적 이슈 그래프는 실생활의 다양한 문제를 해결하기 위한 모형으로 오랫동안 이용되었다. 따라서 그 실생활 문제 대부분은 그에 대응되는 그래프 문제로 변형될 수 있다. 예를 들어 학 부수준에서 배우는 최소 스패닝 트리 구성(Minimum spanning tree) 이라든지 Traveling Sales Person은 가장 잘 알려진 그래프 문제들이다. 그래프 문제는 특성별로 구분하면 Graph Covering, Partitioning, Subgraph, Supergraphs, Vertex Ordering, Iso-and other Morphisms으로 나뉜다 10. 다양한 그래프 문제 중에서 우리는 네트워크 정렬과 직접적으로 관계가 있는 그래프 동일성(isomorphism)문제를 본 보고서에서 분석할 예정이다. 먼저 그래프 동일성 문제를 셜명한다. 아래 그림-2에서 보면 G a 과 G 2 는 vertex label이 없을 때 완전히 동일한 그래 프이다. 그러나 그 아래와 같이 만일 vertex에 label이 있는 경우에는 상황은 달라진다. 단 edge에 label이 있는 경우는 고려할 필요가 없다. 왜냐하면 각 edge는 edge의 양 끝 vertex로 완전히 결정되기 때문에 vertex번호가 정해지면 edge label은 의미가 없다. 모든 그래프 연구에서 제일 먼저 결정되어야 할 것은 대상 그래프가 vertex-labelled graph인지 아닌지의 여부이다. 그래프 이론에서 한가지 유의해야 할 점은 induced subgraph와 partial subgraph의 차이를 이해하는 것이다. vertex induced subgraph는 원 그래프에서 vertex 일부분만을 선택하여 subset을 만들 때, 그들 선택된 vertex subset에 속한 edge들은 반드시 모두 10 이 기준은 Gary and Jhonson의 기준에 따라서 분류한 것이다.

8 1.2 그래프 문제의 알고리즘적 이슈 8 G 1 G G G 4 Figure 2: 정점 레이블 그래프(vertex labelled graph) 와 레이블이 없이 위상(topology) 만 존재하는 그래프. 두 그래프 G 1 과 G 2 는 모양은 달라도 위상적으로 완전히 동일한 그래프이다. 포함시킨 부분 그래프(subgraph)이다. 아래 그림-3에서 G {2,3,4,6} 은 전체 vertex 집합에서 vertex = { 2,3,4,6 }만을 선택하여 구성한 induced subgraph이다. 만일 여기에서 edge (2, 4) 가 빠진다면 induced subgraph는 될 수 없다. 특정 edge 단위로 부분 그래프를 만들 수도 있는데 그것을 partial subgrah라고 한다. 아래 그림-3에서 가장 오른쪽에 있는 그래프 G partial 가 바로 partial subgrah이다. 우리는 partial subgraph는 vertex induced subgraph의 superset이라는 것을 알 수 있다 G G {2,3,4,5} G partial Figure 3: 어떤 그래프 G의 vertex-induced subgraph와 partial subgraph G partial. 만일 생물학적 네트워크 (Biological Network, BN) 을 그래프로 바꿀 때 node 정보 가 확실하면 vertex-labelled 그래프로 모형을 만들어야 한다. 그러나 노드를 이루는 생물학적 개체의 특성이 모호하거나 모두가 같은 기능을 할 경우에는 vertex labelling 이 불가능하기 때문에 이 문제는 vertex unlabelled graph문제로 접근해야 한다. 일견

9 1.2 그래프 문제의 알고리즘적 이슈 9 생각하기에 vertex unlabelled graph 문제가 쉬운 것 같지만 본 보고서에서 다루는 그래프 비교의 문제에서는 vertex unlabelled graph가 그것이 아닌 labelled graph보다 훨씬 더 어렵다. vertex labelled graph에서는 단순히 edge (x, y) 쌍의 일치여부만 보면 되기 때문에 쉬운 반면, unlabelled graph는 전체 구조를 봐야하기 때문에 훨씬 많은 계산을 요한다. 즉 unlabelled graph에서의 solution space가 labelled graph보다 훨씬 더 크기 때문에 더 어려운 문제가 된다. 아래는 그래프 이론 교재에 나오는 대표적인 문제로서 제시된 그래프 중에서 완전히 같은 (isomorphic) 그래프가 무엇인지 알아내는 것이다. 한번에 눈으로 쉽게 풀 수준은 넘어서는 까다로운 문제임을 느낄 수 있을 것이다. 아래 그림-4에서 보면 3개의 그래프는 모두 같은 수의 vertex를 가지고 있다. 또한 모든 vertex의 degree(차수)도 동일하다. 일단 G 3 와 G 2 가 같지 않음은 쉽게 알 수 있다. G 2 는 bipartite graph 이기 때문에 모든 cycle의 길이는 짝수이다. 그러나 G 3 을 보면 Cycle의 길이가 5인 것도 존재하기 때문에 두 그래프는 같은 그래프가 될 수 없다. 이와 같이 두 그래프가 다른 것을 밝히는 것은 하나의 반례적 특정 (counter example characteristics) 만 보여주면 되지만, 두 그래프가 같다는 것은 벍히는 것은 구체적인 isomorphism function (각 vertex가 어떤 vertex 로 대응되는지를 mapping하는 작업) 을 제시해야하기에 반증보다 훨씬 더 복잡하고 어려운 일이다. 이 문제의 exhaustive solution에는 모든 가능한 쌍의 경우를 다 확인해보는 n! 번의 검증작업이 필요하다. 이 문제, 즉 두 개의 vertex unlabelled graph가 서로 isomorphic인지의 여부를 밝히는 문제가 NP-complete 문제인지도 아직 밝혀지지 않은 상황이다. 이와 유사한 subgraph isomorphism 문제, 죽 주어진 QUERY graph G q 가 어떤 target graph G u 안에 embedded 되어있는지의 여부는 NP-complete 문제임이 밝혀졌다. 그래프 비교에서 전체로 비교 하는 문제와 부분적으로 비교하는 문제는 이후 Network Alignment 문제에서 Global alignment, Local alignment로 나누어서 설명한다. 끝으로 그래프 모형을 생물학적 네트워크에 응용할 때 고려해야할 점을 나열하면 다음과 같다. 1. 생물학적 실험결과를 바탕으로 그래프 모형을 만들면 많은 잡음 신호가 들어간다. 즉 수많은 false data가 포함된 불완전한 그래프라는 것을 인지해야 한다. 비록 제시된 그래프 모형은 Solid하게 보일지라도.

10 1.3 그래프와 네트워크 : 용어의 상이점 10 G 1 G 2 G 3 Figure 4: 대표적인 그래프 isomorphism test 문제. 문제는 주어진 3개의 그래프 G 1 G 2, G 3 중에서 isomorphic한 그래프 쌍이 존재한다면 그것을 찻는 것이다. 2. 실험이 가능한, 예를 들어 단백질 상호작용 실험을 할 수 있는 경우가 수 (edge) 가 실험 개체 (vertex, 예를 들면 단백질) 수의 제곱으로 늘어나기 때문에 모든 것을 실험으로 검증하기는 불가능하다. 따라서 그것을 바탕으로 만든 그래프 모형에는 상당히 많은 true data 가 빠져있는 셈이므로 빠져있는 생물학적 사실을 그래프 모형과 계산적 기법을 동원하여 추론하는 것이 가장 중요한 이슈가 된다. 3. 설사 완벽한 생물학적 그래프 모형이 만들어졌다고 하더라고, 그 그래프에서 뭔가 가치있는 것을 알고리즘으로 찾아내거나(주로 optimization solution을 이용해서), 성능의 근사치가 보장된 solution을 찾아내는 일은 현실적 계산이 불가능한 NPcomplete 이상의 복잡도를 가진 문제들이므로 최적의 답을 구해야 한다는 생각을 버려야 한다. 1.3 그래프와 네트워크 : 용어의 상이점 많은 연구 보고서나 논문에서 보면 어떤 경우에는 그래프, 어떤 경우에는 네트워크라는 용어가 쓰인다. 둘의 차이에 대하여 명확한 규정은 없지만 본 연구자의 경험으로 볼 때 그래프는 위상적 중요성을 강조할 때 쓰이는 표현이고 네트워크는 그 내부의 Dynamics를 강조할 때 쓰이는 용어라고 판단된다. network flow analysis가 전형적인 예가 될 수 있을 것이다. 즉 시간의 흐름에 따라서 특정 edge를 통하여 정보가 전달되고 또는 그 edge가 사라지고 각 노드상의 정보가 자주 바뀌는 경우에는 Network이라는 용어가 자주 쓰인다. 한편 전체 연결도 (connectivity) 와 같이 특정한 노드의 위상적 중요성과 같이 정적인 모형에서 각 노드가 차지하는 구조적 문제를 다루는 경우에는 보통 graph라는 표현을

11 2 그래프 유사도 계산문제 11 쓰는 편이다. 생물학적으로 볼 때 각 기관이 서로 엮여있는 모습은 그래프 이론적 접근이 필요하지만 세포내에서의 신호전달, 유전자들간의 시간에 따른 상호작용은 Genetic Network으로 표현되고 있듯이 내부의 동적인 변화를 강조할 경우에는 network이라는 표현이 더 보편적이다. 2 그래프 유사도 계산문제 생물 그래프를 비교하는 것은 그 안에 숨어있는 분자생물학적으로 의미있는 과정을 찾아내기 목적이다. 그러나 우리가 가지고 있는 생물 데이터 자체에는 피할 수 없는 실험오류와 잡음, 그리고 전 과정을 모두 확인할 수 없는 본질적인 문제가 내쟈하고 있기 때문에 같은 데이터를 이용한 분석도 관찰자에 따라서 전혀 다른 결과로 나타나기도 한다[3]. 그 이유는 우리가 연구하고자 하는 생물 네트워크 연구에는 기본적으로 그 모형에 대한 가정을 이미 하고 있기 때문이다. 우리가 가정한 모형 자체가 달라지면 그 결과도 당연히 달라진다. 따라서 이런 모형으로 쓸 수 있는 다양한 그래프 모형에 대하여 먼저 살펴보고자 한다. 2.1 네트워크 모형의 설정 가장 일반적인 모형은 앞에서 설명한 vertex unlabelled (labelled) graph 가 있다. 이 모형은 우리가 탐구하고자 하는 그래프의 전체 위상을 우리가 완벽하게 알고 있다는 것을 가정하고 있다. 다르게 표현하자면 탐구대상이 그래프로 완벽하게, explicitly expressed된 모형이다. 주로 적은 갯수의 노드로 구성된 일반적인 그래프가 여기에 속한다. 예를 들어 지하철 노선이라든지, 작은 집단내에서 친분관계, 또는 상하관계를 그래프로 표현한 것이 여기에 속한다. 문제는 이렇게 표현하기가 불가능한 그래프를 다룰 때 우리가 어떤 그래 프 모형을 가정해야 하는가이다. 그 모형은 크게 무작위 그래프 모형 (Random graph), Small-world Network, Power-law Network 11, 기하기반 네트워크 (Geometric Network) 로 나뉜다. 믈론 각 모형들은 세부적으로 매개변수를 어떻게 설정하는가에 따라서 새로운 변형 모델의 네트워크로 발전시킬 수 있다. 아래 그림-5은 각각의 예를 보여주고 있다. 11 또는 Scale-Free Network이라고도 불린다. 연구분야에 따라서 다르게 불린다. 보통은 Complex Network 이라면 이런 모형을 가정한다고 생각하면 된다.

12 2.1 네트워크 모형의 설정 12 무작위 그래프는 말대로 각 edge가 임의의 노드를 연결하는 방식으로 만들어지는 것이다. 즉 두 vertex x, y 를 연결하는 edge (x, y)는 확률변수로 주어진다. 그 중에서 가장 단순한 모형은 Erdös-Rényi Random graph model로서 G(N, p)로 표현된다. 여기서 N 은 vertex의 갯수 즉 G = N 이고 임의의 edge (x, y) 가 존재할 확률은 uniform distribution 의 확률 0 < p < 1 로 주어진다. 만일 p = 0 이면 edge가 하나도 없이 N 개의 vertex만 존재하는 NULL graph, 또는 N개의 정점을 가진 complete graph의 complement 12 graph 인 K(N) c 이 된다. 그리고 p = 1 이 되면 complete graph K N expected number of edges는 당연히 p N(N 1)/2가 된다. 이 된다. 이 그래프의 별 의미없이 보이는 이 random graph의 가장 중요한 특징은 criticality 13 를 가진다는 것이다. 즉 p 값이 변함에 따라서 어떤 특정한 값 근처에서 성질이 급격하게 변화하는 현상을 보여준다. 흥미로운 예를 들어보자. 이 그래프G(N, p)에서, p값이 증가함에 따라 서 전체 그래프가 하나의 연결된 그래프로 될 확률 C(p)는 특정점에서 급격히 올라가는 특성을 보인다. 인간사회나 집단에서도 한 집단의 개별 친밀도가 일정 이상을 넘어가면 전체가 하나로 연결, 즉 소문이 전체로 퍼질 가능성이 급격히 올라가는 급변현상(critical transition)을 볼 수 있다. 이 급변현상은 현대 과학의 가장 중요한 문제중 하나이다. 즉 급변이 일어나기 전까지는 어떤 외형적 조짐도 나타나지 않다가 아주 미급변점 (critical point)근처에서의 아주 세한 변화에 따라 상황은 급변하게 된다. 급변현상이 일반변화에 비하여 보여주는 또 다른 특성은 급변된 상황이 이전 상황으로 되돌아오는 것은 매우 어렵다는 것이다. 14 Random graph 모형은 전염병의 전파를 예방하거나 설명하는데 매우 적절하다. 예를 들어 각 사람들끼리의 상호작용이 일정 이하가 되면 전염병은 특정지역에서 발생하여도 잠시 창궐해도 더 이상 퍼지지 않고 쉽게 사그라든다. 이이 비해서 사람들끼리의 접촉의 정도가 critical point보다 조금만 더 높으면, 즉 그래프로 보았을 때 평균 degree수가 p c 보다 조금만 더 높으면 병은 삽시간에 전 지역으로 빠르게 퍼지게 된다. 문제는 이 12 G의 complement graph G c 는 G에 존재하는 edge 는 없어지고 G 에 없는 edge가 추가되는 그래프이 다. 13 물이 어는 과정도 여기에 포함된다. 순수한 물은 0도에서 갑자기 그 상태(phase)가 변화하여 액체에서 고체, 또는 고체에서 액체로 바뀐다. -5도에서 물이 90% 얼고 +2도에서 5%가 얼지않는다. 0 도에서 모든 분자가 갑자기(critically) 어는 것이다. 14 경로가 매우 긴 비가역적 반응이라고 한다. 예를 들어 싸운 사람이 화해하여 싸우기 이전으로 돌아가는 것은 전형적인 비가역반응이다.

13 2.1 네트워크 모형의 설정 13 현상에 criticality가 존재한다는 것이다. 즉 전역적으로 전염병이 퍼지기 바로 직전까 지도 아무런 조김이 나타나지 않다가 바로 그 다음에 삽시간에 전역으로 퍼지는 현상을 보인다는 것이다. 따라서 이런 전염병이나 컴퓨터 바이러스, 악성 소문, 각종 반사회적 개체는 critical point에 이르기 전에 적극적으로 예방을 해야만 비상상황을 막을 수 있다. Random graph 는 바로 이런 급변현상을 진단하고 예방하는데 매우 중요한 모형으로 활용되고 있다. Figure 5: 가장 대표적인 4가지 그래프 모형. a) 는 random graph(정확하게는 Erdös- Rényi Random graph model) 이다. 어떤 edge는 거리에 상관없이 임의로 선택된 2 개의 노드를 연결한다. b) small-world graph 이다. c) 는 hub node가 존재하는 scale-free graph, 또는 power-law graph이다. 그리고 마지막 d) 그래프는 geometric graph 이다. 즉 두 개저의 정점은 그 둘의 거리가 L 0 이하가 되면 항상 연결된다. 그 다음은 small-world 모형이 있는데 Watts-Strogatz(WS) random graph라고 불린 다. 이 모형에는 3개의 매개변수가 존재하여 W S(n, k, p) 로 표현된다. n은 전체 vertex 의 수를 나타내며 다음과 같이 구성된다. 일단 n 개의 노드를 원주 위에 놓는다. 그리고

14 2.1 네트워크 모형의 설정 14 각 노드에서 왼쪽으로 윈주상에서 가장 가까운k/2 개, 오른쪽으로 가장 가까운 k/2 를 모두 연결한다. 즉 k = 2 가 되면 양쪽으로 인접한 각 하나씩의 노드를 연결한다. 그 다음 임의의 두 노드를 확률 p롤 잡아서 연결한다. 이것을 small-world graph라고 부르는 것은 각각의 노드는 물리적으로 가까운 k 명의 친구와 연결되어 있으며(실제 사회생활과 빅슷하게), 그리고 간혹 먼 개체와는 낮은 p 의 확룰로 연결되어 있는 것과 닮아있기 때문이다. 이렇게 구성된 WS 그래프는 그 자체적으로 매우 흥미로운 특징을 잘 보여주고 있다. 예를 들어 현대 사회에서 알음알음으로 6번 정도만 건너가면 거의 모든 사람들끼리 연결이 된다는 작은 세상(small world) 현상은 이 그래프의 전형적인 특성이다. 즉 이 그래프에서 임의의 두 노드상의 최단거리는 상상외로 매우 짧다는 특징을 가지고 있다. 그 다음 중요한 또 다른 모형은 그림-5-(c) 에 있는 Scale-free network이다. 이 네 트워크는 A.L. Barabasi와 그의 지도학생인 Reka Albert가 고안한 모형으로 자연계 에서 나타나는 많은 네트워크를 설명하는데 유용한 모형이다. 이 모형이 Erdös-Rényi Random graph model과 다른 것은 edge 가 생기는 과정이 각각 독립적으로 만들어지는 것이 아니라 현재의 상황에 종속적이라는 것이다. Erdös-Rényi 모형은 임의의 두 노드를 연결하는 edge iid분포확률에 의해서 독립적이지만, 이 모형에서 새로운 edge는 이미 구성된 그래프의 특성에 따라서 달라진다. 쉽게 표현하자면 새로운 edge는 이미 많은 이웃을 가진 노드(degree가 높은 노드)에 더 많이 붙으려고 한다는 것이다. 일종의 부익부 빈익빈 15 현상으로도 설명할 수 있다. 이 모형에서 새로운 edge가 추가되는 과정은 다음과 같다. 전체 노드 중에서 새로운 edge가 선택할 vertex는 현재의 vertex degree에 비례하여 확룰적으로 선택된다. 예를 들어 어떤 노드 x의 이웃이 10 명이고 다른 노드 y 의 이웃이 1이라면 16 다음 단계에서 x 에 새로운 edge가 생길 가능성은 y 에 비해서 10배나 높아진다다. 이런 과정으로 네트워크를 구성하다보면 degree가 높은 vertex에는 더 많은 edge 가 붙어있게 되고, 에지가 적은 노드들은 갈수록 edgr가 추가되는 과정에서 도태되게 된다. 이렇게 구성된 그래프의 degree 분포를 계산해보면 그 분포는 지수분포를 보임이 증명되었다. 즉 degree가 k 17 인 노드가 생길 확룰은 (1/k) α 로 표현된다. 다르게 말하면 15 The rich get richer and the poor get poorer 16 앞으로 각 vertex x의 degree는 ρ(x)로 표시한다 17 이웃한 노드의 갯수가 k개

15 2.1 네트워크 모형의 설정 15 차수가 높은 노드가 생길 가능성은 그 차수의 거듭제곱에 반비례한다는 것이다. 이 경우 α 를 scaling factor라고 부르고 이 값은 지수분포 네트워크를 구별하는 중요한 지표, 매개변수가 된다. 지수분포 네트워크의 가장 큰 특성은 매우 높은 차수를 가진 허브 (Hub)노드가 반드시 존재한다는 것이다. 실제 자연계나 사회에 존재하는 대부분은 네트워크들, 예를 들어 World Wide Web 그래프나, PPI 그래프, 각 논문들의 citation 그래프 18 역시 그러하다. 경제학에서도 이 법칙이 존재하는데 Pareto의 법칙이 이것을 설명하고 있다. 부자는 가진 자산을 활용해서 더 큰 부자가 되지만 가난한 사람들은 투자할 돈이 없어 돈을 벌지 못하고 이 때문에 돈은 더욱 줄어들어 갈수록 더 궁핍한 생활을 하게되어 결국 가난의 굴레에서 빠져나오지 못하는 과정이 나타난다. 실제 재산의 정도에 따른 인구수를 나열해보면 대부분의 사회에서 정확하게 지수 분포임을 확인할 수 있다. 이 지수분포 그래프를 Log-Log Chart로 그려보면 직선으로 나타나는데, 고 그때의 기울기가 바로 Scaling factor가 됨을 알 수 있다. 아래 그림-6 는 전형적인 power-law를 따르는 사회현상의 한 예이다. 이 그래프는 Log-Log chart 인데 가로축은 어떤 회사에 속한 사원의 수를 나타낸다. 가장 많은 사원의 수는 표에 나타난바와 같이 10 6 이다. 그리고 세로축은 그런 회사의 전체에서의 비율을 나타낸다. 아래로 갈수록 비율이 적음을 나타낸다. 그림과 같이 그 분포는 log-log chart 에서 매우 정확한 직선을 나타내고 있다. 인간사회의 거의 모든 집단적 특성은 이 power-law를 따르며 그것이 바로 전형적인 사회현상의 한 특징이다. 다시 말해서 사회 특정 집단의 특정 property (attribute) 가 만일 power-law 분포를 따르지 않는다고 하면 그 자체가 매우 중요한 연구대상이 될 수 있다. 이러한 power-law법칙을 따르는 네트워크를 scale-free network이라고도 불리는데 그 뜻은 전체가 지수분포를 따르기 때문에 척도를 알아낼 수 없기 때문이다 어떤 논문 X가 다른 논문 Y를 참고했으면 edge (X, Y )를 추가한다. 이 과정은 부익부 빈익빈 과정의 대표적인 예가 된다. Citation이 많이 되었기 때문에 더 유명해지고, 더 유명해지기 때문에 많은 사람들이 인용을 하게 되는 선순환 구조를 가진다. 역으로 다른 수많은 논문들은 도태 과정을 거치는데, 초기에 인용이 잘 안되기 때문에 다른 논문에서 인용을 잘 하지 않고, 그것 때문에 다시 중요도를 낮게 평가받아 결국 사라지게 된다. 19 만일 어떤 집단의 소득수준이 정확하게 지수분포를 따른다고 한다면, 그 중에서 상위 10%를 뽑아도 그 안에서는 다시 상위, 하부 분포가 전체의 분포대로 나타나고, 하위 10%를 선별해서 다시 그래프로 그려도 그 분포는 같은 scale factor 의 지수분포를 하기 때문에 samping된 집단안에서 분포는 항상 동일하기 때문에 그 집단이 전체에서 어디에 위치하고 있는지를 알 수 없다는 말이다. 만일 우리나라 국민들의

16 2.1 네트워크 모형의 설정 Frequency Firm size (employees) Figure 6: 가로축은 특정 업체의 종업원의 수가 Log scale로 표시된 것이며, 세로축은 그런 특성을 가진 개체의 빈도 (frequency) 가 로그 scale로 표시된 것이다. 이 분포는 놀라울 정도로 정확하게 지수분포를 나타내고 있다. 최근 생물 네트워크 연구자들이 주목하고 있는 것은 아래 그림-7에 표시된 것과 같은 기하 그래프(Geometric graph) 모형 이다. 기하 그래프는 각 개체의 기하학적인 위치로 부터 생성된다. 쉽게 표현하자면 공간상에 점들이 분포하고 그 점들이 일정한 거리보다 가까울 경우 서로 연결된다. 즉 edge를 가지게 된다. 기하 개체는 반드시 점 (point set) 일 필요는 없으며 넓이를 가진 원이나 사각형, 또는 3차원 일반적인 입체도 가능하다. 이 그래프의 특징은 공간적으로 가까운 거리에 있는 개체들끼리 뭉친 형태를 보이는 것이다. 이 그래프의 최대, 최소 차수(degree)라든지, 지름(diameter) 20 에 대한 확률적인 특성은 매우 흥미롭다. 특히 기하 그래프 모형는 최근의 이동통신, sensor network design 에서도 잘 활용되고 있다. 기하 그래프의 역사와 특성, 통계적인 특성, 다양한 응용의 예는 Mathew Penrose의 역작에 잘 기술되어 있으므로 참고하면 될 것이다[5]. 그런데 생물 네트워크 중에 가장 전형적인 예라고 할 수 있는 단백질 상호작용 네트 워크(Protein-Protein Interaction Network) 의 특성이 기하 그래프의 특성과 유사하다는 소둑이 power-law를 따른다면 500대 재벌집단만을 선별하여 그린 지수분포 그래프 k α 나 하위 계층의 소득분포가 보여주는 분포는 완전히 동일하게 나타난다는 것이다. 이것은 결국 부분집단의 scale을 sampling만으로는 알 수 없다는 것을 말해주므로 이것은 scale-free라고 부른다. 또 다른 예로 어떤 험한 산에 있는 돌들의 크기가 지수분포를 가진다면 우리가 개미만큼 작아졌을 때에도 주위에서 보이는 돌들의 크기 분포나, 우리가 거대한 공룡만큼 커진 상황에서 보이는 돌들의 크기분포는 동일하게 느껴질 수 밖에 없다. 20 그래프 모든 점들끼리의 최단거리 중에서 가장 긴 거리

17 2.1 네트워크 모형의 설정 17 새로운 사실이 속속 밝혀져 주목을 받도 있다 [6, 7]. 만일 이것이 사실이라면 PPI연구는 새로운 전기를 맞이하게 되는데, 이전 연구자들 대부분은 PPI 네트워크가 일반적인 power-law network이라고 가정하에서 연구를 전개했기 때문이다. 왜 기하학적인 모양과 아무런 상관이 없는 PPI 네트워크가 기하 그래프적 특성을 가지고 있는지에 대해서는 아직 연구 중이지만 N. Przŭlj 연구팀은 이 이유를 이렇게 설명한다. 일반적으로 유전자, 세부적으로는 각 단백질들은 진화과정에서 자기복제 (selfreplication) 와 변이 (mutation) 을 하게 된다. 또 다른 단백질과 결합하여 결합한 두 개의 단백질과 유사한 새로운 단백질 서열을 만들어 내는데, 그렇게 유사한 단백질들간 상호작용은 다른 쌍들에 비해서 더 활발하다는 것이다. 그래서 상호작용이 높은 이들 쌍은 화학구조적 특성으로나 서열상으로 상당히 닮은 형상을 가지고 있을 수 밖에 없다. 따라서 이들을 유사한 것들끼리 기하공간에 가까이 배치하고 그 중 상호작용을 하는 것끼리 연결을 하면 단백질 장용 그래프는 결국 기하그래프의 구조적 특성과 유사한 연결특성을 가지는 것이 아닐까 한다[8]. y L 0 x z L 0 Figure 7: Geometric graph의 예. geometric graph에서 공간상의 점(개체) 간은 그들의 거리가 어떤 정해진 문턱값(threshold) L 0 보다 작으면 edge로 연결된다. 따라서 거리가 멀리 떨어져 있는 점은 edge로 연결되지 않아 전체적으로 disconnected component도 될 수 있다. 앞서 설명한 모형 외에도 기본 모형에서 변형된 여러 모형이 존재한다. 그리고 각각은 적절한 연구목적에 따라서 다양하게 활용되고 있다. 자세한 내용은 요즘 연구되는 각종 네트워크 관련 모형을 잘 설명한 Newman의 역작을 살펴보면 될 것이다[9].

18 2.2 그래프 동일성(Isomorphism) 판별문제 18 정리해서 말하자면 생물에서 이론적으로 가능한 모든 실험을 다 해볼 수 없고 또한 그런 과정은 필연적으로 많은 오류와 잡음을 포함할 수 밖에 없기 때문에 이렇게 빠진 부분은 이론적 연구를 통하여 메꿔나갈 수 밖에 없다. 그런데 이 과정에서 우리가 어떤 그래프, 네트워크 모형을 가정하고 시작하는가에 따라서 결론은 매우 달라지고 또한 심한 경우 같은 자료로 부터 서로 상반된 결론에 도달할 수 도 있다. 따라서 생물 네트워크 연구시작 전에 어떤 네트워크 모형을 가정하는지에 대한 관점을 분명히 해야할 것이다. 그렇게 해야만 상반된 또는 모순된 결론을 최종적으로 피할 수 있기 때문이다. 다음은 이 보고서의 중심문제인 그래프 매칭, 그래프 동일성 검사 문제를 다루고자 한다. 2.2 그래프 동일성(Isomorphism) 판별문제 두 그래프의 유사도를 정량적으로 계산하는 문제는 여러 분야에서 활용되고 있다. 사회연 결망 분석, 컴퓨터 비전에서 두 물체의 동일성을 판단하는 응용에 있어서 그래프의 유사도 계산은 매우 중요한 역할을 한다. 두 그래프 사이의 다양한 측도의 유사도 (similarity) 를 계산하는 방법은 알고리즘의 유형에 따라서 크게 세가지로 구분된다. 첫번째로는 각 vertex나 edge의 mapping 함수, 즉 isomorphic function을 직접 구하는 방법인 가장 정통적인 접근법이 있다. 이 방법은 매우 전형적인 접근법이긴하지만 그래프 노드수가 많아지면 계산이 시간, 공간상으로 불가능한 단점이 있다. 제한없이 주어진 두 그래프의 isomorphism을 찾아내는 것은 오래전부터 연구된 매우 유명한 계산문제이다. 크기가 같은 두 그래프가 서로 isomorphic한지를 판단하는 문제는 NP-complete인지 아니면 polynomial time algorithm 이 존재하는지 조차 규명되지 못한 상태이다. 같은 상황에 있는 문제 21 로 Gary and Johnson이 밝힌 12개의 문제가 추가로 존재한다. 그러나 subgraph isomorphism 문제는 NP-complete 문제임이 밝혀졌다 22. 아래 그림-8에서 (a)는 전체 그래프의 isomorphism 문제의 예를 보여주는 것이고 (b) 21 아직 효율적인 polynomial time algorithm이 존재하지도 않으면서 동시에 이것이 NP-complete문제 인지도 밝혀지지 않은, 아주 어중간한 상태에 있는 문제 22 이 증명은 비교적 쉽다. 어떤 그래프에서 hamiltonian cycle이 존재하는지를 검사하는 문제는 이 그래프 에서 같은 크기의 Cycle을 subgraph로 가지는지를 검사하는 것과 동일하다. 즉 subgraph isomorphism 문 제는 hamiltonian cycle 문제보다 쉽지 않다. 따라서 NP-complete문제인 hamiltonian 문제로의 reducing 이 가능하므로 제한없는 일반 그래프에서의 subgraph isomorphism문제는 NP-complete 에 속하게 된다.

19 2.2 그래프 동일성(Isomorphism) 판별문제 19 는 subgraph isomorphism문제의 한 예이이다. 전체 isomorphism문제가 요구하는 것은 는 제시된 두 그래프가 vertex와 edge에서 동일하도록 되도록 (만일 동일하다면), G 1 의 모든 vertex를 어떻게G 2 의 vertex로 mapping하는지 그 mapping함수, 또는 isomorphism 을 찾는 것이다. 그러나 (a) 와 달리 (b) 는 G 3 가 G 4 의 어떤 부분과 완전히 일치하는지 그 부분을 찾는 것이 문제가 된다. 따라서 G 4 의 vertex 중에서는 매핑에 들어가지 않는 vertex들이 반드시 존재해야 한다. 그런데 전체 isomorphism 문제에서는 모든 vertex는 반드시 하나씩의 짝으로 매핑되어야 한다. 즉 아래 그림-8에서 볼 때 G 1 과 G 2 은 위상적으로 완전히 동일하다. 이 두 그래프에서 isomorphism은 그것을 유지하는 mapping function 함수(isomorphism) 는 f() 는 다음과 같다. f(1, 2, 3, 4, 5, 6, 7, 8) = (b, c, g, f, a, d, h, e) 이와 유사한 subgraph isomorphism 문제는 G 3 과 같은 위상구조를 가진 subgraph를 G 4 에서 찾는 것이다. 이 subgraph isomorphims문제는 위 두 그래프의 isomorphism을 찾는 문제보다 훨씬 더 어렵다. 그림-8에서 볼 때 우리는 이것이 쉽지 않다는 것을 바로 인지할 수 있다. 왜냐하면 graph isomorphism 문제는 두 그래프에서 특성이 다른 하나의 vertex나 또는 subgraph만 찾아도 isomorphism이 없다는 것이 확인이 되지만 subgraph isomorphism문제는 그런 식으로 그것의 존재가 부정이 되지 못하기 때문이다. 간단한 예 를 들어 G a = 10, G b = 11와 같이 vertex의 수가 다르면 두 그래프는 절대 isomorphic 할 수가 없다. 또한 maximum degree라든지 minimum degree가 달라도 isomorphic하지 않는 것은 쉽게 알 수 있다. 그런데 대상 그래프의 구성요건이 제한적이라고 해서 이 문제가 쉽게 풀리는 것은 아니다. 특별한 class중에서 polynomial time에 풀리는 경우는 아래에서 설명한 tree 클래 스에서는 가능하고 planar graph에서도 가능하다. 그리고 대부분의 perfect graph class 인 interval graph, permutation graph등에서도 isomorphism 문제는 다항시간에 해결이 가능하지만 그 외 대부분의 그래프에서는 아직도 해결되지 못한 영역으로 남아있다. graph isomorphism문제를 해결하는 알고리즘 중에서 그나마 현실적인 solution은 2008년도 제시된 O(2 n log n ) 알고리즘이 가장 나은 복잡도를 보이지만 실제 구현상으

20 2.2 그래프 동일성(Isomorphism) 판별문제 a d 3 4 b c G 2 G 1 f 5 6 e 7 8 g h a b i e c f d h j G 3 G 4 g k Figure 8: G 1 과 G 3 이 같음을 vertex mapping으로 찾아보자. 그리고 G 4 안에 과연 G 3 가 존재 (embedding) 하는지를 찾아보자. 이 두번째 문제가 subgraph isomorphism 문제이다. 로는 매우 어렵다. 이 정도 시간 복잡도라면 대략 노드의 갯수가 1000개 이상인 경우 즉 G > 1000 인 문제는 적절한 시간에 답을 기대할 수 없다. 그러나 트리에서 그래프 동일성 문제, 정확하게 트리 동일성 문제는 선형시간에 쉽게 풀릴 수 있다. 방법은 간단하다. 두 트리 T 1 와 T 2 에서 먼저 center nod 23 를 찾아서 이것을 root로 해서 rooted ordered tree 를 만든다. 그리고 각 subtree를 왼쪽에서 오른쪽으로 정렬할 때, subtree의 갯수가 많은 쪽은 선호해서 정렬한다. 만일 같은 갯수라면 다시 그 subtree의 subtree의 ordering으로 순서를 정한다. 이렇게 정리된 트리를 표준형(Canonical form)으로 정리된 표준형 트리 (canonical tree) 라고 하는데 이 트리를 Preorder 방식으로 traversal하면 선형시간에 두 트리가 동일한지를 쉽게 판단할 수 있다 트리의 Center node는 가장 점 terminal node까지의 거리가 최소가 되는 노드이다. 트리에서 이 center(정확하게는 vertex center) 노드는 최대 2개까지 존재하면 만일 2개가 존재할 경우에는 반드시 인접한다. 24 각 트리의 center node각 최대 2개씩 있을 수 있으므로 정확하게는 각 4 번의 작업, 즉 각 트리의 center node등의 모든 쌍에 대해서 검증작업을 하면 된다.

21 2.3 그래프의 전역특성을 이용한 유사도 측정 21 n m p d q a C c C Tree Center a b c p q r s d b m n Undirected, Unrooted Tree Canonically Ordered Tree Figure 9: 트리의 경우에는 표준순서화를 통하여 쉽세 두 트리가 동일한지를 검사할 수 있다. 트리의 중심 (Center of tree) 를 잡아서 그 subtree들을 왼쪽부터 순서대로 배열한다. 그 순서는 subtree의 노드 수가 많은 순서대로 배치를 고 이것을 모든 subtree 에 대하여 recursive하게 적용하여 모든 중간 노드에서 그 노드의 subtree들은 노드의 갯수에 따라서 왼쪽에서 오른쪽 순서대로 배치한다. 만일 그 subtree의 노드 수가 같으면 그 subtree의 subtree 중에서 가장 큰 것을 기준으로 tie breaking을 한다. 2.3 그래프의 전역특성을 이용한 유사도 측정 계산적으로 불가능한 isomorphism 검사를 대신하는 방법으로는 그래프 자체를 비교하는 것이 아니라 그래프의 주요한 특성치를 비교하는 것이다. 이러한 접근이 전역특성을 이용한 유사성 검사 접근법이다. 예를 들어 두 그래프를 비교하는 가장 간단한 방법은 그래프 G(V, E)의 노드 수 ( V )와 edge 수를 비교하는 것이다. 물론 그래프의 노드수와 에지수가 같다고해서 두 그래프가 우연히 같을 가능성은 거의 없지만 일단 이 둘이 같으면 그나마 두개의 그래프가 같을 가능성이 있다는 점에서 검사에 관한 약간의 정보를 받을 수 있다. 다른 방법은 그래프의 특성 지표를 만들어 그래프 대신 이 지표를 비교하는 것이다. 즉 어떤 그래프 G a (V a, E a ) 를 두 개의 component를 가진 vector인 ( V a, E a ) 로 표시하여 이 vector를 대신 비교하는 것이다. 즉 두 그래프 vector간의 거리로 두 그래프의 위상적 유사도를 짐작하는 방밥이다. 이 방법이 가진 한가지 장점, 즉 그래프의 vector를 그래프 fingerprint로 이용해서 비교하는 방법은 비교대상 그래프의 크기가 아무리 커도 변환된 fingerprint 벡터의 크기는 항상 일정하다는 젬에서 계산상 유리하다 25. 이제 남아있는 문제는 이 그래프 fingerprint 25 아무리 그래프가 커다고 해도 fingerpint의 크기는 항상 일정하기 때문에 memory space면에서 유리

22 2.3 그래프의 전역특성을 이용한 유사도 측정 22 vector에 어떤 요소를 집어 넣을 것인가, 또는 그러한 vector component 를 몇 개나 넣을 것인가이다. 당연히 다양한 vector component가 많을수록 비교는 더 정교해질 수 있지만 항상 그런 것은 아니다. 이 방법은 그래프의 크기가 매우 커서 전체의 구조를 명시적으로 (explicitly) 확보할 수 없는 경우에 활용하기 좋다. 예를 들어 World Wide Web은 그 전체를 탐색하는 것 조차 불가능하기 때문에 이것들 간의 isomorphism을 찾는 것은 이론적으로나 실제적 으로 불가능하다. 가령 예를 들어 독일 전체의 internet interconnection 과 우리나라의 interconnection 을 비교하는 문제를 생각해보자. 이 경우에는 vertex 나 edge 자체가 생겼다가 없어지기도 하기 때문에 graph mapping을 이용하기는 매우 어렵다. 이 경우에 비교할 그래프에 hub site가 존재하는지, 또는 일정 이상 크기의 hub이 몇개나 존재하는지 또는 복수 개의 high-degree 노드 사이를 연결하는 shortest path의 길이가 서로 비슷한지 등을 비교하는 것으로 전체 그래프의 유사성을 대신 짐작할 수는 있을 것이다. 그래프의 전역특성 (global property) 지표 중 가장 단순한 지표는 노드의 수와 에지 (edge)수이다. 일단 에지의 수가 많으면 그래프가 조밀(dense)하다고 짐작할 수 있지만 그것이 complete graph와 가깝지 않는 한 에지 수는 가장 단순한 지표이다. 이보다 좀 더 나은 지표는 네트워크의 차수를 정렬한 그래픽 순서(graphic sequence)이다. 즉 전체 노드의 차수를 내림차순으로 정리한 vector를 해당 그래프 G의 그래픽순서라고 부른다. 즉 정렬된 차수는 graphics(g) = (d 1, d 2..., d n 1, d n ), 단 d i d i+1 를 만족해야 한다. 다음 그림-10은 그래프 G x 와 그 그래픽 순서 graphic(g x )를 보여주고 있다. 그런데 그래픽 순서가 같아도 두 그래프는 전혀 다를 수가 있다는 점이다. 아래 그림-11는 같은 그래픽 순서를 가지는 다른 모양의 그래프의 예를 보여준다. 이것으로 볼 때 단순한 차수의 나열 정도인 그래픽 벡터는 비교할 그래프의 특성을 나타내기에 부족함을 알 수 있다. 생물 네트워크의 초기 연구에는 네트위크의 차수분포가 가장 중요한 특성으로 받아 들여졌다. 그래프의 차수분포만 확실해지면 그것이 기반하여 전체 네트워크에서의 최단 거리, 평균거리, 연결도(connectivity) 26 를 유추하여 계산할 수 있었기 때문이다. 그런데 하다. 26 어떤 그래프를 분리하기 위하여 제거해야할 최소의 vertex(edge) 갯수는 vertex(edge) connectivity 가 된다.

23 2.3 그래프의 전역특성을 이용한 유사도 측정 G x graphic(g x ) = (7,5,4,3,2,2,2,2,1) Figure 10: 주어진 그래프와 그 그래픽 순서(graphic sequence). 그래프 노드에 표시된 숫자는 해당 노드의 차수(the number of incident neighboring vertices) 를 나타낸다. 새로운 분자생물학 실험기기가 속속 등장하고 대규모 실험이 가능해짐에 따라서 생겨난 많은 새로운 데이터들은 이전에 생물 네트워크의 구성 모형인 power-law, scale-free network의 특성과는 상당한 거리가 있음으로 보여주고 있다. 그 이유는 이전 실험에서 잡음을 충분히 제거하지 못했고 그것을 power-law 그래프로 over-fiiting한 결과라고 지 적하는 연구자도 있다. 특히 N. Przŭlj의 최신 결과에 따르면 PPI 네트워크는 scale-free 라기보다는 geometric graph에 훨씬 더 가깝다는 것이다[6, 7]. 최근의 이러한 새로운 결과는 생물 네트워크 연구의 새로운 방향을 제시하고 있다. 기하 그래프의 차수분포는 포아송 분포(Poisson Distribution)를 나타내고 있음이 잘 알려져 있다. G 1 G 2 graphic(g 1 ) = (2,2,2,2,2,2,2) graphic(g 2 ) = (2,2,2,2,2,2,2) Figure 11: 같은 그래픽 순서를 가지고 있지만 서로 다른 그래프의 예. 왼쪽 그래프는 disconnected graph 이지만 오른쪽 그래프는 하나의 연결 component로 구성되어 있다. 어떤 개체의 전체적인 특성을 나타내는 가장 일반적인 방법은 특성의 분포 (distribution) 를 보여주는 것이다. 예를 들어 정규분포에서의 평균과 분산은 전체 집단의

24 2.3 그래프의 전역특성을 이용한 유사도 측정 24 특성을 보여주는 가장 대표적인 지표값이듯이 그래프의 차수 분포(degree distribution), 군집지수(clustering coefficient), 군집 스펙트럼 (clustering spectrum), 네트워크의 지름 (network diameter), 최단거리 스펙트럼은 그래프의 상세특징을 보여주는 실용적인 지표로 쓰이고 있다. 앞서 설명한 바와 같이 차수의 분포는 그래프 모형을 결정하는데 중요한 역할을 한다. 차수의 분포가 지수분포를 따를 경우 해당 그래프는 연결차수가 매우 높은 hub node가 존재하는 power-law graph, 또는 scale-free network가 된다. 만일 그 구성이 scale-free network이라고 한다면 전체의 모양을 쉽게 짐작할 수 있다. 예를 들어 degree 1인 노드의 수가 10000개 이고 degree 2인 노드가 5000 라면 비율은 1/2로 줄어들기 때문에 그 scale factor는 log 2 (1/2) = 1 이 된다. 따라서 차수가 3인 노드의 수는 2500개 정도, 4인 노드는 1250개 정도가 될 것이라고 추측할 수 있다. 각 노드의 차수가 같으면 우리는 이것을 정규 그래프 (regular graph) 라고 부르는데 이같이 차수의 분포가 극단적으로 하나에 몰려있는 경우에도 그래프의 특성은 쉽게 파 악된다. 정규분포에 가까운 그래프 역시 전체 특성을 쉽게 확인할 수 있는데 k regular 그래프의 diameter는 O(log k G ) 임을 쉽게 알 수 있다. 이보다 좀 더 좋은 특성값은 군집지수 분포이다. 어떤 노드 v 의 군집지수는 v 의 이웃 노드(N(v))의 집합간에 연결된 edge 의 수로 결정된다. 만일 모두 연결되어 있다면 지수는 1이 되고, 만일 아무것도 연결되어있지 않다면 그 값은 0이 된다. 아래 그림-12은 군집지수의 예를 보여주고 있다. 군집지수는 v 의 이웃노드간 연결된 edge를 가장 많을 경우와 비교해서 비율로 나타낸 것이다. 즉 이웃들끼리 연결된 edge의 수가 E개라면 그 값은 E/ ( ) N(v) 2 로 정의된다. 만일 아래 그림-12의 (c)와 같이 이웃의 갯수가 5개이고 그들간 모두 연결되는 경우에는 10/ ( 5 2) = 1 이 된다. 전체 그래프의 군집지수는 각 노드 군집지수의 평균으로 계산된다. 그래프의 군집 스펙트럼 (clustering coefficient) 는 전체 노드의 평균 군집지수를 degree 별로 표시한 vector이다. 그래프나 네트워크에서 두 노드 x, y 의 거리(distance), dist(x, y)는 두 점을 연결하는 최단거리로 정의되는데 이 거리의 분포 정보도 그래프의 전역 특성을 나타내는 중요한 지표로 쓰인다. 그래프 G 의 지름 (diameter) 인 diameter(g) 는 max u,v G {dist(u, v)} 으로 정의된다. 그래프의 지름 모든 쌍간의 최던거리 중에서 최대값으로 정의되어 있는데

25 2.3 그래프의 전역특성을 이용한 유사도 측정 25 이 지름은 그래프 노드들이 얼마나 가까이 연결되어있는지를 설명해주는 좋은 지표가 된다. 어떤 생물 네트워크의 군집지수가 a이거나 또는 지름이 d라고 밝혀진 경우 이 결과를 어떻게 활용할 것인지는 아주 중요한 문제다. 그런데 그 값 자체만으로는 의미를 줄 수 없기 때문에 우리는 random graph를 만들어서 그 그래프의 군집지수나 지름을 랜덤 그래프의 그것과 비고하여 새로운 의미를 찾아낸다. 일반적으로 random graph의 지름은 O(log n) 임이 잘 밝혀져 있는데 만일 어떤 PPI의 지름이 이보다 훨씬 더 커거나 또는 더 짧을 경우에는 그 생물 네트워크 또는 PPI는 다른 어떤 의미있는 특성을 가지고 있을 것이라고 추측할 수 있다. 일반적으로 PPI와 같은 생물 네트워크들의 군집지수는 random graph 와 비교해서 훨씬 높음을 알 수 있는데 이런 사실을 이용할 수 있다. 그러나 네트워크의 전역적인 특성만으로 네트워크를 구분하기에는 아직 부족한 면이 많다는 것이 여러 논문에서 지적되고 있다. 예를 들어 전역특성은 거의 비슷하지만 전체적인 특성은 크게 다른 다양한 네트워크들이 이미 다른 연구에서 지적되고 있다[3]. 요약하자면 전역특성은 비숫한 생물 네트워크를 분류하는데는 도움이 되지만 그것 만으로는 부족한 것이 사실이다. 전역특성이 도움이 되는 경우는 서로 다른 네트워크를 분별하는데에는 유용하게 사용될 수 있다. 예를 들어 어떤 두 네트워크가 전역적 특성이 다를 경우라면 일단 이 두 네트워크의 특성은 다르다고 봐야 한다. 전역 특성은 서로 다름 (difference) 를 확인하는데에는 중요한 지표가 될 수 있지만 서로 유사한 특성을 가지고 있음으로 보여주기에는 초기 preprocessing step에서 사용될 수 있는 정도라고 할 수 있다. 예를 들어 어떤 두 미생물의 pathway network을 비교해서 한 개체가 다른 개체의 모델 (reference model) 이 될 수 있는지를 살펴보고자 할 때, 만일 두 network의 전역특성이 다르다면 일찍 비교대상에서 제외할 수 있어 전체 작업 일정을 단축시킬 수 있다. 게다가 대부분 우리가 얻을 수 있는 생물 네트워크 자체는 그 자체로 불완전한, 또는 실험상의 잡음이 많이 포함된 결과이기 때문에 전역특성을 이용한 네트워크의 유사성 비교는 아직 부족한 면에 많다. Web graph라든지 비생물적 개체에서 전역특성, 예를 들어 그래프 adjacency matrix의 eigenvalue, eigenvectors(특성값, 특성벡터) 는 유용한 도구이지만 이런 static한 그래프가 아닌 생물 그래프에서 전역특성은 신뢰할만한 지표는 되지 못하고 있다.

26 2.4 그래프의 지역특성을 이용한 유사도 측정 26 b a b a b a c v v v e c e c d d (a) (b) (c) Figure 12: 노드 v 의 군집지수를 계산한 3가지 예. v 의 이웃노드인 {a, b, c, d, e}끼리의 연결정도가 군집지수 계산에 사용된다. (a) 의 경우에 하나의 연결 edge가 없으므로 군집지수는 0/10=0.0, (b) 의 경우는 4개(점선으로 표시)가 존재하므로 4/10=0.25, (c) 의 경우에는 모든 가능한 쌍에 대하여 존재하므로 10/10=1.0 이 됨을 알 수 있다. 2.4 그래프의 지역특성을 이용한 유사도 측정 네트워크의 지역특성(local property)은 매우 중요한 개념이다. 생태계가 모두 연결되어 있고 인간의 두뇌 뉴런들이 조밀하게 연결되어 있지만 실제 신경세포의 예와 같이 구조롤 본다면 각 단위체들은 모두 주위의 몇 이웃들과만 연결되어 있다. 이들이 전일적으로 기작을 하여 전체가 하나의 제어구조상에서 움직이는 것 같이 관찰되지만 실제로는 bottom-up 구조로 연결되어있고 그 방식으로 동작을 하고 있다. 따라서 각 개체의 local 특성을 파악하는 것은 생물 네트워크 이해의 중요한 모멘텀이 될 수 있다. 실제 분자 생물학 기준으로 볼 때 어떤 기능이 개체의 전신에서 동시에 일어나는 것은 거의 없기 때문이다. 지역특성을 이용하여 두 그래프를 비교하는 기본적인 방법론은 기본 building block 을 먼저 정의한 뒤에 component를 이용하여 그 기본 component가 얼마나 존재하는지 를 비교하는 것이다. 가장 대표적인 방법이 graphlet 을 이용하는 방법이다. 이러한 방법을 composition analysis 방법이라고 부르는데, DNA 를 비교할 때 k-mer의 구성 성분을 비교하는 것이다. 즉 어떤 긴 길이의 DNA 를 유사성을 직접 string alignment 를 이용해서 비교하는 것이 아니라 2-mer 즉 AA, AC, AG, AT, GA, GG, GT, GC, TA,TG,TC,TT,CA, CG,CC, CT가 나타난 비율을 비교하는 방식이다. 이 방식은 결국 위에서 설명한 특성비교법과도 유사한 면을 가지고 있다. 이 방식을 Network Query에 기반한 방법이라고도 말한다. 즉 Query graph(graphlet) g Q 가 대상 그래프인 G a, G b d

27 2.4 그래프의 지역특성을 이용한 유사도 측정 27 에서 얼마나 자주 나타나는가를 비교함으로서 유사성을 짐작하는 것이다[10]. 비유하자면 두 개의 긴 문서를 비교할 때 몇 개의 단어를 던져서 그 단어가 두 개의 문서에서 나타난 비율을 조사해서 유사도를 비교하는 방법과 유사하다. 문서비교에서 이러한 방법은 TF-IDF(term frequency, Inverse-Document-frequency) 과도 본질적으로 같은 것이라고 할 수 있다. 그 중에서 가장 중요한 개념은 biological motif(모티브) 이다Motif[11]. 모티브란 작은 subgraph의 일종인데 전체적으로 그 발현빈도가 무작위 그래프에서의 평균 발생빈도이 상으로 자주 나타나는 생물학적 구조체이다. 평균이상으로 자주 나타나는 것은 대부분 그 안에서 어떤 특별한 기능과 의미를 가지고 있다. 예를 들어 한글을 글자단위로 분석 해볼 때 글자 은, 는, 이, 가 는 다른 random한 단위 문자의 출현빈도이 비해서 유의미하게 나타남을 확인할 수 있다. 이 비율의 의미가 말하는 것은 다른 random한 한글 한자에 비해서 은, 는, 이, 가 글자들이 뭔가 다른 기능을 한다는 것을 짐작할 수 있게 해준다. 누군가 영어를 전혀 모르는 외계인이 영어를 분석해본다면 a, an, the 가 훨씬 자주 나타남을 확인할 수 있을 것이다. 따라서 이 단어는 다른 단어와 비교해서 뭔가 다른 기능을 할 것임을 예상할 수 있고 그러한 방향으로 연구를 할 수 있듯이 뭔가 자주 나타나는 개체(frequent item)는 미지의 데이터 분석에서 아주 중요한 시발점이 된다. 생물학적 motif 27 라고 부른다. 그리고 이 motif를 찾아내는 일은 모든 분자생물학 에서 매우 중요한 초기 작업이 되고 있다. 그런데 여기에서 한가지 고려해야할 point가 있다. 우리가 자주 만나는 subgraph의 빈도를 random한 그래프와 비교를 해야하는데 그 random 그래프가 어떤 모양인가에 따라서 전혀 다른 의미로 해석할 수 있다. 이런 이유 때문에 생물 네트워크 연구에서 가장 중요한 것은 우리가 연구하려는 네트워크의 모형이 어디에 기초하고 있는가를 확인하는 일은 가장 선행되어야 하는 작업이다. 두 그래프를 지역적 특성에 기초하여 비교하는 최신 방법으로는 graphlet기법이 27 생물학적 motif는 정의가 명확하지 않는 buzz word이다. 서열연구에서도 일단 자주 나타나는 비슷한 substring을 찾는데 이것은 유전자의 기능을 조절하는 부분으로 유전자의 서열과 기능은 달라고 이 부분은 모두 비슷하다. 따라서 sequence에서 motif를 찾아내는 것은 유전자 사냥의 첫단계가 된다. 다른 비유를 하자면 file system에서 볼 때 file의 내용을 사용자의 의도에 따라서 제각각 이지만 file head 부분은 대부분 비슷한 구조를 가지고 있다. UNIX에서 i-node구조를 motif와 개념적으로 유사하다고 생각하면 된다. 따라서 미지의 disk에서 뭔가 의미있는 binary data를 찾아내려고 한다면 이러한 i-node motif부터 찾아야 할 것이다.

28 2.4 그래프의 지역특성을 이용한 유사도 측정 28 있다[12]. 이 방법은 graphlet이라는 단위 그래프가 두 그래프에서 출현하는 빈도를 기준하고 그 빈도 graphlet vector로 그래프를 대신 비교한다. Graphlet은 작은 몇 개의 노드로 구성된 모든 가능한 subgraph의 집합이다. 그림에는 5개 노드로 구성할 수 있는 30 개의 서로 다른 Graphlet이 있다. 우리는 이것을 이용해서 어떤 두 network N a 와 N b 에서 선택한 두 노드 x 와 y 가 지역적(locally)으로 얼마나 유사한지를 밝히고자 한다[12]. 여러 연구에서 이 방법이 활용되고 있다[13, 14]. 2-node graphlet 0 3-node graphlets node graphlets G 0 G 1 G 2 G 3 G 4 G 5 G 6 G 7 G node graphlets G 9 G 10 G 11 G 12 G 13 G 14 G 15 G 16 G 17 G 18 G G 20 G 21 G 22 G 23 G 24 G 25 G 26 G 27 G 28 G 29 Figure 13: 5개의 노드를 가진 모든 가능한 connected subgraph들의 graphlet이 된다. 단 disconnected graphlet을 고려하면 갯수가 너무 많아지므로 graphlet은 연결된 subgraph 만 고려한다. 그림에서 노드에 붙은 번호는 unlabelled graph에서 노드들의 서로 다른 위상 일변번호를 나타내고 있다. 이것을 automorphism orbit이라고 한다. 예를 들어 5 개의 노드가 하나의 Cycle 로 이루어진 graphlet의 경우 각 노드는 모든 위치에서 위상이 같기 때문에 서로 다른 orbit은 단 하나 뿐임을 알 수 있이다. 두 그래프의 각 두 vertex u, v 에서의 지역적 유사성을 비교하기 위해서는 해당 위 치에서 일정부분에 포함된 subgraph를 모두 찾아내서 그것의 출현빈도 분포로 graph similarity를 계산하는 것이다. 그런데 이 접근에는 2가지 문제가 있다. 하나는 아래 그림과 같이 d G 의 범위를 정하는 것이고 다른 하나는 그렇게 잘라낸 local subgraph을 어떻게 비교할 것인가이다. Graphlet에서 택한 방법은 이 u, v 에 걸쳐있는 graphlet의

29 2.5 네트워크 중심성(Centrality) 기반 분석 29 종류를 비교함으로서 그 노드들의 지역적 유사성을 이들의 graphlet 빈도로 짐작하고자 하는 것이다. v u d G d G G 1 G 2 Figure 14: 두 그래프 G 1, G 2 를 각각의 정점 v, u 에서의 지역적 유사성을 비교 한다. 첫번째 문제는 얼마나 넓은 지역 (그림에서 d G 로 표시) 을 선택할 것인가이고, 또 다른 문제는 그 기본성분 그래프의 출현빈도를 어떻게 비교하는가이다. graphlet을 이용하여 전체 네트워크를 bottom-up 상향식으로 분석하는 시스템으로는 GraphCrunch과 GRAAL이 있다. 이 도구는 생물학 그래프나 일반 위상적 그래프에 상관없이 Graphlet에 기반하여 그래프의 유사성을 비교해준다는 면에서 볼 때 범용성이 있다고 할 수있다[15, 10]. 그림-15에 나타는 예제 그래프의 각 orbit별 나타난 Graphlet의 갯수를 발췌하여 부분적으로 나타내면 다음 표와 같다. 이 73 원소를 가진 Graphlet vector, GV D(v) 와 GV D(u) 사이의 공간거리를 이용하면 두 노드의 지역 유사성(local similarity)를 계산할 수 있고, 모든 노드에서 나타나는 Graphlet의 빈도를 표시한 벡터 GV D(G a ), GV D(G b ) 로 만들어 두 벡터의 거리를 계산하면 이것은 전체 그래프의 유사성으로 사용할 수 있다. graphlet 기반의 GRAAL 시스템은 이후 6장에서 자세히 설명할 예정이다. orbit GDV(v) 네트워크 중심성(Centrality) 기반 분석 네트워크의 특성 지표 중에는 나타내는데 중심성 (Centrality)도 있다. 즉 네트워크에서 중심 이 어디에 있는가를 판별하는 것으로서, 이것 자체로 두 네트위크의 동일성을 검사하기에는 크게 부족하지만 네트워크 분석의 초기단계에서 활용될 수 있다. 두

30 2.5 네트워크 중심성(Centrality) 기반 분석 30 a b a b a b c c c e d e d e d 5 G 0 2 G 1 a b a b a b c c c e d e d e d 2 G 2 2 G 2 2 G 2 a b a b a b c c c e d e d e d 1 G 2 1 G 2 can not be G 2 due to (c,d) edge a b a b c c e d e d 2 G 3 1 G 5 Figure 15: Sample Graph의 노드 v 에 포함된 다양한 Graphlet. G 0 는 하나의 edge인데 이런 것이 모두 5개 존재한다. G 1 은 path의 길이가 2인 것으로 한 끝에 븥어 있는데 vertex induced subgraph중에 1번 orbit을 포함하고있는 graphlet은 모두 2개 뿐임을 알 수 있다. 같은 방식으로 살펴 볼 때 orbit 2번이 v 에 접한 경우는 모두 8개임을 알 수 있다. 네트워크의 중심을 먼저 매칭 (정렬) 시킨 후 나머지를 그리디 (greedy) 하게 정렬하는 방법을 대부분 정렬 알고리즘이 사용하고 있는데, 이 경우 첫 정렬 시작점을 찾을 작업에 네트워크 중심을 활용할 수 있다. 그런데 이 그래프 중심은 우리가 어떻게 정의하는가에 따라서 달라진다.

31 2.6 생물 네트워크 연구의 최근 이슈 31 가장 단순한 중심을 차수중심(degree centrality)이다. 이것은 전체 노드 중에서 가장 차수가 높은 노드를 중심으로 보는 관점이다. 그 다음 근접중심 (closeness centrality) 는 다른 전체 노드와의 거리의 합 (또는 최대값) 이 가장 작은 지점을 찾는 방식으로 결정된다. 이것은 그래프 이론에서 말하는 센터 노드 (center node) 이다. 물론 center node는 한개인 경우가 대부분 이지만 문제에 따라서는 복수개인 k-center를 찾아야 하는 경우도 있다. scale-free network에서 차수중심 노드와 근접중심 노드는 같아질 가능성이 높지만 일반적인 그래프에서 이 두 중심은 아무런 관계가 없다. 예를 들어 도시 (city)로 비유할 때, 도로가 많이 연결된 신흥개발지는 연결차수가 높은 반면 지리적 중심은 아닌 경우가 많다. 유럽 대부분 도시에서 근접중심은 이전 도시가 생길 때 만들어진 구도시 (Old town)에 존재한다. 또 다른 중심성은 사이중심(betweenness centrality)으로 그래프에서 임의의 두 지점 을 연결하는 최단거리가 얼마나 그 지점을 많이 지나가는지의 정도로 결정된다. 즉 어떤 노드 x를 거의 모든 쌍의 최단 경로 path(u, v), u, v G(V )가 지난다면 이 지점은 사이중 심이 된다. 지리적으로 표현하자면 교통의 중심지가 이 사이중심 노드애 해당될 것이다. 그 외에도 다양한 중심노드에 대한 정의가 있으므로 자세한 내용은 Ref-[9] 을 참조하면 될 것이다. 이 네트워크 중심지 비교는 두 네트워크가 유사하다는 것을 밝히는데에는 도움이 크게 되지 않지만 두 네트워크가 상이하다는 것을 빠르게 확인시켜주는데에는 매우 효율적인 지표가 된다. 따라서 네트워크 DB에서 탐색작업을 할 때 candidate space 를 줄여주는 효과가 있다. 즉 두 네트워크의 중심 의 위치나 모양이 크게 다르다면 이 네트워크는 매우 상이한 구조라는 것을 알 수 있기 때문에 고려대상에서 바로 제외시킬 수 있다. 2.6 생물 네트워크 연구의 최근 이슈 최근의 새로운 방법 중에서 인공지능이나 자연어 분석, 자동추론(automated deduction) 에 사용되는 belief propagation network 모형을 이용하는 방법이 제안되었다. 일반적인 그래프 매칭 알고리즘의 휴리스틱 버전들이 대부분 local similarity를 이용해서 유사한 지역을 확장해자는 것에 착안하여 이런 과정은 Loopy Belief Propagation(LBP)과 유사한 것에 착안하여 LBP를 수정하여 그래프 매칭에 이용하였다. 또한 이들은 spectral graph

32 2.6 생물 네트워크 연구의 최근 이슈 32 이론과 주성분 분석 (Principle Component Analysis, PCA) 를 결합하여 부그래프 매칭 문제 풀이법도 제시했다. 그 부산물로서 periodic pattern이나 평균출현 횟수에 비하여 출현빈도가 훨씬 떨어지는 infrequent pattern을 찾아낸다는 점에서 의미를 가진다고 보인다[16]. 그러나 필자의 관점으로 볼 때 이런 복잡한 heuristics이 실제 전통적인 graph 이론 기반의 combinatorial 해법보다 더 나은지에 대해서는 회의적이다. 이러한 방법들은 특정 데이터에 대해서 overfitting되기가 쉽고 그 내부 성능을 조정할 수 있는 많은 주절변수가 있기 때문에 만일 처음 수행했을 때 만족할만한 성능이 나온다면 몰라도, 그것을 조정해서 우리가 원하는 쪽으로 성능을 개선한다든지 또는 새로운 기능이나 관찰지표를 추가하는 것은 상당히 어려운 일이라고 생각된다. 참고문헌[16] 에서 실험에 사용한 데이터의 크기도 그닥 큰 편이 아니라 이 방법의 현실적 실효성에 대해서는 의문이 남아있다. 하지만 다양한 그래프 알고리즘을 응용해서 그래프 유사도 문제에 접근하려는 시도의 일환으로의 작은 가치는 있다고 하겠다. 향후 기존의 AI나 machine learning 기법을 응용한 네트워크 분석이 앞으로 많이 제 시될 것으로 예상된다. 그 이유로는 이전보다 computing power가 매우 높아졌고 다양한 parallel 계산이 가능해졌기 때문에 Support Vector Machine이나 Deep Learning과 같이 이전에는 단순히 이론적인 모형으로만 제시된 알고리즘을 실제 거대 생물네트워크에 적용할 수 있게 되었기 때문이다. 그러나 방법이 아무리 새롭다고 해도 그 성능이 수준에 미치지 못한다면 그 방법만으로의 가치는 떨어진다고 할 것이다. 성능의 불안정성, 사용에서의 불편함, 직관적인 사용자의 간섭이 어려운 것은 AI 기반의 네트워크 정렬 도구들이 공통적으로 가지는 단점이라고 보인다. 앞에서 설명한대로 생물 네트워크가 어떤 그래프 모형을 따르는가를 확인하는 것은 매우 중요한 문제이다. 왜냐하면 그러한 근본적인 가정이 없으면 어떤 과학적인 모형이나 추론이 불가능하기 때문이다. 특히 생물학의 특성상 모든 가능한 실험을 할 수 없기 때문에 네트워크의 특성을 수준별 28 로 확정하기 위한 많은 노력이 생물학 뿐만 아니라 물리학, 전산학에서도 이루지고 있다. 초기에는 자연계 대부분은 네트워크는 Random graph중에서 power-law를 따르는 scale-free graph라는 이론이 대세를 이루었지만 추후 28 분자단위인지, 세포단위인지, 기관단위인지 아니면 개체나 생태계 수준의 거대 단위인지를 미리 결정해야 한다.

33 2.6 생물 네트워크 연구의 최근 이슈 33 새로운 실험의 결과는 이런 모형과는 다른 결론을 보여주었다. 가장 대표적인 결과는 PPI는 geometric graph에 훨씬 가깝다는 연구[6] 와 같이 생물 네트워크는 우리가 어떤 관점으로 보는가에 따라서 전혀 다른 모형으로 될 수 있다. 따라서 네트워크 자체에 어떤 불변의 특징이 존재하는 것이 아나라는 식의 배반된 결과가 속속 확인되고 있는 상황이다[17, 18, 19]. 앞으로도 이 논란은 최신의 실험기기에 의한 실험결과가 만들어짐에 따라서 계속 논란이 될 것으로 예상된다.

34 3 생물 네트워크 연구 개요 34 3 생물 네트워크 연구 개요 3.1 생물 네트워크 유사도 연구의 목적 Next Generation Sequencing 기술과 같은 새로운 장비에 의해서 엄청나게 빠른 속도로 새로운 실험결과가 쏟아져 나오고 있다. 그 결과 새로운 생물학적 사실들도 속속 알려지고 있는데 특히 이전의 sequence 연구에서 확장된 생물학적 네트워크 모형이 최근의 주요 연구주제로 떠오르고 있다. 그러나 이러한 생물 네트워크 (Biological Network) 연구는 아직도 초보적 수준에 머물러 있다. 어떤 생물학적인 연결 관계 (interconnection relation) 도 이를 추상화하면 결국은 그래프 이론적 모형으로 나타낼 수 있다. 그래프 이론은 매우 다양한 위상적 관계를 나타내기 아주 적합한 도구이기 때문에 그래프 이론적 모형과 그 알고리즘을 연구하는 것은 생물 네트워크의 특성과 숨어있는 사실을 찾아주는데 중요한 도구가 된다. 특히 그러한 상호작용 그래프의 크기가 커짐에 따라서 큰 크기의 그래프를 다루는데 필요한 알고리즘의 성능은 갈수록 중요해지고 있다. 생물 네트워크 모형은 어떤 현상을 다루는가, 그 기본 개체가 무엇인가에 따라서 매우 다양하게 분류될 수 있다. 생물 네트워크를 나타낸 그래프에서 각 노드, 또는 vertex는 특정 유전자 (gene), 단백질, metabolite가 될 수 있으며 또한 그들의 결합체로도 될 수 있다. 그리고 그 그래프에서 edge 는 기능적 상호작용 (화학적 상호작용) 을 나타낼 수 있다. 예를 들어 PPI(protein-protein interaction) 네트워크에서 node는 하나의 단백질이 될 수 있으며 그들 간의 edge (x, y) 는 두 단백질 x 와 y 가 결합 (physically bind) 할 수 있을 때 주어진다. 만일 세포 안에 존재하는 모든 단백질에 대하여 PPI 네트워크를 실험적으로 구성한다면 그 크기는 엄청나게 커질 수 있다. 특히 그 그래프에서 edge 의 개수는 노드수의 제곱으로 커지기 때문에 전체 가능한 모든 단백질 쌍에 대하여 실험하는 것은 불가능하다. 또한 같은 단백질을 node로 구성하더라고 다른 기능, 예를 들어 transcriptional regulation, cell signalling, 유전자들 사이의 기능적 연관(예를 들어 synthetic lethality), metabolism(대사과정), neuronal synaptic connection에 기초하면 우리는 새로운 네트워크를 구성할 수 있다. 대사과정 (metabolism) 도 그래프로 묘사될 수 있는 대표적인 생물 네트워크이다.

35 3.1 생물 네트워크 유사도 연구의 목적 35 이 대사 네트워크에는 2종류가 존재하는데 한 종류의 metabolic network에서 node는 chemical compound를 나타내고, edge 는 두 화합물이 동일한 화학적 반응에 동시에 관여할 때 설정된다. 즉 이 그래프에서 C (x, y) 라는 edge가 의미하는 바는 화합물 x 와 y 가 C라는 특정 화학반응에 동원된다는 것을 의미한다. 이와 다른 metabolic network 에서 node는 특정 효소 E i 가 담당하는 각각의 화학반응 r i 을 나타낸다. 이 경우 edge (r i, r j ) 는 두 화학반응 r i, r j 가 적어도 하나 이상의 반응 화합물, 또는 기질 (substrate), 또는 생성물 (product) 을 공유한다는 것을 의미한다. 또한 신호전달, 유전자 조절 (gene regulation), lethal interaction(치사 상호작용) 29 의 동작과정도 그래프로 모형화가 가능하 다. 그리고 세포 신호전달 체계는 가장 대표적인 생물학적 통신 네트워크라고 할 수 있다. 이 신호체계는 세포가 스트레스와 같은 외부 영향에 어떻게 대처할 것인지를 결정하는 매우 중요한 네트워크이다. 이 네트워크에서 노드는 bio-molecule (또는 그 복합물) 이 되고, edge는 각 개체간의 전달신호의 통로를 나타낸다. 각 유전자들 간의 상호 조절작용을 나타내는 유전자 조절 네트워크(Gene Regulatory Network, GRN) 도 대표적인 생물 네트워크이다. 어떤 유전자 a가 일정 수준이상으로 발현되면 그 영향으로 다른 유전자 b 를 up-regulation 시키거나 또는 down-regulation 시키는 역할을 하는데 이것을 directed graph로 모형화 한 것인 GRN이다. 그런데 GRN 은 단순한 그래프 모형에 dynamics까지 더해진 셈이 된다. 특정 유전자가 발현되는 정도에 따라서 다른 유전자에게도 영향을 미치고, 그것이 결국 자신에게 다시 feedback 되기 때문에 GRN을 simulation 하는 일은 복잡한 닫힌계에서의 미분방정식을 푸는 문제로 결국 수렴하게 된다. GRN을 이해하고 예측하는 것은 결국 모든 생물현상을 환원적 레벨에서 이해하는 것이 되기 때문에 가장 근원적인 문제가 되고 있지만 실험 데이터의 오차나 오류, 모형의 정교성에서 미진하기 때문에 현실적 실용성은 미진한 편이다. 그러나 부작용이 최소화된 신약개발이나 유전자 치료에 이 GRN은 궁극의 해답을 주기 때문에 GRN의 분석에 많은 투자가 되고 있다. 이상 살펴본 바와 같이 생물학의 다양한 레벨에서 거의 모든 생명현상은 그래프로 묘사될 수 있기 때문에 다양한 종류의 생물 네트워크를 탐구하는 것은 궁극적인 연구주 제가 된다. 학문적으로 볼 때에도 네트워크 연구는 계산생물학 (computational biology) 29 Synthetic lethality arises when a combination of mutations in two or more genes leads to cell death, whereas a mutation in only one of these genes does not, and by itself is said to be viable.

36 3.1 생물 네트워크 유사도 연구의 목적 36 나 시스템 생물학(systems biology)의 최종 도달점이 될 것이다. Figure 16: 전형적인 Biological Network의 예 [8]. 그림 a)는 PPI 네트워크의 도식이다. 각각 상호작용하는 단백질들끼리 Edge로 연결된 그림이 Tree형태로 오른쪽에 있다. 그림 b) 는 Baker가 구현한 PPI 네트워크 모형이다. 이 그림은 Database of Interaction Protein (DIP) 에서 다운받을 수 있다. 그림 c) 는 b) 그래프의 연결관계를 adjacency 관계로 나타낸 것이다. 그림의 각 entry에 있는 점은 두 개 단백질이 상호작용을 함을 나타낸다. 그림에 나타나있듯이 하나의 단백질과 상호작용을 하는 단백질의 갯수는 대략 power-law 분포를 따르고 있음을 알 수 있다. 즉 많은 것은 아주 많고 sparse한 것은 상당히 sparse하다. 이 현상은 PPI network이 전형적인 Complex Network의 일종임을 잘 보여주고 있다. 그림 d) 는 상호작용 단백질 관계를 spoke형과 행렬형으로 표시한 것이다.

37 3.1 생물 네트워크 유사도 연구의 목적 37 현대 생물학은 sequence에서 network으로 이동하고 있다고 말할 수 있다. 따라서 충분한 실험과 빠른 실험기구가 만들어낸 네트워크 데이터만 있으면 생물학적 모든 사실이 밝혀질 것인가에 대한 기대가 있을 수 있다. 그러나 그런 희망에는 여러 장애가 있다. 가장 큰 장애요소는 실험자료 안에 수많은 실험 오류와 인간의 힘으로 제어할 수 없는 본원적인 잡음(noisy)의 존재다. 따라서 실제 현상을 그대로 묘사하는 네트워크를 인간이 구할 수 있는 것은 거의 불가능한 일이라고 여겨지므로 실험결과에서 빠진 부분은 실제 실험이 아닌 추론이나 예측으로 메꿔야 한다. 이 때문에 동일한 실험으로 부터 만들어진 생물 네트워크의 분석결과끼리 서로 상반되는 결론에 도달하는 경우도 드물지 않게 나타나고 있다. 생물 네트워크 분석의 또 다른 장애는 앞에서 말한 바와 같이 이용가능성이 높은 그 래프 문제는 대부분 NP-complete류의 intractable problem이기 때문에 아무리 계산력이 좋거나 시간이 많아도 최적의 결과를 얻을 수 없다는 것이다. 그러나 한가지 유념해야 할 것은 생물학적 분석에서는 최적의 결과를 얻은 알고리즘을 개발하는데 최종 목적을 두어서는 안된다는 것이다. 이론전산학에서 추구하는 엄밀한 알고리즘보다 유연한 다양 한 휴리스틱이 생물 네트워크 연구에서 더 유용하기 때문에 하나의 최적결과 생산에만 매몰되오서는 좋은 시스템을 개발할 수 없다. 특히 본 보고서에서 소개하는 네트워크 정렬 (Biological Network Alignment, BNA) 의 다양한 알고리즘이 다소 ad hoc하게 보인다고 할지라도 그것을 실험의 유용성면으로 의미가 있으면 충분히 그 가치를 인정받을 수 있다 생물 모듈의 기능예측을 위한 네트워크 비교 생물 네트워크는 그 대상이 되는 생물체의 종과 구성된 생물학적 단위가 어떤 수준인지에 따라서 달라진다. 예를 들어 최상위인 생태계(ecology) 수준인지 아니면 아주 낮은 분자 단위인지, 아니면 그 중간 상위 단계인 세포 내에서의 신호전달 단계, 또는 유전자간의 상호작용인지에 따라서 구성되는 네트워크는 달라질 수 있다. 만일 하나의 model 생물에 대해서는 우리가 그 내부 작용에 대하여 잘 알고 있다고 하자. 예를 들어 우리는 전형적인 모델생물인 애기장대나 대장균에 대해서의 거의 모든 수준에서의 생물학적 동작을 우리가 잘 알고 있다. 이것이 가능한 이유는 이런

38 3.1 생물 네트워크 유사도 연구의 목적 38 reference model organism에 대해서는 다양한 방법의 실험이 가능하기 때문이다. 즉 특정 유전자의 기능이 어떤 것인지, 만일 그 유전자의 기능을 knock-out 시켰을 때 전체에 어떤 영향을 주는 것인지를 실험으로 확인할 수 있다. 그러나 그 보다 상위 생물체인 포유류의 경우에는 이런 조작적 실험이 불가능하다. 왜냐하면 상위의 고등동물일수록 유전자 수준의 조작은 생물의 생존자체를 불가능하게 만들기 때문에 분자유전학적 조작 실험은 할 수가 없다. 특히 인간의 경우에는 현실적으로도 이런 실험이 불가능하다. 배아 상태에서 유전자조작을 하면 거의 대부분의 사산이나 유산이 되기 때문에 실험을 지속할 수가 없으며, 또한 윤리적으로 인간을 대상체로 삼는 실험은 가능하지도 않고, 이런 일은 법으로 엄격하게 제한을 받고 있기 때문이다. 이런 경우 미지의 생물 단위, 예를들어 인간 유전자의 기능을 알아내려면 어떻게 해야 할 것인지가 현대 생물학의 과제이다. 이 경우 인간 유전자 네트워크를 다른 모델 생물의 유전자 네트워크와 비교해서, 그 연결구조가 비슷한 네트워크를 찾으면 그 mapping되는 구조를 이용해서 기능이 알려지지 않은 유전자의 기능을 짐작할 수 있다. 이 과정을 Projecting Functional Annotation 30 이라고 부른다. 이렇게 두 종의 네트워크를 비교하면 기능상으로 비슷한 역할을 하는 것으로 생각되는 개체를 발견할 수 있다. 이런 관계를 homologous하다고 표현한다. 예를 들어 사람의 유전자 g 5 6과 고릴라의 유전자 G x 110이 homologous하다고 표현하는 것은 그것의 자체 서열구조상으로도 유사하고 세포내에서도 비슷한 기능을 하는 유전자라는 것을 의미 한다. 특히 homologous한 관계는 서로 다른 종의 단백질 서열에서도 확인이 가능하다. 만일 homologous한 두 종의 단백질이나 유전자가 진화과정에서 공통 조상에서 갈라져 나온 것이라고 믿어지면 두 개체는 서로 orthologous하다고 표현한다. 그리고 또 다른 개념인 paralogous도 중요한 개념이다. paralogous는 하나의 종에서 하나의 유전자가 자체 내에서 복제(duplication)을 통하여 디른 곳에 새롭게 나타난 것을 말한다. 비유를 들어 설명하자면 최초의 실용적 tablet computer를 ipad라고 한다면 이후 이것을 응 용해서 만들어진 삼성제품이나 소니 제품은 모두 ipad와 기능적으로 homologous라고 할 수 있을 것다. 그리고 삼성의 갤럭시 제품군에서 서로 크기가 조금씩 다른 제품은 삼성이라는 동일종 내에서의 paralogous관계에 있다고 말할 수 있을 것이다. 분자생물학 30 분자생물학에서 annotation이란 알려지지 않는 특성을 밝혀서 그에 관련된 정보를 추가하는 작업을 말한다. annotated gene이란 대략의 기능이 알려진 유전자를 말한다. annotation이 안된 유전자란 서열 상으로만 보았을 때 유전자로 판단된 DNA seuence를 말한다.

39 3.1 생물 네트워크 유사도 연구의 목적 39 연구, 유전체 연구를 좁혀 표현하라고 한다면 결국 homologous한 gene들을 모든 종에서 찾아내는 작업이라고 할 수 있다. 이미 생물학에서는 각종 종의 유전자들에 대해서 이들간 orthologous한 그룹을 연구한 결과를 제공하고 있다. 그것은 Clusters of Orthologous Group(COG) 라고 불리는 데이 터베이스이다[20]. 그리고 이와 유사한 진핵생물체의 orthologous그룹에 대한 대형 DB 인 Inparanoid도 이 목적으로 제공되고 있다[21]. 특히 COG DB는 고등동물의 유전학 연구에서 새로운 유전자의 기능을 찾아내는데 매우 중요한 역할을 하고 있다. COG 는 서열 탐색도구인 BLAST를 이용해서 특정 단백질 (실제로는 유전자의 일부) 과 가장 matching이 잘되는 최상의 3개의 서열을 찾아서 이것을 확장시켜 만들어진 DB이다. 그리고 새로운 단백질 서열이 제시되면 그것을 BLAST로 확인하여 이미 구성된 COG DB 에서 가장 matching이 높은 3 개의 COG node 를 찾아서 그들과 새로운 연결을 만들어 COG DB에 추가하는 식으로 DB가 확장되고 있다 생물학적 핵심기능과 보존 지역(Conserved Region) 앞에서도 잠시 설명했지만 생물 시스템은 다양한 하위 모듈로 분해 (decompose) 할 수 있는 것이 특징이다. 즉 다단계의 계층구조 개체, 기관 (organ), 세포, 단백질등의 하위 기능모듈 (functional module) 로 분해하여 접근할 수 있다. 세포내 상호작용체 (cellular interactome) 인 단백질 작용 네트워크 (PPI), metabolic pathway, metabolic network, 신호전달 경로 (signal transduction network) 은 대표적인 세부 네트워크이다. 그런데 우리는 다른 종간의 각종 생물 네트워크가 완전히 다르지 않음을 알고 있다. 예를 들어 사람이나 대부분 유인원류의 유전자 네트워크를 보면 상당히 일치하는 부분이 많음을 볼 수 있다. 그래프 이론적으로 볼 때 두 그래프 또는 복수개의 그래프에서 어떤 특정한 subgraph G s 가 공통적으로 존재한다면 이 subgraph가 대표하는 기능은 매우 중요한 역할을 하고 있음으로 예상할 수 있다. 이렇게 종간의 서로 다른 특성을 무시하고 공통 적으로 존재하는 어떤 기능은 그 종들에서 가장 핵심적인 기능을 담당하는 경우가 많다. 어떤 종이 진화과정에서 갈라져 나올 때 가장 중요한 기능은 그대로 전달되어야만 새로 변화된 개체가 생명을 유지할 수 있기 때문에 이렇게 보존되는 (Conserved)기능을 찾는 일은 핵심기능을 찾는 일과 같아진다[10]. 따라서 우리가 관심 가지고 있는 Network Local Alignment가 찾아주는 공통 모듈 (Common subgraph) 을 찾는 일을 매우 중요한

40 3.1 생물 네트워크 유사도 연구의 목적 40 의미를 가진다고 할 수 있다. 예를 들어 뒤에 소개할 네트워크 정렬도구인 pathblast[22]는 이스트(S. Cirevisiae) 와 장염의 원인균인 헬리코박터 파이로리 (H. phylori) 균의 pathway를 상호 비교하여 놀라울 정도로 비슷한 pathway를 발견하는데 성공했다. 두 종의진화적 거리가 가깝지 않음에도 불구하고 이런 공통의 pathway가 보존되고 있다는 사실은 여러 생물학자들의 관심을 끌기에 충분했다. 이를 이용하면 각 종에서 알려지지 않는 유전자의 기능을 추론하는 것은 이전에 비해서 훨씬 용이하게 되었다. 설사 그 추론된 기능이 정확하게 일치하지는 않는다고 하더라고 예측되는 기능이 몇 가지로 정리되면, 이것을 실험으로 확인하는데 드는 비용을 획기적으로 줄일 수 있다. 예를 들어 네트워크 정렬도구인 MaWASh와 NetworkBLAST-M, Graemlin[23] 은 이미 분석이 완료된 (annotated) 특정 종의 네트워크를 미지의 네트워크와 정렬 (alignment) 하여 미지의 기능을 추측하는데 유용하게 사용되고 있다 진화과정(Evolutionary Process) 추론 진화는 유전자 수준에서 볼 때 도태, 변이 (mutation), 전달 (transfer) 의 과정이며 특 히 mutation은 종 차원의 진화를 발생하는 가장 중요한 진화 event이다. mutation은 단백질 상호작용 규칙을 변화시키고, 대사 반응 (metabolic reaction), 유전자 수준의 반응 (genetic reaction) 의 변화를 발생시킨다. 이런 변화의 전과정을 추적하는 과정을 진화적 계통분류학 (evolutionary phylogenetics) 이라고 할 수 있다. 우리는 수억년 전의 진화과정을 볼 수도 없고 또한 재현할 수도 없기 때문에 그것을 유추하는 방법은 유전자, 또는 DNA, protein 수준에서 일어난 변화를 바탕으로 계통분석 (phylogenetics) 이라는 수학적 과정으로 이것을 유추한다. 이 작업에서 가장 선행되어야 하는 연구는 두 종간의 단백질 네트워크를 비교하는 것이다. 특히 단백질 네트워크의 정렬(alignment)를 통하여 빠진 모듈, 새로 추가된 모듈, 바뀐 모듈을 찾아내는 것은 진화적 관계를 밝혀주는데 핵심역할을 한다. 가장 낮은 수준에서 단백질의 작은 변화는 구조의 작은 변화를 만 들어주고, 구조의 변화는 결국 DNA 서열의 변이 (mutation) 를 통하여 cellular process 의 변화를 만들어준다. 따라서 단백질 구성 (서열변화, 구조변화, 상호작용) 의 변화를 역추적하면 단계별 진화과정을 유추할 수 있고 이들을 직렬로 쌓아보면 전체적인 진화의 과정을 역으로 구성할 수 있다. 특히 이 작업이 중요한 것은 단순히 단백질 구조의 단위별

41 3.1 생물 네트워크 유사도 연구의 목적 41 변화에 기반한 homologous 연구로는 밝힐 수 없는 모호성을 해결해준다. 예를 들어 p a 가 p b, p c 와 homologous 값으로는 유사하다고 했을 때 p a 와 반응하는 다른 단백질들과의 그래프적 이웃관계를 이용한 진화분석을 통하면 그 모호성을 해결하는데 큰 도움을 줄 수 있다. 특히 세포사멸 (cell death) 에 관한 사실은 단순히 서열분석으로는 알아낼 수 없고, 다양한 진화적 과정 분석을 이용해야만 제대로 알 수 있다는 것이 최근 연구에서 속속 밝혀지고 있다. 예를 들어 2007년 Wagner는 어떤 서로 다른 생물학적 모듈간에 높게 연결된 노드들의 진화 속도가 한 모듈 내에서 같은 정도로 연결된 다른 노드들간의 진화 속도보다 훨씬 빠름을 진화분석 과정에서 밝혀냈다[24]. 또한 각 단백질은 개체별 진화를 하는 것이 아니라 어떤 상호작용을 집중적으로 하는 단백질 클러스터(cluster)를 중심으로 동시다발적으로 진화를 한다는 사실이 Yosef과 그의 동료들에에 의해서 새롭게 밝혀졌다[25]. 네트워크 비교의 의미는 다른 데에도 잇다. 포유류와 같이 겉모양 확인이 가능한 고등 생물들은 진화과정을 모양만으로(phenotype) 도 추측이 가능하지만 세균이나 바이러스와 같이 기능적 모양이 의미가 없을 경우에 그들간의 진화적 관계를 밝히는 것은 유전자 수준으로 내려가지 않으면 불가능하다. 예를 들어 대장균의 변종을 보면 인간에게 치명 적으로 작용하는 O-157(오 일오칠) 등을 포함하여 매우 많은데 이를 구분하여 그들간의 진화과정을 밝히는 일은 DNA수준에서만 분석이 가능하다. 따라서 우리가 살펴볼 네트 워크 정렬 및 비교 도구는 이런 극소 생물체들의 진화트리(evolutionary tree), 계통트리 (phylogenetic tree) 를 구성하는데 필수적으로 활용되고 있다. 요약하자면 생물체들의 진화를 추적하는 것은 현대생물학의 가장 중요한 연구주제인데, 이 과정에 가장 중요한 기법은 각 개체의 생물학적 네트워크를 정렬하고 비교하여 같고 다른 모듈을 찾아내는 것이라고 할 수있다 네트워크 비교분석을 통한 질병 분석 인간의 질병은 암, 자기면역 메커니즘의 고장, 호르몬 조절 과정의 고장, 선천적 유전적 질환, 외부 감염, 신경생리학적 혼란, 정신질환 등으로 분류될 수 있는데 이들은 모두 유전자의 구조적 결함 또는 대사작용 메카니즘의 결함으로 발생하는 것이다. 그것의 근원 은 결국 질병원인성(pathogen)에 의한 감염이나 유전자적 수준에서의 변이(mutation), 손실 (missing), 불필요한 확장 (extra copying) 에 있기 때문에 질병의 원인 분석은 분자