📂알고리즘

서열정렬 점수와 갭 페널티

정의

레퍼런스 서열과 쿼리 서열이 주어져 있다고 하자. 서열정렬 점수^{sequence Alignment Score}란 두 서열을 비교했을 때 얼마나 일치하는지를 수치화하는 것과 그 방법을 말한다. 점수화는 다음과 같은 사항들에 가중치를 주어 계산된다.

1. Match: 두 서열이 일치하는 횟수다.
2. Mismatch: 두 서열이 일치하지 않는 횟수다.

예시

예로써 위와 같은 두 염기서열이 있다고 하자. 이때 서열정렬을 하는 방법은 여러가지가 있겠지만, 어떤 정렬이 가장 좋은지에 대해서는 비교적 객관적인 근거가 있어야할 것이다. 이 예시에서의 두 서열은 길이가 같지 않기 때문에 뒷부분은 밀려쓰게 될텐데, 그것을 방지하기 위해 갭^gap을 추가할 것이다.

이 둘이 얼마나 일치하는지에 대해서 수치화하고 싶다면 매치와 미스매치 수에 비례한 점수를 주는 것이 합리적일 것이다. 매치는 6회, 빨간색 미스매치는 2회다. 여기서 두 개의 점수 체계 A, B를 생각해보자. A 체계는 매치에 2점, 미스매치에 -1점을 주고, B 체계는 매치에 1점, 미스매치에 -2점을 준다면 A 체계로는 $2\cdot 6 - 1 \cdot 2= 10$점, B체계로는 $1\cdot 6 - 2 \cdot 2= 2$점이 될 것이다. 이는 얼마나 같냐와 얼마나 다르냐라는 두 관점으로 정렬을 평가한 것으로 볼 수 있다. 이하로는 매치에 1점, 미스매치에 -1점을 주도록 하자. 그러면 위의 정렬은 $6-2=4$점이 된다.매치와 미스매치에 따른 가산점과 감점은 우리가 임의로 줘도 좋지만, 이미 널리 쓰이고 있는 점수표를 사용할 수도 있다. 이른바 치환행렬이라는 것으로, 꼭 염기서열이 아니라도 단백질서열에도 쓰일 수 있으며 다른 문자라도 얼마나 비슷한지가 반영되어 세밀한 점수 부여가 가능하다.

한편 밀려쓰기를 방지하기 위해 갭을 추가했다지만 엄연히 그것도 차이점이므로 감점을 주려고 하는데, 이를 갭 페널티라고 한다.

갭 페널티

3. Gap: 길이를 맞추기 위해 빈칸이 추가되어야하는 횟수다.
   1. Constant Gap Penalty: 갭이 있으면 감점한다.
   2. Linear Gap Penalty: 갭의 수만큼 감점한다.
   3. Affine Gap Penalty: 갭이 있는 부분과 그 길이로 감점한다.
      1. Open (Gap Penalty): 갭으로 이어진 부분이 시작되는 지점의 수다.
      2. Extension (Gap Penalty): 오픈 뒤로 이어지는 갭의 수를 모두 더한 것이다.

예시

Constant로 갭 페널티 -10을 준다면 아래 정렬의 점수는 $4-10 = -6$점이다. Linear로 갭 페널티 -1을 주면 갭의 수에 비례해 $4-1\cdot 5 = -1$ 점이다.

Affine Gap Penalty는 가장 널리 쓰이는 방식이다. Open은 말 그대로 갭의 구간을 열고, Extension은 열린 구간이 얼마나 확장되는지를 나타낸다. Open의 갭 페널티를 -2, extension의 갭 페널티를 -1이라 주면 갭의 구간이 둘이므로 Open은 2, Extension은 그 둘을 뺀 $5-2=3$ 개가 되어 최종 점수는 $10-2\cdot 2 - 1 \cdot 3 = 3$점이다.

갭 페널티에 붙은 명명들이 타당하다는 것은 다음 그림을 보면 쉽게 이해할 수 있다. Constant는 갭이 있는 것 자체로 페널티를 주고, Linear는 페널티의 수만큼 비례해서 준다. 아핀 혹은 아파인 이 붙은 말은 수학 전반에서 ‘평행이동’을 포함하고, 갭 페널티를 나타내는 직선이 평행이동이라는 개념과 잘 맞아떨어진다.

¹