Smith–Waterman algorithm #

Smith–Waterman algorithm 은 문자열을 정열(alignment) 하기 위해 Smith 와 Waterman이 1981년에 "Identification of Common Molecular Subsequences" 란 제목으로 제안한 알고리즘이다. 이 알고리즘에서는 두 문자열을 x, y축에 각각 두고 Dynamic Programing(동적할당법) 을 이용하여 문제를 푸는 방법으로 n^2 의 Time Complexity 와 Space Complexity 를 가진다. 이후 두 염기서열을 비교하기위하여 이후 이 알고리즘에서 더 특화된 Needleman–Wunsch algorithm 등이 발표되었다.

Algorithm #

먼저 Dynamic Programming 을 이용하여 문제를 풀기 위해 아래와 같이 2D Matrix를 정의한다

즉 (m+1, n+1)크기의 메트릭스를 두고 (0,i) (j,0)의 값을 모두 0으로 저장한다. 이는 Dynamic Programing의 초기값을 정의하는 작업이다. 이후 각 문자열이 일치하는지 비교해야한다. 문자열이 일치하는 방법에 대해서는 Insert, Delete, Match 세가지로 정의 할 수 있는데, 현재 가리키고 있는 문자열이 일치하면 i-1, j-1의 값보다 +1, 만약 Insertion이 일어났다면, i-1, j의 매칭값과 동일하며, 반대로 Deletion이 일어났다면 i, j-1 의 매칭값과 동일 할 것이다.

위에서 설명한 알고리즘의 점화식은 다음과 같이 나타 낼 할 수 있다.

점화식을 정의 한후 점화식에 따라 각 i, j의 결과 값을 구한다. 구해진 결과는 아래와 같다.