Sequence Alignment Algorithm

여러개의 서열 중에서 서로 닮은 부분과 다른 부분을 찾아내는 알고리즘

 

2개의 다른 DNA 서열을 대응시켜 유사성을 비교

G A ·· C G G A T T A G

G A T C G G A A T A G

 

두 서열은 서로 다른 길이를 가질 수 있고 또한 각 서열은 공백들을 가질 수 있다.

주어진 두 서열에 공백들을 포함시켜 서로 같은 길이로 만든다.

공백들끼리 대응되는 것은 허용되지 않지만 서열의 시작부분과 끝 부분에도 공백을 삽입할 수 있다.

---

두 서열을 대응시키기 위해 score를 정한다.

 

1. 한 열(column)에 같은 문자가 있다면 score는 + 1 (match)
2. 다른 문자가 대응되었을 때는 -1 (mismatch)
3. 문자와 공백이 대응되었을 때는 -2
4. 이 방법으로 위 두 서열의 score를 계산하면 9x1 + 1x(-1) + 1x(-2) = 6

 

최선의 alignment(대응)는 전체 Score가 최대 값을 갖는 것이다.

---

동적 프로그래밍 알고리즘

1. 주어진 두 서열을 s 와 t 라 하고 각각의 서열의 길이를 m 과 n 이라고 한다.
2. 서열 s 에는 empty string을 포함하여 모두 m+1 개의 가능한 접두어가 존재
3. 서열 t 에는 n+1 개의 가능한 접두어가 존재
4. 이 모든 가능성을 2차원 행렬로 표현한다면 크기가 (m+1)x(n+1) 이 되고
   그 행렬의 (i,j) 위치에서는 s[1 ... i] 와 t[1 ... j] 사이의 유사성을 나타낸다.

---

 

 

---

예제 : s = AAAC 와 t = AGC 를 위한 최적 alignment를 찾는 방법

첫 번째 행과 첫 번째 열은 space penalty 값 -2를 곱한 값으로 초기화

(i,j) 의 값을 계산하기 위해서는 (i-1, j), (i-1, j-1) 그리고 (i, j-1)의 값이 이용된다.

s[1 ... i]와 t[1 ... j] 두 서열간의 alignment를 얻기 위해서는 다음과 같은 세가지 경우가 고려될 수 있다.

 

1. 서열 s[1 ... i] 를  t[1 ... j] 와 대응시키고 빈 공백(space)과 t[j]를 대응시키는 방법
2. 서열 s[1 ... i-1] 을  t[1 ... j-1] 과 대응시키고 s[i] 와 t[j]를 대응시키는 방법
3. 서열 s[1 ... i-1] 과  t[1 ... j] 를 대응시키고 s[i]를 빈 공백과 대응시키는 방법

- 수식으로 표현 : 여기서 서열 s와 t를 배열 a로 표시

 

- p(i, j) 의 값은 다음과 같이 정의

 

테이블의 각 행부터 차례로 채우기 시작하고, 각 행은 왼쪽에서 오른쪽으로 채워진다.

테이블의 모든 데이터가 채워지면, 마지막으로 그 최대값이 얻어진 위치를 화살표로 표시한다.

 

예를 들어서 a[1,2] 는 다음 세 곳으로부터 계산되어. 최대값인 -1을 이용하므로 그 최대값을 얻은 a[1,1]으로 화살표를 표시한다.

a[1,1] -2 = -1

a[0,1] -1 = -3

a[0,2] -2 = -6

 

만일 최대값이 한 곳 이상으로부터 얻어진다면 최대값을 주는 모든 위치에 화살표를 표시한다.

 

---

Algorithm  Similarity
  // input : two sequences s and t
  // output : similarity between two sequences  s and t
  // q : space penalty
  m=|s|
  n=|t|
  for (i=0; i < = m ; i++)
    a[i,0]=i×q
  for (j=0; j < = n ; j++)
    a[0,j]=j×q
  for (i=1; i < = m ; i++)
    for (j=1; j < = n ; j++)
      a[i,j]=max( a[i,j-1]-q
                       a[i-1,j-1]+p(i,j)
                       a[i-1,j]-q )
  return  a[m,n]