Chapter 07. Bioinformatics, Genetics and Network Models (생물정보학, 유전학, 네트워크 모델)

※ 이 포스팅은 저자 'Kirthi Raman'의 도서 <Mastering Python Data Visualization> 을 공부하며 정리한 글입니다. 

---

Chapter 07. Bioinformatics, Genetics and Network Models (생물정보학, 유전학, 네트워크 모델)

이 장에서는 예제들을 다루기 위해 metaseq, NetworkX, matplotlib, Biopython, ETE toolkit 과 같은 라이브러리들을 사용한다.

Directed Graphs and Multigraphs (방향성 그래프와 멀티 그래프)

그래프와 방향성 그래프의 활용성을 알아보기 위해, 간단한 예를 생각해보자.

대학 캠퍼스 지역 내 서로 연결된 컴퓨터는 연결 그래프로 생각할 수 있고, 이 연결 안에서 각 컴퓨터는 노드(Node)나 정점(Vertex)이라 볼 수 있다.

연결된 길은 모서리이고, 어떤 경우 오직 한 방향 연결만 있다면 그것이 방향성 그래프이다.

또 다른 예로, 매우 엄격한 연방 네트워크는 밖에서부터 안으로 들어오는 어떤 연결도 허락하지 않을 것이나, 아마 반대로는 제약이 없을 것이다.

다음 간단한 그래프는 각 장소들 간의 거리를 보여준다.

앞의 예시에서 A부터 F까지 이름 붙여진 도시의 그래프는 방향성 그래프이고, 오른쪽 다른 그래프는 방향성이 없는 그래프이다.

방향성 그래프에서 화살표 방향이 양쪽으로 되어 있다면, 두 방향으로 갈 수 있는 길이 존재하는 것이다.

한편, 비방향성 그래프에서는 양쪽 방향 모두 가정한다. (오른쪽 그래프)

이러한 그래프들을 어떤 데이터 구조를 사용해 표현해야 할까?

#. Storing Graph Data (그래프 데이터 저장)

그래프 데이터는 보통 희소 행렬이나 인접 행렬로 나타내진다.

인접 행렬은 그래프가 V개의 정점(Vertex) 또는 노드(Node)를 갖는다고 가정했을 때, V2개 행을 갖는 행렬이다.

예를 들어, 앞에서 본 두 그래프들은 다음 표와 같은 인접 행렬이다.

	A	B	C	D	E	F
A	0	25	26
B		0	85	5	10
C	26	85	0			10
D				0		11
E				9	0	88
F				11	88	0

	Chicago	Boston	New York	Wash DC	Miami	Dallas
Chicago	0	1613		1145
Boston	1613	0	338	725
New York		338	0	383	2145
Wash DC	1145	725	383	0	1709	2113
Miami			2145	1709	0	2161
Dallas				2113	2161	0

비방향성 그래프는 대칭적으로 저장공간의 반 정도를 사용하는 것으로 충분하다.

행렬의 빈 성분들은 거리에 관한 충분한 데이터가 있지 않음을 보여준다.

scipy에는 희소 행렬을 편리하게 다룰 수 있는 함수들이 존재한다.

다음 코드는 앞 그림의 첫 그래프에 해당한다.

import scipy.sparse as sparse

matrixA = sparse.lil_matrix((6,6))

matrixA = sparse.lil_matrix([

        [0,25,26,0,0,0],

        [0,0,85,5,10,0],

        [26,85,0,0,0,10],

        [0,0,0,0,0,11],

        [0,0,0,9,0,88],

        [0,0,0,11,88,0]

        ])

print matrixA

  (0, 1)        25

  (0, 2)        26

  (1, 2)        85

  (1, 3)        5

  (1, 4)        10

  (2, 0)        26

  (2, 1)        85

  (2, 5)        10

  (3, 5)        11

  (4, 3)        9

  (4, 5)        88

  (5, 3)        11

  (5, 4)        88

그래프를 보여주기 위해 사용할 수 있는 방대한 파이썬 패키지가 있다. 그 중 많이 사용되고 있는 TOP 3는 NetworkX, igraph, graph-tool 이다.

#. igraph

원래 igraph는 R 언어를 위해 만들어졌는데, 후에 파이썬 버전이 추가됐다.

igraph는 dimacs, dl, edgelist, graml, graphdb, gml, lgl, ncol, pajek 등 몇 가지 포맷들을 제공한다.

GraphML은 XML 기반 파일 포맷이며 큰 그래프에 사용될 수 있다.

