next up previous contents
Next: Global Alignments Up: Dynamic Programming Previous: The DynProg Function

The BackDynProg Function

The DynProg function begins with the leftmost position of both strings and works towards the rightmost positions. Notice however that for some strings, higher scores are possible if one or more bases from the lefthand side of the strings are removed. For example,

> u := 'FRCD':
> v := 'SPAD':
> DynProg(u, v, DM);
[1.4750, 4, 4]
> u1 := 'CD':               # cut the first two positions
> v1 := 'AD':
> DynProg(u1, v1, DM);
[5.2435, 2, 2]
One way to find this ``left starting point'' is to apply dynamic programming in the reverse direction on the strings. The left tail of the resulting alignment indicates a good place for a normal ``forward'' dynamic programming function to begin. The function BackDynProg does exactly this in Darwin.

> BackDynProg(u, v, DM);
[5.2435, 2, 2]
> rev_u := 'DCRF';
> rev_v := 'DAPS';
> DynProg(rev_u, rev_v, DM);
[5.2435, 2, 2]

Gaston Gonnet