니들만-브니쉬(분쉬) 알고리즘 (Needleman-Wunsch)

Goal

1. 니들만-브니쉬 알고리즘이란?
2. 니들만-브니쉬 알고리즘 알아보기

 

니들만-브니쉬 알고리즘이란?

두개의 DNA나 단백질 서열이 있을 때 sequence alignment를 하기 위한 알고리즘이다. Alignment란 쉽게 말해서 두 서열이 어떤 부분에 매치가 되고 어떤 부분엔 매치가 안 되는지 보여주는 것이다.

 

예를 들어 ATGCA와 ATCG를 align 한다면 아래와 같이 정렬할 수 있다.

ATGCA
AT-CG

 

최대한 매치되는 부분을 맞추고 매치가 되지 않는 부분은 하이픈(-)으로 표시하며 이걸 "gap"이라 부른다.

 

이런식으로 두 서열이 매치가 얼마나 잘 됐는지 판단하는 기준으로 alignment score를 사용하게 되는데 매치가 되면 플러스 값을 부여하고 매치가 되지 않거나 gap이 생성되면 패널티 값을 부여해서 총 합을 alignment score로 사용한다. Alignment score가 높을수록 두 서열이 공통적인 조상으로부터 파생되어 변이가 축적된 서열이라는 것에 좀 더 근거를 가질 수 있다.

 

니들만-브니쉬 알고리즘 원리

우선 score와 방향 추적을 하기 위한 매트릭스가 2개 필요하다. 각각 세로와 가로줄에 두 서열을 넣고 gap 패널티 가로세로 줄을 추가한다. 이 시작점을 Initialization이라 부른다.

 

이제 매트릭스를 채워나가야 하는데 방법은 대각선, 왼쪽, 또는 위쪽의 숫자에서 이어나가는 것이다.

 

위에 하이라이트 된 상자의 점수를 계산을 아래와 같이 할 수 있다.

이 중에서 가장 높은 값을 사용해야하기 때문에 1로 채워넣으면 된다. 그리고 1은 대각선으로부터 계산되었기 때문에 Traceback Matrix에도 대각선이라 표기를 한다.

이런식으로 나머지 상자들도 채워나간다.

위와 같이 모든 상자를 채운 후에 Traceback Matrix를 이용해서 가장 오른쪽 아래 칸에서부터 "끝"이라고 표기되어 있는 곳까지 거슬러 올라간다.

Traceback Matrix를 보면 대각선 -> 대각선 -> 왼쪽 -> 대각선 -> 대각선 -> 끝 순서로 이어진걸 확인할 수 있다. 이것을 이제 차례대로 두 서열에 적용을 해야한다.

Alignment 규칙

 

위의 규칙을 따라서 두 서열을 뒤에서부터 써보면 아래와 같이 정렬이 되는 것을 알 수 있다!

최종 sequence alignment

 

참고

https://www.cs.sjsu.edu/~aid/cs152/NeedlemanWunsch.pdf

https://enjoybioinfo.blogspot.com/2020/10/needleman-wunsch-algorithm.html