elegant_laff.py

#This solution is due to Timothy Loh from the Rosalind Web site
# I don't understand it (yet) but the claim is that it uses linear space
# and is able to recover the substrings (start and end) without backtracking


def go(GAP_OPEN, GAP_EXT, s, t, table):
    # note: open is 12 here instead of 11
    best = (-1, 0, 0, 0, 0) # score, s0, t0, s1, t1
    m = l = [(0, i, 0) for i in range(len(s)+1)]
    def add(tp, v):
        return tp[0]+v, tp[1], tp[2]
    for ti,c in enumerate(t, 1):
        l2 = [(0, 0, ti)]
        mx = l2[0]
        for si,c2 in enumerate(s,1):
            l2.append(max(
                add(m[si], -GAP_OPEN),
                add(mx, -GAP_OPEN),
                add(l[si-1], table[c][c2]),
                (0, si, ti)
                ))
            mx = max(add(mx, -GAP_EXT), l2[-1])
            if l2[-1][0] > best[0]:
                best = l2[-1] + (si, ti)
        m = [max(add(si, -GAP_EXT), j) for si,j in zip(m, l2)]
        l = l2
    return best