All shortest paths in weighted grid graphs and its application to finding all approximate repeats in strings

Shortest paths in directed grid graphs of dimension (m×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²n) shortest paths from the vertices in column 0 of the graph to all other vertices. Using these techniques we present a simple O(n² log n) time and O(n²) space algorithm to find all (the locally optimal) approximate tandem (or non-tandem) 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²) algorithm for the cyclic string comparison problem, as compared to O(n² log n) for the case of general weights