Needleman-Wunsch

The N-W algorithm is a dynamic programming algorithm used in bioinformatics to align protein sequences. The algorithm assigns a score to a particular alignment pattern and the pattern with the lowest score has the closest alignment.

Code snippet

int max_cols = 2049;

for( int i = max_cols-4; i >= 0; i--){
   for(idx = 0; idx <= i; idx++){
      int k;
      index = (max_cols-idx-2) * max_cols + idx+max_cols-i-2 ;

      if(input_itemsets[index-1-max_cols]+referrence[index] <= input_itemsets[index-1]-penalty)   //taken 30% of the time
         k = input_itemsets[index-1]-penalty;

      else
         k = input_itemsets[index-1-max_cols]+referrence[index];

      if(k <= input_itemsets[index-max_cols]-penalty)   //taken 30% of the time
         input_itemsets[index] = input_itemsets[index-max_cols]-penalty;

      else
         input_itemsets[index] = k;   
   }
}