4. 분자 상호 작용의 네트워크 분석 4.1 네트워크 표현과 계산 2006.05.15. Yong Jung

목차 4.1 네트워크 표현과 계산 추상화 수준 분자 네트워크 그래프 공통 부분그래프(common subgraph) 네트워크 비교의 경험적 방법 경로 계산 이항 관계(binary relation)와 연역법(deduction) 구현(implementation) 2019-05-31

추상화 수준(1/2) 서열 수준에서 유전자 정보 발현 흐름 (Central dogma) DNA  RNA  단백질 열역학 법칙과 구조 기능 관계는 단일 단백질 분자에 대한 유전자 정보 발현의 부가적인 흐름을 입증 서열  구조  기능 분자들의 네트워크 수준의 추상화된 상위 수준에서의 생물학적 기능 분석 상호작용  네트워크  기능 2019-05-31

추상화 수준(2/2) 유전체 이후 분석 전사체(transcriptome) – mRNA 수준의 유전자 발현 프로필 단백체(proteome) – 단백질 수준의 유전자 발현 프로필 전사체와 단백체는 유전자 조절 네트워크와 단백질 상호작용 네트워크에 대한 많은 정보를 가질 가능성이 높음 2019-05-31

분자 네트워크(1/3) 생물학적 기능 네트워크 – 원소와 이항관계로 구성 분자 수준 – 염기 또는 아미노산 단위의 배열인 서열 정보로 기록 네트워크 수준 – 상호작용하는 네트워크 정보로 기록 네트워크 – 원소와 이항관계로 구성 원소 – 분자 또는 유전자 이항 관계 – 분자들간 또는 유전자들 간의 상호 작용, 두 원소간의 임의의 관계 구성 요소, 연결, 상호작용 등이 모두 생물학적 시스템을 만드는데 필요 고차원(3,4항)의 형태로 관계를 표시하면 현실 세계 데이터가 더 잘 표현되지만 논리적 단순화와 계산상의 효율 때문에 생물학적 시스템의 구성을 원소와 이항관계로 표현 2019-05-31

<그림 4-1> 네트워크 표현. 네트워크(그래프)는 원소(vertex)들의 집합과 2)이항 관계 분자 유전자 1)원소 분자 상호 작용 유전자 상호 작용 다른 형태의 관계 3) 네트워크 이웃 집단 경로 집합체 유전체 계층 트리 <그림 4-1> 네트워크 표현. 네트워크(그래프)는 원소(vertex)들의 집합과 이항관계(edge)들의 집합으로 이루어져 있다. 생물학적 지식과 전산적인 결과는 여러 다른 형태의 네트워크 데이터로 표현된다. 2019-05-31

분자 네트워크(2/3) 생물학적 지식을 표현한 네트워크 경로(Pathway)는 분자 상호 작용의 네트워크 세포 작용의 여러 가지 측면이 집적된 지식의 표현 물질 대사 경로, 신호 변환 경로, 세포 순환 경로, 발육 경로와 그 밖에 다른 많은 조절 경로 집합체(assembly)는 분자 상호 작용의 또 다른 네트워크 네트워크 안의 분자들은 분자 기계장치나 부분 세포 유기체 안에서와 같은 안정된 복합체를 이룸 경로와 집합체를 구분하기엔 모호함 유전체는 유전자 들의 네트워크로서 선형 또는 원형 염색체내의 유전자들의 물리적인 순서를 표현 집합체 유전체 2019-05-31

분자 네트워크(3/3) 이항 관계들로 유도된 네트워크 이웃(neighbor)은 주어진 분자나 유전자에 대한 유사성 관계의 표현 서열 유사성 검색의 결과는 이웃 네트워크의 전형적인 예 클러스터(cluster)는 전체 분자나 유전자들의 집합에 대한 유사성 관계의 표현 클러스터 분석은 모든 쌍별 유사성 점수를 이용하여 유사성 그룹을 정의함 단일 연결 클러스터링- 그룹내의 멤버는 같은 그룹내의 다른 멤버와 적어도 하나 이상의 유사성 관계로 연결 완비 연결 클러스터링 – 그룹은 어떤 멤버가 그룹내의 모든 멤버와 유사성 관계로 연결된 멤버로 구성 계층 트리는 계층적인 클러스터의 연산 결과를 표현 서열 유사성의 임계치 점수는 상위 단계의 그룹을 정의하기 위해 점진적으로 수정됨 유전자 기능의 계층도와 같은 생물학적 지식 표현 집단 계층 트리 2019-05-31

