두 DNA 염기서열, 혹은 string(문자열)이 있다고 하자. 이 두 문자열을 가장 비슷하게 정렬하는 알고리즘을 우리는 찾고 싶다. DNA의 경우 돌연변이가 일어난 상태의 두 DNA strand라도 원래 어떻게 매칭되어 있었는지 알고 싶기(추정하고 싶기) 때문이다. 예를 들어 다음 DNA double strand를 생각해보자.
$$ \text{ACCCGTATG}\\ \text{TGGGCATAC} $$
이 DNA double strand는 잘 정렬되어 있다. 하지만 다음과 같은 mutation이 일어난 double strand를 생각해보자.
$$ \text{ACCCGTATG}\\ \text{TAGGCATAC} $$
두 번째 자리가 $\text{C}-\text{G}$여야 하는데 $\text{C}-\text{A}$로 어긋나있다. Insertion(삽입), deletion(결실)이 경우에는 쉽게 한 자리가 어긋나있다는 사실을 알 수 있지만 어긋난 자리수가 많아지고, 길다란 double strand에서 다양한 위치에서 어긋남이 발생한다면 눈으로 봐서는 쉽게 알아챌 수가 없을 것이다. 그리고 무엇보다도 우리는 눈을 통한 어림짐작으로 수만자가 넘어가는 엄청나게 긴 DNA double strand가 잘 정렬되어 있는지 현실적으로 검토할 방법이 없다. 따라서 컴퓨터에게 이런 일을 시켜야 하는데, “가장 비슷한” double strand의 조합을 찾게 하는 것은 생각보다 까다로운 작업이다. 다음과 같은 double strand를 생각해보자.
$$ \text{ACCCGTATG}\\ \text{GCGGGCATA} $$
위 strand를 살펴보면 제대로 위치한 부분이 9개의 base 중 2개밖에 없다. 하지만 이 double strand는 다음처럼 정렬할 수 있다:
$$ \text{ - ACCCGTATG}\\ \text{GCGGGCATA - } $$
이렇게 빈 칸을 통해 한칸씩 밀게 되면 무려 7자리나 제대로 조합할 수 있게 된다! Needleman-Wunsch algorithm은 dynamic programming을 통해 컴퓨터가 이러한 well-alignedness를 자동으로 찾아주게 만드는 알고리즘이다. 여기까지 했으면 Needleman-Wunsch algorithm을 왜 하는지, 이 알고리즘이 무엇을 하는지는 잘 이해했을거라 생각하고 구체적인 알고리즘을 살펴보자.
사실, 이론적으로야 best alignment는 항상 찾을 수 있다. Brute force로 모든 조합을 다 계산해보면 되기 때문이다. 하지만 한 자리가 증가할 때마다 4개의 base가 늘어나기 때문에 조합은 4배씩 증가할 것이고, 결국 $O(4^n)$정도의 복잡도를 가지게 되어 사실상 100 pair만 된다 하더라도 말도 안되게 경우의 수가 많아질 것이다. 이를 Needleman-Wunsch에서는 dynamic programming으로 해결한다.
먼저 두 염기 서열 $\text{GCATGCG}$와 $\text{GATTACA}$를 생각하자.
| G | C | A | T | G | C | G | ||
|---|---|---|---|---|---|---|---|---|
| G | ||||||||
| A | ||||||||
| T | ||||||||
| T | ||||||||
| A | ||||||||
| T | ||||||||
| A |
그리고 scoring system을 하나 생각한다
예를 들어 다음과 같은 alignment candidate는 (아무렇게나 설정했다.)