﻿ Smith-Waterman

# Smith-Waterman Algorithm(Gap Penalty, 1981)

Main features
• The search for pairs of maximally similar segments on a mathematically rigorous basis
• efficiently and simply programmed on a computer
• searching phase in O(mn) time complexity
Description

The identification of maximally homologous subsequences among sets of long sequences is an important problem in molecular sequence analysis. The problem is straightforward only if one restricts consideration to contiguous subsequences (segments) containing no internal deletions or insertions. The more general problem has its solution in an extension of sequence metrics (Sellers 1974; Waterman et al.,1976) developed to measure the minimum number of "events" required to convert one sequence into another.

C source code
```double SmithWaterman_Alg(char *stringA, char *stringB, int m, int n){

int i, j, k, l;
double maxone, wkmax, wlmax, max = 0, **HTable;

/*-----claim and initialize array HTable-----*/
HTable = (double**)calloc((m + 1), sizeof(double*));
for (i = 0; i <= m; i++)
HTable[i] = (double*)calloc((n + 1), sizeof(double));

for (i = 1; i <= m; i++){

for (j = 1; j <= n; j++){
wkmax = 0;
wlmax = 0;
maxone = 0;

if (stringA[i] == stringB[j]){
maxone = HTable[i - 1][j - 1] + 1.0;
}
else{
maxone = HTable[i - 1][j - 1] - (1.0 / 3.0);
}

for (k = 1; kwkmax)
wkmax = HTable[i - k][j] - (1.0 + 1.0 / 3.0*k);
}

if (wkmax > maxone)
maxone = wkmax;

for (l = 1; lwlmax)
wlmax = HTable[i][j - l] - (1.0 + 1.0 / 3.0*l);
}

if (wlmax > maxone)
maxone = wlmax;

if (maxone < 0)
maxone = 0;

HTable[i][j] = maxone;

if (max < maxone)
max = maxone;
}
}

return max;

}
```
The files
main.c   lcslib.h   SmithWaterman_Alg.exe

Reference
T. F. Smith and M. S. Waterman, "Comparison of biosequences," Advances in Applied Mathematics, Vol. 2, pp. 482-489, 1981.