“The execution time required for a gapped extension is ~500

times that for an ungapped extension. However, by triggering

gapped extensions in the manner described, while simultaneously

raising T for the single-hit version of BLAST from 11 to 13,

approximately one gapped extension is invoked for every 4000

ungapped extensions avoided. Because the number of ungapped

extensions is reduced by about two thirds, the total time spent on

the extension stage of BLAST is cut by well over half. Of course,

the two-hit strategy described above reduces the time needed for

the ungapped extensions still further. Once program overhead is

accounted for, the net speedup is a factor of about three.”