그래프(1/2) 네트워크 수학적인 관점에서 점들과 이들을 이은 선들로 이루어져 있는 그래프임 G = (V, E) 분자 네트워크 문제에서 V는 유한 집합이고 G는 각 점에 이름이 부여된 그래프가(labeled graph) 됨 분자 네트워크의 다양한 생물학적 제약 포함을 위한 그래프 연결 그래프 완비 그래프 방향 그래프 (분자의 비 가역적인 작용 경로의 표현에 사용) 가중치 그래프 (신호 변환 경로에서 활성과 억제를 구별함수 있음, 유사한 정도를 점수화 하거나 클러스터링 절차에서 점간의 유사성이 점수나 거리를 정의) 2019-05-31

Figure 1 Graphs that are a) connected b) disconnected c) complete 2019-05-31

그래프(2/2) (a) 점과 선의 표현, 직관적이고 그래프의 위상적인 특성을 나타내는 표현 B (a) 점과 선의 표현, 직관적이고 그래프의 위상적인 특성을 나타내는 표현 (b) 각각의 점들에 대한 연결 정보를 연결 리스트로 표현 (c) 같은 점들을 첨자로 갖는 연결 행렬로 표현 이항 관계와 그래프의 개념이 자연스럽게 연관되어 있음 G1 = (V1, E1), G2 = (V2, E2) 두 그래프가 동형(isomorphic)이라는 수학적으로 같은 구조를 갖고 있음을 뜻함 같은 수의 점을 가지고 있으며 한 그래프의 점 집합과 다른 그래프의 점 집합 사이에 선들의 관계를 유지하는 일대일 대응관계(치환)가 있을 때 C D E F (b) A B C D E F A C D B E C D F (c) 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 2019-05-31

공통 부분그래프(Common subgraph)(1/3) 경로 대 경로 그림 4-3은 분자 네트워크의 다음 두 그래프 간의 비교를 통해 생물학적 예를 보여줌 경로-경로, 경로-유전체, 유전체-유전체, 클러스터-경로 이런 그래프에서 선은 방향이나 가중치를 갖기도 함 유전체내의 유전자 명과 생화학 경로내의 유전자 생성물질에 따라 그래프상의 점들이 바뀔 때, 생물학적 비교문제는 두 그래프간의 비교문제는 두 그래프간의 공통 부분 그래프를 찾는 문제 또는 부분그래프의 동형인 쌍을 찾는 문제로 바뀜 서열 분석에서 두 서열의 유사한 부분서열을 찾는 문제(local similarity)와 유사  경로 대 유전체  유전체 대 유전체  클러스터 대 경로  <그림 4-3> 네트워크 비교의 생물학적 예 2019-05-31

공통 부분그래프(Common subgraph)(2/3) 두 그래프 G1과 G2와 edge의 부분집합 E1’ ⊆ E1, E2’ ⊆ E2 부분 그래프 G1’ = (V1, E1’), G2’ = (V2,E2’) 최대 공통 부분그래프 - 크기(cardinality)가 가장 큰 부분그래프의 쌍(G1’,G2’)를 의미 서열 정렬 용어로 말하자면 삽입과 삭제가 없는 해당 부분이 완전히 일치하는 쌍을 의미 최대 공통 유도(induced) 부분그래프 - V1’에서 유도된 G1의 부분그래프와 V2’에서 유도된 G2의 부분그래프의 동형인 쌍 중에서 크기가 가장 큰 것을 의미 최대 공통 유도 부분그래프의 개념은 <그림 4-4>의 생물학적으로 관련 있는 예에 적용됨 2019-05-31

공통 부분그래프(Common subgraph)(3/3) <그림 4-4> 경로 정렬은 그래프 동형의 문제이다. (a) 최대 공통 유도 부분그래프 (b) 최대 클리크 <그림 4-4>는 서로 다른 두 종에서 나온 두 생화학적 경로의 유사성 정도를 계산 분자들 간의 서로 연결된 구조의 유사성을 알고자 함 <그림 4-4>(a) 경로1은 다섯 개의 분자, 경로2는 여섯 개의 분자 화살표: 활성화 단계, 억제 단계, 가는 점선: 서열 유사성, 공백: 진한 점선 <그림 4-4>(b) 점을 원소로 하는 두 집합내의 모든 리레이블(relabelling)을 5x6 개의 점들에서 유도된 그래프로 표현 원래 그래프에 대응되는 선이 존재할 경우 새롭게 리레이블링한 그래프에도 선을 표현 두 개의 클리크를 가지고 있음 그 중에 (B, b)(C, d),(D, f)는 최적임 최대 클리크를 찾는 문제와 최대 공통 유도 부분그래프를 찾는 문제는 서로 변환 이 문제는 NP-complete (Nondeterministic polynomial time complete) 문제의 범주에 들어감 2019-05-31

