UPGMA

UPGMA 알고리즘의 첫 단계는 분석 대상 객체들 간의 모든 쌍의 거리를 정리한 거리 행렬을 구성하는 것이다. 이 행렬은 대칭 행렬이며, 주 대각선의 값은 자기 자신과의 거리이므로 보통 0으로 설정된다. 입력 데이터는 진화적 거리나 유전적 거리와 같은 수치적 거리 정보로, DNA 서열이나 단백질 서열을 비교하여 얻을 수 있다. 이 거리 행렬은 알고리즘 전체 과정에서 클러스터를 병합하고 거리를 갱신하는 기준이 되는 핵심 자료 구조이다.

거리 행렬의 각 요소는 두 분류군 또는 서열 사이의 차이를 정량화한 값이다. 예를 들어, 염기 서열을 비교할 때는 해밍 거리나 Jukes-Cantor 모델과 같은 진화 모델을 통해 보정된 거리를 사용할 수 있다. 행렬이 완성되면, 알고리즘은 이 행렬에서 가장 작은 거리 값을 찾아 해당하는 두 객체를 첫 번째 클러스터로 병합한다. 이 초기 거리 행렬은 모든 객체가 개별 클러스터인 상태를 나타낸다.

UPGMA의 클러스터 병합 과정은 초기 거리 행렬에서 시작하여 가장 유사한 두 개체 또는 클러스터를 반복적으로 묶어 나가는 방식으로 진행된다. 알고리즘은 모든 개체가 하나의 루트 클러스터로 합쳐질 때까지 다음 단계를 순환한다. 먼저, 현재 거리 행렬에서 가장 작은 거리 값을 갖는 한 쌍의 클러스터(초기에는 개별 개체)를 찾는다. 이 두 클러스터를 선택하여 새로운 상위 클러스터로 병합하고, 계통도 상에서는 이 두 클러스터가 연결되는 분기점의 높이를 해당 거리 값의 절반으로 설정한다.

병합이 이루어진 후, 새로 생성된 클러스터와 나머지 다른 모든 클러스터 간의 새로운 거리를 계산하여 거리 행렬을 갱신해야 한다. UPGMA의 핵심 규칙인 "비가중" 평균 연결법에 따라, 이 새로운 거리는 병합된 두 클러스터 각각과 제3의 클러스터 사이의 기존 거리들의 단순 산술 평균으로 구한다. 예를 들어, 클러스터 A와 B가 병합되어 새 클러스터 (AB)를 형성했다면, (AB)와 다른 클러스터 C 사이의 거리는 (A-C 거리 + B-C 거리) / 2 의 공식으로 계산된다. 이 방법은 병합되는 각 클러스터 내의 개체 수에 관계없이 동등한 가중치를 부여한다는 특징이 있다.

갱신된 거리 행렬에서 다시 최소 거리 쌍을 찾아 병합하는 과정을 반복하면, 점점 더 큰 클러스터가 만들어지고 계통수의 가지가 완성되어 간다. 이 과정은 모든 개체가 하나의 군집으로 통합되어 거리 행렬의 크기가 1x1이 될 때까지 계속된다. 최종적으로 생성된 이진 계통수는 각 분기점의 높이가 병합 당시의 거리 값을 반영하므로, 분자 시계 가설을 가정할 때 진화적 분기 시점을 추정하는 데 활용될 수 있다.

이러한 단순하고 결정론적인 병합 과정은 UPGMA가 진화적 거리가 울트라메트릭 조건, 즉 모든 계통 가지의 말단에서 루트까지의 거리가 동일하다는 조건을 만족하는 데이터에 가장 적합하게 만든다. 실제 염기서열 데이터가 이 조건을 정확히 따르지 않을 경우, 병합 순서와 최종 계통수의 정확도에 영향을 미칠 수 있다.

UPGMA 알고리즘의 최종 결과물은 이진 계통수인 덴드로그램이다. 이 계통수는 알고리즘의 병합 과정을 그대로 반영하여 생성된다. 각 병합 단계에서 두 클러스터가 하나의 새로운 노드 아래에 연결되며, 이 노드의 높이는 두 클러스터 간의 원래 거리의 절반으로 설정된다. 이 높이는 분기점이 발생한 진화적 거리 또는 유전적 거리를 의미한다.

