[algorithm] Smith-waterman algorithm

2023.05.22 - [Computer Science/Data structure & Algorithm] - [Algorithm] Needleman-Wunsch algorithm

[Algorithm] Needleman-Wunsch algorithm

Needleman-Wunsch algorithm에 이어서 설명을 진행하기 때문에 꼭 이전 글을 읽고 오길 바란다. 

 

Smith-Waterman algorithm

Needleman Wunsch algorithm은 global alignment를 찾을 때 사용되었다. 오늘 알아볼 Smith-waterman algorithm은 local alignment를 찾을 때 사용할 수 있다. 

• Local alignment
  두 sequence에서 가상 유사한 부분 서열을 찾는 문제방식으로  일부구조만 같을 때나 길이가 다른 시퀀스 사이의 정렬에 적합하다.

Needlman-Wunsch algorithm에서 조건 하나만 더 추가하면 쉽게 Local alignment를 구현할 수 있다.

맨 위에 0이라는 것이 추가 되었다. 즉, score의 값이 음수가 될 때는 0으로 채워넣는다는 이야기이다. 그리고 종료조건도 x[i][j] == 0일 때로 바뀐다.

 

X = GGTTGACTA
Y = TGTTACGG

일 때, local alignment의 결과 table이다. (match = 3, mismatch = -3, gap = -2)

보이는 것처럼 음수가 된 값은 max 값에 0이 추가되면서 0으로 모두 대체 된다. 

그리고 백 트래킹을 할 때 Needleman과 다른 부분이, 배열의 마지막 요소에서 백트래킹을 하는 것이 아니라, 배열의 max 값에서 출발해야한다. 위 표의 경우 7에서 출발하는 것이 아니라 최댓값이 13에서 출발해야하는 것이다. 

그래서 결과는 아래처럼 된다.

G T T - A C
 
G T T G A C

 

 

관련 문제

2023.05.22 - [Computer Science/Baekjoon] - [2612] python : DNA 유사도

[2612] python : DNA 유사도