Indentification of Common Molecular Subsequences (Smith-Waterman 알고리즘)

Smith-Waterman local sequence alignment 알고리즘은 computational 분자 생물학 분야에서 가장 중요하게 사용되는 기법 중의 하나임은 분명하다. 이 알고리즘은 잘 보존된 부분을 찾고 그렇지 않은 부분을 제거하도록 설계되어졌다.

두 개의 sequence를 A=a₁a₂…a_n과 B=b₁b₂…b_m이라 가정하자. 유사성 S(a, b)는 sequence element a와 b 사이에 주어진다. 일반적으로 dynamic programming에서 이 값은 a와 b가 같으면 1, 다르면 0이다. 그러나 W_k는 1.0 + 1/3 * k 이다.
유사성이 높은 segment 쌍을 찾기 위해 matrix H를 셋업한다.

H의 준비된 값은 H_ij가 a_i와 b_j내의 두 segment의 최대 유사성인 해석을 가진다. 이러한 값을 최대화하는 고전적 dynamic programming으로부터 획득되어진다.

4가지 인자들 중 "0"은 새로운 alignment를 시도하는 것에 해당된다. 이 점에서 alignment 값은 증가할 수 있고 이 점에 이르는 동안 alignment 값의 합은 음수로 되어 임의로 align했을 경우 alignment 값은 도리어 낮아지는 결과가 되므로 차라리 새로운 alignment를 찾는 것이 지금까지 맞춰온 것을 확장하는 것보다 낫다는 의미가 된다. 따라서, alignment 값을 구하는 matrix의 최 상단과 좌측 열은 모두 0으로 셋팅된다.

아래 예제에서 보듯이, 최대 유사성을 가지는 segment 쌍은 matrix H의 최대 element를 갖는 점에서 시작하여 back trace를 함으로써 alignment를 찾아내는 방식이다. 따라서 최대값을 갖는 matrix의 셀을 계속 유지하고 있어야 한다. 이 최대 element에서 back trace를 하면서 0.0인 element까지 반복하면서 찾는다. 참고로, 아래의 예제에서 최대 element를 갖는 점은 (10, 8)인 element로서 3.3이라는 값을 가진다.

이 간단한 예제에서 alignment는 아래와 같이 획득했다.

mismatch와 내부적인 삭제를 포함한다. 이 알고리즘은 수학적으로 엄격한 기본으로 하는 가장 유사한 segment들의 쌍을 찾을 수 있을 뿐만 아니라, 컴퓨터 상에서 효과적이고 간단한 프로그램을 할 수 있다.
단점으로는 실제로 중요한 subsequence alignment가 있음에도 불구하고 sequence가 길다는 점만으로 이를 포함하여 불필요한 alignment가 발생한다는 것이다.
조금 더 자세히 설명하면, 유전적으로 잘 보존되지 못한 부분이 전체 alignment에 포함되어 잘 보존된 부분과 섞여 있을 때, 이것이 alignment를 왜곡시키는 결과로 나타나는 경우가 발생한다. 그 이유로 Smith-Waterman local alignment 알고리즘은 최고의 점수를 갖는 local alignment를 찾지만 초고의 유사성, 최고의 일치도를 갖는 local alignment를 찾지 못하는 문제가 알고리즘 자체에 포함되기 때문이다.

정리를 하면, sequence alignment에서 비유사도(non-similarity)가 높은 시작 부분과 끝 부분 조각을 제거하는데는 효과적이나 비유사성을 갖는 조각이 잘 보존된 alignment 사이에 위치해 있을 때는, 최고의 유사성과 일치도를 갖는 것을 찾지 못한다.

** 관련 글 **
문장 비교
Edit Distance (Edit Operations) using Dynamic Programming

http://www.bioinformatics.uwaterloo.ca/~cs882/Old_courses/W03/sw.pdf
http://naver.nanet.go.kr:8080/dl/CommonView.php?u=c7CN1fs8fKOZt5%2FZ7PKh1up8cOAz15Hbgk6iGtYZ%2FAkCXcdQoJVjN9rsPZreYnbUd0QDUcaGIGPw7Yl11smJnw%3D%3D