따라서 생성된 덴드로그램의 잎 노드들은 원래의 개별 객체(예: 생물 종이나 DNA 서열)를 나타내고, 내부 노드들은 병합된 클러스터를 나타낸다. 모든 잎 노드는 최종 루트 노드까지의 경로 길이의 합이 동일한 균등 분기 특성을 가지며, 이는 분자 시계 가정과 일치하는 형태이다. 이렇게 완성된 계통도는 생물정보학 연구에서 계통 관계를 가시화하고 가설을 검증하는 데 핵심적으로 활용된다.

UPGMA의 가장 큰 장점은 알고리즘의 단순성과 계산의 용이성에 있다. 거리 행렬에서 가장 가까운 두 개체 또는 클러스터를 찾아 병합하고, 새로운 평균 거리를 계산하는 과정을 반복하기 때문에 그 원리를 이해하고 구현하기가 비교적 쉽다. 이로 인해 계통수나 덴드로그램을 빠르게 생성할 수 있어, 특히 데이터 세트의 크기가 크지 않을 때 효율적으로 작동한다.

또 다른 장점은 항상 균형 잡힌 계통수를 생성한다는 점이다. UPGMA는 병합 과정에서 두 클러스터의 크기(포함된 개체 수)에 관계없이 거리만을 기준으로 평균을 계산하는 비가중 방식을 사용한다. 이는 병합되는 두 그룹이 동일한 진화 속도, 즉 분자 시계 가설을 따른다고 가정할 때, 진화 시간에 따라 균형적으로 갈라진 계통을 재구성하는 데 이론적으로 적합한 결과를 제공할 수 있다.

이러한 특성 덕분에 UPGMA는 생물정보학 분야에서 유전적 거리나 형질 데이터를 기반으로 한 예비적인 계통 분석이나 시각화에 널리 활용된다. 방법이 직관적이고 표준화되어 있어, 다양한 계통학 소프트웨어나 통계 패키지에서 기본적인 군집 분석 도구로 포함되는 경우가 많다.

UPGMA는 계산이 간단하고 직관적이라는 장점에도 불구하고 몇 가지 명확한 단점을 지닌다. 가장 큰 문제는 분자 시계 가설을 암묵적으로 가정한다는 점이다. 이 방법은 모든 계통적 계보에서 진화 속도가 일정하다고 가정하여, 병합 과정에서 각 클러스터까지의 거리를 평균으로 계산한다. 따라서 실제 진화 과정에서 진화 속도가 계통군마다 다를 경우, 즉 분기의 길이가 균일하지 않은 경우 잘못된 계통수를 만들어낼 가능성이 높다.

이러한 제한으로 인해 UPGMA는 진화 속도가 비교적 균일한 미토콘드리아 DNA나 특정 바이러스 계통 분석에는 유용할 수 있으나, 일반적인 분자 계통학 분석에서는 더 정교한 방법들에 비해 덜 선호된다. 특히 긴 가지와 짧은 가지가 공존하는 불균일한 진화 속도를 보이는 데이터를 분석할 때는 NJ (Neighbor-Joining) 방법이나 최대 간결법과 같은 방법이 더 정확한 결과를 제공한다.

또한 UPGMA는 거리 행렬 기반 방법이기 때문에, 염기서열 데이터 자체가 아닌 사전 계산된 유전적 거리에 의존한다. 이는 원본 서열 데이터가 갖는 진화적 정보의 일부를 잃어버릴 수 있음을 의미하며, 최대 우도법과 같이 서열 데이터를 직접 모델에 적용하는 방법에 비해 통계적 엄밀성이 떨어진다고 평가받는다. 결론적으로 UPGMA는 빠른 예비 분석이나 교육용 도구로서의 가치는 있으나, 엄격한 학술 연구에서는 그 단점을 보완할 수 있는 다른 계통수 추론 방법이 주로 사용된다.

NJ (Neighbor-Joining) 방법은 UPGMA와 함께 분자 계통학에서 가장 널리 사용되는 거리 기반 계통수 추론 방법 중 하나이다. UPGMA가 진화 속도가 일정하다는 가정(분자 시계 가설)을 전제로 하는 반면, NJ 방법은 진화 속도가 계통마다 다를 수 있다는 점을 고려하여 보다 현실적인 계통수를 구성할 수 있도록 설계되었다. 이 방법은 각 분류군이 다른 모든 분류군과의 거리를 최소화하는 위치에 배치되도록 하는 원리를 바탕으로 한다.

