Abstract
Given d>2 and a set of n grid points Q in ℜ d, we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in \(O(n^{2\over d}\log n)\) sublinear time such that Q has at most \(({d\over d+1}+o(1))n\) points on either side of the hyper-plane, and at most \(c_{d}wn^{d-1\over d}\) points within \(\frac{w}{2}\) distance to the hyper-plane, where c d is a constant for fixed d. In particular, c 3=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akutsu T (1997) NP-hardness results for protein side-chain packing. In: Miyano S, Takagi T (eds) Genome informatics, vol 9, pp 180–186
Alon PN, Thomas R (1990) Planar separator. SIAM J Discret Math 7,2:184–193
Alon N, Seymour P, Thomas R (1990) A separator theorem for graphs with an excluded minor and its applications. In: Proceedings of the 22nd annual ACM symposium on theory of computing. ACM, New York, pp 293–299
Canutescu AA, Shelenkov AA, Dunbrack RL Jr (2003) A graph-theory algorithm for rapid protein side-chain prediction. Protein Sci 12:2001–2014
Chazelle B, Kingsford C, Singh M (2004) A semidefinite programming approach to side-chain positioning with new rounding strategies. INFORMS J Comput 16:86–94
Chen Z, Fu B, Tang Y, Zhu B (2006) A PTAS for a disc covering problem using width-bounded separators. J Comb Optim 11(2):203–217
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge
Djidjev HN (1982) On the problem of partitioning planar graphs. SIAM J Discret Math 3(2):229–240
Djidjev HN, Venkatesan SM (1997) Reduced constants for simple cycle graph separation. Acta Inform 34:231–234
Eppstein D, Miller GL, Teng S-H (1995) A deterministic linear time algorithm for geometric separators and its applications. Fundam Inform 22(4):309–329
Fu B (2006) Theory and application of width bounded geometric separator. In: Proceedings of the 23rd international symposium on theoretical aspects of computer science (STACS’06). Lecture notes in computer science, vol 3884. Springer, Berlin, pp 277–288
Fu B, Wang W (2004) A \(2^{O(n^{1-1/d}\log n)}\) time algorithm for d-dimensional protein folding in the hp-model. In: Proceedings of 31st international colloquium on automata, languages and programming. Lecture notes in computer science, vol 3142. Springer, Berlin, pp 630–644
Gazit H (1986) An improved algorithm for separating a planar graph. Manuscript, USC
Gilbert JR, Hutchinson JP, Tarjan RE (1984) A separation theorem for graphs of bounded genus. J Algorithm 5:391–407
Li M, Ma B, Wang L (2002) On the closest string and substring problems. J ACM 49(2):157–171
Lipton RJ, Tarjan R (1979) A separator theorem for planar graph. SIAM J Appl Math 36:177–189
Miller GL, Thurston W (1990) Separators in two and three dimensions. In: 22nd annual ACM symposium on theory of computing. ACM, New York, pp 300–309
Miller GL, Vavasis SA (1991) Density graphs and separators. In: The second annual ACM-SIAM symposium on Discrete algorithms, pp 331–336
Miller GL, Teng S-H, Vavasis SA (1991) An unified geometric approach to graph separators. In: 32nd annual symposium on foundation of computer science. IEEE, New York, pp 538–547
Motwani R, Raghavan P (2000) Randomized algorithms. Cambridge
Pach J, Agarwal P (1995) Combinatorial geometry. Wiley–Interscience, New York
Plotkin S, Rao S, Smith WD (1990) Shallow excluded minors and improved graph decomposition. In: 5th symposium on discrete algorithms. SIAM, Philadelphia, pp 462–470
Ponter JW, Richards FM (1987) Tertiary templates for proteins: use of packing criteria and the enumeration of allowed sequences for different structural classes. J Mol Biol 193:775–791
Smith WD, Wormald NC (1998) Application of geometric separator theorems. In FOCS, pp 232–243
Spielman DA, Teng SH (1996) Disk packings and planar separators. In: The 12th annual ACM symposium on computational geometry, pp 349–358
Trench WF (1978) Advanced calculus. Harper & Row, New York
Xu J (2005) Rapid protein side-chain packing via tree decomposition. In: Research in computational molecular biology, 9th annual international conference, pp 408–422
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35.
The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.
Rights and permissions
About this article
Cite this article
Fu, B., Chen, Z. Sublinear time width-bounded separators and their application to the protein side-chain packing problem. J Comb Optim 15, 387–407 (2008). https://doi.org/10.1007/s10878-007-9092-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-007-9092-2