In this problem you will implement aspects of the LCS algorithm discussed in Lec

Question

In this problem you will implement aspects of the LCS algorithm discussed in Lecture 3. Create a script called LCS .py. This script must contain the two functions described below, plus any additional code you need to run the script. compute_lcs: this function takes as input two sequences and returns (not prints) the LCS matrix. print_lcs: this function takes as input the same two sequences as well as the computed LCS matrix (from compute_lcs) and prints the LCS Plot. For full credit, print_lcs should: print the two sequences one below the other display every row of the LCS matrix on a separate line. Extra credit: printing the sequence characters next to their associated rows and columns as seen in the example below. Sequence A = "AACTGGCAG" Sequence B = "TACGCTGGA" Example output (LCS highlighted):

Explanation / Answer

def lcs(X, Y, m, n):

if m == 0 or n == 0:
return 0;
elif X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1);
else:
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

X = "AACTGGCAG"
Y = "TACGCTGGA"
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.