A table-driven, full-sensitivity similarity search algorithm.
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.
Myers
Gene
G
Department of Computer Science, University of California, Berkeley, Berkeley, CA 94720-1776, USA. gene@cs.berkeley.edu
Durbin
Richard
R
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