On complexity of protein structure alignment problem under distance constraint.
We study the well known LCP (Largest Common Point-Set) under Bottleneck Distance Problem. Given two proteins a and b (as sequences of points in 3D space) and a distance cutoff &#x03C3;, the goal is to find a spatial superposition and an alignment that maximizes the number of pairs of points from a and b that can be fit under the distance &#x03C3; from each other. The best to date algorithms for approximate and exact solution to this problem run in time O(n^8) and O(n^32), respectively, where n represents the protein length. This work improves the runtime of the approximation algorithm and the algorithm for absolute optimum for both order-dependent and order-independent alignments. More specifically, our algorithms for near-optimal and optimal sequential alignments run in time O(^7 log n) and O(n^14 log n), respectively. For non-sequential alignments, corresponding running times are O(n^7.5) and O(n^14.5).
University of Northern Iowa, Cedar Falls.
Aleksandar
A
Poleksic
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
D011506:Proteins