Name
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1089/106652703321825919 | JOURNAL OF COMPUTATIONAL BIOLOGY |
Keywords | DocType | Volume |
dynamic programming,similarity search | Journal | 10.0 |
Issue | ISSN | Citations |
2 | 1066-5277 | 5 |
PageRank | References | Authors |
0.88 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eugene Myers | 1 | 3164 | 496.92 |
| Richard Durbin | 2 | 273 | 29.79 |