On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance
Abstract
Description
We show that given $m$ proteins (or protein backbones, which are modeled as 3D polygonal chains each of length O(n)) the problem of protein local structure alignment under the discrete Fréchet distance is as hard as Independent Set. So the problem does not admit any approximation of factor $n^{1-ε}$. This is the strongest negative result regarding the protein local structure alignment problem. On the other hand, if $m$ is a constant, then the problem can be solved in polygnomial time.
11 pages, 2 figures
11 pages, 2 figures