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.
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; }