I am trying to write a Python function extractAlignment(S) that takes in as an i

Question

I am trying to write a Python function extractAlignment(S) that takes in as an input a matrix S, of dynamic length nx by ny (these lengths are determined by strings inputted into an earlier function that I wrote to create S) and returns a vector (list in Python) that represents the optimal path in getting back to S[0][0] from the lower right corner S[nx][ny]. S is filled simply with integers.

The optimal path is determined by looking at the values above and to the left before each move, and choosing the node represented by the smallest number. Only upward and leftward movements can be performed in order to reach S[0][0], and in the case of a tie, the path to the next node MUST be randomly chosen. Any help would be greatly appreciated. Thanks!

Explanation / Answer

# Dynamic programming implementation of LCS problem
def lcs(X, Y, m, n):
L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]
Y[0..j-1]
for i in xrange(m+1):
for j in xrange(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
index = L[m][n]
lcs = [""] * (index+1)
lcs[index] = ""
i = m
j = n
while i > 0 and j > 0:

if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i-=1
j-=1
index-=1

elif L[i-1][j] > L[i][j-1]:
i-=1
else:
j-=1

print "LCS of " + X + " and " + Y + " is " + "".join(lcs)
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs(X, Y, m, n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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