alignment.py does not always produce the best alignment possible

[freeseek]

The code in alignment.py does not seem capable of identifying the best alignment.

Take sequences GAAAAAAA and GTTTTTTT for example. It will generate the alignment:

G A A A A A A A _ _ _ _
G _ _ _ _ T T T T T T T

With the score:

1 + -10 + -0.5 + -0.5 + -0.5 + -0.5 + -4 + -4 + -4 + -10 + -0.5 + -0.5 + -0.5 + -0.5 = -35

But the following alignment:

G A A A A A A A _ _ _ _ _ _ _
G _ _ _ _ _ _ _ T T T T T T T

Has a better score:

1 + -10 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 + -10 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 + -0.5 = -26

It seems like the implementation of the algorithm from Gotoh, O. An improved algorithm for matching biological sequences. J Mol Biol 162, 705–708 (1982) is incorrect