﻿ Needleman-Wunsch

# Needleman-Wunsch Algorithm(Maximum-Match, 1970)

Main features
• evaluating the significance of maximum match
• cell values and weighting factors
Description

Needleman and Wunsch proposed a general scheme for the similarity of two amino acids. Their algorithm evaluates the significance of the obtained maximum match based on the probability that this match occurs among random sequences. The value of cell M[i; j] of dynamic programming (DP) lattice is the maximum among M[i + 1; j + 1..n] and M[i +1..m; j + 1], plus 1 if ai = bj . So the time complexity is O(m2n + mn2).

C source code
```int NeedlemanWunsch_Alg(char *stringA, char *stringB, int m, int n)
{
int i, j, ti, tj, max, **tab;

tab = (int**)calloc((m + 1), sizeof(int*));
for (i = 0; i <= m; i++){
tab[i] = (int*)calloc((n + 1), sizeof(int));
}

for (i = 1; i <= m; i++){//initialize tab
for (j = 1; j <= n; j++){
if (stringA[i] == stringB[j]){
tab[i][j] = 1;
}
}
}

for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
max = 0;
if (i != 1){
ti = i - 1;
for (tj = j - 1; tj > 0; tj--){
if (tab[ti][tj] > max){
max = tab[ti][tj];
}
}
}

if (j != 1){
tj = j - 1;
for (ti = i - 1; ti > 0; ti--){
if (tab[ti][tj] > max){
max = tab[ti][tj];
}
}
}
tab[i][j] += max;

}
}

max = 0;
for (i = m; i > 0; i--)
{
if (tab[i][n] > max)
max = tab[i][n];
}

for (j = n; j > 0; j--)
{
if (tab[m][j] > max)
max = tab[m][j];
}

return max;
}
```
The files
main.c   lcslib.h   NeedlemanWunsch_Alg.exe

Reference
D. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, Vol. 48, No. 3, pp. 443-453, 1970.