Local Alignment

Description

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.

Related Problems

Subproblem: Multiple Local Alignment

Parameters

$n$: length of input strings

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
3SUM	if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$ then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$	2014	https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-662-43948-7_4	link
CNF-SAT	if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$ then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$	2014	https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-662-43948-7_4	link