on
컴퓨터 알고리즘 2023-04-09 수업정리
Flow
- Sequence Alignment
- Dynamic Programming - Needleman-Wunsch algorithm
Sequence Alignment
An alignment is an assignment of gaps to positions 0, ..., M in x, and 0, ..., N in y, so as to line up each letter in one sequence with either a letter or a gap in the other sequence
Sequence Alignment란 결국 두 개 이상의 시퀸스(문자열)을 정렬하여 유사한 부분을 찾아내는 것이다.
- 아래는 서로 다른 두 사람의 DNA염기 서열에 대해 sequence alignment를 진행하는 예시이다.
-
Befrore Sequence Alignment
person A : AGGCTATCACCTGACCTCCAGGCCGATGCCC
person B : TAGCTATCACGACCGCGGTCGATTTGCCCGAC
-
After Sequence Alignment
person A : -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC---
person B : TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC
-
What is a good alignment?
-
match, mismatch, gap으로 구분하여 alignment를 비교한다.
-
match, mismatch, gap에 대해서 가중치를 설정하여 우선순위에 맞게 alignment를 진행한다.
-
아래는 matches(5point), mismatches(-3point), gap(-4point)에 따라 alignment를 비교하는 예시이다.
-
6 matches, 3 mismatches, 1 gap : 17point
AGGCTAGTT-
AGCGAAGTTT
-
7 matches, 1 mismatch, 3 gaps : 20point
AGGCTA-GTT-
AG-CGAAGTTT
-
7 matches, 0 mismatches, 5 gaps : 15point
AGGC-TA-GTT-
AG-CG-AAGTTT
Dynamic Programming - Needleman-Wunsch algorithm
- 두 염기서열의 공통 부분이 가장 많아지도록 정렬할 때 사용되는 알고리즘
- The score of the alignment = (# of matches) * m - (# of mismatches) * s - (# of gaps) * d
- 두 서열에서 문자쌍이 일치할 경우 : +m점
- 두 서열에서 문자쌍이 서로 다를 경우 : -s점
- Sequence Alignmnet 중 gap이 발생할 경우 : -d점
- F(i, j)가 주어진 sequence x, y의 subsequence x[1..i], y[1..j]의 정렬에 대한 optimal 점수라고 하자. subsequence x[1..i], y[1..j] 에 대해 다음과 같은 세 가지 경우가 존재한다.
$$x_1 ..... x_i $$$$y_1.....y_j$$
- x(i)가 y(i)에 align되는 경우 : F(i, j) = F(i-1, j-1) + { (x(i) == y(i)) ? m : -s }
- x(i)가 gap과 align되는 경우 : F(i, j) = F(i-1, j) - d
- y(i)가 gap과 align되는 경우 : F(i, j) = F(i, j-1) - d
- 따라서 F(i-1, j-1)이 optimal하다고 했을 떄 아래와 같은 recursive equation이 도출된다.$$F(i, j)=max\begin{cases}F(i-1,j-1)+s(x_i,y_i)\F(i-1,j)-d\F(i,j-1)-d\end{cases}$$$$s(x_i, y_i) = \begin{cases}m,\ (if\ x_i = y_i)\-s,\ (otherwise)\end{cases}$$
- 이와 같은 recursice equation과 F(i, j)의 score를 저장하는 matrix를 통해 Dynamic Programming을 통한 Sequence Alignmnet를 수행할 수 있다.(Needleman-Wunsch Algorithm)
- 아래는 두 염기서열에 대한 Needleman-Wunsch Algorithm)을 step by step으로 적용한 것이다.
- Score 행렬 초기화
- Score 계산
- Score를 계산하면서 해당 칸이 위, 왼쪽, 왼쪽 대각선 위 세 방향 중 어디에서 유래했는지를 별도의 matrix를 통해 저장해야 한다.
- 그림에서는 정답에 대해서만 빨간색 실선 화살표로 나타냈다.
- 트레이싱
- 가장 점수가 높은 칸은 8이다.
- 이 지점에서부터 해당 칸의 이전 단계로 step 2에서 작성한 matrix를 참고하여 돌아간다(tracing)
- 모든 경로가 파악되면 s1, s2에 대한 optimal solution을 알 수 있다.
- 위에서 내려오는 칸은 s2가 gap을 가지고, 좌에서 우로 이동하는 칸은 s1이 gap을 가진다.
- s1 : C A T - - A C
- s2 : - A T C G A C
- 만약 최댓값이 같아 어느 방향에서 오는 지 특정할 수 없는 경우 임의의 칸을 선택하면 된다.
- 위 그림에서 빨간 점선 테두리의 칸은 두 가지 이상의 기원을 가질 수 있다.
- 아무 값이나 임의로 선택하면 된다.
- Score 행렬 초기화
Implementation
// TODO (`2023-04-15)