Sparse normalized local alignment
Given two strings, X and Y, both of length O(n) over alphabet Sigma, a basic problem (local alignment) is to find pairs of similar substrings, one from X and one from Y. For substrings V and Y' from X and Y, respectively, the metric we use to measure their similarity is normalized alignment value: LCS(X', Y')/(\X'\ + \Y'\). Given an integer M we consider only those substrings whose LCS length is at least M. We present an algorithm that reports the pairs of substrings with the highest normalized alignment value in O(n log\Sigma\+ rM log log n) time (r-the number of matches between X and Y). We also present an O(n log\Sigma\ + rL log log n) algorithm (L = LCS(X, Y)) that reports all substring pairs with a normalized alignment value above a given threshold.
local alignment algorithms string matching dynamic programming largest common subsequence (lcs).