Neighbor-Joining

거리 행렬 계산은 Neighbor-Joining 알고리즘의 첫 번째 단계로, 분석 대상 분류군들 사이의 진화적 거리를 수치화하여 정방형 행렬 형태로 구성하는 과정이다. 이 거리 행렬은 알고리즘의 모든 후속 계산의 기초가 된다.

거리 행렬의 각 요소는 일반적으로 분자 계통학에서 널리 사용되는 유전적 거리 척도, 예를 들어 p-거리나 Jukes-Cantor 모델과 같은 진화 모델에 기반한 보정 거리 등을 사용하여 계산된다. 입력 데이터는 DNA 서열이나 단백질 서열과 같은 분자 데이터가 일반적이며, 서열 간의 상동성을 정렬한 후 변이의 비율을 측정한다.

이렇게 계산된 거리 행렬은 대칭적이며, 대각선 요소(자기 자신과의 거리)는 0이다. 예를 들어, 네 개의 분류군(A, B, C, D)에 대한 거리 행렬은 다음과 같은 형태를 가진다.

이 초기 거리 행렬은 알고리즘의 다음 단계인 Q-행렬 계산의 입력값으로 사용된다. 거리 추정의 정확성은 최종 계통수의 신뢰도에 직접적인 영향을 미치므로, 적절한 진화 모델을 선택하는 것이 중요하다.

Neighbor-Joining 알고리즘의 핵심 단계는 거리 행렬로부터 Q-행렬을 계산하는 것이다. 이 과정은 현재 남아 있는 클러스터 또는 OTU 쌍들 중에서 가장 가까운 이웃, 즉 병합할 후보 쌍을 선택하기 위해 수행된다.

Q-행렬의 각 원소 Q(i,j)는 다음 공식에 따라 계산된다. Q(i,j) = (n-2) * d(i,j) - Σ_k d(i,k) - Σ_k d(j,k). 여기서 d(i,j)는 OTU i와 j 사이의 진화적 거리를 나타내며, n은 현재 반복 단계에서 남아 있는 OTU의 총 개수이다. Σ_k d(i,k)는 OTU i로부터 다른 모든 OTU까지의 거리의 합을 의미한다. 이 공식은 두 클러스터가 병합될 때 발생하는 계통수의 총 길이 증가를 최소화하는 쌍을 찾는 원리에 기반한다.

간단히 말해, 이 계산은 단순한 쌍별 거리 d(i,j)만을 보는 것이 아니라, 해당 쌍이 전체 계통망에서 얼마나 '고립'되어 있는지를 고려한다. 다른 모든 노드로부터의 거리 합이 큰, 즉 전체적으로 멀리 떨어진 클러스터 쌍에 대해 불이익을 주는 방식으로 작동한다. 결과적으로 Q-행렬에서 가장 작은 값을 갖는 원소의 인덱스 (i, j)가 다음 반복에서 연결될 이웃 쌍으로 선택된다.

이 Q-행렬 계산 단계는 Neighbor-Joining이 UPGMA와 같은 단순 클러스터링 방법과 구분되는 특징이다. UPGMA는 항상 가장 짧은 거리를 가진 쌍을 병합하지만, Neighbor-Joining은 진화 속도가 균일하지 않을 수 있는 상황, 즉 분기 길이에 불균형이 존재할 수 있는 현실적인 계통학 데이터를 더 잘 처리할 수 있도록 설계되었다.

이 단계에서는 계산된 Q-행렬에서 가장 작은 값을 갖는 두 클러스터 i와 j를 선택하여 새로운 내부 노드 u를 생성하고, 이들을 연결한다. 이때 노드 u와 기존 노드 i, j 사이의 가지 길이를 계산해야 한다. 이 거리는 다른 모든 노드 k에 대한 기존의 거리 데이터를 기반으로 산출된다.

새로운 노드 u와 클러스터 i 사이의 가지 길이는 공식 (d_iu = d_ij / 2 + (S_i - S_j) / 2(N-2))을 사용하여 계산된다. 여기서 d_ij는 i와 j 사이의 원래 거리이며, S_i와 S_j는 각각 i와 j에 대한 거리의 합, N은 현재 클러스터의 총 개수를 나타낸다. 노드 u와 j 사이의 거리 d_ju는 d_ij에서 d_iu를 빼거나, 대칭적인 공식으로 구할 수 있다. 이 계산은 새로 연결된 두 노드가 나무의 다른 모든 노드로부터 동일한 거리에 있도록 보장하지는 않지만, 최소 진화 원칙을 충족하는 추정치를 제공한다.

새로운 노드 u가 생성된 후, 이 노드와 나머지 모든 노드 k 사이의 새로운 거리 d_uk를 계산해야 한다. 이 거리는 공식 d_uk = (d_ik + d_jk - d_ij) / 2 을 통해 구한다. 이는 노드 i와 j를 통합한 후, 노드 u와 다른 노드 k 사이의 거리를 기존의 쌍별 거리로부터 추정하는 과정이다. 이렇게 계산된 새로운 거리 d_uk는 다음 반복 단계에서 사용될 새로운 거리 행렬에 포함된다.

