대표적인 네트워크 지역정렬 시스템

내는 것이기 때문에 conserved region이 존재하는 복수개의 네트워크도 NAPA Bench 를 이용하여 만들 수 있다. 이렇게 정답이 확실한 데이터를 이용하면 객관적인 성능 비교평가가 가능하다. 하지만 실제 wet lab에서 생성된 real 네트워크는 전체 구조나 annotation 내용이 지속적으로 바뀌고 (개선되고) 있기 때문에 평가시 어떤 version의 데이터를 이용하는가에 따라서 그 결과는 크게 달라질 수 있기 때문에 어려움이 많다.

Clark의 비교평가에서 실제 Wet lab data로는 IsoBase의 자료를 이용했다. 실제 데 이트를 사용해서 평가할 때의 문제는 정렬된 모듈들이 진짜 의미있는 것인지를 확인하기 어렵다는 단점이 있다. 특히 NGS기반의 새로운 실험기술의 등장으로 엄청나게 빠른 속도로 새로운 실험데이터가 쏟아지는 현실에서 실제 생물 데이터의 정답을 확정하기란 거의 불가능한 일이다. 이것이 실제 데이터를 통하여 성능평가를 할 때의 가장 큰 어려 움이라고 할 수 있다.

6.4 대표적인 네트워크 지역정렬 시스템

지금부터는 공표된 네트워크 정렬 시스템 중에서 언급할만한 성능의 시스템에 대하여 그들의 주된 방법론과 특성, 차별성에 대하여 지역정렬과 전역정렬로 나누어서 설명하 고자 한다. 그리고 최근 들어 주목을 받고 있는 graphlet 기반의 정렬 알고리즘은 따로 구분하여 설명한다.

6.4.1 정렬 시스템의 시초 PathBLAST

pathBLAST는 Biological Network alignment용 실용적 도구로 처음으로 주목을 받은 시스템이다[22]. 이 도구는 이미 많은 연구가 이루어진 박테리아의 pathway 위상정보와 이스트의 pathway에서 유사한 부분을 찾아내기 위해서 사용되었으며 이름이 말해주듯이 서열 정렬도구인 BLAST의 방법을 원용 (exploited) 한 도구이다. BLAST와 같은 방법의 정렬도구를 The BLAST family라고 부르고 이 안에는 이 pathBLAST와 이것을 확장한 NetworkBLAST, 그리고 이것을 다시 개선한 NetworkBLAST-M이 있다.

서로 다른 두개의 network에서 선택된 2개의 path들의 각 노드들끼리 짝을 지어 match, mismatch, gap을 형성하고 있는 모양을 그림-31에서 볼 수 있다. pathBLAST의 방법은 linear sequence alignment의 일반적인 구조와 본질적으로 동일하다. 짝 지워진

6.4 대표적인 네트워크 지역정렬 시스템

82

Figure 31: PathBLAST로 두 개의 path가 alig된 예. dummy node가 정렬에 포함되어 있다.

노드의 생물학적인 유사성 (homology) 에 따라서 pathBLAST의 alignment 모양은 달라 진다.

pathBLAST는 두 개 이상의 Biological Network N_aN_b에서 의미가 있는 path를 align 해준다. 이 단순한 방법은 이렇게 시작된다. N_a에서 임의의 한 노드 x_i를 찾고 그와 가장 유사한 노드 y_i를 N_b에서 찾는다. 그 다음 이 출발점 노드에서 연결된 이웃 노드 중에서 서로 가장 유사한 노드를 하나씩 짝을 지워 그 path를 점점 확장해 나간다. 비유하자면 이런 식이다. 서울과 뉴욕을 도로중심으로 pathBLAST로 수행시킨다고 가정해보자.

먼저 두 지역에서 가장 번잡한 출발점을 선택한다. 즉 서울에서는 가장 번잡한 종로가 선택하고 그와 대응되는 뉴욕의 중심거리의 Y 가 선택될 것이다. 그 다음 종로와 인전한 지점과 Y 와 인접한 지점 중에서 가장 유사한 형상의 거리를 계산해서 찾는다. 이런 방식으로 path를 확장해나간다. 어떤 경우에는 서로 인접한 지점이 일치할 수도 있고 (match), 또는 불일치 할 수도 있고 (mismatch), 또는 한 지역을 건너뛰어 (gap) 나갈 수도 있다. 이 경우 지역, 그러니까 path를 한단계씩 확장해 나갈 때 scoring function를 고려해서 이 과정을 진행한다. 즉 scoring function을 최적화 시키는 방향으로 진행하면 N_aN_b 에서 생물학적으로 유사한 pathway을 pthBLAST가 찾아준다.

6.4 대표적인 네트워크 지역정렬 시스템

83

S(P ) =∑

v∈P

log p(v) prandom

+∑

v∈P

log q(v) qrandom

여기에서 p(e) 는 align된 path상의 protein v 가 짝을 이루고 있는 다른 쪽 protein 과의 homologous 한 정도를 나타내는 유사도이며, q(e) 는 alignment graph 에 포함된 interaction edge(N_a와 N_b를 연결해주는) 들의 상호작용의 정도를 나타내는 확률값이다.

