SEQUENCE ALLIGNMENT String x = AACAGTTACC String Y = TAAGGTCA Void opt(int i , i
ID: 3857405 • Letter: S
Question
SEQUENCE ALLIGNMENT
String x = AACAGTTACC
String Y = TAAGGTCA
Void opt(int i , int j)
{
if (i == m)
opt = 2(n-j);
elseif (i == m)
opt = 2(n-j);
else{
if (x[i]==y[j])
penalty = 0;
else
penalty = 1;
opt = min (opt(i+1,j+1)+penalty , opt(i+1,j)+2 , opt(i,j+1)+2);
}
}
find a string x and y such that opt[ i ][ j ] = 2 + opt[ i+1][ j ] = 2 + opt[ i ][ j+1] = 0 + opt[ i + 1][ j + 1].
at some point of calculations there should a tie between all three values .
or prove it is not possible.
y T A A G G T C A - x 0 1 2 3 4 5 6 7 8 A 0 7 8 10 12 13 15 16 18 20 A 1 6 6 8 10 11 13 14 16 18 C 2 6 5 6 8 9 11 12 14 16 A 3 7 5 4 6 7 9 11 12 14 G 4 9 7 5 4 5 7 9 10 12 T 5 8 8 6 4 4 5 7 8 10 T 6 9 8 7 5 3 3 5 6 8 A 7 11 9 7 6 4 2 3 4 6 C 8 13 11 9 7 5 3 1 3 4 C 9 14 12 10 8 6 4 2 1 2 - 10 16 14 12 10 8 6 4 2 0Explanation / Answer
Here the string x and y
opt[i][j] = 2 + opt[i+1][j+1] = 0 + opt[ i + 1][ j + 1]
String x = AACAGTTACC
String Y = TAAGGTCA
Void opt(int i , int j)
{
if (i == m)
opt = 2(n-j);
elseif (i == m)
opt = 2(n-j);
else{
if (x[i]==y[j])
penalty = 0;
else
penalty = 1;
opt = min (opt(i+1,j+1)+penalty , opt(i+1,j)+2 , opt(i,j+1)+2);
}
}
calculations should be tie between all three values
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.