Abstract
In this paper, we present an $O(N^2 \log ^2 )$ algorithm for finding the two nonoverlapping substrings of a given string of length N which have the highest-scoring alignment between them. This significantly improves the previously best-known bound of $O(N^3 )$ for the worst-case complexity of this problem. One of the central ideas in the design of this algorithm is that of partitioning a matrix into pieces in such a way that all submatrices of interest for this problem can be put together as the union of very few of these pieces. Other ideas include the use of candidate lists, an application of the ideas of Apostolico et al. [SIAM J. Comput., 19 (1990), pp. 968–988] to our problem domain, and divide-and-conquer techniques.
Keywords
SubstringAlgorithmBlock matrixDivide and conquer algorithmsMathematicsString (physics)Block (permutation group theory)Domain (mathematical analysis)Edit distanceUpper and lower boundsMatrix (chemical analysis)Computer scienceCombinatoricsSet (abstract data type)
Related Publications
A spectral algorithm for envelope reduction of sparse matrices
Abstract The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope‐reducing reordering is...
An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
Efficient use of a distributed memory parallel computer requires that the computational load be balanced across processors in a way that minimizes interprocessor communication. ...
Decoding by Linear Programming
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e....
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...
Publication Info
- Year
- 1996
- Type
- article
- Volume
- 25
- Issue
- 3
- Pages
- 648-662
- Citations
- 41
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
41
OpenAlex
Cite This
Sampath K. Kannan,
Eugene W. Myers
(1996).
An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score.
SIAM Journal on Computing
, 25
(3)
, 648-662.
https://doi.org/10.1137/s0097539794262677
Identifiers
- DOI
- 10.1137/s0097539794262677