  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\'{e}chet distance is as hard as Independent
Set. So the problem does not admit any approximation of factor
$n^{1-\epsilon}$. 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.
