A Blast From The Past
While Blast is one of the most widely-used search engines for molecular
biology, and there is a general understanding of how it works, few know the
story of how it came about and the theoretical algorithmic result from
which it was derived. I will tell the story and explain the theoretical
algorithm --- an O(DNpow(D/P)logN) expected-time algorithm for finding all D-matches to a query of length P in a database of length N >> P. Surprisingly, this result, published in early 1994, has not been improved upon to this day.