Skip to content

Neighbor joining #
Find similar titles

Structured data

Category
Algorithm

Neighbor joining(이웃 결합) #

Neighbor joining은 거리 계산 방법중 하나로, UPGMA법을 사용할 때 생길 수 있는 오류를 제거할 수 있다.

UPGMA는 거리를 기준으로 가장 가까운 가지들이 이웃하는 트리를 만든다.

이 가정은 트리의 토폴로지에 제한을 가하여 어떤 상황에는 잘못된 트리를 만들 수도 있다.

이런 문제를 해결하기 위해 NJ 알고리즘은 단지 거리 계산에 의한 최소의 pairwise 거리만 찾는 것이 아니라 트리의 전체 길이를 최소화하는 이웃의 집합을 탐색한다.

NJ 알고리즘은 전체 염기서열에서 각 두 개의 염기서열을 비교하여 진화적 거리를 계산한다는점에서 Maximum likelihood와 같은 진화적 모델을 사용한다.

실제로 염기서열간의 거리는 Maximum likelihood 방법을 사용하기도 한다.

하지만 이렇게 계산한 거리값을 가지고 계통수를 바로 만들려면, 항상 이들 염기서열 상호간의 거리들을 모두 만족시키는 계통수가 실제로 없으므로, 따라서 이들 값을 가장 많이 만족시키는 소위 best-fitting phylogeny를 NJ 알고리즘 등의 방법을 통해 얻게 된다. 이러한 방법들은 몇가지 단점이 있는데, 대표적인 것으로 우선 염기서열간 차이를 거리라고 하는 숫자로 변환시킴으로써 염기서열 그 자체에 대한 정보가 사라진다는 점을 등 수 있다.

그럼에도, NJ 알고리즘은 거리 기반의 방법으로 가장 널리 사용되며 특히 진화적인 거리가 가까울수록 합리적인 트리를 만들 수 있다.

참고문헌 #

Suggested Pages #

0.0.1_20140628_0