Skip to content

Smith–Waterman algorithm #

Find similar titles

6회 업데이트 됨.

Edit
  • 최초 작성자
    Duskan
  • 최근 업데이트
    YearSora

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를 다음과 같이 정의하겠다.

Image

\(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\)으로 초기화한다.

Image

이제 점화식의 정의에 따라 scoring matrix를 계산한다.

구해진 결과는 아래와 같다.

Image

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

0.0.1_20240214_1_v81