I seem to need this from time to time. It isn't very efficient but it works.

needlemanwunsch.py

def nw(a, b):
    """ Returns Levenstein distance of two strings using NW """
    a = ' ' + a
    b = ' ' + b
    class matrix(list):
        """ A cute little matrix object """
        def __init__(self, x, y):
            """ initialize """
            [ self.append([0]*x) for i in range(y) ]
             
        def __repr__(self):
            """ niceprint """
            return '\n'.join([' '.join([str(j) for j in i]) for i in self ])
    
    m = matrix(len(a), len(b))

    for f, y in zip(b, range(len(m))):
        for s, x in zip(a, range(len(m[y]))):
            if y is 0 and x is 0:
                continue
            elif y == 0:
                m[y][x] = m[y][x-1] + 1
            elif x == 0:
                m[y][x] = m[y-1][x] + 1
            elif f == s:
                m[y][x] = m[y-1][x-1]
            elif f != s:
                m[y][x] = min([m[y-1][x-1]+1, m[y-1][x]+1, m[y][x-1]+1])
     
    print m
                
    print '%s from %s = %s' % (a[1:], b[1:], m[-1][-1])