Bioinformatics Stack Exchange is a question and answer site for researchers, developers, students, teachers, and end users interested in bioinformatics. It only takes a minute to sign up.
Sign up to join this community
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
So it turns out the Gapped Blast paper doesn't actually give the extension algorithm. It gives a high level overview and refers to an article in preparation at the time:
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.
The motivation for this approach is to be a "smarter" version of the banded alignment approach. The issue with banded alignment approaches is that they implicitly won't allow for large insertions/deletions within the alignment, even if the areas around the alignment are high scoring. Increasing the band with to allow for this reduces the speedup gained by the band constraint. This is where the idea of "Alignments Without Low-Scoring Regions" comes into play. This paper is the one cited as "in-prep" by the gapped blast paper, and it describes an early version of the gapped extension approach. However, that approach seems to have been superseded by the one described here 2 years later by the same lead author (the former paper in '98 having 67 citations and the latter in 2000 having 4700+).
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.