알고리즘의 핵심은 거리 행렬과 Q-행렬 계산, 그리고 노드 연결을 반복적으로 수행하여 계통수를 완성하는 데 있다. 이 과정은 남은 클러스터의 개수가 2개가 될 때까지 계속된다.

반복 과정은 다음과 같이 진행된다. 먼저, 현재 거리 행렬을 바탕으로 Q-행렬을 계산하고, 그 값이 가장 작은 두 클러스터 i와 j를 선택하여 새로운 내부 노드 u를 생성한다. 그런 다음, i와 j에서 u까지의 가지 길이를 계산하고, i와 j를 거리 행렬에서 제거한 후 새 노드 u를 추가한다. 새 노드 u와 나머지 다른 모든 클러스터 k 사이의 거리도 계산하여 갱신된 거리 행렬을 만든다. 이렇게 한 사이클이 완료되면, 남은 클러스터의 수가 하나 줄어든 상태에서 동일한 과정을 처음부터 다시 시작한다.

이러한 단계는 계통수의 가지가 하나씩 완성되어 나가며, 최종적으로 마지막 두 클러스터를 연결하는 가지 길이를 계산하면 전체 계통수가 완성된다. 이 방법은 최소진화법의 원리를 근사적으로 구현하는 하향식 접근법으로, 각 반복에서 국소적으로 최적인 쌍을 선택하여 전체 계통수를 구성한다.

반복 과정의 효율성 덕분에 Neighbor-Joining은 비교적 빠른 계산 속도를 가지며, 대규모 유전자 서열 데이터나 형질 데이터를 분석하는 데 널리 사용된다. 이 알고리즘은 분자 계통학과 생물정보학 연구에서 진화적 관계를 시각화하는 표준 도구 중 하나로 자리 잡았다.

Neighbor-Joining 알고리즘의 가장 큰 장점은 계산 속도가 빠르다는 점이다. 이 알고리즘은 거리 행렬만을 기반으로 하여 계통수를 구성하기 때문에, 최대 간명법이나 최대 우도법과 같은 다른 방법들에 비해 계산 복잡도가 현저히 낮다. 이는 특히 염기서열이나 아미노산 서열과 같이 많은 분자 데이터를 다루는 분자 계통학 연구에서 큰 이점으로 작용하며, 대규모 계통 분석을 실용적으로 수행할 수 있게 해준다.

또한, 이 방법은 진화 모델에 대한 강한 가정을 필요로 하지 않는다는 장점을 가진다. 알고리즘은 입력된 쌍별 거리 정보를 바탕으로 진화적 거리를 추정하므로, 복잡한 진화 모델을 설정하거나 평가할 필요가 없다. 이는 분석 과정을 단순화하고, 다양한 종류의 생물학적 데이터에 적용하기 용이하게 만든다.

마지막으로, Neighbor-Joining은 가산적 거리 조건을 완전히 만족하지 않는 데이터에서도 비교적 견고한 결과를 제공하는 경향이 있다. 즉, 실제 진화 과정에서 발생할 수 있는 변이율의 차이나 다른 복잡한 요인으로 인해 거리 행렬이 이상적이지 않을 경우에도, 다른 간단한 거리 기반 방법들보다는 더 정확한 계통수를 추정할 가능성이 높은 것으로 알려져 있다. 이러한 실용성과 효율성 덕분에 이 알고리즘은 생물정보학 및 진화생물학 분야에서 가장 널리 사용되는 계통수 추정 도구 중 하나로 자리 잡았다.

Neighbor-Joining 알고리즘은 계산 효율성과 유용성에도 불구하고 몇 가지 명확한 단점을 지닌다. 가장 큰 한계는 거리 기반 방법이라는 근본적인 속성에서 비롯된다. 이 알고리즘은 계통수를 구성하기 위해 진화적 거리를 요약한 거리 행렬에 전적으로 의존한다. 이는 최대 우도법이나 베이즈 추론과 같은 문자 기반 방법과 달리, 실제 염기서열이나 아미노산 서열 데이터에 내재된 진화적 정보의 세부 사항을 활용하지 못함을 의미한다. 결과적으로, 진화 모델의 복잡성이나 염기 치환의 패턴 같은 중요한 정보를 고려하지 못할 수 있다.

또 다른 단점은 단일 계통수를 생성한다는 점이다. 알고리즘은 각 단계에서 최소화 기준에 따라 결정을 내리기 때문에, 데이터에서 가능한 여러 가지 합리적인 계통수 가설을 탐색하거나 그 신뢰도를 평가하지 않는다. 이는 부트스트랩 분석과 같은 추가적인 절차 없이는 생성된 나무 가지의 통계적 지원도를 제공하기 어렵게 만든다. 따라서 Neighbor-Joining으로 얻은 결과는 종종 추가 검증을 위한 출발점으로 간주된다.

마지막으로, 알고리즘의 성능은 입력된 거리 행렬의 정확도에 크게 좌우된다. 거리 추정에 오류가 있거나, 사용된 진화 모델이 데이터에 적합하지 않다면, 그 오류는 계통수 추정 과정으로 전파되어 잘못된 위상을 초래할 수 있다. 특히 장거리 가지 현상이 있는 데이터나 진화 속도가 균일하지 않은 경우에 이러한 문제가 두드러질 수 있다.