NeedlemanWunschAlgorithm

Needleman & Wunsch에 의해 1970년 소개됨. Main idea는 optimal alignment를 만들기 위해, 이전단계의 하나작은 서열의 솔루션을 사용한다는것. DynamicProgramming의 일종.

서열의 시작부분부터 끝까지의 Gap penalty를 적용한 LogOddsRatio의 합F(i, j). recursive하게 계산된다.

linear score로 Gap penalty를 적용했을 때,

initionally

$F(i,j) = \max \left\{ \begin{array}{ll} F(i-1,j-1)+s(x_i,y_i) & \textrm{} \\ F(i-1,j)-d & \textrm{} \\ F(i,j-1)-d & \textrm{} \end{array} \right$

traceback : 내려온 길을 거슬러 올라간다. 대각선이동시 match, 수직이동시 가로서열에 Gap, 수평이동시 세로서열에 Gap 적용 --> SequenceGraphStructure 문제, HeinsAlgorithm적용

Big O notation for algorithmic complexity

저장한 정보 : (n+1)*(m+1) matrix --> O(nm) time and O(nm) memory --> O(n²)

Bioinformatics에서 O(n²) complexity는 feasible하나 약간 느린편. O(n³)은 짧은 서열에대해서만 가능.