분자 상호 작용의 네트워크 분석 분자유전체의학 문정희

4.1 네트워크 표현과 계산 추상화 수준 DNA  RNA  단백질 서열  구조  기능 상호작용  네트워크  기능 열역학 법칙과 구조 –기능 관계는 단일 단백질 분자에 대한 유전자 정보 발현이 부가적인 흐름을 입증합니다 따라서 유전자(DNA)는 단백질 기능에 대한 모든 정보를 실질적으로 가지고 있으며, 또한 분자간의 상호작용은 네트워크에 얽혀 있고, 이러한 상호작용을 이해하므로써 정보의 흐름을 이해하는것이 필요하다. 생명이 창조되는 데 필요한 분자들의 상호작용 전부에 대한 정보를 유전자가 가지고 있다고 믿기는 힘들다. 반드시 분자들의 상호작용과 반작용의 공간과 시간에 대한 변화에 따라 변화하는 반응들도 반드시 분석에 포함된다.

분자 네트워크 ► 원소 ; 분자 또는 유전자 ► 이항관계: 분자 또는 유전자들간의 상호작용이나 두 원소간의 임 의의 관계 1) 원소 2) 이항관계 3) 네트워크 경로 유전체 집합체 이웃 계층트리 집단 생물학적 기능에 관한 정보는 상호작용하는 네트워크 정보로 쓰여 있다고 생각되며 네트워크는 원소와 이항관계로 이루어져 있다. 워소는 분자 또는 유전자를 말하며, 이항관계는 분자들간 도는 유전자들간의 상호작용이나 두 원소간의 임의의 관계를 말한다. 네트워크의 두가지 범주는 하나는 생물학적 지식을 표현한 것이고 나머지 하나는 이항관계로부터 계산된것이다. 경로 : 분자상호작용의 네트워크를 말하며, 물질 대사 경로, 신호 변환 경로, 세포 순환 경로, 발육 경로와 그 밖에 많은 조절 경로와 같은 세포 작용의 여 러가지 측면이 집적된 지식을 표현한다. 집합체; 분자 상호작용의 다른 네트 워크로써 그 안에서 분자들은 분자 기계장치나 부분 세포 유기체 안에서와 같은 안정된 복합체를 이룬다. 유전체: 유전자들의 네트 워크로써 선형, 원형 염색체내의 유전자들의 물리적 순서를 표현. 다른 형태의 네트워크는 이항관계 들로부터 유도한 것들이다. 다음그림의 다른 형태의 네트워크는 이항관계들로부터 유도한 것들이다. 이웃은 주어진 분자나 유전자에 대한 유사성 관계를 표현한다. 질의서열이 서열 유사성의 이항 관꼐에 의해 다중 서열로 연결되었을때, 서열 유사성의 검사는 이웃 네트워크의 전형적인 예가 된다. 클러스터는 전체 분자나 유전자들의 집합에 관한

그래프 G = (V, E) 점(V; vertex), 선(E; edge) (a) ⓐ (b) 연결 그래프(connected graph) 완비 그래프(complete graph) 방향 그래프(directed graph) 가중치그래프(weighted graph) (a) ⓐ ⓑ ⓒ ⓓ ⓔ ⓕ (b) a b c d e f a, c, d b, e c, d, f a b c d e f a b c d e f 1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 (c) 연결그래프는 임시의 두점 사이에 하나 또는 여러 개의 선들을 통해 연결된 경로가 존재하는 그래프이며, 완비 그래프는 두 점 사이를 연결하는 선이 반드시 존재하는 그래프에 다양한 생물한적 제약을 포함하려면 그래프 구조에 추가적인 다른속성이 필요하며, 이에 방향이 있는 선을 갖기 때문에 분자의 비가역적인 작용 경로를 표현하는데 사용할 수 있는 방향 그래프가 있습니다. 각 선에 가중치를 적용함으로써 신보 변환 경로에서 활성화와 억제를 구별할 수 있다. 가중치 그래프는 유사한 정도를 점수화하거나, 클러스터링 절차에서 점간의 유사성 점수나 거리를 정의하는데 사용하기도 한다. (a)는 가장 직관적이고 그래프의 위상적 특징을 가장 잘 나타낸 표준적인 표현이며, (b)는 각 점들의 연결정보는 연결 리스트로 표현된다. (c) 는 점들을 첨자로 갖는 행렬표, 대응대는 점의 쌍이 있으면1, 그렇지 않으면 0 이항관계의 개념과 그래프의 개념이 자연스럽게 연관되어 있다는 것  G1=(V1, E1), G2=(V2, E2) 는 동형이며 이는 수학적으로 같은 구조이고, 즉 한그래프의 점집합이 다른 그래프의 점집합 사이에 선들의 관계를 유지하는 일대일 대응관계(치환) 이 있다는 것입니다. G1=(V1, E1), G2 = (V2, E2)

