All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings

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...