All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
Author:
- Jeanette P. SchmidtJSJeanette P. Schmidt
- 1 August 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (4) , 972-992
Abstract
Weighted paths in directed grid graphs of dimension (m X n) can be used to model the string edit problem, which consists of obtaining optimal (weighted) alignments between substrings of A, |A|=m, and substrings of B, |B|=n. We build a data structure (in O(mn log m) time) that supports O(log m) time queries about the weight of any of the O(m 2 n) best paths from the vertices in column 0 of the graph to all other vertices. Using these techniques we present a simple O(n 2 log n) time and $\Theta(n^2)$ space algorithm to find all (the locally optimal) approximate tandem (or nontandem) repeats xy within a string of size n. This improves (by a factor of log n) upon several previous algorithms for this problem and is the first algorithm to find all locally optimal repeats. For edit graphs with weights in {0, -1, 1}, a slight modification of our techniques yields an O(n 2 ) algorithm for the cyclic string comparison problem, as compared to O(n 2 log n) for the case of general weights.
Keywords
This publication has 16 references indexed in Scilit:
- Incremental String ComparisonSIAM Journal on Computing, 1998
- Sparse dynamic programming IJournal of the ACM, 1992
- Sparse dynamic programming IIJournal of the ACM, 1992
- Efficient Parallel Algorithms for String Editing and Related ProblemsSIAM Journal on Computing, 1990
- On a cyclic string-to-string correction problemInformation Processing Letters, 1990
- Fast string matching with k differencesJournal of Computer and System Sciences, 1988
- A lower bound for the edit-distance problem under an arbitrary cost functionInformation Processing Letters, 1988
- Geometric applications of a matrix-searching algorithmAlgorithmica, 1987
- Optimal off-line detection of repetitions in a stringTheoretical Computer Science, 1983
- An optimal algorithm for computing the repetitions in a wordInformation Processing Letters, 1981