An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score

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.