An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score

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