Suppose you are given the following items as input: a string A[1..n], a string B
ID: 3828798 • Letter: S
Question
Suppose you are given the following items as input: a string A[1..n], a string B[1..m], and the (n + 1) (m + 1) matrix D produced by the edit distance algorithm. Give an optimal algorithm that constructs an optimal alignment from the input. For example, suppose the input to your algorithm is the string A[1..3] = HAS, string B[1..4] = THIS, and the following matrix D.
T
H
I
S
0
1
2
3
4
H
1
1
1
2
3
A
2
2
2
2
3
S
3
3
3
3
2
Then, the output of your algorithm would be the following optimal alignment:
THIS
-HAS
Note: The optimal alignment for strings A and B may not be unique. Your algorithm only has to produce one such alignment. Your algorithm analysis section must discuss why your algorithm is optimal.
T
H
I
S
0
1
2
3
4
H
1
1
1
2
3
A
2
2
2
2
3
S
3
3
3
3
2
Explanation / Answer
We will use the dynamic programming algorithm to find the optimal alignment between two strings.
Given two strings, A of length n and B of length m, D[i,j] is defined to be the best score of aligning the two substrings A[1..i] and B[1..j].
i := n + 1; j := m + 1;
a_aln := ‘’; b_aln := ‘’;
while i > 1 and j > 1 do
if D[i,j] - sim_mat[BToInt(A[i-1]),BToInt(B[j-1])] = D[i-1,j-1] then //sim_mat is a gap score array
b_aln := b[i-1].b_aln;
a_aln := a[j-1].a_aln;
i := i-1; j := j-1;
elif D[i,j] - gap_score = D[i,j-1] then
a_aln := a[j-1].a_aln;
b_aln := '_'.b_aln;
j := j-1;
elif D[i,j] - gap_score = D[i-1,j] then
a_aln := '_'.a_aln;
b_aln := b[i-1].b_aln;
i := i-1;
else
error('should not happen');
fi;
od:
if j > 1 then
while j > 1 do
a_aln := a[j-1].a_aln;
b_aln := '_'.b_aln;
j := j-1; od;
elif i > 1 then
while i > 1 do
a_aln := '_'.a_aln;
b_aln := b[i-1].b_aln;
i := i-1; od;
fi;
printf('%s %s ',a_aln,b_aln);
Dynamic programming is an algorithm in which an optimization problem is solved by saving the optimal scores for the solution of every sub problem instead of recalculating them. Hence the above algorithm is optimal.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.