◈ 공통 부분 그래프(common subgraph) • 그래프간의 공통의 부분 그래프를 찾는 문제 또는 부분그래프의 동형인쌍을 찾는 문제 (local similarity). • 두 그래프 G1과 G2 와 edge의 부분집합 E1’⊆ E1, E2’⊆ E2 에 대한 부분집합은 G1’ = (V1, E1’), G2’ =(V2, E2’) 정의된다. • 즉 삽입과 삭제가 없는 해당 부분이 완전히 일치하는 쌍을 말하며, 이 일치하는 부분은 여러 조각으로 떨어져 분리되어 있어도 상관없다. • 삽입과 삭제를 허용하려면, 같은 크기(cardinality)를 갖는 점의 부분집합을 고려한다. V1’ ⊆V1, V2 ⊆V2 을 각각의 그래프에서 같은 개수의 점들이 각 그래프에서 선택됨 • 최대 공통 유도 부분그래프는 V1’에서 유도된 G1의 부분그래프와 V2’에서 유도된 G2’에서 유도된 G2의 부분그래프의 동형인 쌍 중에서 크기가 가장 큰 것을 말한다. 경로 대 경로 경로 대 유전체 유전체 대 유전체 클러스터 대 경로 경로-경로, 경로 유전체, 유전체-유전체, 클러스터 – 경로 등의 분자 네트워크는 선이 방향성이 있거나 가중치를 갖기도 합니다 즉 유전체내의 유전자명, 생화학 경로내의 유전자 생성물질명에 따라서 그래프상의 점들의 이름이 바뀔때나 유전자쌍 또는 단백질 쌍의 서열 유사성에 따라서 점들의 이름이 바뀔때, 생물학적 비교문제는 두 그래프 간의 공통의 그래프를 찾는 문제 또는 부분 그래프의 동형인 쌍을 찾는 문제로 바뀌게 됩니다. 즉 서열 분석에서 두 서열의 유사한 부분 서열을 찾는 문제와 유사하게 됩니다. 두 그래프 G1과 G2 와 edge의 부분집합 E1’⊆ E1, E2’⊆ E2 에 대한 부분집합은 G1’ = (V1, E1’), G2’ =(V2, E2’) 정의된다. 즉 삽입과 삭제가 없는 해당 부분이 완전히 일치하는 쌍을 말하며, 이 일치하는 부분은 여러조각으로 떨어져 분리되어 있어도 상관없다. 삽입과 삭제를 허용하려면, 같은 크기(cardinality)를 갖는 점의 부분집합을 고려한다. V1’ ⊆V1, V2 ⊆V2 을 각각의 그래프에서 같은 개수의 점들이 각 그래프에서 선택됨 최대 공통 유도 부분그래프는 V1’에서 유도된 G1의 부분그래프와 ㅍ2’에서 유도된 G2’에서 유도된 G2의 부분그래프의 도인 쌍중에서 크기가 가장 큰것을 말한다.

