Sequence alignment algorithm, 서열정렬 알고리즘은 여러 DNA혹은 단백질 서열을 정렬하는 알고리즘이다. 
그 중 가장 유명한   Needleman-Wunsch algorithm 에 대해 이야기해보고자 한다.
- 1970 년에 개발. 
- 가장 일반적으로 쓰이는  global pairwise sequence alignment algorithm.

예를들어, 
AATCGCTA 와  AAGTCCCA를 정렬한다고 할 때, 
눈으로도 이렇게 아래처럼 정렬할 수 있다.

AA-TCGCTA
AAGTCCC-A

하지만 시퀀스가 길 경우엔 어떻게 정렬이 될까?

이 알고리즘에서는, 두개의 시퀀스가 match  되면 +1 점, match가 안되면 0점 건너뛰게되면 ( gap) -1 점을 부여하는 식으로 진행이 된다.

또한, 하나의 문제를 단 한번만 풀도록 하는 알고리즘인 Dynamic programming(다이나믹 프로그래밍) 을 적용하여 긴 시퀀스의 경우 컴퓨터가 어떻게 풀어나가는지 살펴보자.

예제로 Seq1 : AGTCG (행),  Seq2: ATGG(열) 을 아래와 같은 테이블로 만들어 볼 수 있다.


자 이 때 먼저 테이블을 작성할때에 주의 점은 한 열/행의 여유를 두고 작성해야한다. 
그 후 위에 보듯이 Gap 에 대한 점수를 -1로 설정한 것을 볼 수 있다. 
그러므로 첫번째 열과 행은 gap 이 길이에 따라 증가하므로 -1, -2, -3, -4, -5 를 작성해 주는것이다.

자 그렇다면 이제 준비는 끝났다. 이제 스코어 메트릭스를 채워보자. 첫번째로 채울 공간은 2행 2열 즉 (A,A) 에 해당하는 공간이다. 이제부터 점수를 채울때의 규칙을 알려줄 것이다

한 공간에서의 점수를 채우기 위해서는 3가지 경우를 고려해야한다. 
1. 대각선에서 이어지는 경우
2. 왼쪽에서 이어지는경우 
3. 위에서 이어지는경우

1번의 경우 시퀀스에 해당하는 문자를 보고 이것이 match  인지 mis match  인지 고려 해서 점수를 준다. 2,3 번은 그냥 gap  에 해당하는 점수를 주면된다.

이때, 그 이전의 셀에 나와있는 점수를 더해서 계산한다.
아래 그림에서 노란색 박스를 보면 3개경우에서 더해진 점수를 볼 수있다.



세 점수 중 가장 큰 점수는 무엇인가? 1 이다. 
즉 대각선에서 내려온 경우이다.
그러면 우리는 1을 선택하고, 또 어디서 점수가 전해져왔는지 그 해당 "길"(path)를 꼭 표시해준다.
이러한 방식으로 계산해서 매트릭스를 완성하면 아래와 같다.


보는것과 같이 한 셀에서 한개 이상에 셀에 화살표를 줄수는 있어도, 받을 때는  화살표는 딱 한개만 받게 되어있다. 
그런데 여기서 예외인 셀이 하나 보인다 바로 3열 5행에 해당되는 셀이다. 
이셀은 대각선, 위에서 두개에서 점수를 이어받고 있다. 
그 이유는 아까 3가지 경우에서 최대값을 선택할때 2개가 최대값이 었기 때문이다!
 이럴경우엔 그냥 랜덤으로 대각선 또는 위 하나를 선택해 주면된다.

자이렇게 스코어매트릭스를 완성했으면 이제 아래에서 위로 올라가야한다.
가장 큰 스코어 숫자는 "2" 다! 그러면 이제 2에서부터 화살표를 따라가면 시퀀스가 완성된다.

여기에서는
2 -> 1 -> 1 -> 0 -> 1 이다.

이를 색을 칠해보면 아래와 같고,

 


즉, 얼라이먼트 정렬 결과는
AGTCG
A-TGG
로 된것이다.



http://experiments.mostafa.io/public/needleman-wunsch/

위 웹사이트는 시퀀스를 넣었을 때 어떻게 alignment 가 이루어지는 데에 대한 예제로 잘 활용해 볼 수 있다.


더욱 자세한 설명은 아래 영상을 참고해주세요



질문은 댓글에 남겨주시면 24시간내에 답변해드리려고 노력하고 있습니다. 
모든 질문을 환영합니다.