Multiple Local Alignment (Local Alignment)

Description

Given $k$ input strings and a scoring function on pairs of letters, one is asked to find the substrings of the $k$ input strings that are most similar under the scoring function.

Related Problems

Generalizations: Local Alignment

Parameters

k: number of input strings

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
CNF-SAT	if: to-time: $N^{k-\epsilon}$ for some $\epsilon > {0}$ on $k$ binary strings of length $n$ with $k$-wise scoring then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$	2014	https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4	link