Consequences of Faster Alignment of Sequences

Abstract. The Local Alignment problem is a classical problem with ap-plications in biology. Given two input strings and a scoring function on pairs of letters, one is asked to find the substrings of the two input strings that are most similar under the scoring function. The best algorithms for Local Alignment run in time that is roughly quadratic in the string length. It is a big open problem whether substantially subquadratic al-gorithms exist. In this paper we show that for all ε> 0, an O(n2−ε) time algorithm for Local Alignment on strings of length n would imply breakthroughs on three longstanding open problems: it would imply that for some δ> 0, 3SUM on n numbers is in O(n2−δ) time, CNF-SAT on n variables is in O((2 − δ)n) time, and Max Weight 4-Clique is in O(n4−δ) time. Our result for CNF-SAT also applies to the easier problem of find-ing the longest common substring of binary strings with don’t cares. We also give strong conditional lower bounds for the more general Multiple Local Alignment problem on k strings, under both k-wise and SP scor-ing, and for other string similarity problems such as Global Alignment with gap penalties and normalized Longest Common Subsequence.