Needleman-Wunsch Algorithm

Needleman-Wunsch Algorithm

Needleman-Wunsch Algorithm은 Global alignment에 사용되는 algorithm이고, Smith-Waterman Algorithm은 Local alignment에 
사용되는 algorithm이다.
Nedleman-Wunsch Algorithm은 행렬의 생성과 Traceback의 2단계로 구성되어있다. 행렬의 생성은 행렬의 왼쪽 위에서 오른쪽 아래로 
탐색해 나가면서 x,y의 위치에서 x+1,y+1과 x,y+1/ x+1,y/ 의 3가지 경로에 대하여 최고의 점수를 찾아가면서 행렬의 생성및 진행방향을 
그릴수 있다. 행렬 Taceback은 완성된 행렬의 끝에서부터 경로를 역추적하며 정렬된 데이터의 값을 이용해 최적의 서열 정렬 결과를 
생성하게 된다.
http://biocc.ngic.re.kr/Biopedia/Biowiki/images/8/85/Needleman.JPG