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.
Keywords
SubstringCombinatoricsMathematicsBinary logarithmString (physics)Edit distanceString searching algorithmDimension (graph theory)Running timeDiscrete mathematicsData structureAlgorithmComputer science
Related Publications
Improved time bounds for near-optimal sparse Fourier representations
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) ca...
Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
Let ${M}$ be a compact Riemannian submanifold of ${{\\bf R}^m}$ of dimension\n$\\scriptstyle{d}$ and let ${X_1,...,X_n}$ be a sample of i.i.d. points in ${M}$\nwith uniform dist...
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f ∈ C N and a randomly chosen set of freque...
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...
Active Learning with Statistical Models
For many types of machine learning algorithms, one can compute the statistically `optimal' way to select training data. In this paper, we review how optimal data selection techn...
Publication Info
- Year
- 1998
- Type
- article
- Volume
- 27
- Issue
- 4
- Pages
- 972-992
- Citations
- 141
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
141
OpenAlex
Cite This
Jeanette P. Schmidt
(1998).
All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings.
SIAM Journal on Computing
, 27
(4)
, 972-992.
https://doi.org/10.1137/s0097539795288489
Identifiers
- DOI
- 10.1137/s0097539795288489