ScientistsperformingDNAsequencealignmentoftendesireamoreparametrized way of alig

Question

ScientistsperformingDNAsequencealignmentoftendesireamoreparametrized way of aligning two strings than simply computing a longest common subse- quence between these two strings. One way to achieve such flexibility is to use the Smith-Waterman algorithm, which is generalization of the dynamic pro- gramming algorithm for computing a longest common subsequence so that it can handle weighted scoring functions. In particular, for two strings, X and Y , sup- pose we are given functions, defined on characters, a, from X, and b from Y , as follows:

M (a, b) = the positive benefit for a match, if a = b
M (a, b) = the negative cost for a mismatch, if a a?= b
I(a) = the negative cost for inserting a at a position in X D(b) = the negative cost of deleting b from some position in Y .

Given a string, X, of length n and a string, Y , of length m, describe an algorithm running in O(nm) time for finding the maximum-weight way of transforming X into Y , according to the above weight functions, using the operations of match- ing, substitution, insertion in X, and deletion from Y .

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SENTINEL (-1)
#define EDIT_COST (1)

int min(int a, int b) {
return a < b ? a : b;
}

int Minimum(int a, int b, int c)
{
return min(min(a, b), c);
}

int EditDistanceDP(char X[], char Y[]){
int cost = 0;
int leftCell, topCell, cornerCell;
int i,j;

int m = strlen(X)+1;
int n = strlen(Y)+1;

int *T = (int *)malloc(m * n * sizeof(int));

for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
*(T + i * n + j) = SENTINEL;

for(i = 0; i < m; i++)
*(T + i * n) = i;

for(j = 0; j < n; j++)
*(T + j) = j;

for(i = 1; i < m; i++)
{
for(j = 1; j < n; j++){
leftCell = *(T + i*n + j-1);
leftCell += EDIT_COST;

topCell = *(T + (i-1)*n + j);
topCell += EDIT_COST;

cornerCell = *(T + (i-1)*n + (j-1) );

cornerCell += (X[i-1] != Y[j-1]);

*(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
}
}
cost = *(T + m*n - 1);
free(T);
return cost;
}

int main(){
char X[100];
char Y[100];

printf("Enter First String : ");
scanf("%s",X);
printf("Enter Second String : ");
scanf("%s",Y);

printf("Minimum edits required to convert %s into %s is %d ", X, Y, EditDistanceDP(X, Y) );
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.