Advertisement
RicardasSim

Needleman-Wunsch algorithm

Jul 13th, 2019
418
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.36 KB | None | 0 0
  1. //-std=c99 -Wall -Wextra -Wpedantic -Wshadow
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6.  
  7. static inline int largestOfThree(int a, int b, int c)
  8. {
  9.     if(a>b)
  10.     {
  11.         if(a>c) return a;
  12.         else return c;
  13.     }
  14.     else if(b>c) return b;
  15.     else return c;
  16. }
  17.  
  18. int main()
  19. {
  20.  
  21.     char str1[]="ACCGTGTCA";
  22.     char str2[]="GCCGTGTCGACC";
  23.    
  24.     int match = 1;
  25.     int mismatch = -1;
  26.     int gap = -2;
  27.    
  28.     unsigned int lenStr1 = strlen(str1);
  29.     unsigned int lenStr2 = strlen(str2);
  30.    
  31.     int tbl[lenStr2+1][lenStr1+1];
  32.    
  33.     unsigned int i,z;
  34.    
  35.     int scoreLeft, scoreUp, scoreDiagonal;
  36.    
  37.    
  38.     //initialize the table
  39.    
  40.     tbl[0][0] = 0;
  41.    
  42.     for(i=1;i<lenStr1+1;++i)
  43.     {
  44.        tbl[0][i] = tbl[0][i-1] + gap;
  45.     }
  46.  
  47.     for(i=1;i<lenStr2+1;++i)
  48.     {
  49.        tbl[i][0] = tbl[i-1][0] + gap;
  50.     }
  51.    
  52.     //scores
  53.    
  54.     for(z=1;z<lenStr2+1;++z)
  55.     {
  56.         for(i=1;i<lenStr1+1;++i)
  57.         {
  58.            
  59.             scoreLeft = tbl[z][i-1] + gap;
  60.             scoreUp = tbl[z-1][i] + gap;
  61.            
  62.             if(str1[i-1]==str2[z-1])
  63.                 scoreDiagonal = tbl[z-1][i-1] + match;
  64.             else
  65.                 scoreDiagonal = tbl[z-1][i-1] + mismatch;
  66.            
  67.             tbl[z][i] = largestOfThree(scoreLeft, scoreUp, scoreDiagonal);
  68.            
  69.         }
  70.     }
  71.  
  72. //TEST:
  73. //>>>>>>>>>> print table >>>>>>>>>>
  74.  
  75.     printf("\t\t");
  76.    
  77.     for(i=0;i<lenStr1;++i)
  78.     {
  79.         printf("%c\t",str1[i]);
  80.     }
  81.    
  82.     printf("\n");
  83.  
  84.     for(z=0;z<lenStr2+1;++z)
  85.     {
  86.         if (!z) printf("\t");
  87.         else printf("%c\t",str2[z-1]);
  88.  
  89.         for(i=0;i<lenStr1+1;++i)
  90.         {
  91.             printf("%d\t",tbl[z][i]);
  92.         }
  93.         printf("\n");
  94.     }
  95.  
  96. //<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  97.  
  98.  
  99. //TODO: find all paths
  100.  
  101.    
  102.     return 0;
  103. }
  104.  
  105. /*
  106. output:
  107.  
  108.         A   C   C   G   T   G   T   C   A  
  109.     0   -2  -4  -6  -8  -10 -12 -14 -16 -18
  110. G   -2  -1  -3  -5  -5  -7  -9  -11 -13 -15
  111. C   -4  -3  0   -2  -4  -6  -8  -10 -10 -12
  112. C   -6  -5  -2  1   -1  -3  -5  -7  -9  -11
  113. G   -8  -7  -4  -1  2   0   -2  -4  -6  -8 
  114. T   -10 -9  -6  -3  0   3   1   -1  -3  -5 
  115. G   -12 -11 -8  -5  -2  1   4   2   0   -2 
  116. T   -14 -13 -10 -7  -4  -1  2   5   3   1  
  117. C   -16 -15 -12 -9  -6  -3  0   3   6   4  
  118. G   -18 -17 -14 -11 -8  -5  -2  1   4   5  
  119. A   -20 -17 -16 -13 -10 -7  -4  -1  2   5  
  120. C   -22 -19 -16 -15 -12 -9  -6  -3  0   3  
  121. C   -24 -21 -18 -15 -14 -11 -8  -5  -2  1
  122.  
  123. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement