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

Simple item page
dc.creatorZhu, Binhai
dc.date2007-09-05
dc.date.accessioned2026-07-07T08:27:46Z
dc.date.available2026-07-07T08:27:46Z
dc.descriptionWe 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.
dc.description11 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/0709.0677
dc.identifierhttp://arxiv.org/abs/0709.0677
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/137379
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.titleOn the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance
dc.typetext

Files

Collections

arXiv