Paper Info
Title
All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
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(m2n) best paths from the vertices in column 0 of the graph to all other vertices. Using these techniques we present a simple O(n2 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(n2) algorithm for the cyclic string comparison problem, as compared to O(n2 log n) for the case of general weights.
Year
DOI
Venue
1998
10.1137/S0097539795288489
SIAM J. Comput.
Keywords
Field
DocType
simple o,weighted grid graphs,cyclic string comparison problem,highest scoring paths,optimal repeat,approximate repeats,m x n,mn log m,size n,previous algorithm,log n,log m,n2 log n,dynamic programming,edit distance,string matching,tandem repeats
Edit distance,String searching algorithm,Discrete mathematics,Dynamic programming,Binary logarithm,Substring,Combinatorics,Vertex (geometry),Directed graph,Rabin–Karp algorithm,Mathematics
Journal
Volume
Issue
ISSN
27
4
0097-5397
Citations 
PageRank 
References 
75
4.36
6
Authors
1
Name
Order
Citations
PageRank
Jeanette P. Schmidt1611129.32