이것을 자세히 나타내면 아래와 같다.

q(e) =∏

i∈e

P r[i]

그 아래 prandom은 p(v), q(e) 의 aligned 된 그래프에서의 평균값이다. 이 scoring function은 저자들의 경험적 측정실험에 의해서 결정된 것이다. 가장 의미있는 path 들이 서로 대응되는 것 상황을 실험으로 확인하여 결정된 변수값이다. 이 시스템은 http://www.pathblast.org에서 다운받아 활용할 수 있다.

6.4.2 그리디 기반의 MaWISh(Maximum Weight Induced SubgrapH)

이 시스템은 네트워크 노드 유사도를 진화거리로 계산하여 그것을 정렬 비용으로 사용 한다. 원래 Maximum Weight Induced Subgraph 문제는 Subgraph isomorphism보다 더 어려운 문제이다. 왜냐하면 Maximum Weight Induced Subgraph문제에서 모든 vertex, edge weight가 1일때가 바로 subgraph isomorphism문제가 되기 때문이다. 그들이 제 시한 방법은 전형적인 그리디 접근법으로, 하나의 anchor node쌍에서 시작하여 조금씩 유사한 영역을 확장해가며 매칭을 진행한다. 물론 local minima에 빠질 수도 있지만 적절한 randomization을 사용하여 확룰적으로 그것을 피해나가는 방법을 택하고 있다.

www.cs.purdue.edu/homes/koyuturk/mule에 가면 해당 시스템과 사용된 데이터, 분 석결과를 모두 확인할 수 있다.

6.4.3 Graemlin

원래 1.0 버전은 다중정렬 (multiple network alignment) 전용으로 먼저 개발된 도구이 다[23]. 이후 2.0 판에서는 전역정렬도 가능하도록 개선되었다. 기본적인 방법은 각

6.4 대표적인 네트워크 지역정렬 시스템

84

입력 네트워크의 부분 그래프를 equivalence class로 나눠서 각 class들끼리 matching 시키는 방법을 사용한다. 공통의 조상으로부터 유래된 단백질 집합이나 같은 종내에서의 paralogs가 매칭 단위를 이루는 equivalence class로 정리된다. 하나의 네트워크에서 진화적으로 가장 가까운 종의 내트워크를 순차적으로 정렬해가기 때문에 progressive alignment 라고도 불린다. 2.0 에서는 hill climbing method 를 이용해서 좀 더 빠르게 local minima 를 벋어나는 방법이 추가되었다. 그리고 이전 수작업으로 확인된 true set에 가까운 alignment 결과를 user defined 함수로 추가할 수 있도록 허용하여 최종 결과물이 신뢰도를 더 높일 수 있게한다. 사용자의 경험 (이미 정리된 정렬결과) 를 추가 하는 과정에 다양한 machine learning 방법이 사용되고 있다. 관련된 자료와 시스템은 http://graemlin.stanford.edu/graemlin-2.01.tar.gz에서 얻을 수 있다.

6.4.4 진화최적화 방법의 GEDEVO

요즘 유행하는 다양한 AI기법이 네트워크 정렬에도 다양하게 응용되고 있다. 그 이유는 정렬 시스템은 결국 NP-complete문제를 푸는 heuristics algorithm이기 될 수 밖에 없기 때문에 optimization에 사용되는 모든 방법, 예를 들어 선형계획 (Linear programming), Quadratic Programming, Neural Net, Belief Network[16] 와 같은 시도가 모두 활용될 수 있다.

이 시스템은 두 그래프의 편집거리를 구하는 과정을 진화개선 알고리즘으로 접근하고 있다[36]. 대략의 방법은 이런 식이다. 매칭을 시켜야하는 두 그래프를 “짝” 을 (mating) 지워 그 중간 단계의 다양한 자식 그래프를 만든다. 이 자식 그래프들 중에서 양쪽 부모와 가장 닮은 그래프 후보를 몇 개 골라서 다시 다음 세대 개체군을 형성한다⁵⁹. 이 과정을 반복해서 편집거리가 가까운 그래프를 정리하면 그것이 바로 A 그래프에서 B 그래프로 변화시키는 최단거리, 즉 최단편집의 과정을 보여주는 operation path가 되는 것이다.

저자들의 주장에 의하면 이미 잘 알려진 SPINAL, GHOST, C-GRAAL, M-GRAAL보다 더 나은 성능을 보여준다고 하는데 그 성능 결과와 평가 기준에는 동의하기 힘들 점이 있다. 이들은 단순히 EC measure만을 사용했기 성능을 비교했다. 이 시스템은 노드별 domain-specific knowledge적 관점을 고려하지 않았기 때문에 다른 생물학적 서열유사도 나 GO DB유사도를 같이 사용하는 SPINAL, GHOST, C-GRAAL, M-GRAAL와 비교

59전형적인 evolutionary optimization 과정이다