next up previous contents
Next: The Match Structure Up: Dynamic Programming Previous: The BackDynProg Function

Global Alignments

If we pass the lengths of the strings as arguments to DynProg, the routine finds the best global alignment. That is, the routine does not allow the number of bases in the alignment to fall below max(length(x), length(y)). Let us compare the results of using DynProg without the lengths specified (local alignment) and with the lengths specified (global alignment). The Tryptophan bases W score very well when aligned against themselves (a score of 14.2). The alignment begins very well. The Tryosine base Y also scores extremely well when conserved (a score of 7.8). The remaining part of the alignment scores very poorly (all scores are negative). A local alignment algorithm would return only the first six bases from x and y.

> CreateDayMatrices();
> x := 'WWWWYWCDYPHQILWYWWC':
> y := 'WWWWYWPPDCGCSTAGPPP':
> DynProg(x, y, DM);
[78.5205, 6, 6]

However, the global alignment scores much lower.

> DynProg(x, y, DM, length(x), length(y));
[41.2944, 19, 19]



Gaston Gonnet
1998-09-15