Paper Info
Title
Invited Lecture - Accelerating Smith-Waterman Searches
Abstract
Searching a database for a local alignment to a query under a typical scoring scheme such as PAM120 or BLOSUM62, 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 does yields 3.33 factor improvement over the basic algorithm in practice.
Year
DOI
Venue
2002
10.1007/3-540-45784-4_25
WABI
Keywords
Field
DocType
basic algorithm,dynamic programming matrix,accelerating smith-waterman searches,query preprocessing step,asymptotic improvement,large fraction,original smith-waterman algorithm,factor improvement,dynamic programming,local alignment,invited lecture,algorithmic improvement
Dynamic programming,Matrix (mathematics),Computer science,Algorithm,Remainder,Theoretical computer science,Preprocessor,Smith–Waterman algorithm,Computation
Conference
Volume
ISSN
ISBN
2452
0302-9743
3-540-44211-1
Citations 
PageRank 
References 
0
0.34
5
Authors
2
Name
Order
Citations
PageRank
Eugene Myers13164496.92
Richard Durbin227329.79