네트워크 비교의 경험적 방법(1/2) 경험적인 알고리즘(heuristic algorithm)을 이용해 해결 두 그래프의 점 간에 대응이 주어져 있을 때 연관된 영역을 부분적으로 일치 다른 유형의 비교에서 가능한 대응의 수는 작음 두 그래프가 <그림 4-4>(a)에서처럼 대응에 의해 연결되면 그 대응의 클러스터를 찾아 해결할 수 있음 G1 = (V1, E1), G2 = (V2, E2) 모든 대응은 쌍별(이항) 관계로 표현 집합이 n개의 대응을 포함한다면 n개의 점을 정해진 거리 측정에 따라 클러스터 하는 문제가 됨 각 점이 G1의 노드와 G2 의 노드 간의 대응을 나타내므로 두 거리 i와 j간의 거리는 다음 두 개의 거리 측도로 정의 됨 d1(I,j) : 그래프 G1 의 두 노드 v1j간의 가장 짧은 경로 d2(I,j) : 그래프 G2 의 두 노드 v2j간의 가장 짧은 경로 2019-05-31

네트워크 비교의 경험적 방법(2/2) 각 대응은 개별적인 클러스터로 간주 <그림 4-5> 생물학적 그래프 비교에 대한 경험적 알고리즘. 대응되는 클러스터에 대해 (a)와 같이 검색한다. (a)는 (b)에서 보는 것과 같이 서열 정렬과 유사하다. 각 대응은 개별적인 클러스터로 간주 N개의 초기 클러스터 단일 연결 클러스터링은 두 클러스터 Ci와 Cj의 병합여부를 다음의 기준으로 수행 Gap1과 Gap2는 공백에 대한 파라미터 (정수) 클러스터의 병합은 어느 정도의 공백과 불일치를 허용 이 알고리즘은 동형인 부분그래프를 알아내지 못하지만 두 그래프의 노드 간의 상호 연관된 클러스터를 발견 1 if min{d1(r,s) | r ∈ Ci, s ∈ Cj}≤ 1 + Gap1 and min{d2(r’,s’) | r’ ∈ Ci, s’ ∈ Cj}≤ 1 + Gap2 0 otherwise r, s δ(I, j) = r’, s’ 2019-05-31

Relation R : a relation on a set A R : reflexive ↔ (a, a) ∈ R, ∀a ∈ A R : symmetric ↔ [(a, b) ∈ R → (b, a) ∈ R, ∀a, b ∈ A] R : anti-symmetric ↔ [(a, b) ∈ R, (b, a) ∈ R → a=b] R : transitive ↔ [(a, b) ∈ R, (b, a) ∈ R → (a, c) ∈ R, ∀a, b, c ∈ A] 2019-05-31

 O(N3) Warshall Algorithm 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; 하나의 선으로 직접 연결되어 있거나, 여러 개의 선으로 간접적으로 연결되어 있는 것을 결정해주는 algorithm  O(N3) 2019-05-31

Shortest path Dijkstra Algorithm 최단거리를 구하는 유명한 알고리즘 한 점에서 출발해서 각 정점에 최단거리를 구함 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]; 2019-05-31

Minimum spanning tree Minimum spanning tree : minimum weight subgraph of G which includes all vertices of G and is a tree Kruskal’s algorithm, Prim’s algorithm, Sollin’s algorithm Cluster analysis (N points) complete weighted graph with N nodes N(N-1)/2 edges Minimum spanning tree  single linkage hierarchical cluster analysis 2019-05-31

이항관계와 연역법 Transitive closure : ∴ 다른 형태의 데이터와 지식 - 이항관계로 구성  Edge (connection) – 이항관계 Path – 연역적 단계 Graph – 가능한 연역적 단계의 전체 네트워크 ∴ 다른 형태의 데이터와 지식 - 이항관계로 구성  자동으로 경로계산, 추론 2019-05-31

이항관계 (binary relation) 사실관계 (factual relation) 유사관계 (similarity relation) 기능관계 (functional relation) 2019-05-31

유사관계 (similarity relation) DBGET/LinkDB - Pre-computed partial transitive closure - Dynamic linking capacity 2019-05-31

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

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) 2019-05-31

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

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

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

KEGG (Kyoto Encyclopedia of Genes and Genomes) 2019-05-31

Example - pathway 2019-05-31

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

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

2019-05-31

KEGG 의 방향 2019-05-31

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