Smiley face

Smith-Waterman Algorithm(Gap Penalty, 1981)


Main features
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.