Longest common sub-sequence code error

I was trying to convert the LCS algorithm (CLRS p. 394) into python code, but finally, the code does not return the expected result. The code takes two sequences and returns the longest common subsequences. Moreover, I was trying to see the matrices as well and how they are filled. The first matrix looks like below, and it is surrounded by zeros.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 2, 2, 2, 2, 2, 2, 2, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 3, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 3, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 3, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 3, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 4, 0]
[0, 1, 2, 2, 2, 2, 2, 3, 4, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 

However, it supposed to return something like the matrix below. The numbers inside the matrices is also quite different.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 5, 5]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6]
[0, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6]

Any suggestions on how to fix this?

def LCS(x,y):
    '''Return a longest common subsequence of xs and ys.

    Example
    >>> lcs("HUMAN", "CHIMPANZEE")
    '''
    if x == [] or y == []:
        return []
    m, n = len(x), len(y)

    c=[[0 for i in range(n+1)] for j in range(m+1)]
    b=[[0 for i in range(n+1)] for j in range(m+1)]


    for i in range (m):
        for j in range (n):
            if x[i]==y[j]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 'DIAG'
            elif c[i-1][j]>= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 'UP'
            else:
            c[i][j] = c[i][j-1]
            b[i][j] = 'LEFT'
    return c,b


def printLcs(b,x,i,j):
    if i==0 or j==0:
        return
    if b[i][j]=='DIAG':
        printLcs(b,x,i-1,j-1)
        print(x[i],end='')
    elif b[i][j]=='UP':
        printLcs(b,x,i-1,j)
    else:
        printLcs(b,x,i,j-1)
x = 'ATGCCCCAA'
y = 'ATGGGGGCA' 

c,b=LCS(x,y)
for i in c:
    print(i)
print('')
for j in b:
    print(j)
print('')
printLcs(b,x,len(x),len(y))
print('')

Leave a Reply

Your email address will not be published. Required fields are marked *