title: A table-driven, full-sensitivity similarity search algorithm.
abstract: Searching a database for a local alignment to a query under a typical scoring scheme, such as PAM120 or BLOSUM62 with affine gap costs, is a computation that has resisted algorithmic improvement due to its basis in dynamic programming and the weak nature of the signals being searched for. In a query preprocessing step, a set of tables can be built that permit one to (a) eliminate a large fraction of the dynamic programming matrix from consideration and (b) to compute several steps of the remainder with a single table lookup. While this result is not an asymptotic improvement over the original Smith-Waterman algorithm, its complexity is characterized in terms of some sparse features of the matrix and it yields the fastest software implementation to date for such searches.
authors.affiliation: Department of Computer Science, University of California, Berkeley, Berkeley, CA 94720-1776, USA. gene@cs.berkeley.edu
authors.forename: Gene
authors.initials: G
authors.lastname: Myers
authors.forename: Richard
authors.initials: R
authors.lastname: Durbin
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D016208:Databases, Factual; D016247:Information Storage and Retrieval; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D012984:Software