Smith–Waterman algorithm #
Smith–Waterman algorithm 은 문자열을 정렬(alignment) 하기 위해 Smith 와 Waterman이 1981년에 "Identification of Common Molecular Subsequences" 란 제목으로 제안한 알고리즘이다. 이 알고리즘에서는 두 문자열의 유사도를 Dynamic Programing(동적계획법) 을 이용하여 매기는 방법이다. 비교할 두 문자열의 길이를 각각 \(n, m\)이라 하면, 점근적으로 \(O(nm)\)의 Time Complexity 와 Space Complexity 를 가진다. 이후 두 염기서열을 비교하기위하여 이후 이 알고리즘에서 더 특화된 Needleman–Wunsch algorithm 등이 발표되었다.
Algorithm #
\(A\)와 \(B\)를 정렬(aligning)할 두 문자열이라 하자. 또, \(n=|A|\), \(m=|B|\)이라 하겠다.
이제, \((n+1) \times (m+1)\)의 크기를 가지는 scoring matrix를 다음과 같이 정의하겠다.
\(s(a,b)\)는 \(A\)의 원소 \(a\)와 \(B\)의 원소 \(b\)의 유사도 점수이고, \(W_k\) 는 길이 \(k\)의 차이에 따른 패널티이다. 여기서 \(s(a,b)\)와 \(W_k\)는 이용하는 것에 따라 달라질 수 있다.
본문에서는 \(s(a,b)\)를 \(a=b\)일때 \(+3\), 아닐 때 \(-3\)으로, \(W_k = 2k\)로 정의한다.
\(H_{i,0} = H_{0,j} =0\) for all \(1 \le k \le n\) and \(0 \le l \le m\)으로 초기화한다.
이제 점화식의 정의에 따라 scoring matrix를 계산한다.
구해진 결과는 아래와 같다.
scoring matrix를 계산했다면, dynamic programming 역추적을 통해 가장 점수가 높은 \(A\)와 \(B\)의 substring을 찾아야 한다.
위에서 다룬 경우, \(H_{7,6} = 13\)이 가장 높은 점수이다.
위의 경우에서 역추적이 끝난 결과는 다음과 같다.
$$ (1,1),\ (2,2),\ (3,3),\ (4,4),\ (5,4), \ (6,5),\ (7,6) $$
이 결과를 통해 \(A\)와 \(B\)를 aligning 한 결과는 다음과 같다.
\( A' : \) G T T - A C
| | | | |
\( B' : \) G T T G A C