(A,a) (A,b) (A,c) (A,d) (A,e) (A,f) 경로1 a b c d e f B-a B-b C-d D-f 경로2 (A,a) (A,b) (A,c) (A,d) (A,e) (A,f) (B,a) (B,b) (B,c) (B,d) (B,e) (B,f) (C,a) (C,b) (C,c) (C,d) (C,e) (C,f) (D,a) (D,b) (D,c) (D,d) (D,e) (D,f) (E,a) (E,b) (E,c) (E,d) (E,e) (E,f) 부분경로 B C와 b d 공백없이 일치된 쌍이며 B C D와 b  d f는 공백을 허용한 유사경로의 쌍으로 볼수 있다. 이 경우 공백은 진한 점선으로 표시된 d—f 오 나타난다. 따라서 공백을 허용한 부분 경로 정렬문제의 접근 방법은 인접하지 않는 두점을 가상의 선으로 연결하는것도 고려되는 것이다. 즉 공벽 벌점에 대한 적합한 선 가중치를 갖는 두개의 완비 그래프를 고려하는 것이다. 여기서 특징은 상호 인접한 점들의 클리크인데 5x6개의 점들에서 유도된 그래프로 푠현되며, 대응대는 선을 그어보면 두선이 모두 화살표일 수 있고또는 화살표 하나와 가상의선(공백)일 경우도 있다. 두개의 클리프를 가지고 있는데, 그중 하나인 서로 연결된 점들의 집합 (B,b)(C,d)(D,f)는 최적의 것이다. 이것이 유사한 부분 경로로 구분된다. 따라서 최대의 클리크를 찾는 문제는 NP-완비(nondeterministic polynomial time complete )문제의 범주로 들어가는데, 이슨 비결정 튜링 머신으로 다항 시간안에 풀 수 있다고 여겨지나, 실제로는 극히 어려운 문제중 하나이다. (a) 최대 공통 유도 부분그래프 (b) 최대 클리크( clique)

(b) A-B-C-D-E-F-G-H-I-J-K ⓐ ⓒ ⓑ ⓓ ⓚ ⓔ ⓖ ⓘ ⓗ ⓕ ⓙ 대응 A B C D E F G H I J K A-a B-b C-c D-d … A B C D E F G H I J K 클러스터링 알고리즘 ⓐ ⓒ ⓑ ⓓ ⓚ ⓔ ⓖ ⓘ ⓗ ⓕ ⓙ 경험적인 알고리즘을 이용해서 해결할 수 있는데, 두 그래프의 점간에 대응이 주어지면 연관된 영역을 부분적으로 일치시키려고 한다. 이때 가능한 대응의 수는 매우 제한되어져 있다. 대응에 연결되어 있음을 확인하고, 그 대응의 클러스터를 찾으면 문제를 해결할 수 있다. (b) A-B-C-D-E-F-G-H-I-J-K a-b-c-d-e-f-h-g-j-k-I

◈ 추이페포(Transitive closure) I  j, j  k ; I  k 어떤 그래프에 새로운 선을 전부를 추가한 그래프 ( 3단논법 추이 연산에 의해 닫혀 있는 그래프) ◈ 와셀(Warshall Alg.) for (j = 1; j <= N; j++) for (I = 1; I <= N; i++) if (a[i][j] ) for (k = 1; k <= N; k++) if (a[j][k]) a[i][k] = 1;  O(N3)

◈ 다익스트라(Dijkstra Alg.) 최단거리를 구하는 유명한 알고리즘 Greedy & Dynamic 방법 한 점에서 출발해서 각 정점에 최단거리를 구함

 O(N3) ◈ 플로이드(Folyed Alg.) for (j = 1; j <= N; j++) 모든 점에서 출발해서 출발 한 정점을 제외한 모든 정점을 도착점으로 하는 최단거리를 구하는 알고리즘. 추이폐포의 확장보다 효율적임. for (j = 1; j <= N; j++) for (i = 1; i <= N; i++) if (a[i][j] ) for (k = 1; k <= N; k++) if (a[j][k] > 0) if (!a[i][j] || (a[i][j] + a[j][k] < a[i][k])) a[i][k] = a[i][j] + a[j][k];  O(N3)

