5 네트워크 정렬문제
5.4 네트워크의 다중정렬 알고리즘
5.4 네트워크의 다중정렬 알고리즘
65
앞서 언급한대로 여러 종의 생물 네트워크에서 공통적으로 존재하는 기능은 생존이라 는 궁국의 공통목적에 필수불가결한 기능으로 쓰일 수 밖에 없기 때문이다. 매우 중요한 의미를 가진다. 서열정렬에서 언급한대로 다중정렬은 그 비교할 종 갯수의 제곱으로 시간, 공간 복잡도가 늘어나기 때문에 비교종의 수가 많아지면 문제는 현실적으로 해결 불가능한 상태가 되어버린다. 이를 위해서 다양한 휴리스틱이 존재하는데 가장 단순한 방법은 그리디 (greedy) 전략을 사용하는 것이다. 만일 방법은 비교할 g 개의 네트워크가 N1, N2. . . Ng가 있다고 할 때, 일단 가장 비숫한 두 종의 네트워크를 선택하여 먼저 쌍정 렬을 통하여 매칭되는 짝을 결정하는 방법이 가장 단순한 그리디 전략이 된다. 그렇게 선택된 해당 쌍이 Ni, Nj라고 하자. 그러면 이 둘을 제외한 g− 2개의 네트워크 중에 이미 정렬된 Ni, Nj과 가장 유사성이 높은 네트워크를 추가로 찾아서 이미 정렬된 네트워크에 추가하여 정렬을 한다. 이런 식으로 매번의 단계에서 가장 높은 정렬값을 가진 쌍을 선택하여 정렬하면 전체 다중정렬된 네트워크들은 tree 구조로 연결되게 된다. 추가할 때 제약을 주면 linear한 path 모양으로도 정렬할 수 있다. 다중 정렬의 휴리스틱으로 star alignment도 있다. 이 방법은 다른 g − 1 개와의 유사성이 가장 높은 (모두 더한 값으로) 네트워크를 하나 선택해서 이것을 정렬의 중심이 두는 것이다. 그리고 나머지 네트워크들을 이 중심과 star graph 형식으로 연결한다. 이 모두는 최적 정렬을 위한 휴리스틱이기 때문에 실제 데이터의 특성과 제한하는 조건에 따라서 많은 성능 차이를 보인다.
아래 그림-22으로 다중정렬을 셜명한다. 그림에 제시된 4개의 그래프 A, B, C, D에서 1,2,4,5 노드로 구성된 subgraph는 4개의 네트워크에 공통으로 존재하는 것임을 알 수 있다[40]. 그러나 그 아래 그림-23에서는 4개의 그래프 모두에 공통으로 존재하는 크기가 4인 subgraph는 없음을 알 수 있다. 그런데 이 4개의 그래프에서 그림과 같은 회색 노드를 인위적으로 추가함으로서 위와 같은 4개 노드로 구성된 공통의 subgraph { 1,2,4,5}를 찾아낼 수 있다. 즉 각 그래프 A, B, C, D에 하나씩의 dummy를 추가함으로서 크기가 4인 공통 그래프를 찾아니는 것이 편집 비용적으로 이득이라고 판단하였기 때문이다. 즉 공통 그래프를 위하여 추가한 dummy node에 따른 비용보다 그것을 넣음으로서 우리가 얻을 수 있는 공통부분의 가치 (크기) 에 따라서 dummy노드를 추가할지의 여부가 결정된다.
문제는 어디에 얼마만큼의 dummy node를 만들어 넣는가 하는가가 하는 것인데 이는 결국 비용함수에 따라서 결정된다. dummy insertion의 비용이 비싸면 추가되는 일은
5.4 네트워크의 다중정렬 알고리즘
66
5.4 네트워크의 다중정렬 알고리즘
67
되는 네트워크를 먼저 선택한다. 그것은 다른 모든 그래프와의 유사도가 가장 좋은 것을 선택해도 좋고 (평균), 또는 최고 유사도값을 가지는 한 쌍에서 선택해도 좋다. 그것을 Gi라고 하자. 그러면 Gi와 그것과 가장 유사한 다른 Gj를 pairwise align한다. 이때 필요하면 dummy node를 추가한다. 이제 나머지 align 되지 못한 Gk중에서 이미 align된 그래프와 가장 유사한 것을 찾아서 정렬한다. Weskamp의 다중정렬 방식은 간단하지만 중앙 center graph를 어떻게 잘 잡는가에 따라서 성능은 크게 좌우된다. 따라서 몇 개의 다른 seed를 선택하여 위 작업을 반복한 뒤에 적절한 결과를 만들어내는 반복개선 작업이 필수적이다.
요약하자면 시간복잡도나 공간복잡도의 관점에서 압도적으로 우위에 있는 정렬 알고리즘은 없다고 보는 것이 타당할 것이다. 정렬 알고리즘은 전처리 (Preprocessing) 를 하는지, 한다면 어떻게 하는지, 입력 데이터의 모형을 얼마나 잘 활용하는지44, 또는 오류의 범위를 어디까지 허용하는지에 따라서 다양한 변형이 나타날 수 있다.
44예를 들어 생물 네트워크에서 아주 큰 Degree를 가진 hub가 존재한다면 이것을 중심 (center) 에 놓고 정렬함으로서 거의 선형시간에 정렬을 마칠 수 있다.