An algorithm for approximate database searching

public databases, searching for similarity to a query sequence
has become a basic operation in molecular biology.
But even today's fast algorithms reach their limits when
applied to all-versus-all comparisons of large databases.


I will present a new database searching
algorithm called QUASAR (Q-gram Alignment based on Suffix ARrays)
which was designed to quickly detect sequences with strong
similarity to the query in a context where many searches are
conducted on one database. Our algorithm applies a modification of
$q$-tuple filtering implemented on top of a suffix array.
It is, however, restricted to the search for strongly similar DNA
sequences as is typically required, e.g., in the context of clustering
expressed sequence tags (ESTs).

I will also give some comments on the problems i am currently working
on.