# Pseudocode for gapped BLAST seed extension

I am trying to understand in detail how does the gapped BLAST seed extension DP algorithm works. Despite searching for days now, I could not find anywhere a pseudocode that would allow implementing this in python. Not being a C programmer, it would be impossible for me to grasp this from the BLAST source code.

Can anyone help me with this?

Thank you all. Best,

Daniel

The central idea is to consider only cells for which the optimal local alignment score falls no more than $$X_g$$ below the best alignment score yet found. Starting from a single aligned pair of residues, called the seed, the dynamic programming proceeds both forward and backward through the path graph (Zheng Zhang et al., manuscript in preparation) (Figs 3a and 4). The advantage of this approach is that the region of the path graph explored adapts to the alignment being constructed. The alignment can wander arbitrarily many diagonals away from the seed, but the number of cells expanded on each row tends to remain limited, and may even shrink to zero before a boundary of the path graph is encountered (Fig. 4). The $$X_g$$ parameter serves a similar function to the band-width parameter of the earlier heuristic, but the region of the path graph it implicitly specifies be explored is in general more productively chosen.
For completeness, I've pasted some pseudocode from the more popular x-drop paper from 2000. Note that $$X$$ is a user specified parameter, with larger $$X$$ allowing for a larger search space but slower speed.
• Yes, the algorithm is semi-global in the sense that it seeks two prefixes of the input sequences that maximizes the alignment score. However, the initial value of the origin is arbitrary. The algorithm only cares that no cell in the search path falls $X_g$ below the best value seen thus far. The novelty of the X-drop algorithm in Blast is (1) the search termination bounds (i.e. the x-drop) and (2) the greedy algorithm which is faster than typical DP. Jul 5, 2021 at 13:31