Implement the dynamic programming algorithm in Python to compute the edit distan
ID: 3709225 • Letter: I
Question
Implement the dynamic programming algorithm in Python to compute the edit distance between two strings, as given in Section 6.3 of Algorithms by Dasgupta.
Your program should input two strings X and Y and print the edit distance between them, as well as the alignment of the two strings.
For example, given X= EXPONENTIAL and Y= POLYNOMIAL, the output should be:
edit distance = 6
alignment:
EXPONEN-TIAL
--POLYNOMIAL
Report your output on the following strings:
X='CATAAGCTTCTGACTCTTACCTCCCTCTCTCCTACTCCTGCTCGCATCTGCTATAGTGGAGGCCGGAGCAGGAACAGGTTGAACAG'
Y='CGTAGCTTTTTGGTTAATTCCTCCTTCAGGTTTGATGTTGGTAGCAAGCTATTTTGTTGAGGGTGCTGCTCAGGCTGGATGGA'
Explanation / Answer
#Function to return the distance between two strings - Levenshtein distance
X = "CATAAGCTTCTGACTCTTACCTCCCTCTCTCCTACTCCTGCTCGCATCTGCTATAGTGGAGGCCGGAGCAGGAACAGGTTGAACAG"
Y = "CGTAGCTTTTTGGTTAATTCCTCCTTCAGGTTTGATGTTGGTAGCAAGCTATTTTGTTGAGGGTGCTGCTCAGGCTGGATGGA"
def lv_number(X, Y):
string1 = X
string2 = Y
distance = 0
n1 = len(string1)
n2 = len(string2)
if n1 >= n2:
for i in range(n1):
if i < n2:
if string1[i] != string2[i]:
distance += 1
else:
distance += 1
else:
for i in range(n2):
if i < n1:
if string2[i] != string1[i]:
distance -= 1
else:
distance -= 1
return distance
print "Distance: " + str(lv_number(X, Y))