UPGMA
1. 개요
1. 개요
UPGMA는 비가중 짝별 평균 연결법의 약자로, 계층적 군집 분석의 대표적인 방법 중 하나이다. 이 방법은 주로 생물정보학 분야에서 분자 계통수를 구성하는 데 널리 사용되며, 유전적 거리나 형질 데이터를 바탕으로 계통 발생 관계를 추론하는 데 활용된다.
이 알고리즘의 기본 원리는 객체들 간의 거리 정보가 담긴 거리 행렬을 입력받아, 가장 가까운 두 클러스터를 반복적으로 병합해 나가는 것이다. 각 병합 단계에서 새로 형성된 클러스터와 나머지 클러스터 간의 거리는, 상대 클러스터에 속한 모든 객체 쌍 간 거리의 산술 평균으로 계산하여 갱신한다. 이 과정은 모든 객체가 하나의 클러스터로 통합될 때까지 계속된다.
이러한 병합 과정의 결과는 이진 계통수 형태의 덴드로그램으로 시각화된다. 덴드로그램의 가지 길이는 병합된 클러스터 사이의 거리를 나타내며, 이를 통해 전체 데이터셋의 계층적 구조를 한눈에 파악할 수 있다. UPGMA는 계산이 비교적 간단하고 직관적이라는 장점이 있어, 계통학 초기 연구에서 많이 사용된 고전적인 방법이다.
2. 원리와 알고리즘
2. 원리와 알고리즘
2.1. 거리 행렬
2.1. 거리 행렬
UPGMA 알고리즘의 첫 단계는 분석 대상 객체들 간의 모든 쌍의 거리를 정리한 거리 행렬을 구성하는 것이다. 이 행렬은 대칭 행렬이며, 주 대각선의 값은 자기 자신과의 거리이므로 보통 0으로 설정된다. 입력 데이터는 진화적 거리나 유전적 거리와 같은 수치적 거리 정보로, DNA 서열이나 단백질 서열을 비교하여 얻을 수 있다. 이 거리 행렬은 알고리즘 전체 과정에서 클러스터를 병합하고 거리를 갱신하는 기준이 되는 핵심 자료 구조이다.
거리 행렬의 각 요소는 두 분류군 또는 서열 사이의 차이를 정량화한 값이다. 예를 들어, 염기 서열을 비교할 때는 해밍 거리나 Jukes-Cantor 모델과 같은 진화 모델을 통해 보정된 거리를 사용할 수 있다. 행렬이 완성되면, 알고리즘은 이 행렬에서 가장 작은 거리 값을 찾아 해당하는 두 객체를 첫 번째 클러스터로 병합한다. 이 초기 거리 행렬은 모든 객체가 개별 클러스터인 상태를 나타낸다.
2.2. 클러스터 병합 과정
2.2. 클러스터 병합 과정
UPGMA의 클러스터 병합 과정은 초기 거리 행렬에서 시작하여 가장 유사한 두 개체 또는 클러스터를 반복적으로 묶어 나가는 방식으로 진행된다. 알고리즘은 모든 개체가 하나의 루트 클러스터로 합쳐질 때까지 다음 단계를 순환한다. 먼저, 현재 거리 행렬에서 가장 작은 거리 값을 갖는 한 쌍의 클러스터(초기에는 개별 개체)를 찾는다. 이 두 클러스터를 선택하여 새로운 상위 클러스터로 병합하고, 계통도 상에서는 이 두 클러스터가 연결되는 분기점의 높이를 해당 거리 값의 절반으로 설정한다.
병합이 이루어진 후, 새로 생성된 클러스터와 나머지 다른 모든 클러스터 간의 새로운 거리를 계산하여 거리 행렬을 갱신해야 한다. UPGMA의 핵심 규칙인 "비가중" 평균 연결법에 따라, 이 새로운 거리는 병합된 두 클러스터 각각과 제3의 클러스터 사이의 기존 거리들의 단순 산술 평균으로 구한다. 예를 들어, 클러스터 A와 B가 병합되어 새 클러스터 (AB)를 형성했다면, (AB)와 다른 클러스터 C 사이의 거리는 (A-C 거리 + B-C 거리) / 2 의 공식으로 계산된다. 이 방법은 병합되는 각 클러스터 내의 개체 수에 관계없이 동등한 가중치를 부여한다는 특징이 있다.
갱신된 거리 행렬에서 다시 최소 거리 쌍을 찾아 병합하는 과정을 반복하면, 점점 더 큰 클러스터가 만들어지고 계통수의 가지가 완성되어 간다. 이 과정은 모든 개체가 하나의 군집으로 통합되어 거리 행렬의 크기가 1x1이 될 때까지 계속된다. 최종적으로 생성된 이진 계통수는 각 분기점의 높이가 병합 당시의 거리 값을 반영하므로, 분자 시계 가설을 가정할 때 진화적 분기 시점을 추정하는 데 활용될 수 있다.
이러한 단순하고 결정론적인 병합 과정은 UPGMA가 진화적 거리가 울트라메트릭 조건, 즉 모든 계통 가지의 말단에서 루트까지의 거리가 동일하다는 조건을 만족하는 데이터에 가장 적합하게 만든다. 실제 염기서열 데이터가 이 조건을 정확히 따르지 않을 경우, 병합 순서와 최종 계통수의 정확도에 영향을 미칠 수 있다.
2.3. 계통도 생성
2.3. 계통도 생성
UPGMA 알고리즘의 최종 결과물은 이진 계통수인 덴드로그램이다. 이 계통수는 알고리즘의 병합 과정을 그대로 반영하여 생성된다. 각 병합 단계에서 두 클러스터가 하나의 새로운 노드 아래에 연결되며, 이 노드의 높이는 두 클러스터 간의 원래 거리의 절반으로 설정된다. 이 높이는 분기점이 발생한 진화적 거리 또는 유전적 거리를 의미한다.
따라서 생성된 덴드로그램의 잎 노드들은 원래의 개별 객체(예: 생물 종이나 DNA 서열)를 나타내고, 내부 노드들은 병합된 클러스터를 나타낸다. 모든 잎 노드는 최종 루트 노드까지의 경로 길이의 합이 동일한 균등 분기 특성을 가지며, 이는 분자 시계 가정과 일치하는 형태이다. 이렇게 완성된 계통도는 생물정보학 연구에서 계통 관계를 가시화하고 가설을 검증하는 데 핵심적으로 활용된다.
3. 장단점
3. 장단점
3.1. 장점
3.1. 장점
UPGMA의 가장 큰 장점은 알고리즘의 단순성과 계산의 용이성에 있다. 거리 행렬에서 가장 가까운 두 개체 또는 클러스터를 찾아 병합하고, 새로운 평균 거리를 계산하는 과정을 반복하기 때문에 그 원리를 이해하고 구현하기가 비교적 쉽다. 이로 인해 계통수나 덴드로그램을 빠르게 생성할 수 있어, 특히 데이터 세트의 크기가 크지 않을 때 효율적으로 작동한다.
또 다른 장점은 항상 균형 잡힌 계통수를 생성한다는 점이다. UPGMA는 병합 과정에서 두 클러스터의 크기(포함된 개체 수)에 관계없이 거리만을 기준으로 평균을 계산하는 비가중 방식을 사용한다. 이는 병합되는 두 그룹이 동일한 진화 속도, 즉 분자 시계 가설을 따른다고 가정할 때, 진화 시간에 따라 균형적으로 갈라진 계통을 재구성하는 데 이론적으로 적합한 결과를 제공할 수 있다.
이러한 특성 덕분에 UPGMA는 생물정보학 분야에서 유전적 거리나 형질 데이터를 기반으로 한 예비적인 계통 분석이나 시각화에 널리 활용된다. 방법이 직관적이고 표준화되어 있어, 다양한 계통학 소프트웨어나 통계 패키지에서 기본적인 군집 분석 도구로 포함되는 경우가 많다.
3.2. 단점
3.2. 단점
UPGMA는 계산이 간단하고 직관적이라는 장점에도 불구하고 몇 가지 명확한 단점을 지닌다. 가장 큰 문제는 분자 시계 가설을 암묵적으로 가정한다는 점이다. 이 방법은 모든 계통적 계보에서 진화 속도가 일정하다고 가정하여, 병합 과정에서 각 클러스터까지의 거리를 평균으로 계산한다. 따라서 실제 진화 과정에서 진화 속도가 계통군마다 다를 경우, 즉 분기의 길이가 균일하지 않은 경우 잘못된 계통수를 만들어낼 가능성이 높다.
이러한 제한으로 인해 UPGMA는 진화 속도가 비교적 균일한 미토콘드리아 DNA나 특정 바이러스 계통 분석에는 유용할 수 있으나, 일반적인 분자 계통학 분석에서는 더 정교한 방법들에 비해 덜 선호된다. 특히 긴 가지와 짧은 가지가 공존하는 불균일한 진화 속도를 보이는 데이터를 분석할 때는 NJ (Neighbor-Joining) 방법이나 최대 간결법과 같은 방법이 더 정확한 결과를 제공한다.
또한 UPGMA는 거리 행렬 기반 방법이기 때문에, 염기서열 데이터 자체가 아닌 사전 계산된 유전적 거리에 의존한다. 이는 원본 서열 데이터가 갖는 진화적 정보의 일부를 잃어버릴 수 있음을 의미하며, 최대 우도법과 같이 서열 데이터를 직접 모델에 적용하는 방법에 비해 통계적 엄밀성이 떨어진다고 평가받는다. 결론적으로 UPGMA는 빠른 예비 분석이나 교육용 도구로서의 가치는 있으나, 엄격한 학술 연구에서는 그 단점을 보완할 수 있는 다른 계통수 추론 방법이 주로 사용된다.
4. 응용 분야
4. 응용 분야
UPGMA는 그 직관적이고 계산이 비교적 간단한 알고리즘 덕분에 여러 분야에서 계층적 군집 분석을 수행하는 데 활용된다. 특히 생물정보학 분야에서 분자 계통수를 구성하는 기본 도구로 널리 사용된다. DNA 서열이나 단백질 서열 간의 유전적 거리를 계산하여 얻은 거리 행렬을 입력으로, 종이나 계통군 간의 진화적 유연관계를 시각적으로 보여주는 덴드로그램을 생성하는 데 자주 적용된다.
이 방법은 유전체학 연구에서 다양한 생물 집단의 유전적 다양성과 구조를 분석할 때 유용하게 쓰인다. 예를 들어, 서로 다른 지리적 집단에 속하는 개체들의 유전자 변이 패턴을 비교하거나, 바이러스의 계통발생학적 역사를 추적하는 데 활용될 수 있다. 미생물 군집 연구에서도 메타지노믹스 데이터를 바탕으로 군집 구조를 파악하는 데 도움을 준다.
생물학 외에도, 언어학에서 언어 계통수를 만들거나, 문화인류학에서 다양한 문화적 특성의 유사성을 기반으로 문화군을 분류하는 데 응용되기도 한다. 간단한 데이터 마이닝 작업에서도 클러스터링 기법의 하나로 사용되어, 복잡한 다변량 데이터의 구조를 이해하는 데 기여한다.
5. 관련 개념 및 방법
5. 관련 개념 및 방법
5.1. NJ (Neighbor-Joining) 방법
5.1. NJ (Neighbor-Joining) 방법
NJ (Neighbor-Joining) 방법은 UPGMA와 함께 분자 계통학에서 가장 널리 사용되는 거리 기반 계통수 추론 방법 중 하나이다. UPGMA가 진화 속도가 일정하다는 가정(분자 시계 가설)을 전제로 하는 반면, NJ 방법은 진화 속도가 계통마다 다를 수 있다는 점을 고려하여 보다 현실적인 계통수를 구성할 수 있도록 설계되었다. 이 방법은 각 분류군이 다른 모든 분류군과의 거리를 최소화하는 위치에 배치되도록 하는 원리를 바탕으로 한다.
알고리즘은 초기에 성상도 형태로 시작하여, 반복적인 단계를 거쳐 계통수를 완성한다. 각 단계에서는 현재 거리 행렬을 바탕으로 각 분류군 쌍에 대한 'Q 값'을 계산하는데, 이 값은 해당 두 분류군을 병합했을 때 전체 계통 길이가 얼마나 짧아지는지를 나타내는 지표 역할을 한다. Q 값이 가장 작은, 즉 병합 시 가장 효율적인 두 분류군(또는 노드)을 선택하여 새로운 내부 노드로 연결한다. 이후 새로 형성된 노드와 나머지 모든 노드 간의 거리를 다시 계산하고, 병합된 두 분류군을 제거한 새로운 거리 행렬을 생성한다. 이 과정을 노드가 하나만 남을 때까지 반복한다.
NJ 방법의 주요 장점은 계산 속도가 비교적 빠르고, 진화 속도의 불균일성을 어느 정도 수용할 수 있어 UPGMA보다 더 정확한 계통수를 제공할 가능성이 높다는 점이다. 이로 인해 염기 서열 데이터나 단백질 서열 데이터로부터 유전적 거리를 계산한 후 계통수를 그리는 표준적인 방법으로 자리 잡았다. 특히 생물정보학 소프트웨어인 MEGA나 PHYLIP 같은 패키지에서 기본적으로 제공되는 방법이다.
하지만 NJ 방법 역시 완벽하지는 않다. 이 방법은 하나의 계통수만을 결과로 제시하며, 데이터에 내재된 불확실성(예: 부트스트랩 값)을 직접 평가하지는 않는다. 또한 거리 행렬 자체가 이미 정보의 손실을 포함하고 있기 때문에, 원시 염기 서열 데이터를 직접 사용하는 최대 간결법이나 최대 가능도법 같은 문자 기반 방법에 비해 정확도가 떨어질 수 있다는 비판도 존재한다.
5.2. 최대 간결법
5.2. 최대 간결법
최대 간결법은 계통수를 추론하는 방법 중 하나로, 계통수 상에서 필요한 진화적 변화의 횟수를 최소화하는 원칙에 기반한다. 이 방법은 관찰된 데이터(예: 염기서열이나 형질 상태)를 설명하는 데 가장 간단한 진화 시나리오를 선호한다. 즉, 가장 적은 수의 돌연변이나 형질 변화만으로 현재의 관찰 결과를 설명할 수 있는 계통수를 선택하는 것이다. 이는 오컴의 면도날 원칙을 계통학에 적용한 것으로 볼 수 있다.
이 방법은 분자 계통학과 형태 계통학 모두에서 사용되며, 특히 염기서열 데이터를 분석할 때 널리 활용된다. 분석 과정에서는 가능한 모든 계통수 후보를 평가하여, 각 후보 계통수에서 데이터를 설명하는 데 필요한 진화 변화의 총 횟수를 계산한다. 이 총 횟수를 트리 길이라고 하며, 트리 길이가 가장 짧은 계통수가 최적의 계통수로 선택된다. 이 계산은 종종 파스퇴르 알고리즘과 같은 효율적인 알고리즘을 통해 수행된다.
최대 간결법의 주요 장점은 진화 모델에 대한 명시적인 가정을 크게 요구하지 않는다는 점이다. 거리 기반 방법이나 최대 가능도법과 달리, 진화 속도가 일정하다는 가정이나 특정 뉴클레오타이드 치환 모델을 필요로 하지 않는다. 따라서 형태학적 데이터나 복잡한 진화 역사를 가진 데이터를 분석할 때 유용하게 적용될 수 있다.
그러나 이 방법은 동형성과 상동성을 구분하는 데 어려움을 겪을 수 있으며, 진화 과정에서 수렴 진화나 되돌이 돌연변이가 빈번하게 일어난 경우 잘못된 계통수를 추론할 위험이 있다. 또한 가능한 모든 계통수를 탐색해야 하기 때문에 분석 대상 분류군의 수가 많아지면 계산량이 기하급수적으로 증가하는 계산상의 한계를 지닌다.
6. 여담
6. 여담
UPGMA는 계층적 군집 분석 방법 중 가장 기본적이고 직관적인 알고리즘 중 하나로 간주된다. 이 방법은 계통수를 구성하는 초기 방법으로 널리 사용되었으며, 특히 생물정보학 분야에서 분자 진화 연구의 초석을 마련하는 데 기여했다. UPGMA의 간단한 원리 덕분에 계산 생물학 입문 교육에서도 자주 다루어지는 주제이다.
그러나 UPGMA는 모든 진화적 계보가 동일한 진화 속도를 가진다는, 즉 분자 시계 가설이 엄격하게 성립한다는 전제를 내포하고 있다. 이는 현실의 많은 생물 종 간 유전적 거리 데이터에서는 성립하기 어려운 가정으로, 이로 인해 생성된 계통수가 실제 계통 발생 역사를 왜곡할 가능성이 지적받는다. 이러한 한계점은 NJ 방법이나 최대 간결법과 같은 보다 정교한 방법들이 개발되는 동기가 되었다.
오늘날 UPGMA는 그 역사적 중요성과 개념적 명료성 때문에 교육적 목적이나 빠른 예비 분석에 여전히 사용된다. 또한 유전체학이나 메타지노믹스에서 방대한 서열 데이터를 초기 단계에서 그룹화하여 시각화하는 데 유용한 도구로 활용되기도 한다. 복잡한 계통학적 분석의 첫걸음으로서 UPGMA의 역할은 여전히 유효하다고 볼 수 있다.