NCOL 와 LGL 그래프 포멧은 Weighted Edge List를 가진 큰 그래프에 적합하다.

다른 대부분의 포맷들은 간단한 원문 포맷을 사용한다.

DL 파일 포맷만 igraph에 의해 모두 지원되며, 다른 포맷들은 부분적으로 지원한다.

igraph의 장점은, 편리하며 SVG 포맷으로 결과를 저장해 HTML 파일에 내장할 수 있다는 것이다.

(Anaconda Prompt에서 win-64(Microsoft Windows 64bit OS) 환경에서 다음 명령어를 통해 igraph를 설치할 수 있습니다.)

conda install -c vtraag python-igraph

이제, pajek 포맷을 포함하는 예제를 살펴보자. (http://vlado.fmf.uni-lj.si/pub/networks/pajek/ 참고)

import igraph

vertices = ["A", "B", "C", "D", "E"]

edges = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1),

         (1,8),  (8,2),(2,4),(4,9),(9,5),(5,7),(7,0)]

graphStyle = { 'vertex_size': 20}

g = igraph.Graph(vertex_attrs={"label": vertices}, edges=edges, directed=True)

g.write_svg("simple_star.svg", width=500, height=300, **graphStyle)

다음은 파일로부터 그래프 데이터를 읽는 예제 코드이다.

(http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm 에서 데이터 다운로드 가능)

from igraph import read  

g=read("Ragusa18.net",format="pajek")  

  

g.vs["color"]="#3d679d" 

g.es["color"]="red" 

graphStyle={ 'vertex_size': 12, 'margin': 6} 

#graphStyle["layout"]=g.layout("fr")  # optional

g.write_svg("ragusa_graph.svg", width=600, height=600,**graphStyle)

같은 데이터셋에서 다음 코드처럼 원형 모양 등의 레이아웃 옵션을 선택적으로 할당할 수 있다.

graphStyle["layout"]=g.layout("circle")

#. NetworkX

다음은 matplotlib을 통해 방향성 그래프를 만든 예제 코드이다

import matplotlib.pyplot as plt

import pylab

from pylab import rcParams

import networkx as nx

# set the graph display size as 10 by 10 inches

rcParams['figure.figsize'] = 10, 10

G = nx.DiGraph()

# Add the edges and weights

G.add_edges_from([('K', 'I'),('R','T'),('V','T')], weight=3)

G.add_edges_from([('T','K'),('T','H'),('T','H')], weight=4)

# these values to determine node colors

val_map = {'K': 1.5, 'I': 0.9, 'R': 0.6, 'T': 0.2}

values = [val_map.get(node, 1.0) for node in G.nodes()]

edge_labels=dict([((u,v,),d['weight'])

                 for u,v,d in G.edges(data=True)])

#set edge colors

red_edges = [('R','T'),('T','K')]

edge_colors = ['green' if not edge in red_edges else 'red' for edge in G.edges()]

pos=nx.spring_layout(G)

nx.draw_networkx_edges(G,pos,width=2.0,alpha=0.65)

nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

nx.draw(G,pos, node_color = values, node_size=1500,

 edge_color=edge_colors, edge_cmap=plt.cm.Reds)

pylab.show()

nx.is_directed_acyclic_graph(G) 

.

이 그래프는 NetworkX를 사용해 그래프의 시각미와 모서리 굵기를 조절한 것이다.

방향성 그래프를 보여주는 여러 방법 중 NetworkX는 방향을 화살표 대신 끝을 두꺼운 막대로 표시한다.

추가로 최단 경로부터 연결수 분포, 클러스터링 계수까지 NetworkX는 다양한 그래프 분석 방법을 제공한다.

다음 코드는 최단 경로를 보여주는 간단한 예제 코드이다.

import networkx as nx

g = nx.Graph()

g.add_edge('m','i',weight=0.1)

g.add_edge('i','a',weight=1.5)

g.add_edge('m','a',weight=1.0)

g.add_edge('a','e',weight=0.75)

g.add_edge('e','h',weight=1.5) 

g.add_edge('a','h',weight=2.2)

nx.draw(g)

print nx.shortest_path(g,'i','h')

['i', 'a', 'h']

다음 예제는 레미제러블 소설에 등장하는 인물들의 관계를 나태낸다.

