×

Sublinear time width-bounded separators and their application to the protein side-chain packing problem. (English) Zbl 1181.68325

Summary: Given \(d >2\) and a set of \(n\) grid points \(Q\) in \(\mathbb R^{d}\), we design a randomized algorithm that finds a \(w\)-wide separator, which is determined by a hyper-plane, in \(O(n^{\frac 2d}\log n)\) sublinear time such that \(Q\) has at most \((\frac{d}{d+1}+o(1))n\) points on either side of the hyper-plane, and at most \(c_{d}wn^{\frac{d-1}{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 J. Xu [“Rapid protein side-chain packing via tree decomposition”, in: Research in computational molecular biology, 9th annual international conference, 408–422 (2005)].

MSC:

68W20 Randomized algorithms
92C40 Biochemistry, molecular biology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akutsu T (1997) NP-hardness results for protein side-chain packing. In: Miyano S, Takagi T (eds) Genome informatics, vol 9, pp 180–186
[2] Alon PN, Thomas R (1990) Planar separator. SIAM J Discret Math 7,2:184–193
[3] 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
[4] Canutescu AA, Shelenkov AA, Dunbrack RL Jr (2003) A graph-theory algorithm for rapid protein side-chain prediction. Protein Sci 12:2001–2014 · doi:10.1110/ps.03154503
[5] 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 · Zbl 1239.90083 · doi:10.1287/ijoc.1040.0096
[6] 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 · Zbl 1130.90050 · doi:10.1007/s10878-006-7132-y
[7] Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge
[8] Djidjev HN (1982) On the problem of partitioning planar graphs. SIAM J Discret Math 3(2):229–240 · Zbl 0503.05057 · doi:10.1137/0603022
[9] Djidjev HN, Venkatesan SM (1997) Reduced constants for simple cycle graph separation. Acta Inform 34:231–234 · Zbl 0865.05049 · doi:10.1007/s002360050082
[10] 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 · Zbl 0822.68039
[11] 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 · Zbl 1136.68573
[12] 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 · Zbl 1099.68130
[13] Gazit H (1986) An improved algorithm for separating a planar graph. Manuscript, USC
[14] Gilbert JR, Hutchinson JP, Tarjan RE (1984) A separation theorem for graphs of bounded genus. J Algorithm 5:391–407 · Zbl 0556.05022 · doi:10.1016/0196-6774(84)90019-1
[15] Li M, Ma B, Wang L (2002) On the closest string and substring problems. J ACM 49(2):157–171 · Zbl 1323.68635 · doi:10.1145/506147.506150
[16] Lipton RJ, Tarjan R (1979) A separator theorem for planar graph. SIAM J Appl Math 36:177–189 · Zbl 0432.05022 · doi:10.1137/0136016
[17] 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
[18] Miller GL, Vavasis SA (1991) Density graphs and separators. In: The second annual ACM-SIAM symposium on Discrete algorithms, pp 331–336 · Zbl 0785.05029
[19] 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
[20] Motwani R, Raghavan P (2000) Randomized algorithms. Cambridge · Zbl 0849.68039
[21] Pach J, Agarwal P (1995) Combinatorial geometry. Wiley–Interscience, New York · Zbl 0881.52001
[22] 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 · Zbl 0867.05069
[23] 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 · doi:10.1016/0022-2836(87)90358-5
[24] Smith WD, Wormald NC (1998) Application of geometric separator theorems. In FOCS, pp 232–243
[25] Spielman DA, Teng SH (1996) Disk packings and planar separators. In: The 12th annual ACM symposium on computational geometry, pp 349–358
[26] Trench WF (1978) Advanced calculus. Harper & Row, New York · Zbl 0382.26001
[27] Xu J (2005) Rapid protein side-chain packing via tree decomposition. In: Research in computational molecular biology, 9th annual international conference, pp 408–422 · Zbl 1119.92339
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.