Gene Myers, Max Planck Institute, Dresden, Germany

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.