(https://gephi.org/datasets/lesmiserables.gml.zip 으로부터 데이터셋을 받을 수 있으며, GML 포맷 데이터로 되어있다.)

import networkx as nx

from pylab import rcParams

rcParams['figure.figsize'] = 12, 12

G = nx.read_gml('./lesmiserables.gml')

G8 = G.copy()

dn = nx.degree(G8)

#for n in G8.nodes():

#  if dn[n] <= 8:

#    G8.remove_node(n)

pos= nx.spring_layout(G8)

nx.draw(G8, node_size=10, edge_color='b', alpha=0.45, font_size=9, pos=pos)

labels = nx.draw_networkx_labels(G8, pos=pos)

#. The Planar Graph Test (평면 그래프 테스트)

평면 그래프는 교차하는 가장자리(Intersecting Edge) 없이 평면에 그려질 수 있는 그래프이다.

평면 그래프를 그리기 위해 정점으로부터 시작해 가장자리(edge)와 엣지(edge)를 그리고, 그려지는 면(face)들을 계속해서 추적해야 한다.

다음은 평면 그래프의 간단한 예이다.

오일러의 공식은 정점, 가장자리(edge), 면(face)들을 연결한다.

오일러에 따르면, 유한 연결 평면 그래프(Finite and Connected Planar Graph)가 교차하는 가장자리(edge) 없이 평면에 그려졌을때 다음 식이 성립한다.

v - e + f = 2 (v : 정점의 수, e = 가장자리 수, f = 면의 수)

#. The Directed Acyclic Graph Test (방향성 비순환 그래프 테스트)

방향성 비순환 그래프(DAG, Directed Acyclic Graph)란, 예로 정점 A로부터 B로의 엣지들은 특정 방향(A -> B or B -> A)을 지시하고 비순환성을 지닌다.

비순환 그래프는 순환이 없다. 다시말해, 사이클이 없는 것을 의미한다.

NetworkX 패키지의 is_directed_acyclic_graph(Graph)는 시각화의 맥락에서 그래프가 비순환인지 아닌지를 체크하는 방법을 제공한다.

import matplotlib.pyplot as plt

import pylab

from pylab import rcParams

import networkx as nx

# set the graph display size as 10 by 10 inches

rcParams['figure.figsize'] = 10, 10

G = nx.DiGraph()

# Add the edges and weights

G.add_edges_from([('K', 'I'),('R','T'),('V','T')], weight=3)

G.add_edges_from([('T','K'),('T','H'),('T','H')], weight=4)

# these values to determine node colors

val_map = {'K': 1.5, 'I': 0.9, 'R': 0.6, 'T': 0.2}

values = [val_map.get(node, 1.0) for node in G.nodes()]

edge_labels=dict([((u,v,),d['weight'])

                 for u,v,d in G.edges(data=True)])

#set edge colors

red_edges = [('R','T'),('T','K')]

edge_colors = ['green' if not edge in red_edges else 'red' for edge in G.edges()]

pos=nx.spring_layout(G)

nx.draw_networkx_edges(G,pos,width=2.0,alpha=0.65)

nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

nx.draw(G,pos, node_color = values, node_size=1500,

 edge_color=edge_colors, edge_cmap=plt.cm.Reds)

pylab.show()

nx.is_directed_acyclic_graph(G) 

True

#. Maximum Flow and Minimum Cut (최대 플로우와 최소 컷)

'플로우 네트워크'는 소스로부터 목적지까지 방향성을 가진 그래프이며 각 엣지를 따라 할당된 용량(Capacity)이 주어진다.

최단 경로를 찾기 위해 방향성 그래프로 거리 지도를 모델링하는 것과 비슷하게, 플로우 네트워크로 방향성 그래프를 해석할 수 있다.

예시로는 파이프를 통해 흐르는 액체, 전기 네트워크를 통과하는 전류, 데이터 통신 네트워크를 통해 전송되는 데이터 등이다.

그래프 G의 엣지들은 엣지가 얼만큼의 플로우를 지원할 수 있는지에 대한 용량을 가지고 있다. 용량이 없다면 무한으로 가정한다.

위 그래프에서 플로우 네트워크 G의 최대 플로우는 4이다.

NetworkX 패키지의 maximum_flow_value(Graph, from, to)는 그래프의 최대 플로우를 계산한다.

import networkx as nx

G = nx.DiGraph()

G.add_edge('p','y', capacity=5.0)

G.add_edge('p','s', capacity=4.0)

G.add_edge('y','t', capacity=3.0)

G.add_edge('s','h', capacity=5.0)

G.add_edge('s','o', capacity=4.0)

flow_value = nx.maximum_flow_value(G, 'p', 'o')

print "Flow value", flow_value

Flow value 4.0

...