알고리즘은 초기에 성상도 형태로 시작하여, 반복적인 단계를 거쳐 계통수를 완성한다. 각 단계에서는 현재 거리 행렬을 바탕으로 각 분류군 쌍에 대한 'Q 값'을 계산하는데, 이 값은 해당 두 분류군을 병합했을 때 전체 계통 길이가 얼마나 짧아지는지를 나타내는 지표 역할을 한다. Q 값이 가장 작은, 즉 병합 시 가장 효율적인 두 분류군(또는 노드)을 선택하여 새로운 내부 노드로 연결한다. 이후 새로 형성된 노드와 나머지 모든 노드 간의 거리를 다시 계산하고, 병합된 두 분류군을 제거한 새로운 거리 행렬을 생성한다. 이 과정을 노드가 하나만 남을 때까지 반복한다.

NJ 방법의 주요 장점은 계산 속도가 비교적 빠르고, 진화 속도의 불균일성을 어느 정도 수용할 수 있어 UPGMA보다 더 정확한 계통수를 제공할 가능성이 높다는 점이다. 이로 인해 염기 서열 데이터나 단백질 서열 데이터로부터 유전적 거리를 계산한 후 계통수를 그리는 표준적인 방법으로 자리 잡았다. 특히 생물정보학 소프트웨어인 MEGA나 PHYLIP 같은 패키지에서 기본적으로 제공되는 방법이다.

하지만 NJ 방법 역시 완벽하지는 않다. 이 방법은 하나의 계통수만을 결과로 제시하며, 데이터에 내재된 불확실성(예: 부트스트랩 값)을 직접 평가하지는 않는다. 또한 거리 행렬 자체가 이미 정보의 손실을 포함하고 있기 때문에, 원시 염기 서열 데이터를 직접 사용하는 최대 간결법이나 최대 가능도법 같은 문자 기반 방법에 비해 정확도가 떨어질 수 있다는 비판도 존재한다.

최대 간결법은 계통수를 추론하는 방법 중 하나로, 계통수 상에서 필요한 진화적 변화의 횟수를 최소화하는 원칙에 기반한다. 이 방법은 관찰된 데이터(예: 염기서열이나 형질 상태)를 설명하는 데 가장 간단한 진화 시나리오를 선호한다. 즉, 가장 적은 수의 돌연변이나 형질 변화만으로 현재의 관찰 결과를 설명할 수 있는 계통수를 선택하는 것이다. 이는 오컴의 면도날 원칙을 계통학에 적용한 것으로 볼 수 있다.

이 방법은 분자 계통학과 형태 계통학 모두에서 사용되며, 특히 염기서열 데이터를 분석할 때 널리 활용된다. 분석 과정에서는 가능한 모든 계통수 후보를 평가하여, 각 후보 계통수에서 데이터를 설명하는 데 필요한 진화 변화의 총 횟수를 계산한다. 이 총 횟수를 트리 길이라고 하며, 트리 길이가 가장 짧은 계통수가 최적의 계통수로 선택된다. 이 계산은 종종 파스퇴르 알고리즘과 같은 효율적인 알고리즘을 통해 수행된다.

최대 간결법의 주요 장점은 진화 모델에 대한 명시적인 가정을 크게 요구하지 않는다는 점이다. 거리 기반 방법이나 최대 가능도법과 달리, 진화 속도가 일정하다는 가정이나 특정 뉴클레오타이드 치환 모델을 필요로 하지 않는다. 따라서 형태학적 데이터나 복잡한 진화 역사를 가진 데이터를 분석할 때 유용하게 적용될 수 있다.

그러나 이 방법은 동형성과 상동성을 구분하는 데 어려움을 겪을 수 있으며, 진화 과정에서 수렴 진화나 되돌이 돌연변이가 빈번하게 일어난 경우 잘못된 계통수를 추론할 위험이 있다. 또한 가능한 모든 계통수를 탐색해야 하기 때문에 분석 대상 분류군의 수가 많아지면 계산량이 기하급수적으로 증가하는 계산상의 한계를 지닌다.