◈ 최소확장트리(Minimum spanning tree) 클러스터 분석은 모든 두 점 사이에 거리가 정의되어 있는 기하 공간의 N 개의 점 집합을 수반하며, 이것은 N개의 노드와 N(N-1)/2 개의 선으로 이루어진 완비 가중치 그래프가 된다. 최소 확장 트리( mimimum spanning tree weight graph)가 된다.

2. 이항관계와 연역법 추이폐포(Transitive closure) : - 선(Edge)  이항관계 - 경로(Path)  연역적 단계 - 그래프(Graph)  가능한 연역적 단계의 전체 네트워크 ◈ 다른 형태의 데이터와 지식 - 이항관계로 구성  자동으로 경로계산, 추론

이항관계 (binary relation) 사실관계 (factual relation) 유사관계 (similarity relation) 기능관계 (functional relation) 사실관계는 다른 데이터 베이스 엔트리간의 자명한 링크들을 나타내며, 분자 생물학 데이터 베이스에서 교차-참조정보의 형태로써 저장되어 있다. 유사관계는 서열이나 3차원 구조 데이터베이스와 비교하여 계산적으로 듀도된다.

사실관계 (factual relation) 데이터베이스 엔트리간의 연결 Cross-reference information 형태 - 서열데이터와 그것의 출판정보 - 염기서열과 번역된 아미노산 서열 - 단백질 서열과 3D 구조

유사관계 (similarity relation) 서열이나 3D 구조 데이터베이스와 비교하여 계산적으로 유도 컴퓨터를 이용한 유사성/상보성 - Sequence similarity, 3D structural similarity - 3D structural complementary

유사관계 (similarity relation) DBGET/LinkDB - Precomputed partial transitive closure - Dynamic linking capacity

Example <Figure 4-6> 기질-생성물(substrate-product) 상호작용의 이항관계 집합과 효소목록이 주어진 상태에서, Pyruvate(C00022)로부터 L-alanine(C00041)로의 가능한 반응 경로의 계산 예 (Node – 화합물 Edge - 효소명)

Example ‘효소 E가 화합물 X를 Y로 변환하는 화학적 작용에 촉매역할을 한다.’ : reaction (E, X, Y) path (X,Y,[E])  reaction (E,X,Y) OR path (X,Y,[E|EL])  reaction (E,Z,Y), path (X,Z,EL)

Example 질의 완화 (query relaxation)  이항관계(edge)들의 개수와 검색될 반응공간(graph)의 확장 reaction (E’, X, Y)  reaction (E,X,Y), group (G,E,E’)

Example “B  F” 간의 가상경로  E 와 E’의 기능적 동질성으로부터 추론 기능적 동질성 : - 서열간 유사성 or 서열 모티프

3. 구현(Implemantation) 기능관계 (functional relation) : 전통적인 데이터베이스에서는 계산 불능 다양한 영역으로부터의 기능적 데이터  여러 다른 형태의 이항관계를 계산적으로나 논리적으로 결합하기 위하여 이항관계의 형태로 표현 KEGG : - 추상화 수준 : 분자 네트워크 수준 - 이항관계 : 분자간의 상호작용, 유전자간 상호작용, 분자 또는 유전자간의 다른 관계

KEGG (Kyoto Encyclopedia of Genes and Genomes)

Example - pathway

Example - pathway

유전체-경로 비교 “유전체에서 동시에 조절되는 위치적으로 관련된 일군의 유전자들(오페론 구조)  물질대사 경로에서 하나의 기능적 단위” 에 대응

계층트리 네트워크 표현이 매우 제한적 유전자 목록 : 생화학적 경로 및 집합의 분류에 의한 유전자의 기능적 계층도 분자 목록 : 단백질 분자, RNA 분자, 화합물 등의 기능적이거나 구조적인 분류 계층 트리와 경로간의 비교  구조적으로 유산한 효소들에 의해 촉진된 일련의 반응 단계 존재

KEGG 의 방향

KEGG 의 방향 완전한 유전체 서열로부터 생화학적 네트워크 전체를 예측 생화학적 네트워크에 대한 지식 기반 예측 (knowledge based prediction)의 활용 참조 데이터베이스 (Reference database)