Name
Abstract | ||
|---|---|---|
Common string alignment algorithms such as the basic dynamic programming algorithm (DPA) and the time efficient Ukkonen algorithm use quadratic space to determine an alignment between two strings. In this paper we present a technique that can be applied to these algorithms to obtain an alignment using only linear space, while having little or no effect on the time complexity. This new technique has several advantages over previous methods for determining alignments in linear space, such as: simplicity, the ability to use essentially the same technique when using different cost functions, and the practical advantage of easily being able to trade available memory for running time. © 1999 Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0020-0190(99)00053-8 | Inf. Process. Lett. |
Keywords | DocType | Volume |
sequence alignment,algorithms,dynamic programming,versatile divide,optimal string alignment,edit distance,cost function,divide and conquer,dynamic programming algorithm,linear space,time complexity | Journal | 70 |
Issue | ISSN | Citations |
3 | 0020-0190 | 6 |
PageRank | References | Authors |
0.82 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David R. Powell | 1 | 56 | 5.51 |
| Lloyd Allison | 2 | 414 | 46.15 |
| Trevor I. Dix | 3 | 233 | 26.19 |