PYTHON ONLY

Problem 1 (Calculating Edit Distance Using Dynamic Programming) Write a program edit_distance.py that reads strings x and y from standard input and computes the edit-distance matrix opt. The program should output x, y, the dimensions (number of rows and columns) of opt, and opt itself.

Hints

Read the sequences x and y from standard input, as strings

Create an (M + 1) x (N + 1) edit-distance matrix opt with all elements initialized to 0, where M and N are the lengths of x and y respectively

Set the bottom row of opt to 2 * (N - j) and its right column to 2 * (M - i), where 0 <= j <= N - 1 and 0 <= i <= M - 1

Problem 2 (Recovering the Alignment) Write a program alignment.py that reads from standard input, the output produced by edit_distance.py, ie, input strings x and y, and the opt matrix. The program should then recover an optimal alignment, and write to standard output the edit distance between x and y and the alignment itself.

Hints Read from standard input the sequences x and y as strings, and the matrix opt as a 2D array of integers

Write the edit distance between x and y, ie, the value of opt[0][0] Recover and output the alignment, starting at opt[0][0] and ending at opt[M - 1][N - 1], as follows: if opt[i][j] equals opt[i + 1][j] + 2, then align x[i] with a gap and penalty of 2, and increment i by 1; if opt[i][j] equals opt[i][j + 1] + 2, then align a gap with y[j] and penalty of 2, and increment j by 1; otherwise, align x[i] with y[j] and penalty of 0/1 based on whether x[i] and y[j] match or not, and increment both i and j by 1

Note: if one of the sequences is exhausted before the other, align a character from the other with a gap and penalty of 2