On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance

Details On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance

2007-09-05

arxiv.org/abs/0709.0677v1

Computer Science

Computational Complexity

11 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-470804