[Reincarnate]

Untested code, let me know if this is returning the right values for you -- if so then I'll clean up the code and make it a little more readable / with better coding practices / whatever -- just want to ensure it's returning the right vals first

class memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args, **kwds):
        import cPickle
        str = cPickle.dumps(args, 1)+cPickle.dumps(kwds, 1)
        if not self.memo.has_key(str):
            self.memo[str] = self.fn(*args, **kwds)
        return self.memo[str]



@memoize
def dpScore( mat, baseMap, seq1, seq2, gapsLeft, g ):
    if (len(seq1)==0 and gapsLeft>0) or gapsLeft<0: return -9999999999999999999999 #lazy right now, using a sentinel
    if len(seq1)==0 or len(seq2)==0: return 0

    possibleScore1 = g + mat[baseMap[seq1[0]]][baseMap[seq1[0]]] + dpScore( mat, baseMap, seq1[1:], seq2, gapsLeft-1, g )

    if seq1[0] == seq2[0]: matchScore = mat[baseMap[seq1[0]]][baseMap[seq2[0]]]
    else: matchScore = -mat[baseMap[seq1[0]]][baseMap[seq2[0]]]

    possibleScore2 = matchScore + dpScore( mat, baseMap, seq1[1:], seq2[1:], gapsLeft, g )
    
    return max(possibleScore1, possibleScore2)



def bestStringScore( mat, baseMap, seq1, seq2, g = -5 ):
    gapsLeft = abs(len(seq1)-len(seq2))
    if len(seq1) > len(seq2):
        return dpScore(mat, baseMap, seq1, seq2, gapsLeft, g)
    else:
        return dpScore(mat, baseMap, seq2, seq1, gapsLeft, g)



mat = [[20, 10, 5, 5],
       [10, 20, 5, 5],
       [5, 5, 20, 10],
       [5, 5, 10, 20]]

alphabet = "TCAG"
baseMap = {base:index for index,base in enumerate(alphabet)}

seq1 = 'ATGTTAT'
seq2 = 'ATCGTAG'

print bestStringScore(mat, baseMap, seq1, seq2)