Distance (거리) #

Distance는 두 오브젝트(object) 간에 간격을 나타내는 척도로 거리 함수를 이용하여 거리를 정의 할 수 있다. 기하학적으로는 두 점(두 물체) 사이가 얼마나 멀리 떨어지는가를 나타내며 기하학상의 두 점 이외에도 다양한 형태의 두 오브젝트를 거리 함수를 이용하여 두 오브젝트간의 거리를 정의 할 수 있으며 두 오브젝트 간의 차이를 수치화 하여 나타내는데 주로 사용한다.

거리함수 \( d ( P ,Q ) \)는 다음과 같은 조건을 만족해야 한다.

1. \( d ( P , Q ) \geq 0 \) (단 \(d(x,y) =0\) 은 \(x = y\)일 때 만족한다)
2. \( d ( P , Q ) = d ( Q , P ) \) (교환 법칙 성립)
3. \( d ( P , Q ) + d ( Q , P ) >= d ( P , R ) \)

컴퓨터 사이언스에서도 위와 같은 정의를 이용하여 같은 형식의 두 Data 간의 차이를 수치적으로 나타내는데 활용한다.

Distance 종류 #

Euclidean distance #

일반적으로 널리 알려진 Distance 는 유클리디안 거리(Euclidean distance) 로 두 점 사이의 거리를 계산할 때 널리 사용되는 방법으로 비 유클리디안 공간에서는 성립하지 않는다. \(n \)차원의 공간의 두 점 \(P, Q\)에서 유클리디안 거리\( d(P, Q) \)는 다음과 같이 정의된다. $$ d(P, Q ) = (~ \sum_{i = 1}^{n} (~|~q_i~-~p_j~|~)^{2}~ )^{1/2} $$

Manhattan distance #

맨해튼 거리, 혹은 택시 거리라고 불리며, 유클리디안 공간상에서 좌표의 각 성분의 차를 이용하여 거리를 정의한다. 점들이 의미하는 데이터의 특성에 따라 유클리디안 거리 대신 사용되기도 한다. 맨해튼 거리는 다음 식을 이용하여 구할 수 있다. $$ d(P, Q ) = \sum_{i = 1}^{n}(~|~q_i~-~p_j~|~) $$

Minkowski distance #

만코프스키 거리는 유클리디안 공간에서 두점 사이의 거리를 정의하는 가장 기본이 되는 방법으로 많은 거리 함수들이 만코프스키 거리를 기반으로 정의되었으며. 앞서 소개한 유클리디안 거리 및 맨해튼 거리 역시 \(r=1, r=2\) 일 때 만코프스키 거리이다. $$ d(P, Q ) = (~\sum_{i = 1}^{n} (~|~q_i~-~p_j ~|~)^{r}~)^{1/r} $$

Edit distance #

두 문자열 간의 거리를 나타낼 때 가장 널리 사용되는 거리 함수로, 두 문자열 간의 비유사도(Dissimilarity)를 나타내는데 사용된다. Edit distance는 A 문자열에서 B문자열로 변환하기 위해서는 몇 번의 Edit Operation을 수행해야 하는가에 의해 결정된다. Edit Operation 은 각 문자에 대해 다음 3가지 경우로 정의된다.

• Insertion(삽입) - 문자열에 하나의 Symbol을 추가할 경우.
• Deletion(삭제) - 문자열에서 하나의 Symbol을 제거할 경우.
• Subtitution (치환) - 문자열에서 하나의 Symbol을 다른 Symbol로 변환 할 경우

예를 들어 Kitten과 Kitchen 두 문장의 Edit distance는

1. Kitchen > Kitthen (Subtitution c > t)
2. Kitthen > Kitten (Deletion h)

두번의 Edit Operation으로 실행가능하므로 Edit Distance는 2가된다. Edit distance 는 Edit Operation 을 어떻게 사용하는가에 따라 무한대의 범위까지 값이 늘어나나 일반적으로 Edit Distance는 Minimum Edit Distance를 의미한다.

Bioinformatics 에서는 위와 같은 편집거리를 이용하여 두 유전자의 변이를 확인하거나 RNA Sequence를 Mapping 하는데 주로 사용된다. Bioinformatics에서 Edit Distance를 계산하는 가장 대표적인 알고리즘으로는 Minimum Edit Distance를 계산하는 Alignment 알고리즘 중 스미스-워터만 알고리즘이 있다.

Genetic distance #

Genetic distance 란 같은 종안의 집단간의 genetic divergence 를 측정하는 것이다.

종간, 아종간 등 일반적으로 다른 생물집단 사이의 유전적 차이를 유전자빈도나 상동인 DNA의 염기배열 상의 차이를 이용하여 나타내는 척도. 유전적 거리의 표현법에는 몇 가지 방식이 있는데, 유전자빈도의 자료에 근거하여 잘 사용하는 방식은 표준유전거리이다. 이 거리는 이상화된 조건에서는 진화의 과정에서 집단 사이에 하나의 유전자자리당 축적된 다른 돌연변이의 수를 나타낸다.

아종간에서는 0.16, 종간에서는 0.76, 속간에서는 2.0 정도인 것으로 알려져 있다. 신뢰도가 높은 유전적 거리의 추정치를 얻기 위해서는 많은 유전자자리를 사용할 필요가 있다. 또한 이 거리나 DNA배열의 차이를 이용하여 분자나 종의 계통수를 만드는 것이 가능해짐에 따라 분자계통학이라는 새로운 분야가 탄생하게 되었다. 유전적 거리 [genetic distance, 遺傳的距離] (생명과학대사전, 초판 2008., 개정판 2014., 도서출판 여초)